一类动态车辆路径问题模型和两阶段算法

Model and Two-stage Algorithm on Dynamic Vehicle Routing Problem

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

In order to effectively solve dynamic vehicle routing problem（DVRP）, this paper analyzes the substantial effect of four main categories of dynamic information on classical vehicle routing problem, and transform DVRP into multiple static fleet size and mixed open vehicle routing problems（FSMOVRP）. And FSMOVRP could be further converted to multiple capacitated vehicle routing problems（CVRP）. The model based on CVRP is built up for DVRP. After that a two-stage algorithm is proposed to solve DVRP model according to the analysis of DVRP characteristics. In the first stage, a fast construction algorithm with merely O（nlogn） complexity is proposed on the basis of delivery region cutting strategy by K-d trees method. In the second stage, a hybrid local search algorithm is designed by analysis of structural principal of algorithm＇s solution searching space. Finally for the purpose of algorithm verification, we design and solve 36 DVRP instances generated from 12 large scale CVRP benchmark instances. The results demonstrate the effectiveness of the model and two-stage solving algorithm.