CAJ | 학술논문

针对一类动态车辆路径问题，分析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算例。求解结果表明了模型和两阶段算法的有效性。
침대일류동태차량로경문제，분석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.