基于三部分遗传算法的多目标出港列车装载优化研究

《IEEE Transactions on Intelligent Transportation Systems》：Three-Part Genetic Algorithm to Optimize the Outbound Train Using a Multi-Objective Approach

本研究针对干港出港列车装载中的效率低下问题，开发了一种结合ε-约束方法的三部分遗传算法（TPGA2）。该研究同时优化了高优先级集装箱装载、列车容量最大化以及装卸机械行驶距离最小化三个目标。在三种复杂度递增的场景测试中，TPGA2均优于12种启发式方法，在最具现实性的场景下实现了至少98.6%的列车利用率，并将装载距离减少了7%，预计每年可节省9049.41欧元。这项工作为铁路物流运营提供了高效的决策支持工具。

　　

在全球化贸易的推动下，集装箱化货运量持续增长，干港作为连接海港与内陆的关键节点，其运营效率至关重要。铁路运输以其大运量、长距离的优势，成为干港物流体系中不可或缺的一环。然而，出港列车的装载过程却面临着诸多挑战：高优先级集装箱未能及时装车可能导致错过船舶离港截止日期，严重影响终端竞争力；列车容量未充分利用会造成存储区域拥堵，降低物流效率；此外，用于集装箱搬运的机械（如集装箱堆高机）燃料消耗高，不仅带来巨大的运营成本，还加剧了温室气体排放。传统的装载方法往往依赖于人工经验，难以在复杂的约束条件下实现多目标协同优化。

为了系统解决上述问题，来自科英布拉大学和Fordesi的研究团队在《IEEE Transactions on Intelligent Transportation Systems》上发表了他们的最新研究成果。该研究聚焦于Wagon-Container Assignment Problem (WCAP)的一个高级变体，旨在通过一种新颖的优化方法提升干港出港列车装载的效率。研究人员设定三个核心优化目标：优先装载高优先级集装箱、最大化列车容量利用率以及最小化装卸机械的总行驶距离。

为实现这些目标，研究团队采用了多目标优化方法。他们首先对问题进行了形式化定义，考虑了集装箱的尺寸（C_size）和优先级（C_prio），以及货车的容量（W_cap）等约束条件。在此基础上，他们改进了之前提出的三部分遗传算法（Three-Part Genetic Algorithm, TPGA），开发出了TPGA2版本。TPGA2的核心创新在于其染色体表示方法和适应度函数。染色体由三部分组成：集装箱序列、货车序列以及用于划分多车辆路径的断点序列。这种表示方法能够有效编码复杂的装载方案。为了处理多目标之间的权衡，研究人员将TPGA2与ε-约束方法（ε-constraint method）相结合，从而生成一组非支配解（non-dominated solutions），为决策者提供多种帕累托最优方案选择。

研究的关键技术方法主要包括：1) 构建了基于真实运营数据的数据集，包含6列具有不同配置的出港列车信息；2) 设计了12种启发式算法作为基准对比，模拟终端工作人员的决策逻辑；3) 实现了TPGA2算法，包括其特有的交叉（采用IPMX方法）和变异（采用交换变异和翻转变异）操作；4) 应用ε-约束方法对解空间进行修剪，聚焦于满足终端工作人员核心关切（即近乎满载且优先装载高优先级集装箱）的解决方案。

问题定义与数学模型

研究对WCAP问题给出了明确的数学定义。模型包含多个集合和参数，如货车集合W、集装箱集合C、车辆集合V等。决策变量包括x_i,j（表示集装箱c_j是否分配给货车w_i）、z_p,j（表示集装箱c_j是否分配给车辆v_p）等。模型受到多种约束条件的限制，例如每个货车的装载量不能超过其容量（公式1），每个集装箱最多分配给一个货车（公式2）等。三个优化目标分别为：最小化总剩余容量（公式11，等价于最大化利用率）、最小化总行驶距离（公式12）和最小化总优先级数值（公式13，数值越低优先级越高）。

三部分遗传算法（TPGA2）的设计

TPGA2的染色体结构是其独特之处。第一部分是集装箱序列，第二部分是货车序列（每个货车的基因数量等于其以TEU为单位的容量），第三部分是断点序列。这种设计确保了解决方案的可行性。交叉和变异操作分别作用于这三个部分，例如对集装箱和货车序列使用顺序交叉（OX），对断点序列使用单点交叉。适应度函数（公式1）综合了三个目标，但只有当剩余空间（Total Capacity）或优先级浪费（Total Priority）超过预设阈值（ε₁和ε₂）时，相应的惩罚项才会被加入适应度值中，这得益于ε-约束方法的引入。

模型评估与实验结果

研究设计了两个复杂度递增的场景进行评估。场景一（静态输入与动态变量）假设所有集装箱都能装入列车且优先级相同。场景二（动态输入与动态变量）则更为现实，集装箱可能无法全部装车，且具有不同的优先级。

实验结果表明，TPGA2在两种场景下均显著优于所有12种启发式方法。在场景一中，TPGA2生成的帕累托解集支配了所有启发式解。例如，对于列车1，TPGA2在装载所有集装箱并达到91.5%空间利用率的同时，将行驶距离从最佳启发式方法（Heur5）的19291.4米降低到18138.3米。在更具挑战性的场景二中，TPGA2同样表现优异，其解集始终能提供在优先级和空间利用率上不劣于、在行驶距离上更优的解决方案。特别是在列车4这种集装箱数量远超过列车容量的极端情况下，TPGA2依然能有效找到高质量的解决方案，而多数启发式方法则难以找到符合条件的可行解。在所有测试中，TPGA2都能实现满载或接近满载（至少98.6%的利用率），并确保优先装载最紧急的集装箱。

研究结论与意义

本研究成功扩展了WCAP问题，首次将集装箱优先级、列车容量最大化以及行驶距离最小化三个目标同时纳入优化框架。改进后的TPGA2算法结合ε-约束方法，能够为决策者提供一系列高质量的帕累托最优解，这些解充分考虑了终端运营的实际需求：即优先保证高优先级集装箱的装运和列车的高利用率。与模拟人工经验的启发式方法相比，TPGA2在实现相同甚至更优装载效果的前提下，平均减少了7%的机械行驶距离。根据研究估算，这一效率提升在现实运营中可转化为每年约9049.41欧元的成本节约，这还未考虑因避免集装箱翻倒（Container Reshuffling）和实际路径更复杂可能带来的更大潜在收益。

该研究的实际意义重大。研究成果已经通过API（Application Programming Interface）集成到测试终端的终端操作系统（Terminal Operating System, TOS）中进行实地测试，展现出直接应用于生产环境的潜力。它不仅为干港和铁路物流运营提供了一种强大的智能化决策支持工具，有助于提升运营效率、降低成本和减少环境影响，而且所提出的TPGA2框架和ε-约束方法的应用也为解决其他复杂的物流优化问题提供了有价值的参考。未来工作方向包括在多车辆环境下进一步测试算法、深入研究优先级约束值的影响，以及考虑与集装箱翻倒问题（Container Reshuffling Problem, CRP）集成，以构建更全面的优化模型。