基于时间窗的铁路空箱调运问题分析

郑 燕

（兰州交通大学 交通运输学院，甘肃 兰州 730070）

1 机会成本与重箱的经济效益

机会成本是一个多阶段的优化问题，本文中为研究方便，当考虑机会成本最小时，只考虑若早于时间窗情况下给予的线性处罚；若晚于时间窗到达的话，将资源用于下一周期使用，此过程中空箱将产生堆存费，另外，没有按要求时间到达的空箱，因没有投入生产，也会损失部分运输收入，这部分收入也将作为机会成本的处罚。因此，要使本规定的机会成本最小。

当空箱转载货物以后变成重箱，重箱不断累加，形成重箱流（重箱流指某条径路上由重箱形成的流）。在考虑集装箱空箱调运优化时，应尽量考虑如何使空箱变成重箱后产生的总价值最大。例如：A 地调运到B地的调运成本为2 000，产生的经济效益是4 000，而A 地调运到C 地的调运成本为3 000，产生的经济效益为6 000，那么在决策时当然要选择从A 地调运到C地。因为，其空箱变成重箱后产生的总价值，后者显然要比前者大。

在众多的研究中，绝大多数研究均注重调运成本，甚至把调运成本最小化作为唯一的优化目标，当然，这也是有一定道理的，但是从空箱的产生到空箱的调运，再到空箱的使用，这个宏观体系来考虑，其实这几个环节是相互影响，而不是独立的，因此，在研究过程中也应当考虑空箱的使用。

2 基于时间窗的铁路空箱调运问题分析

空箱调运问题是一类重要的运筹学和组合优化问题，合理科学的调运空箱方案，不但可以提高集装箱的配送效率，同时又能够产生巨大的经济和社会效益，带来众多正面效应。用户使用集装箱来运输自己的货物时，必然会对何时能够得到空箱有一定的要求，所以，在服务时间上空箱到达一般分为3种情况：没有时间窗要求（A）、有硬时间窗要求（B），有软时间窗要求（C）。

硬时间窗要求是指客户接受服务的条件是对客户的服务必须在给定的时间段内进行，没有商量的余地，否则，该客户拒绝接受服务。

上述机会损失可以表示为：

1）在规定时间内到达，而此时正好需要空箱，于是空箱正好被及时的投入生产，这是恰到好处的情况。

2）在规定的时间段内提前到达，空箱将会被暂时的存放，由于这个原因而产生一些空箱堆存费，这是等待的情况。

3）在规定时间段延后达到，即前一个时段已经结束，于是即使空箱到达了也不能够在此周期将空箱投入生产，此时的选择便是：可以选择不调运或者把调运的空箱投入下一周期。

在研究过程中所做的目标就是如何使这种机会损失达到最小，本论文对于那些晚于时间窗到达的空箱放到下一周期使用，但把这部分空箱的堆存费和假设按时到达产生的收益作为惩罚成本。

2.1 模型假设

假设系统中，有m个货运车站，由于运空箱需求和供应的不平衡性，必然导致部分车站空箱多余、部分车站空箱不足，为了更好的利用空箱，需要对这m个车站的空箱进行调运。由于各车站对集装箱空箱的到、发时间有一定的要求，需在带有时间约束情况下合理调运空箱。空箱调运周期设为T天，为简化计算，各车站之间视为只有一种类型的集装箱，而且车站之间延误的单位集装箱损失的经济效益相同。

参数设定如下：

1）第i个车站中，可供应的集装箱空箱数为Gi（i＝1，2，3，…，m）；

2）第j个车站中，需求的集装箱空箱数Xj（j＝1，2，3，…，m）；

3）i车站到j车站：集装箱空箱的单位的运输成本Cij；

4）i车站可以从j车站调配到的集装箱空箱的数量xij；

5）i车站到j车站的实际运输时间（与箱型无关）tij；

6）i车站出发到j车站的空箱的到达、发送时间分别为

7）没按规定时间到达，造成的单位空箱单位时间集装箱场地占有费为F；

8）迟于最晚时间到达的单位空箱，在准时到达时投入生产所产生的经济效益W；

9）i车站到j车站的之间，存在的集装箱空箱运输能力限制为Lij；

10）在i车站所能接受的集装箱空箱最早时间、最晚时间分别为ei，li；

在存在时间窗的状况下，可以假设调运任务i需在时间段［ai，bi］内完成，其一般关系如下

式中：τi为到达i节点的时刻，ti为在i节点等待的时间，si为到达j节点的时间。

式（3）表示在硬时间窗内必须满足在要求时间内完成空箱调运，否则为不可行解；那么在软时间窗时不能按照要求时间完成的任务将给予一定惩罚。

客户基本上都会有一个允许的提供的空箱最早和最晚到达时间的容忍区间，空箱提前到达，对于之后的货物运输工作实现了条件，但同时也会产生一些问题：比如说会产生一定的场地积压费用，而且也会占用集装箱堆场的空间。而如果空箱到达太晚，必定会损失一定的客源，由于一些客户对时间的要求非常严格，这便产生了一些无形的但是又有实际负面效果的机会成本。

2.2 基于时间窗的铁路集装箱空箱调运问题分析

2.2.1 不考虑时间窗的约束

模型此时即转化为经典的“货郎担”问题，只需使用动态规划的方法，便可求出全局的最优解。如果把目标定为成本最小，模型为

约束条件为

式（6）表示多余空箱节点发送到缺箱节点的空箱总和，小于或者等于多余空箱节点可提供的空箱数目；式（7）表示要尽量满足缺箱节点上反映出的缺箱需求；式（8）表示要满足运输能力的约束，不能忽略实际情况；式（9）表示发送节点的发送时间加上发到节点之间的运行时间等于到节点的到达时间。

此种情况下约束条件中的都应满足非负数约束。

2.2.2 软时间窗

假如某些任务不能在规定的时间窗内完成，这种状况下，必定会增加部分费用，第一种假设条件，假定没有时间窗，这便回到了（1）状况，用（1）的方法求的无时间窗下的最优成本，若此时有时间要求的话，则可能会违反时间窗的范围，这便会出现相应的堆存费与延误费，在一定意义上便增加成本值及其余相关费用。因此，问题转化为堆存费和假设没有迟于最晚时间的空箱产生的经济效益的减少与运输成本增加之间寻求最优值。

在软时间窗下除了一部分满足时间要求，即在规定时间内提供服务，还有一部分不能够在要求时间内到达，在本文中将其产生的堆存费和假设没有迟于最晚时间的空箱产生的经济效益定义为机会成本，表示这些空箱未能够得到充分利用，则问题可转化为在优化时使机会成本最小。对于那些迟于最晚时间到达的空箱可为不确定条件下的空箱需求或者直接转为下一周期使用，本论文不考虑不确定性条件下的空箱需求。

首先设定选择软时间窗情况下空箱调运的处罚函数

f（xij）为从i车站到j车站调运的空箱xij获得的惩罚成本。

模型为

机会成本最小模型约束条件与无时间窗约束条件一样。

在空箱配流时一般情况下都要考虑调运成本最小，式（11）如果加上这些集装箱空箱走行费用则为在软时间窗下空箱调运费用最小化模型

2.2.3 只有硬时间窗

在规定内的时间内完成每项调运任务，而且是硬性要求的。即必须满足式（3），若超出这个范围，便会得到不可行解。

这种情况下有一种办法，便是可以将单位时间堆存费，以及假设没有迟于最晚时间的空箱产生的经济效益设置为无穷大（F＝W＝P（P→∞）），即必须满足时间窗，毫无例外，在这样约束的情况下，进行求解，否则不可行。

此时模型目标应为调运费用最小化，模型为

约束条件与无时间窗约束条件一样。

2.2.4 如果同时含有软时间窗和硬时间窗

假定先不考虑硬时间窗，求最优路径的方法是按（11）求得，之后，在考虑硬时间窗的点，逐步检查看是否满足，满足则可行，即为最优解，否则只能硬时间窗单独提出来，对剩余的点按照（13）进行判定，逐步优化，哪些点是机会成本最小的，这便得到了，在这种状况下的最优成本及路径。

3 结束语

铁路集装箱空箱调运一直困扰着我国铁路集装箱事业的发展，做好空箱调运工作，能够最大的挖掘其存在的产业效益潜力，对我国铁路集装箱事业产生巨大的推动作用。本文结合自身专业知识，并参考大量文献，对基于时间窗的铁路集装箱空箱调运问题提出了一些解决方法。但是本文在一些方面仍需努力，如对客户价值进行划分，由于空箱调运是一个系统的工作，实际有不同主体及其利益，从客户来讲，不同客户具有不同的价值，将客户进行系统的划分，区分其价值大小，然后将客户价值与调运成本结合起来，有助于提高整个铁路企业的经济效益。

［1］赵丹.随机环境下海运集装箱空箱调配问题研究［D］.上海：上海海事大学，2005.

［2］闫海峰，彭其渊，谭云江.结点站间集装箱班列开行方案的优化模型及算法［J］.中国铁道科学，2008，29（1）：101－189.

［3］周红梅，方芳.航运集装箱空箱调运优化模型的研究［J］.武汉理工大学学报（交通科学与工程版），2003（6）：354－357.

［4］汪传旭，刘大熔，贺斌.随机条件下空箱调配模型研究［J］.交通运输工程学报，2001（9）：119－122.

［5］罗孝彬.杨容浩.邓虎成.带时间窗的货物配送方案模型及软件实现［J］.成都信息工程学院学报，2005（3）：175－179.

［6］杨银奇.集装箱空箱调运问题研究［D］.大连：大连海事大学，2007.

［7］彭其渊，闫海峰，周勇.集装箱班列编组计划相关因素分析［J］.中国铁道科学，2003，24（5）：120－123.