中文摘要：

时变网络中车辆在任意两节点间的行驶时间不仅与节点间的距离有关，还与所处的时段有关．对时变车辆调度问题提出一种满足先入先出准则的跨时段处理方法，直接推导出跨时段对应的车辆行驶时间．在此基础上建立了数学模型，并构造动态规划启发式算法进行求解．该算法能够通过设置参数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.