面向快递同城运输的车辆路径问题研究

为降低运输成本，研究了快递同城运输中的车辆路径问题。建立多车型，含时间窗约束、容量约束、车辆限行约束，并考虑错峰交货的，以最小化运输成本为目标的混合整数规划模型。提出以点到点集的距离之和作为邻域搜索优先指标的构造性启发式算法，设计了基于“路径−；车型对”的列生成算法，初始列由启发式算法求得。实验结果显示，对于120个点的大规模问题，列生成算法只需175秒就能得到近似最优解，验证了该算法的有效性及对一定规模内快递同城运输问题的适用性。

A Study of Vehicle Routing Problem for Urban Transport of Express

The problem for urban transport of express is essentially a vehicle routing problem. A mixed-integer programming with the objective of minimum cost is built, which includes the constraints of capacity, time windows, vehicle restriction and it also considers staggering the delivery time. A constructive heuristics is proposed and it takes the distance from one point to the set of points as the priority index for neighborhood search. A column generation algorithm based on pairs of "route-vehicle" is designed and the initial columns are solved by the heuristics. The experimental results show that the approximate optimal solution can be obtained in 175 seconds for the large-scale problem with up to 120 points, which proves the effectiveness of the algorithm and its applicability to VRP for urban transport of express within a certain scale.