动态车辆路径问题的优化方法

设计了在动态环境下进行车辆路径优化的导向局域搜索算法.算法在产生初始解以后的动态求解过程中,不再做车辆之间的顾客调整,而只应用2-opt局域搜索算子更新车辆服务顾客的顺序,即针对每辆车辆的旅行路线求解一个旅行商问题.建立了在动态环境下车辆执行运输任务过程的仿真模型.仿真过程中,应用算法根据交通路网实际情况实时优化车辆路径,并采用4种接受准则判别是否接受新的车辆路径.仿真结果表明:算法具有实时、高效的特点,满足动态车辆路径问题的求解要求.

Optimization Approach to Solving Dynamic Vehicle Routing Problems

A guided local search(GLS) algorithm is presented to solve dynamic vehicle routing problems(DVRP).In the dynamic solving process after an initial solution, the GLS does not exchange customers between vehicles but applies the 2-opt local search operator to updating the servicing sequence for customers,i.e.,to solve a traveling salesman problem of traveling routing of each vehicle.A simulation model is thus developed for the dynamic process during which vehicles are in traffic.In the simulation model the GLS algorithm is applied to optimizing the vehicle routes in accordance to the real-time traffic situation,and four rules are applied to judging if the newly optimized vehicle routes are accepted.The simulation results reveal that the GLS algorithm can provide real-time response to dynamic information to satisfy the requirements of solving DVRP.