点击次数：

论文类型：期刊论文

发表时间：2015-02-15

发表刊物：交通运输系统工程与信息

收录刊物：Scopus、EI、PKU、ISTIC、CSCD

卷号：15

期号：1

页面范围：159-166

ISSN号：1009-6744

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

摘要：针对一类动态车辆路径问题，分析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算例。求解结果表明了模型和两阶段算法的有效性。