整车智能调度运输研究*

□ 李董洁，梁革英

(广西大学 数学与信息科学学院，广西 南宁 530004)

1 引言

为解决销售给客户的汽车里程表为零公里的要求，就要求汽车生产企业将汽车直接运输到指定的销售地点。由于汽车企业运输的车辆变多、地点变多，手工分派不能满足企业运输的需求，需要使用计算机智能选择整车运输路径。整车的运输方案影响着企业的利益和顾客对企业的满意度，如何选择合适的运输路径是整车运输的核心问题，合理的路径安排不仅可以降低运输成本，还可以提高顾客对企业的满意度。因此，本文在平衡运输成本与运输时间的情况下建立运输模型。

目前在整车调度运输以及物流配送方面已有不少文献，大多数研究中采用遗传算法、蚁群算法、遗传算法以及Dijkstra算法来进行求解路径优化问题。这些经典算法本身存在一定的缺陷，如遗传算法存在易出现局部收敛且当问题较为复杂时需要进行大量计算；蚁群算法存在收敛速度慢及易出现局部最优的问题；而粒子群法相比遗传算法具有算法简单，收敛速度快的优点，但也存在着陷入局部最优解的可能。因而，不少人在研究时都对传统的算法做了改进。

如陈磊提出使用混合遗传算法来解决物流配送问题，建立满足客户需求的同时使得运输费用最少模型[1]；刘娜翠等通过使用改进的遗传算法求解以费用最小为目的的带时间窗的整车物流配送问题[2]；袁彬等提出了一种基于改进Dijkstra的物流网络路径优化模型[3]；徐鹏等提出Dijkstra算法在GIS中的优化与应用[17]；刘臣宇等使用Dijkstra算法通过对目的点标号的形式解决直送式配送问题[4]；姜辰凯等提出通过改进Dijkstra算法解决无碰撞路径规划问题[5]。1995年,美国学者Kennedy J与Eberhart R共同提出了粒子群算法[6]。有不少学者应用粒子群算法解决路径选择问题，并对传统算法改进：如Shi Y等在论文中基于粒子群算法引入惯性权重的概念，并且指出惯性权重取0.9-1.2是合适的[7]；Shi Y等还提出了线性递减惯性权重LDIW(Linear Decreasing Inertia Weight)[8];毛开富等考虑调节非对称学习因子对粒子群算法的影响，确定使用c1=2.5-0.5,c2=1.0-2.25的非对称调节因子对粒子群算法有明显的改进[9]。李宁等提出使用粒子群算法来解决车辆路径问题，并且验证粒子群算法(PSO)在应用于VRP(vehicle routing problem,VRP)问题时有着运算速度快、鲁棒性好等优点[10]；李宁等还提出了带时间窗车辆路径问题的粒子群算法[11]。张丹露、黄向红提出通过改进蚁群算法来解决VRP问题[12]。刘娜等通过改进惯性权重来改进粒子群算法从而求解质押物配送路径问题[13]。为提高企业的竞争力，在求解路径规划问题时结合实际，既要尽可能地满足客户的需求，又要考虑降低运输费用减少企业开支。如，蔡鉴明、吴松城提出对整车物流运输网络进行研究时还需要考虑碳税政策对运输路径选择的影响[14]；杨树国、李春霞通过使轿车运能最大化求出相应的配载模式，与实际相结合，解决整车物流配送优化问题[15]；张庆莹在考虑了各方主体利益、货源紧急程度以及运力资源的利用率三个因素建立了考虑货源时间窗的整车运力资源选择模型[16]。

2 研究思路

为解决汽车制造企业整车运输的问题，根据整车运输的特点将整车运输过程分成两段：一段是跨省的长距离运输，即从生产厂家运输到销售商所在省的中转仓库；另一段是省内的短距离配送运输，即从中转库运输到销售商的销售点。一般物流的运输方式有四种：水路运输、铁路运输、公路运输以及航空运输。因为航空运输的成本较高且运输能力有限，故一般整车调度运输不采用航空运输。对于跨省的长距离运输，运输方式主要有三种方式：水路运输、铁路运输和公路运输[13]。而对于省内城市之间的运输，由于目前在全国各地省内的高速路网已完善，时间与效率能满足客户对整车运输的要求，成本在可控的范围内，所以省内运输一般通过公路运输到指定的销售网点。

对于长距离的跨省运输部分：建立可以根据订单的紧急程度来考虑运输费用还是运输时间作为影响路径的绝对因素的路径选择模型，由于Dijkstra算法可以针对有向图求解最短路径且可以根据订单紧急程度改变路径权值，算法成熟且具有简单、运算快和更易于找到满意解的优点，因此本文针对长距离的跨省运输部分采用Dijkstra算法求解最优路径方案。

对于短距离的省内运输部分：在考虑汽车企业本身利益的情况下，为提高顾客对汽车企业的满意度，求解的路径结果应满足顾客对整车运达时间的期望，因此本文将VRP问题转化为VRPTW(VRP with Time Windows)问题，即建立以总运输费用最少且带时间窗的整车运输路径模型。由于粒子群算法相比于遗传算法更易于收敛于最优解且粒子群算法相较于遗传算法和蚁群算法更为简单，故本文粒子群算法来求解该模型并通过对粒子群算法改进从而克服其易陷入局部最优解的问题。

为实现上述目标，根据运输的特征建立两段路径模型：第一段，由仓库运输到各省份相应的中转库(也可以称为配送中心)；第二段，由中转库运送到经销商。如图1整车调度运输网络所示。

图1 整车调度运输网络

3 模型建立

3.1 全局假设

在公路运输过程中没有运输意外发生，如车祸、堵车等，且在运输中为了保证运输时间，在派送前将选择路况良好(通行车辆少)的时间段。

3.2 第一段模型

每条路径根据实际情况选择水路、公路或者铁路。

迪杰斯特拉算法(Dijkstra)是一种用于求解带权有向图中的最短路径问题的经典算法。最短路径是指从源点到达终点一条路径上所有经过边的权值之和最小的路径[18]。根据任务的紧急程度或费用优先相应地将权值定为经过这条边所需的时间或所花费的费用，利用Dijkstra算法求出花费时间成本最小、费用最少的最短路径。因此根据实际应用写出对应的邻接矩阵是关键。

第一段的运输路径选择可以按以下方式进行：

①根据订单的紧急程度进行规则选择，若为紧急订单，使用以时间作为路径权重的运输规则；若为非紧急订单，使用以费用作为路径权重的运输规则。

②确定运输规则后，依据运输成本(运输时间)为权值建立相应的运输成本(运输时间)的邻接矩阵。设S为出发点也可以将S称为源点(S中包含{s})，源点到源点的最短路径为0。设N为终点，除源点以外的点都设为目的地包含在t(t中包含{j=1,2,…}以及终点N)中，若两点之间存在路径，两点间的距离设为相应的权值(注意方向)，若两点间无法到达则将邻边距离设为∞。

③使用Dijkstra算法计算出所需费用(运输时间)最少的路径。

a.从t中找到与出发点s距离(此距离指代相应路径权值)最小的目的地t，把t加入到S中。

b.将加入S的t考虑为新的出发点，修改t中各顶点j的最短距离值(即权值)。

c.重复上述步骤二和步骤三，直至得出最终结果。

④如果是计算路径，利用公式成本=每公里变动运输费用×路径长度+固定运输费用，得到第一段的成本。

具体实现流程图如图 2所示。

图2 具体步骤流程图

3.3 第二段模型

3.3.1 第二段模型的假设

①运输路径上各经销商的整车需求的总重不超过运输车辆的额定载重量。

②运输车辆最后会回到中转库。

③每一个经销商只能由一辆运输车进行配送。

④每一辆运输车的行驶总里程小于其单次运输车辆的最大里程。

⑤每次运输的车辆为同一款车系。

3.3.2 符号说明

构建第二段模型所需要用到的符号如表1符号说明所示。

表1 符号说明

3.3.3 第二段路径计算

构建第二段模型是为了解决整车从配送中心到达省内各地经销商的问题，除了要考虑整车的运输费用外，还需考虑经销商对接收整车的时间区间的期望。因此建立以总整车配送费用最小为目标建立含有时间窗的运输总成本按以下方式计算[2]：

(1)

公式(1)有以下约束条件：

(2)

(3)

(4)

(5)

Etj≤Sj≤Ltj

(6)

xijn∈{0,1}i,j=0,1,…,M;n=1,2,…,N

(7)

yin∈{0,1}i=0,1,…,M;n=1,2,…,N

(8)

根据实际运输情况，做如下定义：

式(1)为目标函数；式(2)表示运输车辆上装载的货物量不超过运输车的额定载货量；式(3)表示经销商由特定车辆进行配送；式(4)与(5)表示运输车辆的运输方向是唯一的；式(6)表示通过对决策变量取整来对模型进行约束。

3.3.4 改进后的粒子群算法实现路径选择

对于第二段模型，本文选用粒子群算法(PSO)[6]进行求解。粒子群算法的基本原理是通过鸟群觅食的方法对模型进行求解，鸟的位置是随机的，每只鸟每次只会在离食物最近的鸟的附近寻找食物，若发现有更加接近食物的鸟，则鸟对其所在位置进行更新，下一步将在更接近食物的鸟的周围进行寻找食物，依次迭代最终找到食物。其核心思想可以概括为，利用个体在群体中共享的信息的特点，使整个种群在动态的问题求解空间中产生从无序到有序的转变。

粒子群算法的具体公式为：

(9)

(10)

由于基本的粒子群算法存在局部收敛过快的缺点，因此需要对粒子群算法进行相应的改进，平衡算法的全局搜索以及局部搜索能力。一个较大的惯性权值有利于全局搜索，而一个较小的权值更有利于局部搜索，因此可以考虑对惯性权重进行改进。

粒子群算法有多种改进方式，本文通过对惯性权重进行线性递减惯性权重以及改进非对称学习因子对模型进行改进。采用ShiY等[8]提出的线性递减惯性权重，改进方式如下：

将权重ω改写为：

(11)

改进非对称学习因子[9]，则c1与c2可以写成：

(12)

4 模型检验

4.1 第一段的检验

对实际路径及运输节点进行相应简化[18]，抽象得到如图 3所示的运输路径图。由图 3得知，从整车生产基地出发由水路、铁路和公路可以将整车运输到中转库，而针对水路和铁路的运输还需要进行公路运输才能把整车运送到中转库；再由中转库或水路仓库、铁路仓库经公路或铁路运输到相应的仓库(仓库之间可以进行运输)；最后经公路将整车运送到配送中心。

图3 运输路径情况图

将图 3进行简化，将生产基地、仓库、中转库等节点用编号指代，隐去公路、铁路以及水路的标识，给路径给予相应的权值如图4运输路径简化图所示。

图4 运输路径简化图

假设本次权重设置为时间成本，如图 4 运输路径简化图所示，假设出发点(生产基地)编号为0，目的地编号为6，编号为1，2，3，4，5分别代表水路仓库1、中转库、铁路仓库1、仓库2、仓库3，又依据水路、公路及铁路的特性，公路运输时间短，铁路运输时间较长，而水路运输时间最长的特性来设置路径权重，例如，0→2权重为4，0→3权重为5，0→1权重为7；又根据路径长短不同设置不同的权重，例如1→2与2→5皆为公路运输，但是由于1→2距离较短则权重设为1，而2→3权重设为3；若无路径到达某一目的地，则该相应路径权重设为∞。每次经过中转站可以选择不同的路径行走，每条路径只对应某一种运输方式(公路、铁路或水路)。则由此假设此时的路径权值代表的是运输时间，此时的邻接矩阵可以写成以下形式：

为找出所需运输时间最少的运输路径，使用C++程序进行计算，计算结果如表2由Dijkstra算法计算出运输时间最少的路径所示。

表2 由Dijkstra算法计算出运输时间最少的路径

由表2可知，从生产基地到达目的地(配送仓库)所耗费时间最短的路径是：0→2→5→6。由于此次假设考虑的是紧急订单的情况，因此选用运输时间最少的运输路径，为能计算运输成本，需要计算每一小节运输距离以相应运输方式单位变动运输费用最后加上相应运输方式固定运输费用。由上诉结果可知，运输时间最少的运输路径为0→2→5→6，该运输路径中的运输方式均为公路，假设该路径距离一共为1000km，又由刘娜翠等[2]提出的数据假设，固定运输费用为100元，单位变动运输费用为4元/km，则

路径总费用=4×1000+100=40100元

该模型可以依据考虑情况的不同而设置不同的权重，从而得到符合要求的最优结果。

4.2 第二段模型的检验

本文使用Solomon算例中的标准测试集r104的前25个数据进行模型检验，根据数据集所给数据运输车辆最大载货量为200个货物，假设配送中心一共有10辆运输车可用，数据集如表3所示。

表3 算例r104前25个数据

基于毛开富等[9]将学习因子写为c11=2.5,c12=0.5,c21=1,c22=2.25，由Shi,Y[8]的文章中指出，ω1取0.9，ω2取0.4，本文将粒子群的初始规模设定为50，单位固定运输费用设定为100元，单位变动运输费用设定为4元/km位变动(单位固定费用、单位变动运输费用以及车辆行驶速度的设置参照刘娜翠等在基于遗传算法的汽车整车销售物流配送路径优化文章中所使用的数据[2])，超出时间窗的惩罚系数定为200，而超出车辆额定载重的惩罚系数定为20000(为形成约束，惩罚系数应设置得尽量大)[2]，基于多次实验发现，迭代次数设置为100次已经能够得出较优结果，因此在本文中算法的迭代次数设为100次。

基本的粒子群算法的迭代结果如图 5(a)所示与改进后的粒子群迭代结果如图 5(b)所示。

图5 算法结果对比图

由图5算法结果对比图所示，使用基本的粒子群算法图5(a)以及改进后的粒子群算法图5(b)在迭代100次后得到两个不同的方案，使用基本粒子群算法得出的方案为：配送路线1：0→7→19→11→8→17→5→18→0，配送路线2：0→21→22→23→4→24→12→0，配送路线3：0→2→15→14→16→6→13→0，配送路线4：0→3→9→20→10→1→0；而使用改进后的粒子群算法得出的方案为：配送路线1：0→2→15→14→16→17→5→6→0，配送路线2：0→21→22→23→4→0，配送路线3：0→12→24→3→9→20→10→1→0，配送路线4：0→7→19→11→8→18→13→0。

将100次迭代所得结果可视化迭代结果对比图如图6所示：

图6 迭代结果对比图

由图 6(a)基本粒子群算法的迭代次数与图 6(b)改进后的粒子群算法可知，使用改进后的粒子群算法可以更快收敛找到满意解。

最后依据两种算法得出的结果分别初始化粒子群后，再次进行迭代，此时将迭代次数设置为1000。即，第一次使用粒子群算法是对所有结果进行全局搜索从而找到最优方案；第二次使用粒子群算法是依据第一次所得结果，重新确定粒子群的初始位置后再次进行局部搜索，从而得出最终结果。通过实验计算出使用两种方案初始化粒子群在经过1000次迭代之后将得到最优配送方案，其结果与改进后的粒子群算法的计算结果相似，配送方案为配送路线1：0→2→15→14→16→17→5→0，配送路线2：0→21→22→23→4→0，配送路线3：0→12→24→3→9→20→10→1→0，配送路线4：0→7→19→11→8→18→6→13→0。基于全局搜索后进行局部搜索得出得最佳方案图如图7所示。

图7 基于全局搜索后进行局部搜索得出得最佳方案

将所得数据整理成表，最终实验结果如表 4 计算结果所示。

表4 计算结果

由表4计算结果以及图6迭代结果对比图可知在算法仅进行100次迭代时，使用改进后的粒子群算法与使用基本的粒子群算法相比所找到的派送方案更优，且所得结果更接近最终结果。因此，改进后的粒子群算法在面对规模较大的组合问题时更具优势，所需得迭代此次更少且方案更优。从实验结果可知，使用改进后的粒子群算法，在有限的迭代次数中，可以生成更优的配送方案，通过改变路径方案，可以减少相应的运输费用与运输距离，而且还能满足顾客对接收货物的时间窗的需要。该模型从公司运营角度出发在考虑运输成本最少的同时还考虑了影响顾客满意度的时间窗的因素，极大地平衡了企业对运输降低费用的需求与顾客对期望时间收到货物的需求。

5 结论

本文通过建立两段模型来规划整车物流运输路径，由实证的计算结果可知，本文用到的改进粒子群算法可以找出费用(时间)所需更少的运输路径。在进行整车调度运输路径的规划时，考虑了时效和费用对路径分配的影响，可以通过需求(订单是否紧急)灵活的选择车辆的运输路径，再根据每段采用的运输方式计算运输成本。在今后的研究中，在考虑车企对运输成本的需求以及客户的需求之外，面对国家正大力倡导的节能减排，车企在进行整车运输时也应考虑碳税政策以及承运商的生存问题，因此更加灵活多变的运输路径规划是值得研究的一个课题，本文建立的整车调度运输模型为整车调度运输路径规划提供了一种思路。