一种基于云计算环境的动态车辆路径问题解决策略

A New Scheduling Strategy of Dynamic Vehicle Routing Problem Under Cloud Environment

针对动态环境下车辆路径问题,以最小化车辆数和配送里程、最大化载货率为目标,建立动态车辆路径问题的数学模型,提出了云自适应遗传算法。针对车辆路径问题的特点,提出车辆分配链和配送货物顺序链的双链量子编码方法;针对遗传算法交叉和变异操作可能导致早熟收敛和后期多样性丢失的问题,利用云计算方法设计了云交叉算子和云变异算子,并进行操作,还提出改进的云自适应遗传算法。仿真调度算例验证了与其他算法相比较,所提算法能降低早熟概率和提高迭代搜索效率。

For the purpose of solving the dynamic vehicle routing problem （DVRP） in the dynamic environment, a simulation model was established aiming at minimizing the number of vehicles and distances, maximizing the freight rate, besides, a novel cloud-based adaptive genetic algorithm （CAGA） was proposed. On the basis of the characteristics of the dynamic scheduling in actual distribution, a double chain quantum coding including vehicle allocation chain and goods chain was introduced. To overcome the shortcoming of premature convergence and the loss of diversity later in the genetic algorithm, the cloud crossover operator and cloud mutation operator were designed and an improved CAGA was proposed. The simulation results using dynamic simulation demonstrate that the proposed algorithm can reduce the precocious probability and improve the efficiency of iterative search.