一种基于冷链低碳物流路径的混合优化算法

邵可南，吕成瑶，张帅帅，宫 婧

(南京邮电大学 理学院，江苏 南京 210023)

0 引 言

随着人们生活水平的提高，越来越多的人选择在线上购买生鲜商品。近几年，国内冷链物流运输市场逐步扩大，如何控制运输成本成为研究的热点。冷链物流是一种新型的物流运输方式，与传统物流运输有较大的不同。首先，冷链物流运输的车辆需要使用额外的电能对生鲜商品进行低温冷冻；其次，生鲜商品必须要长期保存在低温环境下，在运输过程中和卸货配送过程中的温度变化都会导致生鲜商品的变质腐败；再次，冷链运输对于配送时间窗的要求很高，物流运输车如果在客户期望的时间窗外到达客户点，无论是早到和迟到都会付出一定的代价；最后，冷链物流过程中使用了降温装置，造成的碳排放也会随之增大，要通过合理规划路径减少碳排放。

车辆路径优化问题(VRP)是一类经典的组合优化问题，这类问题的研究工作有着非常重要的理论意义和应用价值。其中，带有容量约束的车辆路径优化问题(CVRP)具有更高的现实意义，所以得到了学术界更加广泛的关注。目前，国内外学者基于CVRP模型，构建了很多冷链物流路径优化模型。Mansoureh Naderipour等[1]提出了考虑二氧化碳和氮氧化物排放以及开放时间窗的车辆路径优化模型。赵志学等[2]提出了考虑交通拥堵的冷链物流城市配送的绿色车辆路径优化模型。Ferani E.Zulvia等[3]提出了考虑运营成本、货损成本、碳排放量、客户满意度和时间窗的路径优化模型。刘虹等[4]提出了考虑客户厌恶度和总成本的冷链物流路径优化模型。徐松梅[5]提出了考虑了固定成本、运输成本、制冷成本的带时间窗路径优化模型。孙明明等[6]提出了考虑冷链物流配送过程中的时间成本、温度成本和货损成本的路径优化模型。

针对CVRP问题的求解算法，可以大致分为两类，即精确算法和智能优化算法。CVRP是一类典型的NP问题，精确算法虽然可以得到全局最优解，但是随着问题规模的扩大，算法带来的运算量会以指数级的速度增长，这是人们无法接受的。因此，绝大多数研究者都将关注点放在了智能优化算法上。20世纪70年代以来，伴随着仿生学和人工智能科学的发展，人们提出了一系列传统的智能优化算法，包括粒子群算法、禁忌搜索、模拟退火算法、蚁群算法、遗传算法以及人工神经网络技术等。随后，研究者们也提出了很多改进的智能优化算法。蒋丽等[7]提出了求解众包配送路径问题的改进蚁群算法。颜腾威[8]提出了求解VRP问题的改进和声算法。Ziauddin Ursani 等[9]提出了求解带时间窗VRP问题的局部遗传算法。Jean-François Cordeau等[10]提出了求解VRP问题的并行迭代禁忌搜索算法。Artur Pessoa等[11]提出了求解异构车队VRP问题的改进分支定价算法。庞凌[12]提出了结合烟花算法和遗传算法来求解异质车队VRP问题。李小川等[13]提出了求解多目标带时间窗VRP问题的文化狼群算法。殷亚等[14]提出了多种混合蝙蝠算法用以求解带硬时间窗的多目标车辆路径问题。

该文提出的冷链低碳物流路径优化模型是一个考虑综合运输代价、带有硬时间窗和容量约束的车辆路径优化问题模型(CVRP-TW)，并使用模拟退火—遗传混合算法进行仿真实验。

1 冷链低碳物流路径优化模型的构建

1.1 模型简述

根据冷链物流运输的特点及需求，该文构建了多车辆、带有硬时间窗约束和容量约束并且考虑综合运输代价的冷链物流运输模型(CVRP-TW)。模型的结构如图1所示。

图1 模型结构

为了界定研究的问题，提出以下假设：

只有一个物流中心，但有若干台冷链运输车，所有冷链运输车均为同一型号，运输商品全部是同一种生鲜商品。物流企业事先已经了解所有配送客户的准确位置、货物需求量、期望和接受的时间窗和卸货配送所需要的时间。冷链运输车的最大载货量不小于任一客户的货物需求量。物流企业有足够的冷链运输车以确保能够一次性完成整个运输配送过程。每个客户的货物只能由一台冷链物流车为其配送一次，并且所有客户的货物需求量都得到满足。所有冷链运输车在完成最后一个配送客户的服务之后需要返回物流中心。冷链运输车到达客户点的时间必须在客户可接受的时间窗之内。

基于上述假设，该文研究的问题描述为：在一次完整的物流运输过程，有一个物流中心，若干台冷链运输车和若干个客户参与其中，运输货物完全为生鲜商品。在保证配送客户货物需求量和可接受时间窗的前提下，合理规划路径，找到一个综合运输代价最小的配送方案。考虑的综合运输代价包括运输固定代价、车辆运输代价、制冷代价、货损代价、时间惩罚代价和碳排放代价。

1.2 模型建立

1.2.1 优化目标

根据问题描述，建立考虑综合代价的CVRP-TW模型，其中优化目标为：

minC=C1+C2+C3+C4+C5+C6

(1)

其中，C1至C6分别表示运输固定代价、车辆运输代价、制冷代价、货损代价、时间窗代价和碳排放代价。

(1)固定代价C1：

C1=mc1

(2)

其中，c1是每辆车的固定代价。

(2)车辆运输代价C2：

(3)

其中，c2是车辆行驶单位路程所造成的车辆运输代价，对所有车辆在运送回路上的距离求和并乘上单位运输代价即为车辆运输代价。

(3)制冷代价C3：

(4)

其中，p31为车辆行驶过程中单位时间产生的制冷代价，p32为卸货配送过程中单位时间产生的制冷代价，对车辆行驶时间和卸货配送时间分别求和乘上对应的单位制冷代价作为总的制冷代价。

(4)货损代价C4：

其中，p0为生鲜商品的单价，α为车辆行驶中的商品变质率，β为卸货配送过程中的商品变质率。一个客户点的商品，从物流中心出发到客户点会经历车辆运输的时间和之前客户点的卸货配送时间，在这段时间商品会产生变质，货损和时间的关系可以用线性关系刻画[15]。故对运输时间和卸货时间分别求和乘上货物量和相应的变质率作为各客户点的货损，再对所有客户点的货损求和并乘上商品单价作为总的货损代价。

(5)时间惩罚代价C5：

(6)

(7)

(6)碳排放代价C6：

其中，p51为冷链运输车早到单位时间的等待代价，p52为冷链运输车迟到单位时间的迟到代价。ε0为冷链运输车空载时行驶单位距离的油耗，εM为冷链运输车满载时行驶单位距离的油耗，q(k,i,j)为第k辆车行驶在地点i到地点j之间时的车辆载重量。E2为制冷设备工作单位时间产生的能耗，e为二氧化碳排放系数即单位能耗所排放的二氧化碳质量，p6为排放单位质量二氧化碳所产生的代价。式(8)计算了车辆行驶时发动机工作产生的能耗和制冷设备工作时产生的能耗(其中发动机工作产生的代价和车辆当前载重有关)，再乘上单位能耗产生的二氧化碳和单位碳排放代价作为总的碳排放代价[16]。

1.2.2 约束条件

根据上述问题假设，得到模型的约束条件。每个客户的货物需求量不能超过一台冷链运输车的最大载重量，即：

Qj≤QM,j=1,2,…,n

(9)

每个客户都被服务并且只能由一台配送车辆为其服务一次，即：

(10)

所有冷链运输车在完成最后一个配送客户的服务之后需要返回物流中心，即：

(11)

冷链运输车到达客户点的时间必须在客户可接受的时间窗之内，即：

(12)

2 求解CVRP-TW问题的模拟退火-遗传混合算法

CVRP-TW是一类典型的NP问题，需要使用智能优化算法对问题的解空间进行有效的搜索来寻找最优解。该文将使用一种模拟退火-遗传混合算法来求解CVRP-TW问题。

2.1 算法流程

Step1：初始化算法环境，输入原始参数，设置算法参数：种群规模np，初始选择规模ns，初始交叉概率pc，初始模拟退火算法执行概率ps，线性参数k1,k2,k3，进化代数M。置迭代数gen=1；

Step3：计算当前种群中个体的适应度，选择ns+⎣gen/k1」个体，并复制一部分个体填充新种群；

Step4：对当前种群中所有个体两两配对，依概率pc-k2gen进行交叉操作；

Step5：对当前种群中所有个体依概率ps+k3gen执行模拟退火算法；

Step6：gen=gen+1，若gen

2.2 算法实现

由于CVRP-TW问题的特殊性，为考虑算法的计算可行性，该文采用针对该问题的编码方式和解的更新操作。

(1)编码方式是自然数编码，具体方式为在每辆车的配送路径(即配送客户点编号序列)后加上0(最后一辆车不用加)。例如：1,2,3,0,4,5,6表示第一辆车配送客户点编号先后为1,2,3，第二辆车配送客户点编号先后为4,5,6。算法首先会生成一个配送方案集合。

(2)配送方案选择操作是选择ns+⎣gen/k1」个当前配送方案集合中的方案保留到下一代配送方案。其中最好的前5%配送方案直接保留，剩下的选择名额会根据适应度用轮盘赌选出，适应度为配送方案代价的倒数。最后对新集合最终适应度排名靠前的np-ns-⎣gen/k1」个配送方案进行复制填充入新集合。

(3)交叉操作是随机选择两个配送方案，再随机选择两个交叉点，互换选中的两个配送方案里两个交叉点之间的编码(0的位置不动)，再根据交换表更新非交换部分的编码。

随着高等教育体制改革的逐步深入，高校办学规模不断扩大，师生数量、资产购置、基建投资规模和经费总量都大幅度增长，高校在经费使用、基建工程、物资设备采购等方面拥有越来越多的自主权。因此，廉洁风险防控机制是高校规范权力运行、科学有序发展的必然要求，是完善大学治理体系、建设现代大学制度的现实需要，是加强高校干部队伍作风建设、推动学校预防腐败工作的有力抓手[1]。高校要围绕“人、财、物”等管理监督重点，加强廉洁风险防控机制建设。

(4)模拟退火算法中的配送方案的更新为随机选择的两点交换或三点轮换(0的位置可以改变，但0不能连续或在头尾)。

为保证配送方案的有效性，只要对配送方案本身进行改变，就要对新配送方案进行约束条件检测，确保配送方案集合里所有的配送方案都是可行的。SA-GA算法的实现流程如图2所示。

图2 SA-GA算法执行流程

2.3 算法小结

模拟退火-遗传混合算法(SA-GA)是通过对经典的遗传算法和模拟退火算法进行结合和优化形成的一种混合算法。经典遗传算法中的变异操作是保证遗传算法局部搜索精度的操作，该文将这个操作用模拟退火算法进行替换。此外，种群选择的规模、个体交叉的概率和对种群每个个体执行模拟退火的概率采用动态设置，以保证在算法执行初期能有较大的全局搜索范围，在算法执行中后期能够对相对固定的种群进行较大次数的迭代寻优，从而在搜索范围和求解精度两个方面尽可能保证算法的性能。

3 仿真实验设计与分析

通过仿真实验测试遗传算法的求解效果。问题参数设置如下：一个物流中心要向20个客户点提供冷链物流配送服务，共有四辆冷链运输车，冷链运输车行驶速度为50 km/h、最大载重量12 t，模型的参数如表1所示。

表1 仿真实验参数设置

续表1

3.1 仿真实验求解结果

使用上述设定数据进行模拟退火-遗传混合算法的实验仿真。设置算法参数如下：最大进化代数M=100，种群规模np=100，初始交叉率pc=0.8，初始模拟退火算法执行率ps=0.8，线性参数k1=3,k2=0.008,k3=0.002，模拟退火算法初始温度T0=126，终止温度Tf=91.7，降温系数αc=0.968 8，Markov链长度Lk=1。随机生成初代配送方案集合，执行20次模拟退火-遗传混合算法，得到最优代价为5 901.5，最佳配送方案中四辆冷链运输车的配送代价分别为1 453.6、1 509.7、1 417.0和1 521.2。在求解算法中每一次更新解都会进行约束条件检验，所以最优解是有效的。

3.2 实验结果与分析

为了验证算法的有效性，该文使用经典的遗传算法和模拟退火算法各进行20次实验仿真，三种算法的求解效果如表2所示，求解最优解时的收敛轨迹如图3所示。

表2 仿真实验结果比较

图3 收敛轨迹

根据表2所示，模拟退火-遗传混合算法相比前两种经典算法有着更好的求解性能，这主要体现在：

(1)求解效率提高。

模拟退火-遗传混合算法在相同次数的实验下比两种经典算法有着更小的平均收敛代数，意味着混合算法的搜索效率更好。从最优解的离散情况来看，混合算法的最小代价标准差介于两种算法之间。

(2)搜索范围较大。

模拟退火-遗传混合算法求出的最优配送方案的综合代价优于两种经典算法，这表明了混合算法的搜索范围是较大的，并且最优解没有陷入局部最优，收敛到全局最优。

(3)求解精度更高。

模拟退火-遗传混合算法的平均代价比两种经典算法要好，表明了混合算法在每个生成解的领域内有着较高的搜索精度。

模拟退火-遗传混合算法可以看作是模拟退火算法和遗传算法的一种折中方案。如果智能优化方法既要扩大搜索范围，又要提高求解精度，势必要增加运算量。所以模拟退火-遗传混合算法是旨在保持相同数量级运算量的前提下，对搜索范围和搜索精度的一种权衡。混合算法在执行的前期尽可能地扩大搜索范围，避免算法陷入局部最优解，在执行的中后期根据动态概率的设定尽可能使种群稳定下来，让模拟退火算法对于每个个体有尽可能大的执行次数，提高个体领域内的搜索精度，并且由于每个个体领域的搜索是独立的，也可以保证算法在中后期的搜索范围。上述实验结果也表明了模拟退火-遗传混合算法相对于前两种经典算法而言，是一种更加高效的智能搜索方法。同时，模拟退火-遗传混合算法实现简单，继承了遗传算法的鲁棒性和潜在的并行性，有着较高的实用价值。

4 结束语

根据当前冷链物流运输行业的需求，建立了带硬时间窗的冷链低碳物流路径优化模型，确定了以综合代价最优为目标的CVRP-TW问题。其后通过遗传算法和模拟退火算法这两个经典的智能优化算法对建立的模型进行仿真实验求解。之后根据遗传算法和模拟退火算法的优缺点，将两种经典算法进行改进和结合，提出了模拟退火-遗传混合算法。通过仿真实验模拟求解，验证了模拟退火-遗传混合算法在解决冷链低碳物流路径优化问题上有着更好的效率并且能给出更好质量的解。下一步考虑将这一算法应用到多物流中心和多配送车型等更多约束的路径优化问题的求解上。