时变单车路径问题建模及算法设计

讨论了一类时变单车配送路径优化问题。综合考虑车辆行驶速度随时间、路段不同而变化的特点,及车辆为多条路线上的客户提供服务时对车辆路径优化的影响,建立了以配送完成时间最早为优化目标的时变单车配送路径优化模型。在行驶时间满足FIFO规则下,设计了基于Inver-over操作的PSO启发式算法及满足贪婪配送策略下的动态规划精确求解算法,并讨论了增加贪婪补货策略的单车配送路径问题解与原问题解的关系。最后分别用两种算法对算例进行求解,并通过对求解优化结果及计算时间的对比分析验证了IOPSO算法的有效性。

Route Modeling and Algorithm Designing of Time-Dependent Single Vehicle

The route optimization problems of one kind of time-dependent single vehicle are discussed.With the comprehensive consideration that vehicle’s velocity is changing with time and different sections of road,as well as the influence of vehicle route optimization when the vehicle provides service for multiple routes customers,a route optimization model of time-dependent single vehicle is established,which takes the earliest distribution completion time as the optimization target.A particle swarm optimization algorithm based on inver-over operator with FIFO rule is developed.Adding greed dispatching restriction,a dynamic programming algorithm with FIFO rule is provided.The numerical example verifies the validity of theoretical analysis results.