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

被引：14

作者：

李妍峰 ^{[1
]}

李军 ^{[1
]}

高自友 ^{[2
]}

机构：

[1] 西南交通大学经济管理学院

[2] 北京交通大学系统科学研究所

来源：

系统工程理论与实践 | 2012年 / 32卷 / 08期

关键词：

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

D O I：

暂无

中图分类号：

U492.22 [];

学科分类号：

082302 ; 082303 ;

摘要：

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

引用

页码：1712 / 1718

页数：7

共 6 条

[1] 时变网络环境下旅行商问题研究 [J].

李妍峰 ;

李军 ;

高自友 .

系统工程学报, 2010, 25 (05) :585-591

[2] 一种求解时变条件下有宵禁限制最短路的算法 [J].

魏航 .

管理科学学报, 2009, (01) :9-17

[3] 用动态搜索算法求解时间依赖型旅行商问题 [J].

李妍峰 ;

李军 ;

赵达 .

西南交通大学学报, 2008, (02) :187-193

[4] 时变条件下有害物品运输的路径问题研究 [J].

魏航 ;

李军 ;

蒲云 .

系统工程理论与实践, 2006, (10) :107-112

[5]

A Queueing Framework for Routing Problems with Time-dependent Travel Times[J] . Tom Van Woensel,Laoucine Kerbache,Herbert Peremans,Nico Vandaele.Journal of Mathematical Modelling and Algorithms . 2007 (1)

[6] A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem [J].

Malandraki, C ;

Dial, RB .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 90 (01) :45-55

← 1 →