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

摘要： 为了研究沿途补货策略在客户需求动态变化环境下的实用性，提出基于沿途补货的多配送中心动态需求车辆路径问题。将动态问题按照时间轴依次分解为一系列的静态调度子问题，并建立其两阶段数学模型；设计了一种最邻近法结合贪婪法则来控制车辆沿途补货的解码方法；提出了自适应免疫量子进化算法的求解方法，引入免疫算子进行线路内和线路间的再优化，从关于问题的先验知识中提取疫苗，有效地加快了算法的收敛速度，提高了解的质量，同时在疫苗接种的过程中设计了一种随个体适应度大小而变化的自适应选择概率，减少了算法的运行时间。对实例进行仿真测试并与其他算法进行了比较，结果表明所提算法能获得较好的解，能有效求解动态调度问题，同时分析了沿途补货策略影响，实验表明沿途补货策略适用于动态需求车辆路径问题。

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