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

摘要：

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

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

所属期刊栏目：32

分类号：F253.4(物资经济)

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

在线出版日期：2013-03-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：1712-1718