优化空车调配问题

优化空车调配问题李文权杜文周贤伟(西南交通大学 运输工程系 成都 610031)【摘 要】 首先阐述了车站空车调配问题对编制车站日班工作计划的意义, 通过利用卸后空车对配空车问题进行优化研究, 给出配空车问题的数学模型。【关键词】 铁路; 车站; 车流组织; 空车调配; 优化【分类号】 U 291. 7空车调配问题是铁路运输管理研究部门最为关注和广泛研究的问题之一。 许多学者一直在寻求建立能够反映空车调配过程优化的数学模型。 目前国内外学者对此问题的研究集中在 结合列车径路及编组计划, 对路网上空车调配进行综合优化1- 10 。文中以提高车辆利用率为目标。 将车站空车调配问题分为两个子问题: (1) 如何根据货主 的请求车种和货物品类调配最少数量的车数来满足货主需求。 (2) 充分利用本站卸后车, 根据某时刻车站货物各货位上空车分布确定调配空车方法。车数最少的空车调配模型1无论从提高车辆利用率或是从缩小总的作业车停站时间上分析, 用最少的车数, 满足一定的货物运送, 减少不合理代用是最有效的方法。 这就要求采取车货配合的原则, 充分提高车辆 利用率。设车站货场或专用线有 m 种待运货物分布在 m 个货位上。 第 j 货位上的货物 ( 称第 j 种 货物) 共有 bj。车站可用货车共 n 种, 其中第 i 种共有 a i 辆, 它可运载第 j 种货物 cij。问题是寻求一种合理调配方案使得能运完所有 m 种货物的情况下, 运用总车数最少。 若记 x ij 表示第 i种车辆调配给货位 j 的车数。 若第 j 种车不可运载第 j 种货物则令 cij = 0, 于是该问题模型为n mx ijm in z =i= 1 j = 1ns. t. ci j x ij = bji= 1mx ij a ij = 1i = 1, 2,x i j 0 且为整数, nj = 1, 2, m这是一个非标准的分派问题。与此问题等价的另一表现形式是当车站可利用车少, 而待收稿日期: 1997203203李文权: 男, 1964 年生, 讲师, 博士。 384 西南交通大学学报第 33 卷运量多时, 最多装车量模型为nmm ax z = C ij x iji= 1 j = 1ns. t. C ij x ij bji= 1mx ij = a ij = 1i = 1, 2,x ij 0 且为整数j = 1, 2, m对于上述模型已经有很多应用程序求解, 可以直接移植。2车站货场、专用线空车调配模型上节考虑了为完成本站装本任务而需向各作业点最优配拨空车数。对于不同性质的车站,这个问题的表现形式不同, 适应情况也不同。例如对于装车站或卸车站是适应的。但对于一般 的装卸车站, 由于按双重作业方式可以压缩停时, 减少空车出入货场、专用线的调移。因而车站都积极采用卸后车来实现装车, 扩大双重作业车比重。 若本站装车数大于卸车数, 则除本站卸 后空车能用者外还要求其它站配空。若卸车多于装车, 则本站装车所需空车主要用卸后车。对 多余卸后空车向其它站排空。 车辆在装卸车站货场, 专用线的状态变化和移动见附图。(a)(b )装车数大于卸车数卸车数大于装车数附图作业车状态变化示意图由于第 1 节模型得出配空数为计算期内第 j 种货所需第 i 种车总数。 然而由于车场货位能力等原因, 这个数目的车种是在计划期内分时段逐次实现的。 在每一时段开始时, 各装车作 业点所需空车首先从卸车作业点卸毕空车中挑选。挑选目标是调车行程最小。为此需分时段,根据各装卸点的待装及卸车车种、车数进行再次具体分配。 现建立其模型。由于货场或专用线布置线路都可以抽象为放射状, 树枝状或放射状与树枝状的混合。从图 论观点上看它们都是一棵树根为车站的有根树。 货物作业点都位于树的末端- 树叶上。 而树中任两点间最短路唯一, 从而不同作业点间距离唯一, 这些距离构成了一个矩阵 D = (d i j ) m m ,其中 d ij 为货位 i 到 j 的距离。设第 j 个货物作业点在 t 时刻需第 k 种货车为 a k t , 第 i 个卸车点于 t 时刻前卸后第 k 种货j车为 bk t , 求最优调配方案使总的调移距离最短。若令 x k t 表示 t 时刻 i 作业点提供给 j 作业点 kii j 1994-2014 China Academic Journal Electronic Publishing House. All rights reserved. 第 4 期李文权等: 优化空车调配问题385种空车数, 则该问题模型为mmm in z = d i j x k tiji= 1 j = 1mx k t bk ts. t.ijij = 1mx k tk ti j = a ji= 1j = 1, 2,x k ti j 0i = 1, 2, m, mk P , N , C , G , B 以上是卸车数大于装车数的模型。 若装车数大于卸车数, 则模型可写为m mm in z = d i j x k tiji= 1 j = 1mx k t = bk ts. t.ijij = 1m x k tk tij a ji= 1x k ti j 0i = 1, 2, mj = 1, 2, mk P , N , C , G , B 将上述模型综合起来得如下统一形式mmm in z = d i j x k tiji= 1 j = 1mx k t bk ts. t.ijij = 1mx k tk ti j a ji= 1x k ti j 0i = 1, 2, mj = 1, 2, mk P , N , C , G , B 需要说明的是:(1) 若 t 时刻只有 j 货位需 k 种车 a k t 辆, 则上述运输问题便退化为jmmm in z = d i j x k tiji= 1 j = 1x k t bk ts. t.i j imx k tk ti j = a ji= 1x k tij 0i = 1, 2, mk P , N , C , G , B (2)若各线于 t 时刻可提供 k 种空车均小于所需这种空车时, 为了赶车流, 必须由邻站调配空车, 其数目为上述模型变成标准形式时的松弛变量值。(3) 对于给定 t 值, 上述模型可用文献10方法求解。3完成配空任务的机车使用模型考虑为压缩本站作业车在站停留而采取卸后空车来进行配空的优化模型。 它只解决了 t时刻地点上的距离优化问题。 由于车辆在货场的状态是随时间而变化的。 调机的使用正是各 1994-2014 China Academic Journal Electronic Publishing House. All rights reserved. 386 西南交通大学学报第 33 卷作业点车辆状态发生变换的前提。各作业点装卸动力的实施则是车辆状态发生变化的条件。众所周知, 向某作业点送车, 其先决条件是该点有货位和动力。取车必须在作业完毕, 否则只能造 成不必要的等待。 调机在货场的工作过程通常是: 将卸车后可利用空车调移给装车点, 把不用空车及装后车收集起来出线 (送到调车场)。 再于特定时刻将到发线上成组换挂或调车场本站 作业车停留线上货车挑选出送入货场或专用线 (入线)。 调机的这一取送过程正好为各作业点 提供了作业时间促成车辆状态发生变化。如此周而复始反复运作。其中调机于何时入线, 调移 车辆次序等都属于调机应用模型解决的问题。 它既与车流性质有关又与货场能力及工作量有 关。 其具体模型将另文讨论。参 考 文 献1H agh an i A E. R a il f re igh t t ran spo r ta t io n: a rev iew o f recen t op t im iza t io n m o de ls fo r t ra in ro u t ing andem p ty ca r d isr ibu t io n s. J. o f A dv. T ran s. , 1987; 21: 142-172韩廷桂. 车站货运作业过程优化的探讨. 兰州铁道学院学报, 1992, 11 (3) : 120- 125M isra S C. L inea r p ro g ramm ing o f em p ty w ago n d ispo sit io n. R a il In te rna t io na l. 1972; 3 (3) : 151- 180P h ilip C E , X u ssm an J M . Inven to ry m o de l o f th e ra ilro ad em p ty ca r d ist r ibu t io n p ro ce ss. T ran s2234po r ta t io n R e sea rch R eco rd. , 1977; 56: 52-605M end ira t ta V B. A dynam ic op t im iza t io n m o de l o f th e em p ty ca r d ist r ibu t io n p ro ce ss. P h. D. D isse r ta2t io n , N o thw e ste rn U n ive r sity, E van sto n, Illino is, 1981M end ira t ta V B , T u rnqu ist M A. M o de l fo r m anagem en t o f em p ty f re igh t ca r s. T ran spo r ta t io n R e26sea rch R eco rd. , 1982; 838: 50-557Jo rdan W C , T u rnqu ist M A. A sto ch a st ic dynam ic m o de l fo r ra ilro ad ca r d ist r ibu t io n. T ran spo r ta t io nSc ience, 1983; 17 (2) : 123- 145H agh an i A E. Fo rm u la t io n and so lu t io n o f a com b ined t ra in ro u t ing and m ak eup , and em p ty ca r d is28t r ibu t io n m o de l. T ran spo r ta t io n R e sea rch R eco rd (p a r t B ) , 1989; 23: 433-4529刘海林. 用电子计算机进行铁路空车调配的探讨. 铁道运输与经济, 1987: 29- 3210 李文权, 杜文. 运输问题原设一对偶算法的一个改进. 西南交通大学学报, 1995; 30 (5) : 543- 549O p t im a l A ss ignm en t of Em p ty Ca r sL i W en qu a n D u W enZ h ou X ia nw e i(D ep t. o f T ran sp. E ng. , So u th e st J iao to ng U n ive r sity, C h engdu 610031, C h ina)【 A bstra c t 】 T h e op t im a l a ssignm en t o f em p ty ca r s is stu d ied in th is p ap e r. T h esign if ican ce o f stu dy in g th e p ro b lem o f da ily an d sh if t p lan s is d is2 cu ssed. T h e p ro b lem is stu d ied w ith re sp ec t to u n lo aded em p ty ca r s, an d it s m a th em a t ica l m o de ls a re p re sen ted.【Keyword s】 ra ilw ay s; sta t io n s; o rgan iza t io n o f ca r f low ; a ssignm en t o f em p tyca r s; op t im iza t io n 1994-2014 China Academic Journal Electronic Publishing House. All rights reserved.