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

来源：交通运输系统工程与信息杂志2015年第1期北京时间：

作者：饶卫振，金淳，刘锋，杨磊

单位：1. 山东科技大学经济管理学院，山东青岛266590；2. 大连理工大学系统工程研究所，辽宁，大连116024； 3. 东北财经大学管理科学与工学院，辽宁，大连116025

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

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

基金资助：国家自然科学基金（71271041）；山东省优秀中青年科学家科研奖励基金（BS2014SF001）；山东科技大学人才引进基金（RCJJ2013020）；山东省软科学研究计划项目（2014RKB01506 ）.