基于遗传算法的广西集装箱多式联运运输优化研究

申慧芝　经素萍　黄睿伶

【摘 要】集装箱多式联运作为一种新型多式联运方式，将多式联运和集装箱有效地结合在一起，与传统的运输方式相比更安全、更灵活、更有效，正是这些特点使得近几十年来集装箱多式联运快速发展，然而如何优化集装箱多式联运，有效地协调各种运输方式，降低运输成本，提高运输效率，成为集装箱多式联运的有效研究课题。

【关键词】遗传算法；集装箱；多式联运；运输优化

0 引言

随着全球经济一体化进程的加快，产业供应链变得越来越复杂，运输网络变得越来越广泛，货物运输需求也发生了变化——以顾客需求为中心的方便、快捷、高效、低价的货物运输已成为必然趋势，单一的集装箱运输模式已经不能满足当今全球供应链管理的发展要求，因此，以货物运输为主的集装箱多式联运在全球范围内得到了广泛的认可与使用，创建高效的集装箱多式联运模式也已成为各国经济可持续发展的关键因素之一。

集装箱多式联运的发展是建立在完善的综合运输体系之上的。然而，长期以来广西的交通运输已成为其经济发展的瓶颈，由于基础设施不完善，没有一个统一的综合运输统筹部门，各种运输方式没有真正发挥组合优化的作用，通畅的、安全的、便捷的集装箱多式联运网络尚未建立。因此，本文希望通过分析广西集装箱多式联运存在的问题，以广西集装箱多式联运系统内各运输方式与运输路径实现最优化组合为目标，为广西集装箱多式联运的发展提供参考和理论指导。

1 遗传算法的原理及优化模型的建立和实现

1.1 遗传算法的原理

遗传算法简称GA（Genetic Algorithm），在本质上是一种不依赖具体问题的直接搜索方法。遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说，Darwin进化论最重要的是适者生存原理：它认为每一物种在发展中会越来越适应环境，物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体才能保留下来。Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在于细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质，所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。

下图是遗传算法的运算过程图：

基于上述思路，在应用上设计多式联运最优路径求解的步骤。将数据随机置于起始点，对每条路线按照多个起始点计算其运输费用。

1.2 优化模型的建立和实现

（1）根据集装箱多式联运运输资源配置的分析可知，该问题属于非线性约束组合问题，即使问题规模较小时也难以解决，随着规模的增大，解决问题的复杂度也增大。近几年来随着仿真优化方法研究的逐渐完善，Tabu算法越来越多应用到仿真模型优化中，该算法具有大量随机参数的组合优化问题等特点。

（2）運用仿真优化方法，结合仿真模型算法的特点对系统资源配置协调优化问题进行求解，通过运行仿真模型得到相应的评价指标，在满足约束条件的基础上，对仿真方案进行不断的矫正，最后得出较优的运输方案。

（3）优化模块。主要通过遗传算法算出问题的最优解，根据具体的目标，采用科学算法，搜索仿真模型的最优解，并对其进行优化组合。

2 基于遗传算法的广西集装箱多式联运运输优化实例分析

2.1 问题假设

假设某多式联运经营人准备建立和开发一条由广西柳州（O）至广西钦州（D）的集装箱多式联运路线，中途可选择若干个（n个）城市作为中间节点，任意相邻的两个城市之间都有若干种（g种）运输方式可供选择，在相邻的两个城市之间各种运输方式的运输时间、运费、运输能力不同，当从一种运输方式转换到另一种运输方式时，需要一定的中转时间和中转费用，而且在整个运输过程中的总时间不能超过运输期限（T），在考虑上述各种因素的前提下确定最佳的运输路线和组合方式，使得总运费和总运输时间为最少。

为了对问题进行有效的求解，参考Spiess和Florian提出的多式联运的优化算法，本文将每一个城市到另一个城市的每一种运输方式都单独作为一条运输路线加入到运输网络中。即如图2城市1到城市2是连通的，我们用一条有向箭头表示城市1到城市2之间连通，但实际城市1到城市2共有三种运输方式可行，所以将图2进行改进后成为了图3，两种从城市1到达城市2的运输方式成为了三条可选的运输路线。这样就可以将这个多式联运运输优化问题转化成一个最短路问题。

2.2 优化模型的建立

针对最短路问题的特点先对模型作以下假设：

（1）运量在某两个城市之间不能分割，即在某两个特定的城市之间，只能选择一种运输方式；

（2）运输成本与距离成线性关系。

为了建立模型用有向图G（N，A）来代表多式联运的运输网络图，其中N表示结点集合，A表示边集合，N表示G图的结点总个数。C=[Cijk]表示图G的邻接权矩阵——即运输费用矩阵，k={1，2，3}代表三种可行的运输方式，其中T=[tijk]表示第二邻接权矩阵——即运输时间矩阵，当城市i、j没有任何方式相邻的时候：Cijk=tijk=N（N为一非常大的正整数）。始点与终点分别以O和D来表示。Ii表示节点i是否被选择到运输路线中。Ii=1代表节点被选取到运输路线中，0代表没有被选取。Wijk等于I（i）与I（j）相与，即I（i）与I（j）是否以第k种运输方式被选入到运输路线中，当I（i）&I（j）=1时，Wijk=1；当I（i）&I（i）=0时，Wijk=N，即节点i， j之间没有被选择作为运输路线。

2.3 优化模型的求解算法

基于上面的问题模型可以看出这个问题是一个NP难题，很难得到全局最优解或满意解，如用改进的遗传算法对其进行求解，能取得较好的效果[i]。在用遗传算法对该模型进行求解时主要要进行下面几项工作。endprint

（1）确定个体的编码方式：对于遗传算法来说，它的可行解由个体来表示，主要在个体之间中进行交叉、变异的操作生成新的个体，直到得到合乎条件的个体为止。所以如何决定个体的编码方式，对问题的求解速度、误码率、最优解的范围都有很大影响。拿一个8城市3种运输方式的运输网络来说，染色体长度就是8x（8+1）=72，其中城市选取用0-1来代表节点是否被选中，而运输方式的选取用1-3的自然数编码来表示。

（2）确定初始群体：若干个染色体或个体组成的一组向量称为一个群体，遗传算法计算的第一步首先要确定一个初始群体，在此基础上才可以进行之后的遗传进化过程。初始群体的选择应该具有较为广泛的代表性，并且要有足够多的染色体（个体），否则有可能陷人局部最优解而出现早熟现象。论文的染色体生产的方式是随机生成大部分染色体，再在群体中加入一部分可行解染色体，作为初始群体。

（3）确定适应度函数：在遗传算法中用适应度函数来表明个体和解的优劣性，用来确定个体遗传到下一带的概率，适应度越高的个体遗传到下代的概率就越高，这样就保证了个体向最优解的方向发展。本文直接用目标函数作为适应度函数，即f（x）=z（x）。同时为了防止在计算早期出现个别特殊个体，用以下方式对适应度函数其中f是原适应度函数，f'是标定后的适应度函数，fmax、fmin分别是按照实际问题的一个估计值，δ为一个0到1之间的正实数。

（4）确定交叉和变异规则：交叉是指种群中确定的染色体做为父代，通过一定规则产生子代染色体的过程，这一过程所遵循的规则称为交叉规则。这里我们采用两点交叉法，在这种方法中，在亲代中选择好两个染色体，随机产生两个点，作为交叉点，然后将两个染色体中两个交叉点之间的对应信息码相交换得到两个子代的染色体。然而，经过该操作后，新产生的后代不一定符合约束条件，所以还要对产生的新个体进行检验，如果不符合约束条件，还要重新进行交叉，直到满足约束条件为止。

3 总结

由以上的分析可以看出，集装箱多式联运运输方式组合优化模型在成本最小的前提下，通过遗传算法和计算机编程的运用，可以较方便地求出最优解。在多式联运运输下，以运输系统收益最大为目标，设计与遗传算法相结合的组合算法对模型进行求解。在集装箱多式联运运输总成本最小化的基础上，通过对各种费用和时间的分析，为多式联运企业选择最优运输路径，也为广西集装箱多式联运运输方式合理安排提供了一定的依据。

【参考文献】

[1]倪呈英.浅析我国集装箱多式联运现状[J].物流工程与管理，2016，38（08）：88-89.

[2]潘常虹，范厚明.集装箱多式联运系统的Petri网建模及其性能分析[J].铁道运输与经济，2015，37（03）：59-63.

[3]周跃.集装箱多式联运运输决策与协调问题的研究[D].南京：河海大學，2006.

[4]张得志，凌春雨.多种运输方式的组合优化模型及求解算法[J].长沙铁道学院学报，2002.

[5]井祥鹤，魏冬峰，周献忠.运输方式选择多目标优化问题混合遗传算法[J].计算机工程与应用，2008（6）：210-214.

[6]康凯，牛海娇，朱越杰，张维存.多式联运中运输方式与运输路径集成优化模型研究[J].计算机应用研究，2010.endprint