一种求解两级累计式车辆路径问题的两阶段启发式算法

A Two-phase Heuristic Algorithm for the Two-echelon Cumulative Capacitated Vehicle Routing Problem

现代物流的发展中,运输网络的多级化以及对快速服务的更高要求是两大重要趋势。在这样的背景下,提出两级累计式车辆路径问题(2E-CCVRP),其中两级是指物资须由中心仓库配送至中转站(1级)再转送给客户(2级),累计式是指优化目标为所有客户的累计等待时间最小。2E-CCVRP是NP-hard问题,抽象并建模后使用一种两阶段启发式算法进行求解,第一阶段使用改进的CCVRP-split算法找到初始可行解,第二阶段通过扰乱结合局部搜索进行优化。实验结果显示,该算法能够取得高质量的解,且求解速度快,稳定性好。

In modern logistics,complex network construction and faster service are two important trends.This paper proposes the two-echelon cumulative capacitated vehicle routing problem(2E-CCVRP),in which freight is compulsorily delivered from center depot to satellites(first echelon) before handed to customers from satellites(second echelon),and the objective is the minimization of the sum of arrival times at customers,instead of the total routing cost.In this literature,we model this NP-hard problem and propose a two-phase heuristic algorithm to solve it.In first phase the customers are assigned to the satellites reasonably by an improved CCVRP-split algorithm,the result is optimized by local search algorithm with perturbation in second phase.Testing result shows this algorithm is well applied to 2E-CCVRP with great quality and high efficiency.