模拟退火算法在整车物流问题中的应用

张远++余依

摘 要：通过对整车物流问题进行分析，建立了一个多轿运车、多乘用车的整车物流模型。整车物流的轿运车和乘用车具有特殊的装载方式，且轿运车的多层多排结构决定了轿运车和乘用车之间具有多种装载方案，再从不超载的行驶路径下找到满足装载条件的装载方案。文章基于传统模拟退火算法的思想对算法进行改进，最后通过验证24个客户点的订单问题，将初温设置为190度，降温系数设置为0.98，求解出共需轿运车8辆，平均装载率为96%。实例验证了算法的可行性。

关键词：模拟退火算法；整车物流；VRP

中图分类号：U294 文献标识码：A

Abstract： According to analyze the influencing factor of finished car logistics， this paper established a finished car logistics model about multiple car transporter and multiple finished cars. Due to special structure and the way of loading， multiple car transporter and multiple finished cars have a variety of loading plan， the goal is find the loading plan adapt to loading conditions. Based on the traditional simulated annealing algorithm， the algorithm is improved. Verifing orders for 24 customer orders， set the initial temperature to 190 degrees， cooling coefficient is 0.98， the result of calculation is need 8 car transporter， average loading rate is 96%. Examples verify the feasibility of the algorithm.

Key words： simulated annealing algorithm； finished car logistics； VRP

0 引 言

整車物流问题是近些年随着我国汽车经济的高速发展随之而来的。整车物流是指从汽车在制造厂完成组装下线后开始，直到送达用户手中为止的一系列仓储、运输、维护、检验、加工以及其他各种增值服务过程，是实物流、信息流、资金流的统一[1]。乘用车私人定制化的普及，汽车生产商在接受到客户订单后需要快速进行组装生成，这种多批次小批量的生产模式也是目前我国主流的乘用车生产模式。而随着乘用车的型号增多，物流公司将面临着更大的运输压力。不同乘用车其长度、宽度和高度都不相同，负责运输的轿运车规格也有不同，且乘用车在运输过程中不能堆压摆放，每辆乘用车之间都必须有一定的安全间隔，以保证在运输过程中乘用车之间不会发生挤压或者碰撞而导致变形等损坏。为规范车辆运输车（轿运车）的使用和管理，保障道路交通安全，交通部、发改委、工信部、公安部、国家质监局五部委于2016年8月18日联合正式发布了《车辆运输车治理工作方案》（以下简称《方案》）并开始实施。自2016年9月21日起，所有的双排车辆禁止上路，从2016年9月21日至2018年6月30日为不合格车辆运输车的整改期，暂时允许“单排车”过渡运行。《方案》的颁布将对整车物流行业造成巨大的影响，目前市场上的轿运车基本都会面临禁止上路或者被改造的命运，本文将按照《方案》的标准对整车物流的装载和配送路径问题进行优化，提出一种新的装载配送模型，经过多次实验验证，该模型能有效降低整车物流成本，提高整车物流效益。

1 整车物流问题

1.1 整车物流问题描述

整车物流问题包括整车物流装载问题和整车物流配送路径优化问题，属于VRP问题的分支。整车物流问题不仅要在路径上进行优化处理，对装载的合理安排也是降低运输成本的一个重要途径。目前已有大量研究运用遗传算法（GA），模拟退火算法（SA）等启发式算法求解多车型车辆路径问题或者装载问题。Golden[2]最早于1984年开始研究多车型车辆路径问题，J.Lawrence将遗传算法用于VRP的研究，并可有效求解带时间窗的VRP[3]。纪寿文等人详细介绍求解货运车辆优化调度问题常用的启发式算法、神经网络算法和遗传算法的原理、模型和求解过程。然后以深圳市科技园的实际路网图，采用神经网络的方法对运输车辆优化调度进行试验研究，给出实验结果[4]。谢红燕[5]针对VRP问题建立了并行模拟退火算法，在传统模拟退火的基础上增加了记忆功能求解VRP问题。模拟退火算法（SA）是一种启发式算法，算法思想源于热力学中退火过程的模拟，即在某一给定的初始温度下，通过缓慢地下降温度参数，使算法能够在多项式时间内给出一个近似的最优解。它以一定的概率来选择邻域中目标值相对比较小的状态，是一种理论上的全局最优算法。本文假设客户的等待时间足够长，建立基于模拟退火算法的整车物流装载与配送路径优化模型使第三方物流公司以最小的成本完成客户订单配送。

目前我国汽车生产商的整车物流大多外包给第三方整车物流公司，第三方物流公司有N种型号的轿运车，共有轿运车n辆，需配送的商品车有m种，轿运车和商品车的型号已知，现有K个客户需要进行配送，每个客户订单需求量已知。第三方物流公司需要根据订单进行合理的装载并选择恰当的配送路线使每辆轿运车的利用率最大，同时所有轿运车的行驶距离最小。物流公司根据运单选择若干辆轿运车进行装载配送，每辆轿运车沿一条包含了若干个客户的封闭的回路进行运输任务，任务完成后返回出发点。

1.2 整车物流问题的模型

整车物流问题是一个NP-难题。传统的VRP问题商品单一，整车物流问题中商品车种类多样，不同型号的商品车和轿运车有成千上万种的装载方案，则对整车的装载问题要求更高，要安排最优的装载方案满足该辆轿运车运输路径上所有客户点的需求。客户订单分为两种情况，一种是订单需求量超过单辆运输车最大容量，一种是小于最大容量。对于订单量超过最大容量的，首先安排单辆轿运车进行整车配送，本文不讨论这种情况。对所有客户点预处理完毕后，每个客户点的需求量都小于单辆运输车的装载量，对模型做一下假设：

（1）现有n辆轿运车在配送中心等待运输任务，共有N种商品车，每种轿运车和商品车的型号已知，共有M种型号的轿运车。共有K个客户点，每个客戶的需求已知，客户点之间的距离以及到配送中心的距离均已知。

（2）需要根据客户点的需求以及客户点之间的距离等约束确定每辆车的装载方案以及运输路线，使所有轿运车的总行驶距离最小。

（3）每个客户点最多只能由一辆轿运车服务，每辆轿运车完成运输任务后返回配送中心。

（4）为建立模型，首先定义如下符号和变量：C=0，1，2，…，k表示配送中心和客户点集合，其中0表示配送中心；N：轿运车的种类；n：可用轿运车的数量；m：商品车的种类；q：第v个客户对第i种商品车的需求量v=1，2，…，k， i=1，2，…，m；

d：客户点u、v之间的距离u=0，1，2，…，k， v=0，1，2，…，k；L：装载到轿运车上的相邻两辆商品车之间的安全间隔；L：第j辆轿运车的装载长度j=1，2，…，n；p：第j种轿运车的排数，2≤P≤4，P=2表示上下各一排，P=3表示下层一排，上层两排，P=4表示上下各两排；f：第j辆轿运车第k排卸载的第i种商品车的数量；j=1，2，…，n， i=1，2，…，m， k=1…

P；s：第i种商品车的车身长度，i=1，2，…，m；e=f，e表示第j辆轿运车卸载的商品车i的总数量，j=1，2，…，n， i=1，2，…，m， k=1…

P；x：轿运车j是否由客户点u行驶至客户点 v，u=1，2，…，k； v=1，2，…，k， j=1，2，…，n。

以所有轿运车总行驶距离最短为目标的整车物流装载与路径优化问题可以表示成如下的整数规划模型：

其中：M是很大的正数。

目标函数表示极小化所有轿运车总行驶距离，约束条件（1）表示轿运车j从点u运输至客户v后在客户点v卸载的商品车i的总数量；约束条件（2）表示只有当轿运车j在客户点v有运输任务时，才开往客户点v；约束条件（3）表示第j辆轿运车下层和上层的装载长度约束；约束条件（4）表示客户点v对各类型商品车的需求量恰好等于所有轿运车在该客户点的卸载量；约束条件（5）表示每辆轿运车都是从配送中心出发；约束条件（6）表示每辆轿运车都要返回配送中心；约束条件（7）、（8）是变量取值约束。

2 模拟退火算法的应用

模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。模拟退火指的是在某一给定的初始温度下，通过缓慢地降低温度系数，使算法能够在多项式时间内给出一个近似的最优解。它以一定的概率来选择邻域中目标值相对比较小的状态，是一种理论上的全局最优算法。

2.1 算法改进

模拟退火算法的基本思想是通过内外两层循环寻求最优解。外循环控制降温，内循环寻找当前温度下最优解。但由于模拟退火算法在求解过程中是单个状态进行求解，当问题规模增大时，求解时间相对其他算法会较长，且较依赖降温速度和其他控制系数。

为得到更高效、更准确的算法，本文对算法进行了改进：（1）初始解状态是基于客户点的数量，对随机生成的每条路径，进行装载条件的判断；（2）在轿运车数量和总行驶距离上优先选择轿运车数量更少的方案；（3）算法先求解了各种型号的轿运车所有满载情况，最后求解得的轿运车车辆装载量不超过任一种满载方案；（4）新状态的产生，算法在上一步最优解的基础上进行邻域解的搜索，采取多种变换算法（2-opt、两点变换法等）；（5）程序中增加运行结果记忆功能，以便于对模型的结果进行分析。算法程序使用MATLAB 2015a进行编程实现。算法主要包括以下几个函数：模拟退火算法主程序，轿运车满载方案函数，随机生成初始解函数，初始化函数，邻域解函数，成本函数。

2.2 基于模拟退火算法的整车物流算法

（1）生成初始解x=Lj，每一个Lj代表一辆轿运车的服务客户及行驶路线。

（2）计算目标函数值x.cost，并令Best=x。

（3）生成邻域解x。

（4）计算目标函数值x.cost。

（5）若新解x的轿运车数量小于最优解的轿运车数量，令Best=x；若新解x的轿运车数量与Best解一致，转6；若新解x的轿运车数量大于Best，放弃该解，转3。

（6）若x.cost

（7）计算Δ=x.cost-x.cost，判断p=exp-delta/T是否被接受，随机生成一个0，1之间的随机数rand，若rand

（8）若x.cost

（9）内循环步骤（3）至步骤（8），达到内循环次数跳出循环。

（10）降温，T=T*alpha，初始温度一般设置较高，alpha为降温系数。

（11）外循环步骤（3）至步骤（10），直到外循环次数结束跳出循环，得到最优解。

2.3 初温及降温系数设置

初始温度的设置影响算法最后结果的精确性，初始温度越高，得到的解越精确，降温系数越接近于1，降温过程越慢，越容易接近全局收敛点，但求解时间过长，降温系数小，降温过程越快，容易陷入局部收敛点，求解时间短。经过多次实验，均匀抽样一组状态，以各状态目标值得方差为初温，降温系数设为0.9。

2.4 构造初始解

将客户点编号进行随机排序，得到一个客户群的随机全排列，从该全排列中的第一个客户点开始，依次放入子路径中，每条子路径代表一辆轿运车的行驶路径。每加入一个客户点，判断该辆该轿运车是否超载，若超载，调用新的轿运车，否则继续装载下一个客户点，直到所有客户点被满足。由于大车型轿运车购买成本较高，所有大车型轿运车数量较少，每次选择轿运车时随机选择，但是大车型的轿运车数量有限。具体算法如下：

（1）将客户点随机排列得到随机全排列q；

（2）随机选择一辆轿运车，并更新剩余类型的轿运车数量；

（3）计算第一个客户点q的需求量n，轿运车行驶的距离D；

（4）加入下一个客户点q，计算新的需求量n=n+n，n表示当前客户点的需求量；

（5）判断新加入客户点后是否超载，若不超载，则更新行驶距离D=D+D，D表示新加入客户点与上一个客户点的距离，n=n；若超载，则转（6）；

（6）保存上一步未超载的路径L，总需求Q，重新选择新的轿运车，j=j+1，将步骤（5）中未加入的客户点保存至新的路径中，n=n，D=D，D表示当前客户点与配送中心的距离；

（7）循环步骤（4）至步骤（6），直到所有客户点被满足。

对于每一个解的任何一条子路径L，计算该条路径的总需求量Q，根据轿运车的基本参数和乘用车的基本参数，不超载条件如下：

Q*s+sumQ

-p*L≤p*L

运用反证法，若轿运车装载的乘用车所需总装载长度不超过轿运车每排的装载长度之和，则必然能找到一种装载方案使得每一排装载长度不超载。初始解记录每条路径选用的轿运车车型，每条路径的装载量，轿运车的行驶路线。

2.5 构造轿运车满载方案

在得到最优解后，需要找到一种装载方案对乘用车进行装载。本文通过构造可行装载方案矩阵得到满载方案。

根据轿运车的和乘用车的种类数生成解空间，轿运车有N种，乘用车有m种，轿运车每排的长度相同，根据整车物流模型约束条件（3）可以得到各种车型的滿载方案。在构造的可行初始解中，根据每条路径选择的轿运车车型至少可以从该种轿运车车型的满载方案中选择一种装载方案满足该条路径的装载需求。

3 算例验证

某汽车生产商主要生产三种车型的乘用车，某第三方整车物流公司有两种型号的轿运车，都为上下单排双层结构，轿运车及乘用车的基本参数如表1，某次订单共有24个客户，客户的需求量如表2，客户与配送中心的距离如表3，根据模型及算法，为保证算法的准确性，并进行了多次计算比较，得到在不同降温系数，不同初始温度下的最优解。

经过多次试验，将初温设置为190，降温系数0.98，求解出最优解。共需8辆轿运车，总行驶距离为1 709.8912千米，平均装载率为95.83%，具体装载方案如表

4 结 论

本文通过研究多车型的整车物流问题，建立整车物流数学模型，在传统模拟退火算法上进行改进，通过均匀抽样计算方差的方式确定初温，避免温度过高收敛较慢、温度过低陷入局部收敛，在轿运车装载问题上采用反向验证，总长度不超载则每一层必有一种不超载的装载方案，优先选择轿运车数量少的方案。实验结果显示了本文算法的有效性。

参考文献：

[1] 吴保峰，刘仲英. 我国整车物流发展趋势及资源整合问题研究[J]. 汽车工程，2005（3）：367-371.

[2] Golden B， Assad A， Levy L， et al. The fleet size and mix vehicle routing problem[J]. Computers and Operations Research， 1984（11）：19-66.

[3] Lawrenee S， Mohammad A. Parametric experimentation with a genetic algorithmic Configuration for solving the vehicle routing problem[C] // Proceedings-Annual Meeting of the Decision sciences Institute. Decis Scil Inst， 1996：488-490.

[4] 纪寿文，缪立新，李克强，等. 货运车辆优化调度方法[J]. 公路交通科技，2003（6）：109-112.

[5] 谢红燕. 基于并行模拟退火算法的VRP问题研究[J]. 物流技术，2010（15）：67-69.