Release Time:2019-03-10  Hits:

Indexed by: Journal Article

Date of Publication: 2015-02-15

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

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

Volume: 15

Issue: 1

Page Number: 159-166

ISSN: 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算例。求解结果表明了模型和两阶段算法的有效性。