汽车物流运输方式及线路的优化设计

乔 睿1，张天昊2，陈 翔3

（长安大学汽车学院，陕西西安 710064）

作者简介：乔 睿（1990－），男，长安大学汽车学院硕士研究生，载运工具运用工程专业。

张天昊（1992－），男，长安大学汽车学院硕士研究生，载运工具运用工程专业。

陈 翔（1991－），男，长安大学汽车学院硕士研究生，载运工具运用工程专业。

摘 要：为解决汽车物流过程中运输方式和线路的组合优化问题，建立了以运输费用最小、运输时间最短、运输碳排放量最少为目标的数学模型，利用LINGO软件对模型进行准确性检验。在此基础上，编写了标准的以及改进的遗传算法程序，并用实际算例进行计算，得到了较为满意的运输方式与路线的优化方案。

关键词：汽车物流；运输方式选择；组合优化；遗传算法

Abstract：To solve the transport modes’and routes’combinatorial optimization problem of vehicle logistics process，a mathe－matical model which objective functions are the minimum cost of transport，the shortest transit time and the least carbon e－mission was established．Further，LINGO program was used to verify the accuracy of the built model．What’s more，age－netic algorithm for solving numerical example was designed with the help of MATLAB．A satisfactory optimization of trans－port modes and routes was obtained．

Key words：automobile logistics；transport modes selection；combinatorial optimization；genetic algorithm

1 引言

随着我国汽车产业的飞速发展，市场对于整车物流的需求日益增加。汽车物流在汽车产业链中起着桥梁和纽带的作用，是实现汽车产业价值流顺畅流动的重要环节和根本保障。而运输作为物流系统的核心部分，运输方式和运输路径的选择是运输环节的一项重要决策。运输方式和路线的合理选择有利于减少运输资源的浪费；有利于减少运输过程中碳排放量，实现环境的可持续发展；更有利于整个物流产业的良性发展。因此，为使汽车物流企业提高效率、降低成本，对物流运输方式和线路进行优化设计是一个非常有现实意义的课题。

如何选择运输方式及路线，国内外学者已进行相关研究。Athanasios［1］等探讨了联合运输系统中最短时间条件下的最佳路线问题，提出了时间约束条件下的多式联运系统最优路径算法。Boussediram［2］等选用双向研究策略解决综合运输网络问题，提出出发点和目的地之间运输时间最少条件下的最优路线算法。张建勇［3］等为了实现总成本最小的目标，构建了多式联运网络最优分配模型，以定量的方法分析了多式联运体系的合理架构。陈相东［4］研究了将运输方式与运输路线相结合的组合优化模型，并且编写了相应的遗传算法程序进行求解。

纵观上述研究文献，多是从时间或者成本最低为目标进行优化，本文将以运输费用最小、运输时间最短、运输碳排放量最少为目标建立数学模型，并实现算法。

2 问题描述

假设一个物流企业需要将一批物品从运输出发点O经过运输网络运送到目的地D，在任何有道路相通的城市节点之间都有m种运输方式可以选择，且两城市之间的不同种类的运输方式所对应的运输费用、时间、碳排放量都不相同。并且当物品在某城市节点由一种运输方式转换到另一种运输方式时，会发生一定的中转费用、中转时间和中转碳排放量。结合上述因素，需选定最佳的运输方式和路径，使运输总费用最低、运输总时间最短、运输产生的总碳排放量最少。

为了更直观的描述该问题，且更容易对模型进行求解，现构造运输节点扩展后的虚拟运输网络，具体步骤是：

（1）除起点O之外，其他每个节点城市均可以扩展为m个城市，其中每个城市分别代表一种不同的运输方式，最后虚拟一个运输终点D′，从D到D′的费用数据、时间数据、碳排放量数据均为0；

（2）由同一个城市扩展而来的节点之间不存在连接弧；

（3）每条弧上的数据分为三类：费用数据、时间数据、碳排放量数据；虚拟运输网络如图1所示。

图1 多式联运的虚拟运输网络

3 运输方式和路径选择模型

3．1 模型假设

结合问题的实际情况，对模型进行如下假设：

（1）确定的运输网络。即整个运输过程所经过的备选节点和备选路径已给出，只要对备选城市和运输方式进行选择即可。

（2）各类运输方式均能实现无缝转换，忽略因接驳过程不当引起的时间和费用的损失。

（3）整个物流过程只存在运输和中转环节，不考虑仓储和流通加工等环节；

（4）运量不能分割。即在运输过程中既不能存在两条运输线路，也不能存在一条运输线路有多种运输方式的情况。

（5）在每个城市节点，运输方式只能转换一次，不能由一种运输方式转换到另一种运输方式后再进行运输方式的转换。

（6）运输网络阶段化。即在备选城市节点之间，同一阶段和非相邻阶段的节点间不存在路径。

3．2 符号说明

M表示运输方式的集合，N表示运输网络阶段数，Ni第i阶段所有城市的集合； 分别表示在第i阶段的第j座城市到第i＋1阶段的第k座城市选择第p种运输方式的费用、时间和碳排放量；分别表示在第i阶段的第j座城市运输方式由p转换为q的中转费用、中转时间和中转碳排放量；α，β分别表示将时间和碳排放量转化为成本的价值系数；表示若为1，表示第i阶段j城市到第i＋1阶段k城市选择第p种方式，若为0，表示选择其他运输方式；表示若为1，表示在第i阶段的第j座城市运输方式由p转换为q，若为0，表示不发生转换。

3．3 模型建立

以运输过程中总费用最低、总时间最短、产生的总碳排放量最少为目标，进行建模。由于该模型是一个多目标优化模型，通常可将该问题转化成单目标优化问题进行求解。具体做法是将运输时间和运输碳排放量的量纲转化为费用。那么该模型就转变为求运输成本、时间成本、碳排放量成本之和最小的单目标优化问题。模型如下：

其中式（1）为目标函数，以运输过程总成本最小为目标；式（2）为运输总成本，包括运输成本和中转成本；式（3）为时间总成本，包括运输时间和中转时间；式（4）为碳排放总成本，包括运输碳排放量和中转碳排放量；式（5）表示运量不能分割。式（6）表示在每个阶段运输方式只能转换一次。式（7）保证了运输的连续性。式（8）表示均为0－1变量。

3．4 模型检验

运输方式和路径选择系统是一个涉及到多种运输方式和不同运输环境的复杂系统。为了模拟这类复杂的系统，研究人员所构建的运输网络模型均有一定的复杂性。因此，模型中有任何细小的错误，都有可能导致求解结果的错误，甚至无法求出最优解。在大多数相关论文中，作者主要阐述如何用所设计的算法求解模型，而往往忽视了对模型准确性的检验，这样可能导致其求解结果的不准确。所以，为保证所设计模型的正确性和为下阶段求解模型提供准确依据，将所构建的模型进行检验是十分必要的。

依据LINGO语言的编写规则，将本文中构建的模型转化为LINGO语言，在Windows7操作系统、2GB内存、2．20GHz的Intel CORE2处理器上应用LINGO11软件对模型进行检验，求解结果如图2所示：

图2 LINGO求解结果

从运行结果可以看出，本研究中构建的模型属于INLP（整数非线性规划），运行时间为1分28秒，最终结果为2231．87，解的状态为全局最优解，这说明本研究构建的运输模型是正确的。本文建立的运输方式路径选择模型属于整数非线性规划问题，当求解的规模比较小时，这类问题可以求得最优解，但当求解规模扩大时，软件的运行时间将以幂次方的速度增加，甚至求不出最优解，此问题属于NP问题［5］。因此，就需要用启发式算法来求解这种问题。

4 遗传算法设计

4．1 编码

编码方式的不同将影响遗传算法的结构，最直接的体现就是初始种群的生成。传统的二进制编码方式可能遇到欺骗性问题，而实数编码以其不受编码解码转换的限制，在运行效率和求解质量上逐渐显现其优势［6］。因此，本研究采用自然数编码，将运输网络分为N阶段，用N维向量X＝（x1，x2，x3，…，xn）表示一个染色体，其中每个元素表示染色体的一个基因，即虚拟的节点城市。

4．2 初始种群生成

本研究运用randint函数生成初始种群（randint表示生成设定范围内的自然数随机数），根据具体问题设定初始种群的规模，一般控制在10～200之间。

4．3 适应度函数编写

由于本文建立的模型的目标函数是最小化问题，为了方便求解，将适应度函数编写为模型的目标函数，并且应用ranking函数对个体的适应度函数值进行降序排序。

4．4 选择算子的编写

本研究采用轮盘赌的方法进行选择操作，用函数rws实现。轮盘赌方式是指种群中每一个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度之和的比值，个体的适应度值越大，被选中的可能性越大，进入下一代的几率就越大。

4．5 交叉算子编写

由于本研究采用的编码方式为自然数编码，因此采取两点交叉的方式进行交叉操作，用函数xovdp实现。交叉概率一般为0．4～0．9。两点交叉的具体过程是：首先在相互配对的两个染色体中随机设定两个交叉点，然后交换两个个体所设定的交叉点之间的部分染色体。交叉的实际意义就是改变所经过的路径。

4．6 变异算子的编写

由于本研究采用的编码方式为自然数编码，因此变异算子也应当为相应的实值均匀变异，用函数mutbga实现。变异一般的概率是0．01～0．1。均匀变异的具体过程是：首先依次指定染色体中每个基因座为变异点，然后对每个变异点，以变异概率从对应基因的取值范围内取以随机数来替代原有值。变异的实际意义是在某阶段随机改变经过的城市以及运输方式。

4．7 重插入函数编写

在种群繁殖过程中，若子代的种群个体数小于父代种群个体数，则子代种群和父代种群数目的差别被称为代沟。为保持原始种群的大小，一些新个体不得不重新插入旧的种群中，这种方法被称为重插入。为了使求解速度加快，Fogarty［7］已证明替代最小适应成员是一有效的优选策略工具，即将适应度小的成员用新的个体替代。本研究中采用reins函数实现重插入操作。

4．8 遗传算法的终止

因为遗传算法是随机搜索算法，找到一个正式的、明确的收敛性判别标准是很困难的。因此常用的方法是采用预先设定的遗传代数来终止运算。若没有可接受的解，遗传算法重新启动或用新的搜索初始条件。本研究设计的遗传算法的流程图如图3所示。

图3 设计的遗传算法流程图

4．9 遗传算法的改进

由于标准的遗传算法可能存在早熟的问题，为降低早熟概率，本文对设计的遗传算法进行一定改进。主要体现在改变选择算子和引入爬山操作。

因为轮盘赌操作主要基于适应度的大小来进行，那么适应度越大的个体保存下来的概率越大，也就容易陷入局部最优解。在此将选择算子改变为随机遍历抽样，用函数sus实现。随机遍历抽样采用随机等距的方法抽取个体，因此对于适应度值不同的个体，被抽取的概率相等，这样种群多样性得以保证。

由于遗传算法存在局部搜索能力差，已发生早熟的缺点。因此可以在遗传算法中加入爬山操作来扩大搜索的邻域。具体方法是：首先设定交换次数a，即在运算的最后a次进行爬山操作；其次在某个体中随机选择两个基因并互相交换位置，判断新个体的适应度函数值是否增加，若增加，则用新个体代替旧个体；最后重复上述操作直至达到预定的交换次数。

5 算例分析

5．1 算例数据

为求解基于遗传算法的运输方式和路径选择模型，本研究以安吉汽车物流南京到沈阳的整车运输为例，对这一运输网络进行运输方式和线路的优化。依据安吉运输网络中整车配送中心的位置以及可能经过的节点城市的地理位置以及交通运输条件，备选节点城市网络如图4所示。为表示方便，将各个节点城市依次编号为0～10，城市编号如图5所示：

图4 运输网络图

图5 运输节点城市编号示意图

各城市之间的采用不同的运输方式时所经过的距离也不相同，如表1所示（注：数据空格表示两节点之间没有该运输方式）。不同种运输方式所产生的费用、行驶的速度、产生的碳排放量也不尽相同，运输方式的特征参数如表2所示。在城市节点进行运输方式转换的中转成本、中转时间、中转碳排放量如表3所示。

表1 不同运输方式各城市之间的距离　单位（km）

表2 运输方式特征参数

表3 不同运输方式转换的数据

5．2 构造虚拟网络图

由于每个节点城市存在三种运输方式，将所有城市节点按照公路运输、铁路运输、水路运输的方式虚拟为三个节点。虚拟后每个节点城市只能通过一种运输方式进行运输。在虚拟运输网络中，虚拟后的城市节点顺序固定，且各虚拟城市之间不存在路径连接。具体的虚拟运输网络如图6所示。

图6 虚拟运输网络图

在虚拟网络图中，0点代表运输的起点南京， 1、2、3是由上海虚拟出的三个点，分别代表从南京以公路、铁路、水路方式到达上海。4、5、6分别代表从南京以公路、铁路、水路方式到达烟台。其他节点以此类推。28、29、30是由终点城市沈阳虚拟出的三个节点，最后一个节点31是虚拟出的终点，没有实际意义，并不参与计算。

5．3 运算结果

通过MATLAB7．0软件，应用遗传算法工具箱编写程序对模型进行求解。在遗传算法程序中，设定初始种群规模为100，最大遗传迭代次数为50代，设定种群代沟为0．9，遗传交叉概率为0．7，遗传变异概率为0．01。在Windows7操作系统、2GB内存、2．20GHz的Intel CORE2处理器上分别应用标准的遗传算法和改进的遗传算法进行求解，求解结果如图7、8所示。

图7 标准遗传算法运算50次后的结果

从图7、8可知，标准遗传算法种群在13代左右达到收敛，而改进的遗传算法在第7代左右就达到收敛，最后的求解结果二者相同。运输过程中所经过的节点城市为南京→烟台→大连→鞍山→沈阳，所采用的运输方式为公路运输→水路运输→铁路运输→铁路运输。本次运输的总成本为2231．9元／辆，其中运输成本为1689．7元／辆，运输时间为4．8d，运输产生的碳排放量为376．8kg／辆。

图8 改进的遗传算法运算50次后的结果

5．4 结果分析

将用遗传算法求解出的结果与LINGO求解出的结果进行比较，如表4所示。

表4 求解结果比较

从表4中的对比可以看出，遗传算法与LIN－GO求得的结果相同，仅在总成本上相差0．03元，这是与两种方法保留小数点的位数的不同有关。而由于LINGO求解的是全局最优解，所以两种遗传算法在本次计算中也得到了最优解，证明了算法的精确性很高。在求解时间上，LINGO所用时间为1分28秒，而标准遗传算法所用的时间为15秒左右，改进的遗传算法在10秒左右，说明算法的时间复杂度比LINGO求解低，因而求解效率大大增加。在算法稳定性方面，LINGO每次运算均可以得到上述最优解，而遗传算法由于是一种随机搜索算法，每次求出的结果可能会有很小的偏差，标准遗传算法结果稳定性大约在70％左右（运算了20次，其中14次取得最优结果）。改进的遗传算法求解结果稳定性大约在80％左右（运算了20次，其中16次取得最优结果）。

6 结论

在竞争日益激烈的汽车物流市场，选择合理的运输方式和路径对于第三方汽车物流企业降低成本、提升运输效率具有十分重要的意义。但多节点、多种运输方式和路径选择是一个NP—hard难题，使用传统的精确求解方法很难得出最优解。为了解决该难题，本文建立了以运输费用最小、运输时间最短、运输碳排放量最少为目标的数学模型，并利用改进的遗传算法进行求解。经过算例验证，并将改进的遗传算法与标准遗传算法和LINGO软件求得的结果进行比较，得出本文设计的改进的遗传算法求解精度很高，时间复杂度较低，求解稳定性较好。本研究对今后关于汽车物流运输方式和路径优化的研究具有一定的参考价值。

参考文献

［1］ Athanasios，Ziliaskopoulos，Whitney Wardell．．An intermodal optimum path algorithm for multimodal networks with dynamic are traveltimes and switching delays［J］．European Journal of Operational Research，2000，125（3）：486－502．

［2］ Boussedjram，Bloch C，Ei moudni A．An exact method to find the Intermodal Shortest Padl［C］．Tai Wan，China， 2004（2）：1075－1080．

［3］ 张建勇，郭耀煌．一种多式联运网络的最优分配模型研究［J］．铁道学报，2002，24（4）：114－116．

［4］ 陈相东，刘彦良，王鹏涛，宁培红．多种运输方式模型优化及求解［J］．天津师范大学报（自然科学版），2005，25（03）．

［5］ 吕凯．面向多式联运的运输优化研究［D］．北京交通大学硕士学位论文．2008．

［6］ 玄光男，程润伟．遗传算法与工程优化［M］．北京．清华大学出版社．2004．

［7］ 雷英杰．MATLAB遗传算法工具箱及应用［M］．西安．西安电子科技大学出版社．2004．