基于混合遗传算法的低碳物流配送路径优化

2022-04-15胡巧丽兰建义河南理工大学工商管理学院河南焦作454000

物流科技 2022年4期

胡巧丽，兰建义（河南理工大学工商管理学院，河南焦作 454000）

0 引言

随着当前世界经济环境污染和全球能源供应枯竭的双重问题日益严重，低碳、绿色和环保发展问题日益得到了社会人们的密切关注。在2015年召开的旨在降低碳排放的巴黎会议上，我国政府承诺到2030年单位GDP二氧化碳排放比2005年下降60%～65%。要实现十四五计划的节约式绿色经济，重点就要强调绿色低碳经济的发展，十年内碳排放量达顶峰，2060年前实现碳中和，它揭示了低碳经济模式是人类社会可持续发展的必然趋势。近几年物流服务行业发展快，已成为我国能源消耗及碳排放量大户。企业要在减少经济成本的同时，考虑到经济利益和社会环境的约束，优化物流网络总体设计结构，实现双赢互利。

1959年，Dantzig和Ramser首次提出了车辆路线问题（Vehicle Routing Problem，VRP）指满足某种经济限制条件下达到一定的目标。关于物流运输路径优化的文章不少，例如Roberto等建立VRP模型以减少碳排放，加入汽车速度、坡度等变量，在增加额外运营成本情况下，实现碳减排。Moghaddam等研究了在不确定需求情况下VRP问题，有助于确定可靠计划及运输线路，增加客户满意度。基于VRP在物流配送领域的广泛性和应用价值，考虑距离和燃油因素时再重点关注带时间窗的低碳VRP。硬时间窗虽能准时完成配送，但刚性作用过强，会直接造成低货车装载率、长距离高速迂回行驶等不良情况。而软时间窗有利于柔性配送与运输成本的降低。本文重点研究带软时间窗的VRPTW。例如Qureshi在时间窗惩罚约束基础上提出软时间窗约束，由于配送过程的不确定性导致任务在所需时间范围内不一定完成，如果提前或超过规定时间配送，则直接设置惩罚函数来解决时间因素的相关问题。由于该类问题是典型的NP-hard问题，求解算法有精确和启发式算法。精确算法适用于规模较小的组合优化问题。启发式算法可求得问题的次优解或以一定的概率求最优解，其稳定、通用及快速收敛是目前衡量的主要标准，包括节约法、模拟退火法、禁忌搜索法、遗传算法、蚁群算法等。遗传算法运算速度虽快，但实现其通用编程语言较复杂，节约法会存在组合点混乱的问题。上述算法单独使用会早熟且求解质量不高。即本文将全局求解质量高的遗传算法与局部求解质量高的模拟退火算法结合，对遗传算法求出的解多次模拟退火寻优，构造一种混合遗传算法求解带时间窗的低碳VRP。

1 物流配送路径优化问题数学模型

1.1 构建带软时间窗的车辆路径问题模型

1.1.1 问题描述

带时间窗限制的VRP问题相对于基本VRP问题要额外考虑运送时间约束，若未在客户规定的时间窗内完成配送会产生经济损失，包括早到闲置等待机会成本和晚到惩罚成本。假设仅有一个配送中心，多辆车向多家配送服务点送货，每个配送点的地理坐标和平均运货量一定，每辆车的平均载重量也一定，配送中心在满足客户的需求及可接受服务时间的条件下，要求有效实现汽车运行线路的合理安排，使总运输距离最短，最终车辆服务完每个客户后返回配送中心。

鉴于实际问题的复杂及不确定性，对带软时间窗的VRP做出基本假设：（1）配送中心有且仅有一个，且能满足所有客户的货物装载；（2）车辆从配送中心出发服务完所有客户，最终返回配送中心；（3）车辆为同种运输车型，其运输总量不能超出其承载容量限制且每位客户的需求量小于车辆承载容量；（4）每位客户的位置坐标、需求量和服务时间和接受服务时间都是已知的；（5）到达和离开某个客户点的车辆都只能是同一辆车；（6）所有车辆必须在规定的时间内返回配送中心；（7）每位客户必须且只能被访问一次；（8）城市路网完全通联，不考虑交通堵塞或交通管制等不可通行情况。

1.1.2 模型中符号和决策变量

表1 变量定义

1.1.3 模型建立

目标函数：

以总成本最小为目标函数，其中第一项为配送车辆的运输成本，第二项和第三项为时间窗约束的定量表示。

1.2 构建带软时间窗的低碳VRP模型

1.2.1 问题描述

本节研究的软时间窗的低碳VRP是建立在前一节基础上，考虑车辆固定用途、燃油消耗、碳排放等费用，求解目标函数总成本。对碳排放量计算，本文考虑了燃油消耗和运输距离的关系，假设二氧化碳排放与油耗成正比，不考虑行驶速度、路况等因素的影响，得出燃油总的消耗量，再通过燃油转换系数转化为该次二氧化碳的排放量，通过对每单位二氧化碳环境成本进行定义，得到最终的二氧化碳的碳排放成本。

1.2.2 模型中符号和决策变量

表2 变量定义

1.2.3 模型建立

（a）目标函数

第一项为车辆配送的固定成本，第二项为车辆配送的运输费用，第三项和第四项为时间窗的定量表示，第五项为配送车辆的燃油消耗费用，第六项为二氧化碳排放的环境费用。

（b）约束条件

2 带软时间窗的低碳VRP的遗传算法设计

2.1 带软时间窗的低碳VRP的遗传算法分析

2.1.1 算法流程分析

遗传算法由美国Michigan大学Holland教授基于“优胜劣汰、适者生存”原则对目标函数进行优化，本质是一种高效全局性搜索智能算法，具有强大的鲁棒性和全局寻优能力，适合求解多极值和组合性的问题。如图1为遗传算法的工作流程图。

图1 遗传算法流程图

2.1.2 算法实现的具体步骤如下：

（1）改进染色体编码。采用直接编码方式，有个客户，将1～（+ 1）自然数随机排列，0表示配送中心，将-1个0随机插入该排列中，由辆车向按1,2,…,编号的客户送出，最后返回配送中心。根据客户的需求安排路径子串，在首尾加0，形成染色体。例如染色体“01402350”表示用2辆运输车辆从配送中心出发给5个客户进行配送，共形成两条路径的配送。路线1：0→1→4→0；路线2：0→2→3→5→0。

（2）种群初始化。种群生物初始系统是遗传算法的一个起点，它会对生物进化后的结果产生很大的直接影响。上述随机程序生成的染色体序列构成一条新的染色体，考虑到实际情况，将初始种群规模设定为100。

（3）计算适应度值。染色体的好坏用适应度值来衡量，适应度值代表最优解的优良程度，在交叉、变异等算子和约束条件下，形成一个个体适应度函数。本文的研究目标是最小配送路径，可对目标函数取倒数，实现最大值与最小值之间的转换，目标函数值越小，适应度函数值越大，适应性越强，个体就越优秀，反之个体越差，即：

（4）迭代判断与局部搜索。设置最大进化代数，判断迭代次数达到预设进化代数时，则停止迭代；否则将迭代次数加1继续迭代。再选取最优个体进行局部搜索，直至获得最佳解。

（5）遗传选择操作。同时采取最优个体保留战略和轮盘赌法。将最优个体即适应度最高个体直接复制到下一代。再用轮盘赌，将该种群的所有可用染色体累加得∑F，再计算每条染色体适应度值在体中占比即F/∑F,即为该染色体选中概率。

（6）交叉操作。在遗传算法中，交叉操作是将两个随机的染色体交换某些基因，产生两个新的基因组合，从而产生两个新个体。除第一条直接复制的最优染色体以外，其余均以交叉概率为基础进行配对。由于一个客户只能由一辆运输车辆完成配货，即染色体的编码中不会产生重复基因代码。例如：本文对种群中个体交叉采用随机交叉方式，设有9个配送点，有两个染色体（0620954078310）和（ 0510793082460）。去掉配送中心0变为（629547831）和（517938246），再随机产生交叉位置，将父代中间部分放在对方前面，如果有重复基因则删除本身重复数字，从而产生两个新染色体。例如随机选择第二位和第五位为交叉点，则染色体分别为=62|954|7831，=51|793|8246，将染色体中间交配区域加到染色体前面，同理将染色体中间交配区域加到染色体前面：得到=793|629547831，=954|517938246；再分别删除、交配后与交配区域相同的自然数编码，得到最终的下一代染色体为：=793625481,=954173826。最终在原有位置重新加载四个0，即最后（=0790362054810，=0950417038260）此法即使是父代相同，也可以产生新的子代。

（7）变异操作。变异操作是指在种群中随机选择个体的变异位置，对该基因串的某些个体进行改变，染色体中的一部位发生相应变化，另一部位也会发生相应变化，保证了种群的多样性与算法收敛性。例如：染色体793625481上的6发生了变异，变为1，则1位上也发生变异，变为6，即得到新染色体793125486。

2.2 带软时间窗的低碳VRP的混合遗传算法分析

模拟退火算法避免了局部最优，可确保全局最佳解的可靠度，通用且适应于并行处理，但运行时间长、收敛速度慢。遗传算法虽可在更大概率下搜索出最优解，但易早熟、局部搜索能力差、控制变量多。若将模拟退火引入遗传算法的交叉运作中，使两种算法结合形成一种混合遗传算法，使遗传算法能接收所有解，包括优良解和劣质解，避免在“早熟”解中陷入困境，增强遗传算法整体收敛性，还可提高进化速度，求得全局最精确解，同时将遗传算法的迭代次数作为模拟退火算法的退火时间。

2.2.1 算法实现步骤

（1）首先确定种群规模大小，交叉概率P，变异概率P，初始退火温度，降温系数θ；

（2）对个体进行编码，随机产生个个体，计算个体的适应度值；

（3）对个体进行选择操作；

（4）分别对个体进行交叉操作和模拟退火工作；

（5）对个体进行变异操作；

（6）降温，θ,θ为一个［0,1 ］之间的常数，为迭代次数；

（7）判断个体是否达到进化代数，若达到则终止运算，否则转回步骤3；

（8）计算结束，得最优解。

2.2.2 混合遗传算法的构造

（1）编码。采用1,2,3,…,的自然数编码。

（2）适应度函数。