摘要:为达到使空车调整真正满足铁路货物运输的需要,实现按计划开车的目的,将空车调整问题分为月度供求计划和日空车调整计划,分别加以求解。在日空车调整计划中结合货物列车时刻表,从空车需要地要车时刻出发,进行空车调度安排。最后结合实例用MATLAB进行求解,验证了模型和算法的实用性和合理性。
关键词:空车调整; 两阶段;列车时刻表;线性规划
现阶段对空车调整的研究大多将实际问题抽象简化为数学规划模型。而空车调整问题本身是一个受主客观诸多复杂因素影响的调度决策问题。且现有研究考虑的实际情况也不够全面,与实际情况结合的不够紧密[1]。 早期的相关研究主要针对数学模型的求解方法,如遗传学算法、蚁群算法。在随后的研究中,考虑了许多实际约束条件的限制。文献[2]综合考虑运输费用,将因到达时间引起的延误费用与管理费用考虑进来,使模型更为合理。文献[3]则进一步考虑了中转站对列车到达的时间要求。文献[4]从货主角度出发进行空车调整优化。
本文主要研究铁路局内各车站间的空车调整问题,并将路局内空车调整问题分为月度调整计划和日空车调整计划,从宏观总体调整到日常微观调整,使得问题更清晰,更符合实际。在日调整计划中,把日调整计划与列车时刻表相结合,从空车需要地要车时刻出发满足空车需求地的需要,以实现按计划开车的目的。
1 两阶段空车调整的思想
空车调整的第一阶段为路局内部空车月度供求计划的调整,根据路局内部各站空车供求情况进行优化分配。铁道部首先根据各路局上报的月度要车计划进行路局之间的空车调整,由于路局之间空车调整问题,,涉及很多主观因素,一般由铁道部直接下达命令进行空车调整。对某个铁路局来说,铁道部下达的空车调整计划可视为路局之间分界点上产生或需要的空车。
空车调整的第二个阶段是在月度空车供求计划的基础上,进行路局内部的空车日调整。在满足空车需要车站要车时刻的前提下,以总输运费用最小为最优的目标,制定空车产生站和需求站间可行的空车调配方案,包括调配空车数和发到时刻。
2 月度供求计划模型与求解思路
2.1 模型描述
假设某铁路局内有个空车需要站,各车站需要空车数量分别为, ;有个空车产生站,各车站产生空车数量分别为,。从站到站共有条走行径路,其中从第条径路运送的空车数量为,此径路上空车单位走行费用为,表示该径路的限制区间的运输能力。表示此路局内所有车站的集合。
铁路局月度空车优化调整问题可描述为:
目标函数: (1)
表示空车运输总费用最小。
约束条件:
(2)
表示站发送空车数不大于该站现有的空车数。
(3)
表示站接收的空车数不大于该站需要的空车数。
(4)
表示满足此径路限制区间的能力约束。
(5)
表示路局某一区间内空车流向不同时占用此径路。
2.2 模型的求解思路
结合图论原理,假设铁路局存在一个虚拟的空车产生站和一个空车需求站。如图1所示:局管外进来的空车可看作分界口站产生的空车,局管外需要的空车可看作分界口站需求的空车。当时,表示局内空车产生站;当时,表示空车需求站。各站间的连接线路上,分别用和表示空车运输能力和空车单位走行费用。空车产生站与虚拟的空车产生站之间、空车需求站与虚拟的空车需求站之间的运输费用均为0,前者的运输能力为空车产生站的现有空车数,后者的运输能力为空车需求站实际需要的空车数量。空车产生站与空车需求站之间的运输能力用表示,单位运输费用用表示,其中 ;。虚拟空车产生站到空车产生站、空车需求站到虚拟空车需求站的运输方向是一定的。内部其他点之间:产生站与产生站之间、产生站与需求站之间、需求站与需求站之间用不确定的单方向箭头连接。可见,铁路局月度空车调整问题可描述为一个最小费用最大流问题,该问题可用dijkstra算法求解。
图1 路局月度空车调整计划安排图
3 日空车调整计划模型与算法
3.1 模型描述
日空车调整计划模型是在第一阶段求得月度空车供求计划的前提下(即已知该月某空车需求地的空车从哪些车站运送),根据空车需要车站的空车需要计划(即空车需要车站根据运输需求所提出的关于空车的要车时刻、要车数量及车种的计划),考虑各空车产生站的空车供应情况,确定本站空车最早可编入列车的发车时刻(即空车产生站最快将已有的空车编入同去向、编组内容符合要求的某一车次货物列车的发车时刻)与最大可发出空车数(此车站已有空车数与该车次按货物列车编组计划最大可编入该站空车数之间的较小数值)。根据中转站的列车时刻表和货物列车编组计划的限制,可建立路网内各空车产生站向各空车需要车站发车的空车调配方案。
3.2 模型的求解
用MATLAB数学软件对日空车调整计划模型进行求解,求解步骤为:
⑴ 根据建好的路网,构建线路结构矩阵,即:两站间可通车,值取1;不可通车,值取0;
⑵ 根据已有数据构建两相邻车站间空车总的走行费用矩阵;
⑶ 获得任意车站单位时间空车停留费用(元/h)(空车产生站也要看作是有停留费用的车站);
⑷ 在已建好的路网中任意两相邻车站间建立一张表格,表格内容应依据货物列车编组计划和货物列车时刻表填写。在表中第1列内,填入该相邻车站中后方车站的某一车次按编组计划最多可编组空车的辆数,第2、3列分别填入该车次在本站的出发时刻、在前方车站的到达时刻,将所有可能编组空车的车次按时间顺序,依次填入每一横行内。
⑸ 根据空车产生站的空车供应情况,从空车需要车站提出空车要车计划时刻开始,确定空车产生站和此刻相邻最近的可行发车时间与此时的最大可发空车数;
⑹ 对于每一空车产生站都取出所有从该站到某一空车需求站站的可行的路径,对于某一条径路,依次取空车产生站的可行发车时间,可得到达下一相邻车站的时间,再从该相邻车站取一个可行的发车时间,以此类推,直至推算出到的时间。如果到站的时间在要车时刻之前,则记为一种可行的空车调配方案,按此枚举出所有的可行径路以及可行的空车调配方案。计算出1辆空车在某一调配方案下在各站的停留费用以及在站间走行的费用,加和,作为1辆空车在此运行径路下的总费用;
⑺ 将所有可行空车调配径路按费用由低到高排列,从最小费用径路开始计算,从该径路的起点运送空车,如果所需的空车数大于该径路的通过能力,则从此站发出恰好为该运行径路下通过能力的车数,剩余空车则从第二个运行径路中得到,依次类推。如果某一空车产生站的空车产生总量已超过空车需求站的通过能力,则剩余空车从其他调配方案中选取费用最小的运行径路进行安排;