黄金正弦模拟退火算法求解低碳有能力约束的车辆路径问题

于建芳， 刘 升

(上海工程技术大学管理学院,上海 201620)

中国是世界上能源消耗和碳排放的大国之一，空气污染越来越严重，雾霾也是常年伴随人们的出行，所以“绿色物流”一词出现的频率越来越高，城市物流的目标不再仅仅是满足客户需求的情况下降低配送成本，同时还要考虑物流配送活动对环境的影响，呼吁社会发展绿色低碳的可循环经济模式迫在眉睫，绿色低碳经济必将成为未来社会的主流经济模式。车辆路径问题(vehicle routing problem，VRP)[1]近年来研究者众多，物流运输在低碳经济中的重要性也使得路径规划变得尤为重要，所以车辆路径问题方面的研究是企业所亟需的。相应的，研究也面临着复杂约束条件、求解规模较大、求解难度大、成本增高等难题。

演化算法的应用可以帮助企业找到成本最低、路径最短、时间最短相结合的最佳的科学配送路径，节约能源，减少碳排放，提高服务质量，所以演化算法是绿色物流的最佳选择方案，对于提高企业的经济效益，具有重要的理论意义和实用价值。以往的研究对具有挑战性的车辆配送问题作出了十分重要的贡献，然而，在大规模部署车辆路径问题方面还是面临着很大的挑战，特别是对于具有不同道路容量和交通延迟约束的区域网络、高速公路瓶颈和城市街道上的信号定时等问题。Gayialis等[2]结合现有研究文献对Scopus科学数据库进行了文献综述，对过去10年的城市物流运输VRP问题进行分类，梳理和分析了城市物流运输VRP的发展趋势。Kenan等[3]提出了一种创新性的G-VRP模型，以降低汽车油箱的油耗为目的，以模拟退火算法求解该模型，降低了CO2的浓度。Dulai等[4]为解决车辆配送过程中突发故障的问题，提出一种容错算法，当突发故障是可以由其他车辆以最有效的方式代为配送完成剩余任务，最小化“路线变更成本”，但是使用容错算法后配送路径长度平均比原车辆路径问题短4.1%～8.6%，为车辆路径问题求解提供新思路。Wang等[5]延伸了车辆路径问题，把油耗和模糊出行时间加入目标函数中，采用模糊函数改进遗传算法以解决绿色模糊车辆路径问题，提高了求解精度，很大程度上缩短了运行时间。

葛显龙等[6]以纯电动汽车为研究对象对车辆路径问题进行研究，减少燃油车的使用固然绿色低碳，但电动车的使用受到很多限制，电量续航是最大的问题，使其比传统汽车具有更高的使用成本；但是电动车在未来必定是最绿色环保的物流配送形式。李珍萍等[7]研究了一种具有多种需求且由不同类型车辆提供服务的顾客需求配送模式，建立了混合整数规划模型，进一步设计了混合遗传算法求解，验证了改进算法的有效性，为解决实际问题提供了决策依据。李小川等[8]提出一种基于文化基因的狼群算法，以最小化总距离和车辆数为目标，求解带时间窗的车辆路径问题，试验结果表明文化狼群算法求解效果较好，为解决VRP问题提供了新途径。钱晓明等[9]提出一种混合模拟退火算法，用于求解固定车辆数的多车型车辆路径问题，模型的实用性和算法的有效性得到了强有力的验证，但是作者仅仅增加禁忌表对模拟退火算法进行改进，过于简单。何东东等[10]以节能减排为目标，构建了考虑低碳和成本节约的多种车型且带时间窗的车辆路径问题模型，采用改进的禁忌搜索算法求解该问题，实验验证了模型和算法的有效性和可行性，但是求解方法不够新颖。

结合上述求解车辆路径问题中的算法改进设计简单，求解案例点数过少等不足，提出了一种基于黄金正弦的模拟退火算法(simulated annealing algorithm based on golden sine,GSSA)。该算法结合新型的启发式算法黄金正弦算法，两个阶段法对所提出的车辆路径模型进行求解，并且增加模拟退火算法的邻域搜索设计和记忆装置，使第二阶段的邻域搜索范围更广，记录目前为止的最优值，以提高算法的收敛精度，减少搜索时间。

1 有能力约束的车辆路径问题(CVRP)

有能力约束的车辆路径问题(capacitated vehicle routing problem，CVRP)是在标准车辆路径问题的基础上增加能力约束使模型更加符合现实生活中遇到的配送问题模型。CVRP可以描述为：某配送中心0用多辆相同汽车向有不同需求的客户配送货物，已知每个客户的位置、需求量以及汽车的容量，配送路径受车辆的容量、行驶路程等限制，需要合理安排车辆配送选择最佳车辆路径，使得总路程最短、总费用最小、配送总时间最短等。

车辆路径问题(VRP)一直都是NP-hard难题，对于这种多目标多约束的问题，其结果也是受到很多因素的影响，需要作出一定的假设，尽可能地减小不必要的因素对结果的影响，减少求解难度，使最终结果更加符合现实生活中的要求，所作出的假设如下。

(1)配送中心具有固定的车辆数且每辆车车型完全相同。

(2)每辆车可以满足多个客户点的需求，而每个客户点只能被一辆车服务，在配送服务完成之后车辆要驶回车场。

(3)假设车辆配送产生的成本与路径长度线性相关，每辆车固定成本相同。

(4)每辆车载量有限，客户点的总需求量不得超过车队总装载量。

(5)有且只有一个配送中心。

VRP涉及的符号及其意义如表1所示。

表1 符号及其意义

设定决策变量[11]如下。

则CVRP的数学模型为

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

式(1)为以行驶距离最短、成本最低为目标的目标函数，表示使总配送成本最小，总配送距离最短，配送的车辆数最少;式(2)为车辆载重约束，限制每辆货车初始装载量的最大值，亦即每辆货车出发时的最大配货量是不能超过一定数值的;式(3)和式(4)为客户配送唯一性，表示每个客户只有一辆车配送;式(5)和式(6)为配送中心约束，有且只有一个配送中心; 式(7)为子回路约束; 式(8)为客户车辆流守恒约束，配送车辆的数目是固定不变的; 式(9)和式(10)为0～1变量约束。

2 基本模拟退火算法

模拟退火(simulated annealing，SA)[12]算法是一种全局统计优化方法，是最适合解决车辆路径问题的算法之一。它最早由Metropolis提出，是从物质的物理退火过程中得到启发。退火过程大致是:先将物体不断加热至高温，温度越高物质内部的粒子活跃性越高，且处于高速转动的不稳定状态，此时物质具有较高的内能;然后缓慢降温，原子运动速度随着温度的下降减慢，活跃度下降，物质的内能下降; 最后，整个物体达到内能最低，变成稳定的状态。

模拟退火过程类似于沿水平方向晃动装有小球的托盘，温度越高则意味着晃动的幅度越大，小球会从一个低谷跳入另一个低谷。从全局优化的角度考虑，每一步低谷的高度要比小球原来所在低谷的高度低，才能最终得到最优解;但正是托盘中小球“爬山”的能力，才使增大小球从局部低谷跳出而落入全局低谷的概率，达到最终的最优值。当然，退火的温度要适合，由强至弱，慢慢减弱小球跳动的能力，使小球不会越爬越高。

固体物质退火过程和组合优化问题有很多共同点:金属温度设置控制参数T来代替，金属状态i及其当前内能类比于实际问题中的结果x及其费用函数f(x)。所以固体物质退火过程和组合优化问题有很大的共性特点，后来人们成功把模拟退火算法用于求解各种组合优化问题。

SA算法迭代优化寻找最优解的过程中，首先需要确定一个初始温度T0，设置参数，并以问题解空间的初始状态作为初始解，然后在一定温度下，对当前解进行搜索算子干扰，模拟固体内部粒子的状态转移过程。之后比较在干扰后状态下得出的新解和当前解，依据Metropolis准则进行替换。该算法准则是以概率1来接受适应度值中的最优解，以一定的概率来接受适应值中的较差点。Metropolis准则的这种特殊能力使得算法不易陷入局部最优停滞，具有跳出局部获得全局最优解的能力。Me-tropolis准则[13]定义为

(11)

由式(11)可知，当E(j)≤E(i)时，即物质的系统能量函数适应值减少时，该系统将会以概率1来接受新的适应度值，即会100%接受；反之，以一定的概率来接受适应值中的较差点。

基本退火算法的Metropolis准则设计使得算法有接受较差解的优势，但是亦导致了可能错过最优解的问题，还有邻域搜索能力不强，导致搜索时间过长等，所以算法仍存在改进空间。

3 基于黄金正弦的模拟退火算法(GSSA)

模拟退火的依据是金属的退火过程，其实质为内外两层温度发生的变温循环：外循环控制温度下降，使其达到适合内循环的温度状态，内循环以当前温度重复抽样直至内部达到稳定为止。模拟退火算法主要包括温度更新函数、初始温度T0、状态函数、状态接受函数、内循环和外循环终止准则。模拟退火算法在理论上是一种全局最优算法，但实际上存在以下不足：①降温过程越缓慢得到的解的质量越高，但相对的收敛速度就会太慢；反之，降温过快很大可能影响全局优化，得不到全局最优解；②求解的质量对参数设置有很强的依赖性；③在解决大规模的实际问题时，运行时间过长。

3.1 编码与解码

Prins[14]提出了一种新型的路径划分方法，根据该路径划分方法，采用无分隔符的编码解码方式，科学合理地对车辆路径问题的算例进行了编码，编码结构形式类似为S=[0—4—6—15—0]。

如图1所示，解码方法如下：假设有5个客户需求点需要配送中心0向其配货，配送中心有车型1、车型2两种车型，fi表示固定费用，vi表示不同车型的速度。计算各个路径的配送成本，比较得出最小成本来确定最优路径。比如需求点1，采用车型1配送，成本c(0,1)=f1+v1[d(0,1)×2]，其中d(i,j)表示需求点之间的距离；然后将点2加入，若不超过容量约束则车型1配送路线为S=[0-2]，成本c(0,2)=f1+v1[d(0,1)+d(1,2)+d(2,0)]。增加点3，由于容量限制，增加车型2 配送，成本c(0,3)=f2+v2[d(0,1)+d(1,2)+d(2,3)+d(3,0)]。如此类推直到所有的点都被加入路线中，比较最终成本。

图1 编码和解码Fig.1 Encoding and decoding

利用该编码方式有效简化了初始解的结构，避免了线路间邻域的计算，节约运行时间，增加了模拟退火算法的搜索精度和速度。

3.2 算法设计

为弥补上述基本模拟退火算法中的不足，进行以下3个方面的策略改进，优化基本模拟退火算法的性能，更加快速高效地求解出最优的结果。

3.2.1 黄金正弦算法

黄金正弦算法(golden sine algorithm，Gold-SA)是Tanyildizi等[15]于2017年提出的新型元启发式算法，该算法的设计灵感来源于数学中的正弦函数，该算法利用数学中的正弦函数进行计算迭代寻优，其优点是收敛速度快、鲁棒性好、易于实现、调节的参数和运算符少。

Gold-SA根据正弦函数与单位圆的关系，可以遍历正弦函数上的所有值，即寻遍单位圆上所有的点，同时在其位置更新过程中引入黄金分割数缩小解决方案的空间，以便扫描可能只产生良好结果的区域，很大提高了搜索速度，且使“搜索”和“开发”达到良好的平衡。

(12)

3.2.2 增加邻域操作方法

基本SA的邻域搜索操作是2-swap两点置换法。因为该方法每代只简单交换其中2个节点，如果要保证得到每一个温度下的最优解，就需要搜索更长的时间，所以该邻域搜索方法对解空间的搜索能力比较弱。加上温度降低，外循环更加频繁，每次迭代的执行时间成倍增长，使得算法的整体运行时间过长。所以线路内交换需要增加邻域搜索，即增加2-opt、3-opt和2-insert 3种交换方法。4种交换方法随机协作实施邻域搜索操作，产生新的可行解。随机协作是基于一定概率来随机确定使用某一种交换方法来进行邻域搜索操作，这样交替更换邻域搜索的方式使产生新解空间的可能性增加，提高了基本算法跳出局部最优停滞的可能性。

2-opt算法比图2所示的(i,i+1)和(j,j+1)是两条可行解路径，若2-opt法进行运算，则j和i+1两个点进行翻转交换，从而得到交换后的两条新边(i,j)和(i+1,j+1)，当然，只有交换后的成本低于交换前，即Ci,i+1+Cj,j+1>Ci,j+Ci+1,j+1，才算得到新的可行解。

图2 2-opt法Fig.2 2-opt method

3-opt算法，从前往后随机选择3 个点依次交换位置，与2-opt法类似但是搜索能力更强，具有产生新解更大的可能性，更加全面快速地搜索最优解，提高全局搜索能力。

2-insert算法，遍历所有的点随机选择相连两个点i,j，若Cj>Ci，则将i点放在j点后面，同样提高算法的搜索能力。

通过随机性选择上述4种邻域操作，增加对解的结构破坏力，共同协作完成搜索，加强了邻域的搜索能力，及时地跳出局部最优停滞，有利于改进算法的全局寻优能力。

3.2.3 设计记忆装置和改变退火温度

由于Metropolis准则，在执行概率接受环节中较易遗失当前遇到的最优解，所以在改进的SA中设计一个记忆数组，用来记录最优解的值，从而使得算法运行过程中输出一直是“Best So Far”的最优解。通过这种方法记忆目前为止的适应度函数最小的解为最优解，避免错过可能的最优值，很大程度上节约算法运行的时间，提高了算法运行的效率。

模拟退火算法在其退火的过程中，随着温度的下降其内部的熵值越来越低，接受较差值的概率也随之降低。所以在算法降温过程的适当时机，将温度以一定比例适当提高，增加固体内部的活跃性，以激活搜索进程中当前状态接受概率，避免算法陷入局部最优停滞。退火过程的温度曲线如图3所示。

图3 退火过程中随降温次数变化的适应函数曲线Fig.3 The curve of the adaptive function varies with the times of cooling during annealing

新颖的黄金正弦算法结合模拟退火算法的特点进行的改进，既弥补了模拟退火算法收敛速度慢的问题，又吸收了模拟退火算法在解决VRP方面的优势；而记忆数组的设置和退火温度的改变又提高了算法全局搜索获得最优的可能性，在一定程度上节约了运行时间，从侧面提高算法得到最优结果的运行速度，优化了模拟退火算法的性能。

3.3 基于黄金正弦的模拟退火算法

综合以上几种方法，从改善初始解、邻域搜索、运行时间、接受可行解的范围几方面对基本模拟退火算法进行改进，以提高SA的优化性能。

在模拟退算法的初始位置引入黄金正弦算法作为第一阶段，由于Gold-SA函数与单位圆的关系，可以遍历正弦函数上的所有值即寻遍单位圆上所有的点，使寻优区域更加全面；同时通过参数R1和R2的随机选择控制位置更新距离和方向，可以逐步缩小搜索空间，快速引领蚁狮个体趋近最优值，从而减少算法的寻优时间，提高算法的寻优速度和精度，获得理想的寻优结果；最后引入黄金分割数，可以根据式(12)确定其更新位置，确定最优初始解。

第二阶段的模拟退火算法结合新增的邻域搜索方法和记忆装置，4种方法随机协作增加算法跳出局部最优的可能性，记忆装置增加算法的记忆功能，记录迄今为止的最优值，节约运行时间，提高算法的优化效率。首先进行线路内交换，4种交换方法随机协作实施邻域搜索操作，这样交替更换邻域搜索的方式破坏解空间结构，增加产生新可行解的可能性，提高了基本算法跳出局部最优停滞的可能性。然后进行线路间的调整，引入λ-interchange思想对产生的可行解进行操作，规定当前温度下邻域搜索的次数为λ，以保证规定时间内获得较高质量的最优解。最后将适应度值最小的解储存到记忆装置，避免接受解Metropolis准则的采用错过当前遇到的最优解；在适当时机增加固体金属的退火温度，使金属内部物质活跃性增加，加大可接受解的范围，很大程度上节约了算法运行的时间，大大提高了算法运行的效率。

改进的模拟退火算法的流程如图4所示，具体步骤如下。

图4 改进模拟退火算法流程Fig.4 Flow chart of improved simulated annealing algorithm

步骤1：设置退火参数，初始温度T0、温度衰减系数α、终止温度tf、当前迭代次数u、当前成功迭代次数l、最大迭代次数U、最大成功迭代次数L。

步骤2：随机产生可行解f0，令fi=f0。

步骤3：利用黄金正弦算法可以遍历正弦函数上的所有值等特点，能够得到较优的适应值作为第二阶段的初始解。

步骤4：构造邻域解。4种邻域搜索方法随机协作得到多个邻域解fj，记忆装置记录当前最优的解，且令u=u+1。

步骤5：比较。如果fj≥fi，则转步骤6；否则fi=fj，记录当前解为最优解，l=l+1，转步骤7。

步骤6：Metropolis准则接受解。Δfij=fj-fi，若exp(-Δfij/Ti)>ε，ε是(0，1)随机数，则fi=fj，l=l+1；否则，转步骤7。

步骤7：最终温度。若u≥U或l≥L，Ti+1=αTi，适当提高温度后，u=0，l=0，转步骤7；否则返回步骤4。

步骤8：算法终止。若连续r=20次迭代结果相同，则算法终止；若当前温度Ti+1≤tf，则算法终止；否则返回步骤4。

4 改进模拟退火算法在绿色物流车辆路径问题中的应用

4.1 案例问题描述

低碳物流运输的发展是势在必行的，车辆路径的优化是低碳物流最有效可行的措施之一。CVRP问题模型是最能体现现实生活中低碳物流的数学模型。某一物流运输公司A，在当地只有一个配送中心0，需要向20 个客户配送所需要的物品。已知配送中心有6辆车，车型都是相同的，车辆固定成本为100，容量为8，客户之间的运输成本与车辆行驶的路径有关。表2所示为配送中心以及各客户的坐标位置以及需求信息。

4.2 参数设置及结果分析

算法所在的实验平台为Window7、64 bit系统、32 GB内存。采用MATLAB 2017b进行环境仿真实验。

经过多次仿真试验,在参数T0=50、α=0.85、U=100、L=30、tf=0.01时，得到结果为840.134 5，耗时为4.656 s，选取30次仿真测试中优化结果最好的一次，路径对比如图5所示，成本收敛曲线对比如图6所示。

表2 配送中心与各客户的坐标位置以及需求信息

图5 20位客户的仿真车辆路径对比Fig.5 Simulated vehicle path diagram of 20 customers

图5(a)和图5(b)分别为配送中心和客户之间两种算法SA和GSSA的路径对比，基本模拟退火算法和改进的模拟退火算法相比明显没有基于黄金正弦的模拟退火算法路径优化路程短，证明该改进算法的良好性能，对求解车辆路径问题有很好的全局优化效果。

由图6可知，两种算法在50次迭代以内均达到了最优的结果，且之后一直保持，但是GSSA的结果明显优于基本SA，收敛性极强，仿真曲线表明GSSA具有很强的稳定性，全局收敛速度快，收敛精度高。

图6 算法运行优化过程中成本的对比收敛曲线Fig.6 Convergence curve of costs during algorithm operation optimization

路径仿真测试结果如表3所示。为证明本文的改进算法的优越性，与其他文献的结果作相应的对比。为显示测试的公平性，与对比文献均采用相同的数据信息，设置相同的参数，对比结果如下。

文献[16]中采用改进蚁群算法对该问题进行求解，相同参数下求得最优路径平均值为863. 44，单次最优为855. 68，优化效果一般，没有达到最优结果。

文献[17]中采用模拟退火算法对VRP中的TSP进行了求解，但求解点数过少，仅对10个节点进行了优化，而本文中提出的基于黄金正弦的模拟退火算法用于VRP的求解，对20个节点数据的客户需要进行了配送求解。结果表明：最优解比改进前的优化解更低，优化能力更强。

文献[18]中采用模拟退火算法对本案例进行了求解，算法设计较为简单，设置相同的参数求得最终运输费用为855.68，很明显优化效果并没有本改进模拟退火算法的优化能力强。

文献[19]中采用遗传算法对本案例进行了求解，车辆数目为6，其运输成本结果为964.48。本改进模拟退火算法设置相同的参数及车辆数目，测得最终结果为845.99。相较之下，本文的改进算法所求得的成本最优，具有更好的全局优化性能。

表3 路径仿真测试结果

5 结论

针对模拟退火算法容易陷入局部最优、收敛速度慢、收敛精度不高等缺点，提出了一种基于黄金正弦的模拟退火算法。该算法以黄金正弦算法优化模拟退火的初始值，第二阶段增加了邻域搜索方式，随机协作提高模拟退火算法的搜索能力；增加记忆装置，记录迭代到目前为止适应值最小值，避免陷入局部最小值；适当提高物体下降温度，增加物体内部活跃性，加大可接受解的范围，很大程度上优化了算法的性能。通过一个运输实例对该改进算法进行了仿真实验，实验结果证明该改进算法解决车辆路径问题具有很好的全局优化效果，对于缩短配送路程、降低碳排放、降低成本费用的城市绿色物流有着很强的实用意义。

燃油车辆运输无论怎么缩短路程、降低排放，都会不同程度地对环境造成污染，所以就需要更加清洁的新能源车辆、电动车辆等来代替燃油车辆，而且吨公里指标的设置能更好衡量油量消耗和碳排放成本，都是未来物流运输市场的新趋势，可为绿色物流及管理提供更多尝试的新方向。