Hits:

Indexed by:期刊论文

Date of Publication:2015-02-15

Journal:交通运输系统工程与信息

Included Journals:Scopus、EI、PKU、ISTIC、CSCD

Volume:15

Issue:1

Page Number:159-166

ISSN No.:1009-6744

Key Words:物流工程;两阶段算法;动态车辆路径问题;K-d树分割策略;算法搜索解空间

Abstract:针对一类动态车辆路径问题，分析4种主要类型动态信息对传统车辆路径问题的本质影响，将动态车辆路径问题(Dynamic Vehicle Routing Problem, DVRP)转化为多个静态的多车型开放式车辆路径问题(The Fleet Size and Mixed Open Vehicle Routing Problem, FSMOVRP)，并进一步转化为多个带能力约束车辆路径问题(Capacitated Vehicle Routing Problem, CVRP)，基于CVRP模型建立了DVRP模型；然后，在分析DVRP问题特点基础上，提出两阶段算法，第一阶段基于利用K-d trees对配送区域进行分割的策略，提出了复杂度仅为O(nlogn)的快速构建型算法，第二阶段通过分析算法搜索解空间结构原理，设计混合局部搜索算法；最后，基于现有12个大规模CVRP标准算例，设计并求解36个DVRP算例。求解结果表明了模型和两阶段算法的有效性。