基于遗传算法的国际多式联运路径优化研究

路 婷 （郑州工商学院 信息工程学院，河南 郑州 451400）

0 引 言

与传统的单一运输方式相比，多式联运可以发挥各种运输方式的优势，使货物运输更加经济、灵活，因此多式联运的路径优化问题也受到了越来越多的关注[1]。文章建立了智能物流网络问题的数学模型，并用约束方法求解，研究了道路拥挤条件下不同碳排放政策对多式联运路线选择的影响，研究了在货物需求不同时多式联运路线的优化问题。郑强提出了一种带精英策略的非支配排序遗传算法的研究与应用[2]，并设计了一种多信息密集算法来解决多式运输路径优化的问题。雷定猷等建立了多式运输路径再利用规划模型，解决了大宗货物收益投资比最大化的问题[3]。刘学之等建立了一个考虑客户服务时间窗口的包含环境成本的多式运输模型并求解[4]。雷异考虑了时间表对多式运输路线选择的影响，所以将所有中转节点的时间表都设成相同的[5]。

在现实生活中，铁路运输和水路运输通常都有固定的时间表，一旦错过，就要等待下一次发车时间。在不同的城市之间使用不同的交通方式可能会有不同的时间表。因此，本文将建立一个在相同时间限制下的多式运输路线优化模型。考虑到智能算法在这类问题中的优越性，设计了一种具有保存策略和转移策略的遗传算法来求解该模型。

多式联运系统的目的是提供各种出行方式。如何在这些出行方式之间做出明智的选择，或者将某些出行方式结合起来，正成为一个棘手的问题。多模式路线被定义为包含两种或两种以上不同模式的路线，不同出行方式的自由组合是其本质特征。然而，很少有研究专注于此。出于自由组合的考虑，战略驱动的时间消耗已经接近于一个硬负担。如何以最小的计算代价组合不同模式，以满足出行者的个性化需求是多联式最优路径规划的瓶颈。

将路径规划问题归为一个优化问题，目的是在确定需求下提供可行路径。在单一标准时代(最短路问题)，该算法被认为是一种有代表性的解决方案，是一种精确的算法。然而，现实世界中的优化问题很难用一个标准、一个结果来表示。在考虑多准则时，经常会出现冲突，即一个准则的改进可能导致另一个准则的恶化，精确的算法也无法很好地处理这种冲突。由于遗传算法同时处理一组解，并且在一个过程中有多个不同的解，因此它是处理多准则优化问题的一种有效算法。在多模式旅行环境中，利用具有多个部分的变长染色体(子染色体)来表征各个部分所描述的一种运输方式。在单模式下重新定义了交叉和变异算子，将超交叉和超变异两种新算子定义为模式间操作。在选择最优解时，可以采用具有支配概念的代表多个准则的p维向量。

本文的结构组织如下：首先介绍相关工作，其次描述了所关注问题，然后介绍一种多模态网络模型，接着提出了一种改进的多准则路径规划方法，并给出了实验和结果，最后归纳出结论。

1 问题描述和模型建立

1.1 问题描述

在起始城市有一批货物需要在规定时间内运送到目的地城市。中心城市为多节点城市，各城市之间的公路、水路、铁路至少有一种交通方式。当选择公路运输时，可以直接离开。但是当选择铁路运输和水路运输时，发车时间受到固定时间表的限制。以总运输成本最小为目标确定多式联运方案，假设条件如下: 货物在运输过程中不能分离；运输方式的转换只发生在节点城市，转运作业在到达城市后立即开始；不同运输方式的速度和成本在不同的城市之间是相同的。

1.2 优化模式有时间限制的多式运输路线优化模式

目标函数(1)最小化总成本，包括运输成本、运输成本、等待成本和碳排放成本。

约束(2)意味着任意两个节点最多只能通过一种运输方式进行运输。约束(3)意味着在任意一个节点只能进行一种运输方式的转换。约束(4)表示节点货流平衡，起点城市为o，目的地城市为d。约束(1)意味着节点i处的货物进入运输方式k，当货物离开运输方式l 时，运输方式转换发生在节点i，保证了运输方式的连续性。约束(2)表示使用运输方式k在不同城市之间的运输时间。约束(3)表示货物在节点i等待中转的时间。它意味着如果货物比中转操作时间早到达节点i，将支付等待费用。约束(4)表示货物在节点完成过境操作时等待运输方式l 离开的时间。约束(1)表示货物的总运输时间。货物离开一个节点转移到下一个节点的时间包括运输时间、等待转运时间、转运时间和装货后等待离开的时间。约束条件(2)以确保货物在规定的时间窗口内运送到目的地城市d。约束(3)意味着决策变量是0～1 个变量。

2 设计算法

多式运输路径最佳化问题是一个难题，可以用智能算法来解决。遗传算法具有良好的全局搜索能力，在求解该问题时更加方便。因此，本文将采用遗传算法对上述模型进行求解。与传统的遗传算法相比，在算法设计中采用了保持策略和转移策略。保持策略可以确保种群中的优势个体能够在下一代继续存在，从而使整个优化过程朝着更好的方向发展。转移策略可以保证人口的多样性，避免过早地陷入局部最优解。具体的设计思路如下。

2.1 多式联运路径优化组合

考虑到多式联运路径优化问题是一个组合优化的问题，运输路径和运输方式的选择会影响结果，因此采用双层编码结构，两者均为实数编码。第一层是运输路径的编码，长度是n，第二层是运输方式的编码，长度是n-1。这两部分的代码共同形成一个完整的染色体代码，如下所示。

在解码时，代码的第一部分表示货物依次通过的节点数，代码的第二部分表示相邻节点之间选择的运输方式。应注意的是，编码中目标城市d后面的节点都是无效节点，因此只有前面的节点会被解码。

2.2 交通路线生成初始种群

第一个数字固定为1，表示出发城市，然后对剩余的节点进行随机排序。在交通方式方面，根据邻近城市之间可以选择的交通方式随机生成一个数字，目的地城市之后的数字均为0。根据上述原则，生成初始个体，直到满足人口数量的要求。

2.3 计算适应度

由于本文所寻求的是最小化问题，并且在后续的选择算子中采用了取大原则，因此每个个体所计算的总成本的倒数被作为适应度。此外，为了确保货物按时交付，在到达时间窗口之外的计划目标值过程中增加了足够大的罚金值。这意味着货物不能早于或晚于指定的时间段到达。

2.4 基因操作

新的种群将来自三个部分。首先，根据初始种群中的个体数、保存率、转移率和遗传比确定每个新种群中的个体数。然后选择亲本群体中适合度较高的个体获得第一个群体g1。根据先前的原理，产生一定数量的新群体，形成第二个种群g2。新群体经过选择、杂交和突变，形成第三个群体g3。选择运算符使用选择的轮盘赌方法，交叉计算采用单点交叉法。变异运算符使用两点交换变异。在新种群中会产生一些不可行个体，最后利用修正算子对不可行个体的运输方式编码进行修改，使其可行。当达到指定的迭代次数时，输出当前最优个体的目标值，算法结束。

3 案例研究

有20 吨的货物将从起点城市被运输到到目的地城市，并使用一个20 英尺的集装箱。中间有9 个节点城市。随机生成城市之间的距离和水路、铁路运输的时间表。碳排放成本为0.1 元/公斤，接收时间窗口为h/TEU，其他的相关参数值见表1和表2。

表1 各种运输方式有关参数值

表2 转运有关参数值

根据已建立的多式运输路线优化模型，采用保存策略和转移策略的遗传算法，通过matlab2016b 软件编程求解。遗传算法的相关参数为: 种群大小为100，迭代次数为500，保存率为0.1，转移率为0.1，遗传比为0.8，交叉概率为0.8，变异概率为0.5。计算结果如下: 运输路线为1(o) -9-10-11(d)，运输方式为铁路-公路-铁路，总运输成本为6 722.328 元，总运输时间为54.216 7 小时。

为了验证出发时间是否会影响运输计划的选择，接下来将选择不同的出发时间进行计算。计算结果见表2。可以看到，当出发时间发生变化时，交通方案的选择也会发生变化。因此，适当提前起飞时间可以有效地降低运输成本。

4 结 论

制定合理的多式运输计划是发挥多式联运优势的关键。本文建立的多式运输路线优化模型考虑了固定时间表对运输时间和运输成本的影响，因此更加实用。经过大量的计算和测试，本文设计的遗传算法能够有效避免陷入局部最优解，并能够快速得到结果，从而证明算法的可行性，为多式运输运营商制定运输方案提供了有用的参考。

多式联运规划的目的是为出行者提供最优的、可行的和个性化的出发点和目的地之间的路径，这会涉及公共和私人出行方式。对此提出了一种改进的多模型、多准则环境下的航路规划方法，在单模型下重新定义了交叉和变异算法，将超交叉和变异定义为模型操作。针对不同的需求，采用基于向量的评价方法来表示多个指标，通过应用遗传算法，给出最优解，该方法实现了旅行模式与各种个体需求之间的自由组合，操作简单，且智能化程度较高。在多模型网络的基础上进行了一个实验，研究结果表明，多种模式组合能够适应不同情况，结果符合目标，为了改进非唯一解的演化运算，今后需要研究多目标优化的问题。目前的遗传算法是有用的，不过需要大量的运行时间。但是，研究中仍然存在一些不足之处，如没有考虑进度、延迟等不确定因素，这些将是未来进一步研究的主题。