火车调度问题---数学模型宣贯.pdf

火车调度问题摘 要近年来随着铁路交通的发展飞速发展, 无论是铁道部门还是旅客都希望缩短登车时间 , 这样铁路部门可以赢得更多时间用于行驶获得丰厚利润, 旅客也可以缩短旅途时间然而随着乘坐火车的旅客越来越多以及火车的容量不断增加, 使得登车时间却在不断加长如何缩短登车时间这一问题亟待解决针对各种列车的调度顺序问题， 文章将以某车站各列车调度为例建立一个状态模型，在此基础上展开并用于实际情况中状态模型的主要思想是： 假设各列车在某时间段内将驶离车站，通过安排驶离顺序使铁路部门利益与旅客对铁路的满意度达到一种理想化状态，使铁路紧张问题得到适当的缓解关键字 ：线性函数满意度退票费火车调度问题问题：某火车站有三个停靠站台，通常是用“先来后到”普通旅客列车（以下简称普通）让行普通快速旅客列车（普快），普快让行快速旅客列车（快速k） ，快速让行特快（ T） ，特快让行直达旅客列车（直达 Z）,直达让行动车（ D 或 C）”原则来分配进站出站所分配停靠站台，上行与下行线路分开， 及当一列火车准备进站和出站时，调度中心负责电告该列火车所进站台假设调度中心可以得到每列火车的如下信息：（1） 预计驶离站台时间（2） 预计停靠站台时间（动车2分，直达 3分，特快 6分，快速 8分，普快 10分，普速 12分）（3） 实际驶离站台时间（4） 火车乘客人数（5） 预定在下一站下车人数（6） 预定在本站上课人数（7） 到达下一站的预定时间（8） 从上一站驶出时间又设共有上行与下行上述旅客列车各一列，乘客数量分别为1600人（普通）、1400人（普快），1200人（快速、特快） 1000人（直达）800人（动车）1 试开发一种能使乘客和铁路公司双方满意的数学模型(2)假设1)铁路调度中心上有一个快速反应的数据库,该库中存贮着每一列火车的正点起行时间 ,正点抵达目的地的时间 ,乘客数量 ,行驶距离等信息 ,其他一些有用的参数 ,可以根据数据库中已有数据估计出来. 2)忽略不同类型火车停靠站台时间，这样可以把时间划分成间隔为的起行时段. 3)标号为 i 的火车在第 j 个时段起行所需费用与先前起行的火车无关,仅与其安排的次序有关 .这一假设使我们可以把总费用作为火车调度排序的线性函数. 4）由于各种火车行驶速度不一样，为使问题解单化，此处只设出平均速度及最大行驶速度 . 5)记为使火车尚能正点到达目的地所推迟起行的最长时间.同时假定 ,当火车的误点时间超过 时,则火车将以最大的安全速度行驶. 6)如果火车推迟起行的时间超过,则车上所有的乘客都将耽误到站. 7)因晚点而要求退票的费用对每一个乘客都是相同的且为平均退票费. (3)记号及意义: 火车的时间间隔 ; 0t最早起行的火车离站时间 ; dt: 正点起行的时间 ; AT: 正点到达目的地的时间 ; t: 晚点时间 ; : 最大允许晚点起行的时间; k: 各种类型的火车晚点起行而引起耗油的费用常数; V: 平均行驶速度 ; maxV: 最大的行驶速度 ; : 晚点而造成退票的退票率; m : 票价P : 乘客总数 ; w : 乘客出现退票的时间点: 由于晚点起行所引起的乘客不满意程度的增长率; a: 全体乘客由于火车晚点起行所引起的不满意度折合成人民币的折合率; 2 b: 退票乘客不满意度折合成人民币的折合率.分析与建模若有 n 列火车都要在正点时刻驶离该火车站（即为从上火车站有n 列火车几乎同时将到达该站 ).我们以总费用最小作为目标来安排火车起行的次序.总费用由三部分组成 ,即铁路部门的费用、退票费和乘客不满意程度所折合的费用. 设ijc为标号 i 的火车在第 j 个起行时段起行的费用 ,则总费用为ninjijijxcZ11由假设条件可知 ,ijc与ijx无关,因而总费用 C 是一个线性函数 . 这是一个调度问题 .假定每隔时间只有一列火车停靠在该站加入到请求起行的行列中 ,这样就保证总有火车请求起行.每隔时间 ,执行一次程序 ,以安排在当前状态下最优的起行次序.这里需要说明一点 ,该程序运行时间极短 ,不到一分钟便可完成 ,因此,如果数据发生变化时 ,如火车晚点进站（视为晚点起行）等,几乎可以立即决策 . 下面来分析费用系数的确定问题. 总费用应包括铁路部门的费用、退票费和乘客的不满意度所折合的费用.首先把基本费用视为0,即设火车在正点起行时的费用为0,仅考虑由于火车晚点起行所导致的额外费用 . 铁路部门的费用主要由两部分组成.一部分为额外的汽油费 ,这个费用主要是由于火车晚点起行时 ,要在快速行驶所额外消耗的汽油费;另一部分为晚点起行造成乘客退票的退票费 .若火车晚点起行 ,为了正点抵达目的地 ,它必须以最快速度行驶,这样由于风阻力的增大和其它因素,就要增加汽油的消耗 . 我们不太清楚速度的增加如何引起耗油费和增加,但当加速过程结束 ,在路上以最大安全速度行驶时 ,额外的耗油费将是一个常数.为简单起见 ,选用线性函数来表示额外的油耗费 ,其公式为 : tktkttF,)(3 其中,t 为火车晚点起行的时间 ,显然当火车正点起行时 ,t=0,若 t0 为首列起行的时刻,dt为正点起行的时刻 ,为起行的时间间隔 ,则第 j 个起行的火车晚点起行的时间为 : dtjtt) 1(0由于为最长的晚点起行时间 ,即当晚点起行的时间超过 以后,即使在路途中以最大速度行驶 ,也不能正点抵达目的地 ,因此m a xVdtTdA其中AT为正点抵达目的地的时刻 ,d 为行驶距离 ,maxV为最大的安全行驶速度.d 可用公式来表示VtTddA)(其中dt为正点起行时刻 ,V为正点起行时平均行驶速度. 常数 k 与油价、单位晚点时间油耗的增加率及最大安全行驶速度有关,同时还应与行驶距离有关 ,当然行驶距离越长 ,额外的油耗就越大 .由于行驶距离为Vtt)(0,则有: tVtkttVttktF,)(,)()(00下面再计算乘客由于火车晚点起行而退票的退票费用为: %80)()(pmtuktR为晚点而造成退票的退票率; u(t)乘客出现退票的时间段即: 0u(t)w,tt0u(t)0,u(t)0d费用系数中还应考虑乘客的不满意程度.一般地 ,火车晚点起行的时间越长 ,旅客就越抱怨 ,其不满意程度就越大 .如果晚点时间只有 12 分钟,旅客就不会太4 不满意 .但是,随着晚点时间的增加 ,旅客会非常生气 ,而不满意度会急骤增加 ,因此我们选用指数函数描述旅客的不满意程度.这个不满意程度对车上每一旅客都是如此,但对要退票的乘客 ,还需要追加另外的不满意度,用 D(t)表示总的不满意程度所折合的费用 ,则)() 1()(tubeaptDtp 为乘客总数 ,为乘客退票率 ,为了保证在正点起行时乘客的不满意度为0,因而采用了) 1(te的形式 ,显然 t=0 时,D(0)=0.为乘客不满意度的增长率,a,b 为折合率,) 1(teap代表全体乘客不满意度折合的费用, )(tub为退票乘客追加的不满意度所折合的费用,这一项只有当dtt才起作用 . 综上所述，费用系数ijc应为额外油耗费、赔偿费、及不满意度所折合的费用之和)()()(tDtRtFcijttuktubeapVtktwtuktubeaptVttkwtttubeaptVttkttcttdtdij%,80)()() 1()(%,80)()() 1()(),() 1()(, 0000t 和由下式给出m a x0)() 1(vVtTtTjtttavdAdAd2）计算实例为了执行简单，再作一些假设。

5 1）至多有三架飞机等候飞行（即n3)，如果不足三架，在模型中增加一架或两架虚拟的飞机，虚拟的飞机的费用系数视为02）任何飞机起飞时间至多1 分钟，即 =1，其间，其它飞机不能占用跑道3）跑道上没有飞机降落；4）每一个改航旅客的赔偿费用为350 美元；5）一个要改航乘客的不满意度是误点15 分钟的乘客的 2 倍乘客多的飞机先起飞例有 A,B,C 三架飞机都已离开了登机口,要求在上午 6 点钟正点起飞 ,这三架飞机将飞往三个不同城市,但空中飞行距离都相同 ,正点抵达目的地的时间均为上午 7 点 20 分.另外,其乘客数量分别为350,100,400, 且每架飞机上都有100 名乘客将在下一站转机 . 执行结果为 : 标号乘客数 /转机乘客数费用系数解A 350/100 0 0.48 0.97 0 1 0 B 100/100 0 0.41 0.83 0 0 1 C 400/100 0 0.5 1 1 0 0 其最小费用为 1.31,起飞的次序为 C,A,B.这一结果与我们的直觉完全一致,即在其它条件相同的情况下 ,乘客数量多的飞机优先起飞. 误点时间最长的飞机优先起飞接着上面问题 ,飞机 C 正在起飞的同时 ,飞机 D 已经离开了登机口请求起飞.已知飞机 D 载有 200 名乘客 ,其中 150 名将在下站转机 ,这架飞机已经晚点18 分钟,要使飞机 D 正点抵达目的地 ,必须在 2 分钟内起飞 (即必须在 6 点 02 分或 6 点 03分两个起飞时段内起飞 ).执行结果如下表 . 标号乘客数 /转机乘客数已晚点时间（min）费用系数解D 200/150 18 0.28 0.91 1 1 0 0 B 100/100 1 0.07 0.15 0.22 0 0 1 A 350/100 1 0.09 0.17 0.26 0 1 0 6 这个例子中的总费用为1.22,最优的起飞次序为D,A,B. 这一结果与直觉相符 ,即晚点时间最长的飞机优先起飞. 优先权相差不明显的情形当系统时钟指向 6 点 03 分,此时 C,D,A 三架飞机已先后起飞 ,飞机 B 已晚点3 分钟,而又有一架飞机E 离开登机口 ,请求起飞 .对飞机 E,我们知道如下信息 :总乘客数不 122 名,其中 89 名乘客在下站转机 ,晚点 1 分钟的费用为 450 美元;最长的晚点时间为 45 分钟. 在求解时 ,须增加一架虚拟飞机X,对应于飞机 X 的所有参数为 0.结果如下 : 标号乘客数 /转机乘客数已晚点时间（min）费用系数解B 100/100 3 0.6 0.8 1 0 1 0 E 122/89 0 0 0.28 0.56 1 0 0 X 0/0 0 0 0 0 0 0 0 从上表可以看到 ,总费用之差 0.88-0.8=0.08, 这个数目不太大 ,因而究竟哪架飞机应该先起飞不甚明显 .事实上 ,由于飞机 E 有较多的富裕时间 ,因而应先安排飞机 B起飞.但是,由于飞机 E 在飞行时费用较大 ,以及有更多的乘客 ,因而飞机 E 应先起飞,这与模型的结果一致 . 。