作者：祝心怡，香港理工大学在读博士生
研究方向:多式联运，客货共运
编者按
尽管多式联运经常面临服务中断的情况，但客户对准时交货的期望却越来越高，为多式联运的规划带来了巨大挑战。一方面，必须尽早投入资源以避免中断的扩大，并保持目标客户的服务水平；另一方面，分配超过必要的资源会导致巨大的成本。本文研究了多式联运的战术规划整合模型，考虑了服务中断、时间窗限制和客户服务要求，并将战略规划和运营规划进行了整合。在改进了模型的下界后，本文使用四种启发式算法进行求解。
1.引言
多式联运网络的单一管理结构不仅能实现更深层次的运营整合，还能在战略和战术规划期间实现资源分配的合理化。过往研究文献中较少考虑货运中出现中断的情况，因为这会使模型变得难以解决。本文从多式联运承运商（后简称承运商）的角度出发，为此类多式联运网络开发了一个整合规划模型：该模型中考虑了货运中面临的中断，并考虑时间表决策和客户服务水平。整合策略上，模型通过对偏离长期战略目标的行为进行惩罚，将战略决策纳入战术规划；并将即时运营规划决策作为追索（recourse）以改进决策。因此，本文解决了战术规划中的随机延误、客户服务水平和实际列车的详细调度问题，同时还考虑到了战略目标、战术规划和运营成本的权衡。
2.多式联运的三层规划
2.1 战略规划
在战略规划阶段，承运商决定优先考虑哪些市场、终点和客户，以及每个市场每年的目标运量。承运商需要对服务的目的地和频率做出承诺，偏离战略目标则需要付出代价。本文考虑如果战术规划阶段分配的运力高于战略规划时设定的运力，会导致更高的战略成本；如果战略规划阶段设定了过多容量但未使用，则会受到惩罚。本文在模型中，假设一周内必须安排的列车行程（行程：列车在预期出发时间从起点出发，在预期到达时间到达终点）应介于期望的最小值和最大值之间来体现这种权衡，对超出此范围的偏差进行惩罚，图1举例说明了行程的上下界。
图1. 战术规划阶段的战略承诺
2.2 战术规划
在战术规划阶段，承运商会制定时间表，将客户订单分配到各个车次。此外，计划人员还可以灵活地在调度点租用额外的列车，以防预计可能出现的严重干扰。确定性情况下，通过直达列车将订单送达最终终点最有效。但是，如果订单终点的时刻表不频繁或需求量小，或者预计会发生中断，则可能会改道至邻近终点，并使用卡车到达终点。具体来说，当预计某些路线会出现严重中断时，改变订单路线可能是满足客户服务水平要求的唯一选择。战术计划的输出是战术时刻表，其中规定了将使用哪些车次、订单分配计划以及将增租多少列车（如有）。
2.3 运营规划
在列车延误显现之后，也就是在运营规划期间，对战术计划进行修改是有一定灵活性的，但修改的数量可能有限，而且通常成本较高。例如，如果火车线路中断，原定班次必然晚点，那么可以取消这些班次，将订单路线重新分配至其他地点，并用卡车将其转运至最终终点。协调这种最后一刻做出的决定相当复杂，取消班次的成本可能很高，而延误可能对前行班次产生的传播效应，会使取消列车服务和重新分配订单的决定变得更加困难。表1是与本文相关的文献综述。
表1. 多式联运特点综述
3.模型构建
3.1 基础模型
本文多式联运网络的设置是将客户的订单从一个起点运送到多个终点。起点和每个终点之间都有火车直达，每对终点之间也有卡车直达。多式联运承运商使用多种运输方式，将订单从出发地运往终点。他们为每种运输方式部署了自己的车队，因此可以在出现中断时重新安排订单路线。
初始模型（DLM）采用两阶段随机混合整数规划，其中订单路线重新分配和行程取消决策被视为追索。具体来说，第一阶段代表战术阶段，决策前往每个终点的列车行程和订单分配。第二阶段代表运营阶段，这一阶段存在延误的不确定性，此时不仅需要对订单路线重新分配，还可能在高额惩罚成本下取消行程。
初始模型决策变量如下：
模型如下：
目标函数公式（3）最小化所有随机情景下的额外列车租车费用、战略目标惩罚、预期卡车运输费用、预期列车行程取消费用和预期列车行程费用。约束可分为三类：第一类约束（4）和（5）是订单-目的地的对应约束 。第二类约束（6）-（12）包含了行程和订单分配约束、容量约束和时间窗约束。第三类约束（13）和（14）是服务水平约束。约束（15）-（20）是决策变量的定义域。
3.2 改进模型
上述模型的线性松弛有一个较弱的下界，因此本文通过引入辅助变量，用约束（22）代替约束（13）和（14），使模型的线性规划松弛更为严格，得到改进模型（IDLM）。
3.3 模型特例
尽管IDLM的线性松弛更加严格，但由于列车时段可用性、场景特定的订单分配和列车分配决策，以及客户服务要求之间的相互作用，使得模型难以求解。因此，本文考虑了一个特例模型-无限车厢模型（IWM）和对应的改进模型（IIWM），即起点有足够多的列车，该情况下不需要租用额外的列车，同时不需要推迟班次的发车时间，因为班次的中断不会影响到其他班次。因此，所有列车都会选择最早的时段出发，时间段集可以忽略。该特例和原始模型相比，不需要考虑时间维度，因此决策变量大量减少。因此，该模型得到的解可以作为IDLM的近似值，作为启发式算法的初始解。
受此启发，本文得到进一步简化模型-固定IDLM，将第一阶段的列车行程和订单分配分配决策固定，只允许为列车选择不同的可用时段。
此时模型的约束条件只剩下(6)、(10)和(22)仍然有效，其他约束可以忽略，因此模型可以很快求解。同时，还引入了半固定版本（semi fixed IDLM），即部分情景下x和y固定，其他情景下x和y需要优化求解。
4.算法设计
使用额外列车的成本很高，通常被视为其他成本总和的数量级。这导致解的质量呈现两极分化：如果固定 IDLM 求出的解不需要额外增加列车，这个解就接近最优；如果固定 IDLM 使用了额外列车，且存在另一个不使用额外列车的解，那么该解可能与最优解相去甚远。因此，若固定IDLM的解需要增加列车，本文使用三种不同的启发式算法对解进行改进。前两种分别是基于情景的启发式算法（SBH）和基于行程的启发式算法（TBH）。SBH跟踪每个场景需要的额外列车数，并衡量不同场景下的延迟时间来改进解。TBH固定行程决策，为订单路线分配决策实现完全的灵活性。第三种混合启发式将前两种启发式相结合。为了衡量算法的效率，本文使用了滚动优化算法和前三种启发式算法进行比较。
为了使用IIWM的易求解性质来求解IDLM，本文提出了启发式算法，该算法将 IIWM 的解作为 IDLM 的初始解，具体求解步骤如下：IIWM 的解，即列车行程安排和订单分配，将用于作为固定 IDLM的初始解；固定IDLM决策选中的列车在哪些时段出发，以及需要增加多少列车，并且增加时间维度。Dillenberger 等人（1994）和 Guzelsoy、Nemhauser 和 Savelsbergh（2013）的限制-松弛方法与本文的方法最为接近。感兴趣的读者，可以参阅相关文章以获取更多信息，在此不做赘述。
5.数值实验
本节就小规模、中规模和大规模的算例进行数值实验，重点结果如下：
DLM和IDLM以及IWM和IIWM在计算时间上的性能比较
表2. 四种模型的计算时间性能（秒）
从表2可以看出， IIWM 和 IDLM 均优于最初的 IWM 和 DLM。因此，本文在进一步的数值实验中使用了改进模型。
基于目标值和计算时间的启发式方法与 IDLM 精确解（Cplex）的性能比较
（i）自有列车数量充足
图2.启发式和最优值（IDLM）的差距小于或等于横轴值的实例百分比
图2显示了每种启发式在解质量上的差异，其中滚动优化和SBH的性能相似，但明显差于TBH和混合启发式，而混合启发式是性能最好的独立启发式。
（ii）自有列车可用性不足
图3.启发式和最优值（IDLM）的差距小于或等于横轴值的实例百分比
图3表明，混合启发式仍然是性能最好的方法，滚动优化、SBH 和 TBH 的性能相似，都不如混合启发式。因此，与有列车的情况相比，在最初没有列车的情况下，整合SBH和TBH的边际价值要高得多。
表3. 求解单个实例的平均计算时间
就解质量而言，混合启发式明显优于其他启发式算法。但是除了求解质量，另一个的衡量标准是求解时间，如表3所示。可以看出，IDLM 比启发式方法要慢。与其他启发式算法相比，混合式算法的速度较慢，但仍然明显快于 IDLM。在自有列车可用性不足的实例中，混合式算法的速度是 IDLM 的 10 倍。
启发式方法在较大实例上的计算时间和解决方案质量评估
表4. 启发式方法在大规模算例上的结果
结果表明，混合启发式的解质量始终优于其他启发式算法，SBH比其他启发式方法的求解速度快。
6.总结
参考文献
Joris Wagenaar, Ioannis Fragkos, Rob Zuidwijk (2021) Integrated Planning for Multimodal Networks with Disruptions and Customer Service Requirements. Transportation Science 55(1):196-221.
Dillenberger C, Escudero LF, Wollensak A, Zhang W (1994) On practical resource allocation for production planning and scheduling with period overlapping setups. Eur. J. Oper. Res. 75(2): 275–286.
Guzelsoy M, Nemhauser G, Savelsbergh M (2013) Restrict-and-relax search for 0-1 mixed-integer programs. EURO J. Comput. Optim. 1(1–2):201–218.
推荐阅读：
用于预测和健康管理的类ChatGPT大型基础模型：综述和路线图
虚拟断层扫描技术：基于机器学习支持测量的加工过程阶段分割新方法
一种用于动态工作条件下锂离子电池多状态估计的CNN-SAM-LSTM混合神经网络
