⑻ 最终获得整体的空车调配计划(即空车在空车产生站的发车时间以及发车数量;空车到达需求车站的数量以及到达时分;空车在各中转站间的到发时分以及数量),以及空车调配总费用。
利用计算机编程时,需要用到图论中图的读取方式,将所有运行径路都读取出来,然后算出每条运行径路的总行车时间。用空车需要时刻与空车从空车产生站出发时刻之差,减去总行车时间即得到每条运行径路上各站停车时间的总和,再结合列车时刻表,得到每条运行径路上空车的走行方案(即到在各中转站的发到时刻)。同时,确定该运行径路的通过能力。在已知具体空车走行径路时,可求得此种方案的一辆空车的调配总费用,再从总费用最小的路径开始,按照费用由低到高的顺序,考虑空车需求与供应能力,安排空车调配方案,直至空车需求全部得到满足为止。在选定了某种具体方案后,可将这种方案的路径看成一条长度不定的链表。链表的每个节点即为车站,节点决定了等待时间,等待费用等信息;链表的链条即为路径,链条决定了行车时间,行车费用等信息。在遍历链表时,由于每站发车的时间一定晚于到站时间,同时到终点站的时间也一定早于截止时间,这就给路线上每一站的发车时间归定了动态的上限和下限,与遍历每个发车时间相比,大大减少了计算量,加快了计算的速度。
4 算法举例
月度空车调整计划可由dijkstra算法得到,在此不再举例说明。以下介绍日空车调整计划的求解过程。
从月度空车调整计划结果可知本月度内点的某一车种的要车计划全部由、站提供。车站的空车要车计划于0时产生。内容为:当日24时以前站需要空车总数为25辆。此时可行的发车方案为15辆空车于0时随某车次货物列车出发,可行的发车方案为25辆空车于2时随某车次货物列车出发。求总费用最小的空车运输方案。
已知站空车调配的路网如图2所示。算法求解过程如下:
图2 D站空车调整路网图
(1)根据图2,可得出线路结构矩阵。
(2)两相邻车站之间1辆空车总走行费用(即线路长度与1辆空车走行1km的费用)如表1。
表1 空车走行费用表
前方车站名称
后方车站名称
一辆空车总走行费用(元)
S1
T1
8
S1
T4
10
S1
D
20
S2
T2
10
S2
D
18
T1
T2
3
T1
T3
6
T2
T1
3
T2
T3
6
T3
D
8
T4
D
12
将表1数据转化成空车走行费用矩阵。
(3)各车站的空车单位时间停留费用见表2。
表2 空车单位时间停留费用表
车站名称
单位停留费用(元/h)
S1
3
S2
4
T1
5
T2
2
T3
3
T4
1
(4)按照货物列车时刻表与列车编组计划建立表3。
表3 列车时刻与编组计划表
发车站最多可编组空车数目
发车站发车时刻
到达站到达时刻
发车站最多可编组空车数目
发车站发车时刻
到达站到达时刻
S1-T1
S1-T4
4
0
7
6
4
13
4
4
11
6
8
17
4
8
15
6
12
21
4
12
19
6
16
25
4
16
23
S2-T2
4
20
27
6
3
12
S1-D
6
0
6
12
4
23
6
11
20
12
16
35
6
15
24
S2-D
T3-D
12
6
23
4
0
7
12
18
35
4
4
11
T4-D
4
8
15
8
6
18
4
12
19
8
14
26
4
16
23
8
22
34
4
20
27
T1-T2
T1-T3
8
0
3
8
2
7
8
8
11
8
10
15
8
16
19
8
18
23
T2-T1
T2-T3
8
4
7
8
2
7
8
12
15
8
10
15
8
20
23
8
18
23
由MATLAB程序优化算得费用最小的最佳空车调配方案为:
于0时向发3辆车,7时到达;于10时向发3辆车,15时到达;于16时向发3辆车;23时到达;于4时向发12辆车,23时到达;于6时向发10辆车,23时到达。空车调配总费用为844元。
5 结束语
本文将空车调整问题分为两个阶段分别进行计算,即从宏观的月度供求计划到微观日的空车调整计划,不仅大大减少了计算量,也使得计算结果更为准确。日空车调整计划与货物列车时刻表的结合不仅使空车调整方案更接近实际,也有利于保证空车需要站要车计划的实现,从而为铁路运输工作的顺利开展打下良好的基础。
参考文献:
[1] 张喜. 铁路空车调整综合优化模型与智能决策方法的研究 [D]. 北京:北京交通大学,2004
[2] 王利华, 张占军. 铁路空车调整综合优化模型 [J]. 铁道运输与经济, 2005 (8):69-71
[3] 陈煜, 张喜. 带时间窗空车调整问题的遗传算法研究 [J]. 铁路计算机应用, 2007,16(2):4-7
[4] 程学庆, 蒲云. 基于货主满意度的模糊空车调配模型的研究 [J]. 铁道运输与经济, 2007(11):71-73