改进遗传算法求解带模糊时间窗冷链配送问题
2016-07-28梁承姬徐德洪
梁承姬，黄 涛，徐德洪，丁 一
(1.上海海事大学科学研究院物流研究中心， 上海201306;2.西安外事学院物流学院， 陕西西安710000)
改进遗传算法求解带模糊时间窗冷链配送问题
梁承姬1，黄涛1，徐德洪2，丁一1
(1.上海海事大学科学研究院物流研究中心， 上海201306;2.西安外事学院物流学院， 陕西西安710000)
摘要：为优化冷链物流配送路径，降低配送成本、提高客户对产品送达时间的满意度水平是冷链物流的关键。考虑到冷链物流承载的货物具有一定的特殊性且对温度的要求较高，提出在冷链物流配送中设定模糊时间窗反映顾客满意度。建立了运输成本、货损成本、时间成本等配送成本最小化和以模糊时间窗进行量化客户满意度最大化的多目标优化模型，采用改进遗传算法求解带模糊时间窗冷链配送问题。通过算例分析，验证了模型和算法的有效性与研究的实用价值。
关键词：冷链物流;模糊时间窗;配送路径优化;遗传算法;顾客满意度
0引言
冷链物流作为物流产业一个新兴的、特殊的类别，正在当下国家振兴物流产业和冷链物流发展规划的背景下高速发展。冷链物流的特点是在整个供应链环节都需要对温度进行把控，这就使得冷链物流相对于传统物流成本更高，技术要求更强。在此基础上，冷链物流的车辆路径优化问题广受关注，车辆路径问题一直是物流配送中最重视的优化研究之一。Dantzig等[1]在1959年率先提出了车辆路径问题的数学模型，并对模型进行求解分析。杨丹婷[2]在研究冷链配送时通过分析C-W节约算法、遗传算法，粒子群算法三种算法，对不同算法的优化结果进行分析对比。廖小红等[3]考虑单个配送中心，多个客户点为第三方冷链配送模型，用改进遗传算法加以分析求解。刘志硕等[4]在研究VRP的过程中，将蚁群算法的思想引入进来，同时针对其特点通过具有自改变功能的混合蚁群算法来解决VRP问题。
冷链物流对时间有较严格的要求，但受到调度策略和交通等主观客观条件的制约，将出现不能在规定的时间范围内送达的情况。因此对车俩配送路径优化问题的研究，通常考虑时间窗的约束。Duygu等[5]通过加入灵活时间窗的约束，允许通过一定成本为代价超出部分时间窗，并和普通时间窗约束下的车辆路径问题对比，验证其可行性。Ali等[6]建立一个较为新颖的混合列生成和现代启发式算法的数学模型，加入一般软时间窗对车辆路径问题进行优化，并通过该算法评估算例实验。向金秀[7]从农产品冷链物流配送企业的角度出发，构造以总成本最小为目标的函数，进而得出了农产品冷链物流车辆配送路径问题的优化模型。李泽华[8]在考虑多种因素影响的条件下，研究构建成本最小化的带软时间窗的生鲜产品配送车辆路径问题的数学模型，通过自适应交叉率的遗传算法进行求解。王君等[9]提出文化基因算法求解带时间窗的物流配送车辆路径问题，遗传算法进行种群搜索，禁忌搜索机智进行局部搜索，然后通过可行邻域结构避免不可行解，有效提高效率。魏凯[10]研究了带有软时间窗的车辆路径问题，同时以遗传算法和模拟退火算法相结合，在全局搜索和局部搜索上有了显著提高，通过算例分析验证了可行性。邓爱民等[11]在考虑软时间窗、车辆的固定成本、满载系数等条件后，建立集配货一体化车辆路径问题数学模型。根据模拟退火算法，结合线路内和线路间交换，增加了记忆功能，采用了双终止准则求解。周屹等[12]考虑建立一种能使配送计划的安排在任何情况下都能统一为求解某种车辆路径问题，采用遗传算法计算第三方物流的带时间窗物流配送车辆路径问题的模型。林清国[13]通过分析比较遗传算法、禁忌搜索算法及模拟退火算法，以遗传算法为基础，提出混合遗传模拟退火算法及混合遗传禁忌搜索模拟退火算法优化带时间窗车辆路径问题。Ghodratnamaa等[14]在研究流水线的多目标优化模型中提出了采用多目标粒子群算法(MOPSO)和NSAGA II算法相结合的方法解决多目标问题。李淑琴等[15]在研究环保多车型组合配送路径时，考虑时间窗约束，采用模拟退火算法求解多目标环保多车型模型，以减少环境污染优化配送路径为目标，求解低碳路径优化问题。
综上所述，传统车辆路径问题的研究大多数采用的是单目标模型、考虑传统时间窗，忽略了目标的多样性和算法的计算时间等的有效性。由于冷链运输货物的特殊性，时间窗的设定往往需要更加灵活，与客户的联系更加密切，不仅需要考虑成本，还需要考虑时间和客户满意度。本文综合考虑了冷链物流配送中的成本、时间和客户满意度等因素，设置模糊时间窗来提高顾客的满意度，建立了配送成本最小化和顾客满意度最大化为目标的线性规划模型，不同于上述文献中多选择单一传统的算法求解，只能考虑个别约束条件对路径优化的影响，同时只解决时间最短的单一目标模型。本文采用改进遗传算法对多目标模型进行求解，增加基因修复确保算法求解符合约束条件，同时非支配排序和拥挤度策略进行解的优化。在求解多目标路径优化问题中，可以综合考虑多个约束条件，改进的遗传算法能更有效地符合实际情况，并使计算结果更加精确。
1问题描述
在冷链物流运输中，不同于传统运输配送只考虑距离成本因素，冷链运输需要全程的温度保证和时间把控。冷链货物从配送中心出发至各个客户点，需要一直调节货箱内的温度以保证冷链货物的质量，同时越短的配送时间和服务时间就越有利于货物的高质量，所以冷链运输的时间窗约束和温度能耗成本是关键所在，也是本文研究的重点。在该问题的研究中，考虑时间窗约束多为硬时间窗和软时间窗两种，硬时间窗即客户点的任务必须要在规定时间内完成，软时间窗则加入惩罚因子，如果车辆无法在规定时间窗内完成配送，将给予一定惩罚成本。
图1 带模糊时间窗配送图
2模型建立
2.1问题假设
为了便于模型的建立和问题的分析求解，设定假设：主要研究进口冷冻食品由配送中心面向附近各主要客户点的配送问题，各主要客户点位置已知，距离已知，需求量已知；配送车辆数量已知，载重量已知；车辆从配送中心出发配送，配送完成返回配送中心；每条配送线路上的客户点需求总量要求不大于配送车辆的最大载重量；货物类型只有一种，每个客户点只能被配送车辆遍历一次。
2.2模型分析
本模型主要参数：
k：配送的车辆总数，v=1,2，…，k；
n：接受配送的客户点，i=1,2，…，n，j=1,2..n；
a：车辆配送货物每千米运输成本；
dij：客户点i与j之间的距离；
qi：客户点i的需求量；
Q：车辆总载重量；
β：货物对时间的敏感系数；
p：冷链货物的价格；
α：装卸过程中的货损率；
δij：冷链运输中的货损系数；
λ1：提前服务所引起的惩罚成本；
λ2：延迟服务所引起的惩罚成本；
本文建立的是冷链配送问题的多目标模型，目标函数为最小化配送成本和最大化顾客满意度，其中最小化成本目标函数包括车辆运输成本、冷链货损成本和时间窗惩罚成本。
①车辆运输成本
车辆运输成本即车辆在从配送中心或上一个客户点运送至下一个客户点所产生的运输成本。该成本与配送路程有关，在计算时应通过决策变量判断车辆是否经过该处。运输成本表达如式(1)：
(1)
②冷链货损成本
该成本体现了冷链食品运输同其他产品配送的不同之处，由于食品的特殊性，在配送和服务过程中产生因温度、时间等导致的货损。在本文研究中，货损成本包括运输时间长短和在客户点服务时配送效率导致温度差两方面因素所造成的成本。货损成本如式(2)：
(2)
③时间窗惩罚成本和顾客满意度
本文建立的是基于模糊时间窗的多目标冷链配送优化模型。模糊时间窗的设立表示车辆应尽量在顾客要求的时间窗内服务，但不同于对固定时间窗的硬性要求，而是面对大多数非刚性需求时要求服务时间外也可以进行服务，但以部分成本作为惩罚，同时将车辆服务时间转化为顾客的满意度，更加直观全面地描述分析顾客需求。本文对模糊时间窗的分析设定如式(3)所示：
(3)
(4)
2.3模型建立
本文以最小化冷链物流配送的综合成本和最大化顾客满意度为目标建立数学模型。该模型综合考虑了时间窗，运输、货损等成本和顾客满意度，与传统冷链路径优化模型相比，可以相对全面地考虑冷链运输的车辆路径优化问题。这里为了方便多目标求解计算，把顾客满意度的最大化转化为最小化求解。
(5)
(6)
约束条件：
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
目标函数(5)表示建立最小化配送成本，最大化顾客满意度的目标模型,其中成本包括车辆运输成本、冷链货损成本和时间窗惩罚成本。目标函数(6)表示建立求解顾客满意度最大化。建立约束条件(7)和(8)保证车辆能遍历每一个客户点，约束条件(9)确保车辆容量不被超出总量，约束条件(10)和(11)保证车辆从配送中心出发配送，配送完成返回配送中心。约束条件(12)确保车辆对客户的服务发生在该客户的模糊时间窗内。约束条件(13)为提早服务时间，同样，约束条件(14)为延迟服务时间。约束条件(15)确保提早服务时间和延迟服务时间是非负的，即保证模糊时间窗存在。
3算法求解
图2 算法流程图Fig.2 The flowchart of algorithm
本文研究的是关于车辆路径的多目标优化问题，采用的是遗传算法求解。通过改进遗传算法求解pareto最优解集的多目标优化问题。这种方法能通过不同代之间的优化组成潜在的最优解种群来避免局部最优从而搜索pareto最优解。本文基于非支配排序遗传算法求解思想，改进自适应调整交叉率和变异率，较好的提高了收敛速度，通过对多目标函数的优化，最后得到Pareto最优解。与传统算法相比，在选择交叉后的基因修复可以有效地防止染色体不符合约束条件，合并新种群后的非支配排序和拥挤度计算又能提高对最优解选择的精确性。对在具体遗传算法求解过程中，求解流程如图2。
首先生成初始种群，在父代种群通过联赛选择生成临时较优种群，然后对较优种群进行先交叉再变异。交叉采用多点交叉，相对于单点交叉更有利于搜索能力和求解精度的提高，变异采用逆转变异策略，与交叉策略同理。将交叉变异后的较优子代种群与父代种群进行重组(根据非支配排序和个体拥挤度距离的计算)生成新种群，最后满足进化计算达到最大设定的进化代数的终止条件即终止计算，否则进行算法重启，重新计算。
3.1染色体编码
考虑到车辆路径优化问题的特点，单纯针对客户的编码方式，或者针对车辆路径的编码方式不能完整的对该问题有效处理，同时由于还要考虑模糊时间窗的优化以达到顾客满意度最大的效果，所以本文采用的编码形式是自然数编码。染色体编码如图3所示，一个车辆路径配送方案对应的染色体基因个数为(客户点数量+车辆数-1)，各基因值为客户点编号，“0”基因为不同车辆间的间隔符号，“0”基因的个数为(车辆数-1)，例如10个客户点由3辆配送车完成的一个配送方案对应的染色体结构及说明如图3所示。这样的编码结构简单直接，从图3中可知，车辆1、车辆2和车辆3服务的客户点以及服务客户点的顺序分别为8-5-2，10-1-7-4，3-9-6。
3.2生成初始种群
初始种群是由一定数量染色体组成的群体，本文采用的是随机生成一定数目的个体。首先任取n个基因(n=车辆数-1)，基因值设为间隔符号“0”，然后随机将车辆编号设定给剩余的基因位，这样就可以形成初始种群。同时设定间隔符号不能出现在基因整体的首末位或两个间隔符号“0”相邻，来确保种群的有效意义。
图3 染色体编码图
3.3适应值函数
遗传算法中，衡量一个个体质量优劣的标准是适应度。适应度是评价个体优劣和进行遗传操作的重要依据，个体的适应度越大，被选择到下一代的概率越大。本算例中选取目标函数的值为适应度值。即Fi=minLP1-100 n(minLP2)的形式，其中由于目标函数LP2是0到1内的小数，代表的是客户对服务的满意程度，对适应度函数的影响程度较小，所以选择100作为变换因子，将顾客满意度转化为费用。
3.4选择操作
3.5交叉操作
针对本文染色体编码的特点，提出随机顺序交叉方法。第一步，随机在父代的基因位中选择两个交叉点，交叉之间的基因位将被父代直接复制到下一代。第二步,为避免重复基因，将父代a和b基因中分别已经被父代b和a复制了的基因删除。第三步，把a和b剩余的基因按顺序分配到b和a的子代。这样就得到了完整的没有重复基因值的两个子代。交叉方法如图4所示：
图4 顺序交叉
3.6变异操作
变异操作有助于局部搜索能力的提高，同时可以保持群体的多样性，防止早熟现象的发生。本文选择逆转变异方法，即在基因位中随机选择两点，再将这两点内的基因按反序插入到原来的位置中。如图5所示。因为染色体中的间隔符“0”没有实际意义，所以规定逆转变异操作中不同时选择个体的两个“0”基因进行交换。
图5 逆转变异
3.7基因修复
在交叉和变异操作后，染色体将产生一些不符合模型约束条件和编码规则的情况。因此笔者针对不符合条件的染色体进行基因修复操作，具体步骤如下：
Step 1：在交叉后，当配送车辆的数量多于两辆时，染色体中有多个“0”出现，判断是否存在删除过多的“0”导致个体不一样长。如果存在，则规定只删除首次重复基因，如果不存在转step 2；
Step 2：判断染色体在交叉变异后是否存在间隔符“0”相邻或处于基因链首末位的情况，这种情况会导致有车辆闲置，应修复该位置的基因，完成基因修复。
3.8非支配排序和拥挤度策略
多目标优化问题的设计关键在于求取Pareto最优解集。NSGA-Ⅱ算法中的快速非支配排序是依据个体的非劣解水平对种群分级，其作用是指引搜索向Pareto最优解集方向进行。高媛[16]在研究非支配排序遗传算法NSGA-Ⅱ中，扩展算法的应用范围，提出一种新的解决函数拟合问题的方法。本文通过引入NSGA-Ⅱ算法思想求解多目标冷链配送模型。在非支配排序和拥挤度策略中，与传统计算方法相比，简化了搜索和计算步骤，以保持种群的多样性和避免算法发生早熟收敛。在整体算法安排中，改进了计算顺序，先通过遗传算法操作形成新的子代，与父代合并后再进行非支配排序和拥挤度策略。采用这种求解步骤，有利于扩大Pareto最优解集的搜索范围，它是一个循环的适应值分级过程，如图6以及下列流程所示：
非支配排序：
①让等级计数r变为0；
②使得r=r+1；
③从种群中找出非支配解集，设为第一级，将其所有个体赋予非支配级r；
④把赋予非支配级的个体从种群中删去；
⑤判断种群是否为空，是，则停止运算，不是，则到第二步继续运算；
拥挤距离计算：
①初始化每个个体i拥挤度为0，即：di=0, i=1,2,…,Z；
②对于每一个目标函数fk，k=1,2,…,n升序排序成组；
③设置两端个体的拥挤度：d1=dZ=∞；
④令j=2到(Z-1)，设dj=dj+(fkj+1-fkj-1)。
拥挤度选择算子：经过排序和拥挤距离的计算，群体中每个个体i都得到两个属性，一个是非支配级r，另一个是拥挤度di。根据结果，定义选择排序规则：x>yifrx
图6 NSGA-Ⅱ流程图
4算例分析
表1 客户点初始数据
根据表1数据，利用改进遗传算法解决多目标冷链配送车辆路径问题，通过计算获得帕累托最优解，如表2和图7。
图7 Pareto最优解图Fig.7 Figure of pareto optimal
解集配送总成本顾客满意度1(A)4350.99323950.96733600.9534(B)3320.94153010.9162930.877(C)2830.82
由图7得出，最优方案为B点，即目标函数1的值为332元，目标函数2的值为0.941，即完成该算例中的冷链物流配送所需的配送总成本为332元，同时顾客满意度为94.1%。车辆在配送中访问的路径顺序见表3。
由于本文是基于改进遗传算法求解的多目标冷链配送问题，所以在相同控制参数条件下，利用标准遗传算法，针对该问题进行搜索。搜索过程中的种群代数、染色体个数和变异概率等控制参数与上述改进遗传算法中的完全相同，得到最优配送路线如表4，冷链物流配送所需的配送总成本为461元，顾客满意度为87.3%。
根据表3和表4结果对比得知，基于改进遗传算法求解得到的最优访问路径，能够多方面考虑冷链配送优化，通过pareto最优求解有效兼顾成本和顾客满意度的双重优化，不仅配送总成本优于标准遗传算法，同时保证顾客满意度达到相同成本下的最优，更能接近理想解。因此，本文采用改进的遗传算法，在求解冷链货物配送路线优化问题时明显优于标准遗传算法。
表3 基于改进遗传算法的多目标任务结果表
表4 基于标准遗传算法的多目标任务结果表
5结语
根据冷链物流配送中实际考虑的因素，本文建立了以运输成本、货损成本，时间成本等成本优化和顾客满意度优化为目标的多目标数学模型。成本模型中以货损系数来突出货损成本，时间窗惩罚来突出时间成本的控制。在考虑成本的同时，设立模糊时间窗，综合考虑顾客满意度，达到成本最小化和顾客满意度最大化的优化效果。通过改进的遗传算法，考虑NSGA-Ⅱ算法的非支配排序和拥挤度计算因素，进行求解，获得了Paretp最优解。在算例分析的实际验证中表明该算法对解决冷链物流配送问题有良好的效果。
参考文献:
[1]DANTZIG G,RAMSER J.The truck dispatching problem[J]. Management Science, 1959 (6): 80-91.
[2]杨丹婷.冷链物流配送路径优化研究[D]. 大连:大连海事大学,2014.
[3]廖小红,周新年,林森,等.第3方冷链物流配送路径优化研究[J]. 运筹与管理,2011,8(4):32-38.
[4]刘志硕,申金升,柴跃廷.基于自适应蚁群算法的车辆路径问题研究[J]. 控制与决策,2005,20(5):562-566.
[5]DUYGU T, OLA J, TOM V W. A vehicle routing problem with flexible time windows[J]. Computers & Operations Research,2014,52:39-54.
[6]ALI K B,SEYED R H,A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window[J]. Information Sciences,2015,316:598-615.
[7]向金秀.带时间窗的农产品冷链物流车辆路径问题研究[D]. 大连:大连海事大学,2011.
[8]李泽华.带时间窗约束的生鲜产品配送车辆路径优化问题研究[D]. 大连:大连海事大学,2009.
[9]王君,李波.带时间窗车辆路径问题的文化基因算法[J]. 计算机工程与应用,2012,48(7):26-29.
[10]魏凯.改进遗传算法在软时间窗车辆路径问题中的应用[D]. 安徽:安徽工业大学,2013.
[11]邓爱民,毛超,周彦霆.带软时间窗的集配货一体化VRP改进模拟退火算法优化研究[J]. 系统工程理论与实践,2009,29(5):187-192.
[12]周屹,李海龙,王锐.遗传算法求解物流配送中带时间窗的VRP问题[J]. 吉林大学学报,2008,46(2):300-304.
[13]林清国.基于混合遗传算法的有时间窗车辆路径问题研究[D]. 山东:山东大学,2007.
[14]GHODRATNAMAA A, JOLAIB F, TAVAKKOLI-MOGHADDAMB R. Solving a new multi-objective multi-route flexible flow line problem by multi-objective particle swarm optimization and NSGA-II[J]. Journal of Manufacturing Systems,2015,36:189-202.
[15]李淑琴,杨斌,赵磊,等.需求带时间窗的环保多车型组合配送路径优化[J]. 广西大学学报(自然科学版),2013,38(2):388-394.
[16]高媛.非支配排序遗传算法(NSGA)的研究与应用[D]. 浙江:浙江大学,2006.
(责任编辑梁碧芬)
收稿日期：2016-01-22；
修订日期：2016-02-21
基金项目：国家自然科学基金资助项目(71471110；71301101)；中国博士后科学基金资助项目(2014M550084)；上海市科委资助项目(14170501500)；陕西省社会科学基金资助项目(2015D060)
通讯作者：梁承姬(1970—)，女(朝鲜族)，吉林龙井人，上海海事大学教授；E-mail:liangcj@shmtu.edu.cn。
doi:10.13624/j.cnki.issn.1001-7445.2016.0826
中图分类号：TP301.6
文献标识码：A
文章编号：1001-7445(2016)03-0826-10
A solution for cold chain distribution with fuzzy time window based on improved genetic algorithm
LIANG Cheng-ji1, HUANG Tao1, XU De-hong2, DING Yi1
(1. Logistics Research Center, Shanghai Maritime University, Shanghai 201306, China;2. Logistics Institute Xi’an International University, Xi’an 710000, China)
Abstract：The key problemsto optimize the path of cold chain logistics distribution include reducing the cost of distribution and improving the customer satisfaction level of product delivery time.Considering the specificity of cold-chain logistics and higher requirements for temperature,fuzzy time windowreflecting customer satisfactionis introduced into cold chain logistics distribution.A multi-objective mathematical model is established, which is to minimize the distribution costs including transportation costs, damage costsand time costs, and to maximize the customer satisfaction quantified by fuzzy time window.The model is solved by an improved genetic algorithm. The effectiveness of the model and the algorithm is verified by a certain example.
Key words：cold-chain logistics;fuzzy time window; distribution path optimization; genetic algorithm; customer satisfaction
引文格式： 梁承姬，黄涛，徐德洪,等.改进遗传算法求解带模糊时间窗冷链配送问题[J].广西大学学报(自然科学版)，2016，41(3)：826-835.
