应急物流中的累计时间式多车场车辆路径问题

Cumulative multi-depot vehicle routing problem in emergency logistics

为提升应急救援的快速性和公平性,以最小化所有受灾点的累计等待时间为目标建立累计时间式多车场车辆路径问题(Cum-MDVRP)的模型.由于该问题具有NP-hard性质,设计了一种多起始点变邻域下降法对其进行快速求解.每次迭代中,多起始点方法通过改进的Split算法结合可行性修复程序生成随机的初始可行解,然后由变邻域下降法对其进一步改进.扩展的标准算例的测试结果验证了所提出模型和求解算法的有效性.

To promote the rapidity and equity（fairness） in emergency rescue, a cumulative multi-depot vehicle routing problem（Cum-MDVRP） model with the objective of minimizing the cumulative waiting time in all affected areas is built. Because of the NP-hard nature of this problem, a multi-start variable neighborhood descent algorithm is developed to solve it efficiently. In each iteration, multi-start methods produce a randomly initial feasible solution by an improved Split algorithm combined with a feasibility repairing procedure, and then this solution is further improved by a variable neighborhood descent algorithm. Results of computational tests on some extended benchmark instances show the effectiveness of the proposed model and the good performance of the developed algorithm.