Abstract: 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 timedependent 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.

Key words: route optimization, dynamic program, particle swarm optimization ( PSO) , time-dependent, FIFO rule

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

关键词: 路径优化, 动态规划, 粒子群算法, 时变, FIFO 规则