数学建模优化物流运输路径可行解的改进算法及其应用

沈 澄，方 伟

（1.浙江工商职业技术学院，浙江 宁波 315012；2.宁波永耀信息科技有限公司，浙江 宁波 315020）

数学建模优化物流运输路径可行解的改进算法及其应用

沈 澄1，方 伟2

（1.浙江工商职业技术学院，浙江 宁波 315012；2.宁波永耀信息科技有限公司，浙江 宁波 315020）

针对带时间窗物流运输最优化路径选择问题，基于概率分布算理的共同机制，将遗传算法全局搜索优势与模拟退火算法局部搜索优势有机整合，有效规避二者算法寻优性能的不足，使构建的改进算法兼顾优越的全局搜优能力和计算效率。针对9个目标点物流运输路径优化问题的可行解，展开算法应用的试验验证。结果显示，若目标点数量较少能够求得最优解，若目标点数量较多则能够求得满意解。

物流运输；路径优化；目标函数；最优解；适应度；可行解

1 引言

在物流运输业中存在许多优化策略问题，运输路径的优化作为NP-C问题，计算复杂性很高，难以通过全局搜索实现最优化求解[1]。众所周知，遗传算法（GA）具有突出的全局搜索能力，但在实际运用中时常早熟收敛，后期搜索效率不高，为此许多学者采用蚁群算法、粒子群算法等对遗传算法进行混合改进，取得了较好的寻优效果。模拟退火算法（SA）具有优秀的局部搜索能力，本文根据物流运输的特点，建立相应的数学模型，将模拟退火算法置入遗传算法，优化改进遗传算法，并展开算法应用的试验验证。

2 问题描述与数学模型建立

将货物从集散中心配送到多个目标，先要确定每个目标的位置和需求量、选择最优配送路径，达到运输效率高、成本最低，还需满足[1-2]：①每条线路的货运量不得超出运输车辆的装载量；②每条线路目标点的需求必须满足，且仅由一辆车在限定时间内送货；③每一运输车辆自集散中心出发，均必须在限定时间内返回集散中心。为此设该运输系统中的目标点集合i=0表示集散中心，车辆数集合，引入决策变量，，其中i,j∈N,i≠j,k∈H。假设每条配送路径对应一辆货车，且一辆货车可以满足这条线路上目标点的配送要求，每一目标仅由单一车辆完成一次配送，建立数学模型的相关参数见表1。

表1 物流运输路径优化的数学模型参数

那么，目标函数[2-3]：

模型中（1）为目标函数，（2）至（12）为约束条件。（2）规定集散中心是运输车辆的起点与终点；（3）规定派出的车辆数不超过拥有的车辆数；（4）规定车辆不能从本地到本地；（5）规定车辆路径连续约束；（6）和（7）规定每一目标点恰好被一辆车服务一次；（8）规定每一路径货运总量的车载重约束；（9）规定车辆运输准时的时间约束；（10）至（12）为时间窗约束。

3 改进算法的分析与实现

3.1 模拟退火算法（SA）

该算法来自热力学中的固体退火原理，固体加热温度至充分高，其内能增大，而冷却过程在常温时达到基态，内能减为最小。N.Metropolis于1953年提出，用固体退火模拟组合优化问题，将内能E模拟为目标函数f，温度T演化成控制参数t，由初始解s和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，当温度终止在低温时内能极小，即目标函数值最小，此时算法终止的当前解即为近似最优解。

这是基于Monte-Carlo迭代求解策略的一种随机寻优算法，搜优过程随着温度的不断下降，赋予一种时变且最终趋于零的概率突跳性，在解空间中随机寻找目标函数的全局最优解，具有跳出局部最优陷阱的能力，随着温度的不断下降至最低温度，搜索过程以概率l收敛于最优解，即在局部的最优解能概率性地跳出并最终趋于全局最优，具有概率的全局优化性能。

设目标函数为min f(Si)，Si∈S，S是离散有限状态空间（即可行解集合），求解过程如下：

（1）初始化，任选初始解Si∈S，给定初始温度T0足够高，终止温度Tf足够低，令迭代计数器k=0，Tk=T0。

（2）随机产生一个邻域解，Sj∈N(Si)，N(Si)表示Si的邻域，计算目标值增量，Δf=f(Sj)-f(Si)。

（3）若Δf<0，令Sj=Si转到第四步，否则产生一个随机数ξ∈U(0，1)，若exp(-Δf/Tk)>ξ，则令Sj=Si。

（4）若达到热平衡转到第五步，否则转到第二步。

（5）k=k+1降低Tk，若Tk

3.2 遗传算法（GA）

该算法1975年由美国J.Holland教授提出，它是借鉴生物界适者生存的遗传机制形成的随机搜索最优解的方法。该算法采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，具有内在的隐并行性和更好的全局寻优能力，可使问题的解一代又一代地优化逼近最优解。GA应用遗传算子经选择、交叉、变异运算，模拟生物种群自然选择、优胜劣汰、不断进化的规律，逐代产生出代表新的解集的种群，后生代种群比前代更加适应环境，解码末代种群的最优个体作为近似最优解。求解过程如下：

（1）初始化求解空间。设进化代数计数器k=0，最大进化代数K，随机生成M个个体作为初始种群的染色体并进行编码。

（3）个体评价。计算适应度函数Fit(Si)的值,即当前种群Z(k)中各Si的适应度。

（4）遗传算子操作。经过选择、交叉、变异运算生成子代种群Z(k+1)。

（5）终止条件判断。若k=K,则以进化过程中所得到的具有最大适应度的个体作为最优解输出；否则返回第三步。

选择算子选择Fit(Si)值较大的个体提高个体被复制的概率，促进算法收敛速度加快，优秀个体Si被选择的概率为，Fiti越大Pi就越大；交叉算子置换两个父系基因，促进算法搜索能力提升，搜索得到更优的个体（或解）；当交叉运算已接近最优解邻域时，变异算子的局部随机搜索能力能加速向最优解收敛，同时维持群体的多样性，这有利于促进算法规避局部最优。但实际应用中遗传算法在进化后期效率不高，容易未成熟收敛，且局部搜索能力较弱，因此有必要引入其他优秀算法对遗传算法进行改进，实现高效运算、快速搜优，防止早熟现象。

3.3 改进算法（GA&SA)

GA和SA算法都是基于概率分布机制的优化算法，具有算法理论的共同契机，改进算法是将模拟退火算法设置为一个独立的算子，置入遗传算法中，对选择、交叉、变异操作生成的每一个新个体独立进行模拟退火，经模拟退火操作后的个体设置为子代个体，迭代次数作为退火时间，迭代直到满足终止条件求得最优解。求解过程如图1所示[4-5]。

下面针对9个目标点的物流运输路径优化问题的可行解为算例，展开算法的应用分析。

（1）染色体编码。用字符串表示种群的染色体，染色体中的数字代表目标点，基因的顺序代表运输车辆的线路与方向，解表示长度为n的定长整形字符串，n表示被访问的目标点个数。那么该物流运输系统可编码为248517963，要求路径m的最后目标点和路径m+1的开始目标点连接，按车辆的装载量划分线路，解码时将基因依序插入到新路径之中，即得到路径1:0→2→4→8→5→0；路径2:0→1→7→9→6→3→0，能使得路径数量最少便可实现运输成本最低。

（2）生成初始种群。随机产生1至n这n个自然数的不重复排列，作为该运输路径种群的个体[6]，依据数学建模的约束条件，在运输系统中设定最低费用的目标点，产生的一部分初始可行解记作S0，随机生成的剩余部分可行解记作S1，S0和S1共同组成初始种群，记种群规模为M。

（3）确定初始温度。k取充分大，确定初温T0=kδ，δ=fmax-fmin，操作中令k=20、80、150、…进行试验，f是初始种群的目标函数。

（4）构建适应度函数。适应度用于度量个体在优化计算中有可能达到或有助于找到最优解的优良程度，直接关系到父代中的优秀基因如何遗传到子代种群。适应度函数是由目标函数变换而成，构建时要考虑具备单值、连续、非负、最大化的特征，还要考虑计算量小、通用性强、符合问题实际、一致性好的要求[7]。本文根据研究问题的目标函数，列出全部父代个体的目标函数值按降序排列，设xi(i=1,2,…,M)表示降序排列后的第i个个体，适应度函数定义为Fit(xi)=1/(a(1-a)i)（0

（5）选择、交叉与变异操作。选择操作采用轮盘赌方法，旋转一次即挑选一个优质个体作为父代个体繁殖到新生种群，选择准则是由第四步计算出父代的所有个体xi的适应度值以及被选择的概率，经多轮轮盘赌选择出的个体进入后续的交叉变异操作。

图1 改进算法求解步骤框图

根据交叉概率，对种群中的个体随机两两组合，并交换二者的部分基因，二个染色体通过交配重组产生新个体，决定着GA的全局搜索能力。由于物流运输路径问题按十进制编码，长度固定排列有序，整数基因只会出现一次，因此选用部分匹配交叉法，在二个父代染色体中随机产生两个交叉点，交叉基因位交换基因码并继承基因。

重组过程的染色体编码中部分基因座的基因值以变异概率变更为该基因座的其他等位基因，从而形成新个体[8]，决定着GA的局部搜索能力。采用倒位变异法，在性质相同的编码中随机选择一个子串以变异概率逆向排列生成新个体，这使得染色体在小范围变化，进一步强化了种群的多样性。变异和交叉相互补充，配合完成全局搜索与局部搜索的最优化问题搜优。

（6）自适应选择。交叉概率与变异概率的取值极大地影响着GA的运算效果，取值太小产生的新个体就少，抑制早熟的能力就会变差，取值较大，虽能产生较多的新个体，但也有可能破坏优良个体。关于自适应性变异概率，采用方差来计算，公式为，其中。如果 λ≥MINPOPDEV=5，那么 Pm=Pmin=0.06；否则Pm=Pmin+0.1×(MINPOPDEV-λ)。在这里自适应性变异概率能够在不成熟收敛与优良个体被破坏的二个问题间寻求解决方法[9-10]。

（7）模拟退火局部搜优。根据退温函数Tk+1=αTk（0<α<1），对选择、交叉、变异操作生成的每一个新个体，独立进行模拟退火，并记住优秀个体。

（8）复制新个体。初始种群经历了交叉、变异、退火的过程，基于Metropolis复制策略，①保留最优个体，②在染色体i的邻域中随机生成新个体j，优胜劣汰决定i 与j谁进入子代种群。计算它们的目标函数值，令Δf=f(xj)-f(xi)，如果Δf<0，便接收xj；如果Δf>0，需满足条件exp(-Δf/Tk)>ξ（ξ是0到1之间的一个随机数），方能将xj复制到子代种群。再求出子代种群目标函数的最小值，便得到运输路径最短、成本最低的近似最佳路线，拟作为服务于全部目标点的最佳方案。

（9）算法终止。经p代进化后，以新生种群中目标函数最小值fmin的变化为判据，如果连续q代未出现变化，那么当前解为最优解输出。

4 模型检测与算例验证

已知该9个目标点的物流运输各配送目的地货物需求量(mi)吨=（1,2,2,3,3,2,3,4,3），各地间的距离矩阵(dij)公里如图2，表2为时间窗。

表2 车辆路径时间窗（时刻）

设置仿真试验相关参数：M=100，退温系数α=0.9，终止条件q=200，h=2，交叉概率 pc=0.9，变异概率Pm=0.06，a=0.01，vh=12×103kg，ui=25min，rh=15min。根据参数编程并将数据分别录入三种算法的运行程序，最优率为求得最优值的次数占总求解次数的比例，方差δk=(f(k)-fopt)/fopt，其中 f(k)为最终目标函数值、fopt为最优目标函数值，验证改进算法的性能。求解结果如图2。

（1）最佳方案。改进算法求得四组可行解，运输路程分别为70.5、69、67、65.5，第四组解比前三组解更满意，即最佳路径1：0→2→4→8→5→0的运输量12t、路程29.5km；路径2：0→1→7→9→6→3→0的运输量11t、路程36km。为研究的方便,车辆行驶的单位路程与所需的单位成本在数值上可视为一致，那么该运输方案的总费用为65.5单位成本，因此最佳方案的路径最短、成本最低、车辆的装载量得到了最大限度的使用。

（2）性能分析。相同条件下三种算法GA&SA、GA、SA获得的最优率分别为96%、85%、74%，方差分别为1.3、6.1、5.6，可见GA&SA的最优率最高、方差最小；SA的解比GA的解分布较均匀，但SA的计算时间较长，求得的最优解比GA较好，然而GA的最优率远远高于SA，说明GA的全局搜索性能优于SA，SA的局部搜索性能优于GA，改进的GA&SA拥有最佳性能，计算最优解的能力明显优于两者。

（3）算法优势。遗传算法的早熟现象是因为种群陷入局部最优而丧失了群体的多样性，退火策略直接对所选个体实施交叉、变异后的退火操作，随着迭代次数的增加，推进局部最优点趋于全局最优点。因此改进算法GA&SA改善了遗传算法的全局收敛性，提高了算法的收敛速度，强化了全局与局部两种环境下的搜索能力，全面优化了搜优功能。

5 结语

建立数学模型优化物流运输路径是现代科学发展带给物流技术的一大便利，本文针对带时间窗物流运输最优化路径的选择问题，将遗传算法全局搜索的优势和模拟退火算法局部搜索的优势进行有机整合，有效规避了二者算法寻优性能的不足，使得改进的GA&SA兼顾了全局寻优能力和计算效率。若目标点数量较少能够求得最优解，若目标点数量较多则能够求得满意解。传统算法受诸多因素限制，获得的运输方案不够经济，凭借经验尝试调整运输车辆的数量以获得较为合理的安排方案，但欠缺科学依据，改进的GA&SA算法为解决物流运输优化方案提供了有力的技术支持。

[1]张维泽,林剑波,吴洪森,等.基于改进蚁群算法的物流配送路径优化[J].浙江大学学报(工学版),2008,(4):574-578

[2]李珍萍，周文峰.物流配送中心选址与路径优化问题—建模与求解[M].北京:机械工业出版社,2014.

[3]吴烨.物流配送网络选址的模糊数学模型及其算法[J].经济数学,2008,(3):277-282.

[4]罗耀波,孙延明,刘小龙.多约束选址—路径问题的改进混合遗传算法研究[J].计算机应用研究,2013,(8):2 283-2 287.

[5]吴烨，李应逑.供应链中物流配送的数学模型及其混合蚁群算法[J].经济数学,2007,(4):398-401.

[6]王旭升，尤小霞.基于混合遗传算法的物流配送路径分析[J].物流技术,2014,(3):269-271.

[7]张全生.基于聚类-遗传混合算法的物流配送路径优化研究[D].淮南:安徽理工大学,2011.

[8]钟惟钰.遗传算法在物流配送运输车辆路径优化中的应用与改进[J].物流技术,2014,(5):323-325.

[9]孙君.应急物流能力优化研究[M].北京:科学出版社,2015.

[10]Lan H C W,Chen T M,Tsui W T,Pang W K.Application of Genetic Algorithms to Solve the Multidepot Vehicle Routing Problem[J].Automation Science and Engineering,IEEE,2010,7(2): 383-392.

M athematical Modeling and Im proved A lgorithm for Feasible Solution of Logistics Transportation Route Model and Its App lication

Shen Cheng1,FangWei2
(1.ZhejiangBusiness Technology Institute,Ningbo 315012;2.Ningbo Yongyao Information TechnologyCo.,Ltd.,Ningbo 315020,China)

In this paper,in view of the logistics transportation route optimization problem with time window and based on the common mechanism of the probabilistic distribution principle,we integrated the genetic algorithm with the strength of global searching and the simulated annealing algorithm which exceled in local searching and then in the numerical example of a logistics transportation route problem withninedestination points,demonstrated and validated thealgorithm.

logistics transportation;routeoptimization;objective function;optimalsolution;degreeof fitness;feasiblesolution

F224.0;F512.6

A

1005-152X(2017)05-0103-05

10.3969/j.issn.1005-152X.2017.05.023

2017-04-05

沈澄（1963-），女，浙江工商职业技术学院副教授，主要研究方向：数学课程教育与应用数学；方伟（1963-），男，宁波永耀信息科技有限公司工程师，主要研究方向：信息技术管理与计算机编程应用。