动态规划启发式算法求解时变车辆调度问题  

Dynamic programming heuristics for solving time dependent vehicle routing problem

作　　者：李妍峰[1] 李军[1] 高自友[2] 

机构地区：[1]西南交通大学经济管理学院,成都610031 [2]北京交通大学系统科学研究所,北京100044

出　　处：《系统工程理论与实践》2012年第8期1712-1718,共7页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71001005);中央高校基本科研业务费专项资金(SWJTU11CX087)

摘　　要：时变网络中车辆在任意两节点间的行驶时间不仅与节点间的距离有关,还与所处的时段有关.对时变车辆调度问题提出一种满足先入先出准则的跨时段处理方法,直接推导出跨时段对应的车辆行驶时间.在此基础上建立了数学模型,并构造动态规划启发式算法进行求解.该算法能够通过设置参数H平衡求解质量和运行时间.通过对10组随机产生的数据进行测试,结果表明动态规划启发式算法能够在很短时间内改进最近邻算法.当H=2时,求解质量改进11%,平均运算时间为1.34秒;当H=3时,在不到2秒的运算时间内求解质量改进17%.The vehicle travel time in time varying network not only depends on the distance between the nodes but also the time of day. In this paper, we developed a method satisfying first-in first-out property to deal with time period（s） crossing. The travel time can be deduced with it directly. The problem was formulated and a novel dynamic programming heuristics was presented to solve it. The algorithm can balance solution quality and computation time with parameter H. From the simulation results on 10 randomly generated cases, the new method can greatly improve the solution of nearest neighborhood algorithm within a very short time. When H=2, the average solution is improved 11% while the computation time is 1.34s. It also can be improved 17% within less than 2s with H=3.

关 键 词：时变车辆调度问题 先入先出 动态规划启发式算法 最近邻算法 

分 类 号：F253.4[经济管理—国民经济]