关键词: 多配送中心, 沿途补货, 动态需求, 车辆路径问题, 两阶段数学模型, 自适应免疫量子进化算法

Abstract: To study the applicability of Dynamic Requests Multi-depot Vehicle Routing Problem (DRMVRP) under dynamic customer requirement changes, a DRMVRP with replenishment on the way was proposed. The DRMVRP was decomposed into a series of static MVRP and a two-phase mathematical programming model was presented for the problem. The DRMVRP was a delivery vehicle routing problem in which multiple depots and real-time service requests were considered. An Adaptive Immune Quantum-Inspired Evolutionary Algorithm (AIQEA) for this dynamic problem was proposed. In the AIQEA, a decoding method of the most neighboring method combined with greedy rules to control vehicle replenishment along the way was designed. An immune operator was introduced to optimize sub-routes for convergence acceleration. To improve real-time performance of the algorithm, during the process of vaccination, an adaptive selection probability was designed, which changed with the size of individual fitness. Benchmark problems were simulated and compared with other algorithms, and the results showed that the proposed algorithm could find high quality solutions and effectively satisfied the requirements of dynamic scheduling problems. At the same time the influence of replenishment along routes was also analyzed. Experiment results revealed that the strategy of replenishment on the way was suitable for dynamic vehicle routing problem.

Key words: multi-depot, replenishment on the way, dynamic requests, vehicle routing problem, two-phase mathematic model, adaptive immune quantum-inspired evolutionary algorithm