摘要：时变网络中车辆在任意两节点间的行驶时间不仅与节点间的距离有关，还与所处的时段有关．对时变车辆调度问题提出一种满足先入先出准则的跨时段处理方法，直接推导出跨时段对应的车辆行驶时间．在此基础上建立了数学模型，并构造动态规划启发式算法进行求解．该算法能够通过设置参数H平衡求解质量和运行时间．通过对10组随机产生的数据进行测试，结果表明动态规划启发式算法能够在很短时间内改进最近邻算法．当H=2时，求解质量改进11％，平均运算时间为1．34秒；当H=3时，在不到2秒的运算时间内求解质量改进17％．

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

单位：西南交通大学经济管理学院 成都610031 北京交通大学系统科学研究所 北京100044