集货需求模糊的异型车同时配集货路径优化

范厚明,刘 浩,刘鹏程,任晓雪

(大连海事大学交通运输工程学院,辽宁大连 116026)

1 引言

车辆路径问题自1959年被提出以来[1],引起了众多学者对其研究,并通过将不同约束加入到经典车辆路径问题(vehicle routing problem,VRP)问题中,使其越来越贴近于实际,逐步衍生出同时配集货车车辆路径问题(vehicle routing problem with simultaneous delivery and pickup,VRPSDP)、异型车辆路径问题(heterogeneous fleet vehicle routing problem,HFVRP)及模糊需求车辆路径问题(vehicle routing problem with fuzzy demand,VRPFD)等.本文研究的集货需求模糊的异型车同时配集货车辆路径问题(heterogeneous fleet vehicle routing problem with simultaneous deterministic delivery and fuzzy pickup,HFVRPSDDFP)是综合考虑了VRPSDP,HFVRP以及VRPFD问题特点而形成的科学问题.现实中,如饮料供应商的配送中心使用不同型号的配送车辆,依据客户需求订单对客户进行配送服务的同时回收可再使用容器(空瓶)、过期饮品,其中配货需求依据订单是确定的,回收空瓶及过期饮品(集货需求)往往是不确定的,具有模糊特征;同样,玻璃厂依据订单配送玻璃的同时回收碎玻璃;医疗药品配送的同时回收过期药品等,都是物流生产过程需要解决的问题.因此针对HFVRPSDDFP展开研究具有理论和现实意义.

有关VRPSDP,HFVRP和VRPFD问题近年来已经成为VRP扩展问题研究的热点.针对VRPSDP的研究,刘玲等[2]对需求可拆分的VRPSDP问题进行研究,设计变邻域搜索算法对问题进行求解.Zhu等[3]对带有随机需求的VRPSDP问题进行研究,设计自适应大邻域搜索算法对问题进行求解.王超等[4]研究了带有时间窗的VRPSDP问题,设计离散布谷鸟算法对问题进行求解.Shi等[5]研究了带有随机旅行和服务时间的VRPSDP问题,并采用Gurobi、混合遗传算法、模拟退火算法、蝙蝠算法和萤火虫算法5种方法进行求解.盛虎宜等[6]对多配送中心的VRPSDP问题进行研究,设计了改进蚁群算法对问题进行求解.可见,众多学者已经从需求可拆分、随机需求、时间窗、随机旅行及服务时间和多配送中心等方面深化了对VRPSDP问题的研究.

针对HFVRP问题的研究较多,葛显龙等[7]研究了以固定成本和油耗费用之和最小为优化目标的HFVRP问题,设计量子遗传算法对问题进行求解.田宇等[8]对带有多车场的HFVRP问题进行研究,设计多属性标签蚁群算法对问题进行求解.潘雯雯[9]等研究了需求可拆分多的HFVRP问题,设计了包括离散型人工蜂群算法和禁忌搜索算法在内的两阶段算法对问题进行求解.郭海湘等[10]对单车场的HFVRP问题进行研究,设计混合蚁群算法求解该问题.Penna等[11]对HFVRP问题进行研究,设计了结合迭代局部搜索和可变邻域下降算法的混合元启发式算法对问题进行求解.Bevilaqua 等[12]对HFVRP 问题进行研究,设计基于文化基因算法的混合算法求解问题.仝凌云等[13]对以低油耗为优化目标的HFVRP问题进行研究,设计了融合邻域搜索算法的混合模拟退火算法对问题进行求解.部分学者综合考虑了HFVRP 和VRPSDP 的特点,对同时配集异形车辆路径问题(heterogeneous fleet vehicle routing problem with simultaneous delivery and pickup,HFVRPSDP)问题进行研究.陈妍等[14]研究HFVRPSDP问题,设计了模拟退火算法对问题进行求解.Kececi等[15]对HFVRPSDP问题进行研究,设计了一种三阶段算法对问题进行求解,即先通过聚类方法为顾客分组并分配车辆,再通过局部搜索算法进行第2阶段的路径间优化和第3阶段路径内优化.Avci等[16]对HFVRPSDP问题进行研究,设计一种阈值调整策略与禁忌搜索算法相结合的混合局部搜索算法.王旭坪[17]对考虑时空距离的HFVRPSDP问题进行研究,设计了变邻域算法进行求解.Madankumar等[18]对带有时间窗的HFVRPSDP问题进行研究,应用CPLEX对该问题进行求解.

目前还未见针对HFVRPSDDFP的研究,但已有一些学者对VRPFD问题进行了研究.曹二保等[19]研究了VRPFD问题,建立基于模糊可信性理论的模糊机会约束规划模型,设计基于随机模拟的混合差分进化算法对问题进行求解.Erera等[20]对VRPFD问题进行研究,设计了一种禁忌搜索算法对问题进行求解.张晓楠等[21]研究了VRPFD问题,提出了根据车辆载货量和路径上待服务顾客总需求的关系来确定失败点的失败点前序点返回策略,设计变邻域分散搜索算法对问题进行求解.Shi等[22]研究了带时间窗限制的VRPFD问题,将其应用于家庭保健公司的药物配送中,提出了一种与随机模拟方法相结合的混合遗传算法对问题进行求解.李阳等[23]对VRPFD问题进行研究,提出两阶段变邻域禁忌搜索算法对问题进行求解,针对服务失败的客户点,提出失败点重调度策略进行调整.范厚明等[24]对带有模糊时间窗的VRPFD问题进行研究,设计了一种混合遗传算法对问题进行求解.

综上,现有研究为本文的研究提供了有意义的参考,但还存在以下不足:

1) 对于HFVRPSDP问题的研究所涉及客户点的配、集货量多为确定型,没有考虑现实生活中客户需求的模糊性和不确定性.

2) 在VRPFD的研究中,由于服务失败后的配送策略多是在以距离为优化目标的情况下制定的,多采用点返回策略(失败点返回策略和失败点前序点返回策略),发现失败点后多采用在运输途中某点处直接返回车场,再次派遣车辆对路径中剩余顾客点服务的运输策略,导致固定成本的增加.

3) 现有HFVRP研究在选择车型时,多制定一定的选择规则(优先使用大车型,优先使用小车型等)或先将客户分组再按组内车辆配送需求量选择车型最后优化,前者的做法没有考虑路径优化和车型分配的关系,可能导致最优解的丢失,后者的做法易使解陷入局部最优,仍可能会造成最优解的丢失.

针对上述不足,本文对集货需求模糊的异型车同时配集货车辆路径问题(HFVRPSDDFP)展开研究;根据研究问题特征,设计了本文失败点服务策略,允许车辆在遭遇失败点后继续为路径中剩余客户点服务,充分利用了车辆装载能力,减少使用车辆数目;根据路径安排和客户点需求计算车辆载率,以此为路径选用车型,设计了编解码方式,采用分别记录客户排列、车辆服务客户、车辆车型的方法,使算方总能生成可行解,不易陷入局部最优.构建了两阶段HFVRPSDDFP模型,预优化阶段基于可信度理论构建模糊机会约束规划模型,重优化阶段为未被完全服务的客户点重新规划路径.设计遗传变邻域算法对问题进行求解,并通过3种算例对模型和算法进行验证.

2 问题描述及模型建立

2.1 问题描述

本文研究的HFVRPSDDFP问题描述如下:假设有完备的有向图G=(V,E),所有节点集合V={0}∪V0,节点0表示配送中心,V0={1,2,···,n}表示客户点集合,E为连接各个节点的所有边的集合,E={(i,j)|i,j ∈V}.

1) 配送中心和客户点.

di:客户点i的配货量.

lij:点i与点j之间的距离.

L:距离矩阵,有L=(lij)nn.

2) 车辆.

R:配送中心可用车型集合,R={1,2,···,r,···,φ},φ为车型种类数.

K:各车型车辆的集合,K={K1,K2,···,Kr,···,Kφ},Kr为r型车集合.

kr:某一辆r型车,kr ∈Kr.

Qr:r型车的容量.

crf:每辆r型车的派遣成本.

cr1:每辆r型车在空载时的单位距离油耗成本.

cr2:每辆r型车在满载时的单位距离油耗成本.

3) 决策变量.

车辆配集货过程中涉及的上述各参数、变量如图1所示.

图1 带有参数和变量的车辆服务过程示意图Fig.1 Vehicle service diagram with the parameters and variables

本文需要解决的问题是合理选择不同车型的车辆从配送中心出发,对客户进行配、集货服务,最后返回配送中心,要求规划车辆行驶路线,使得总配送成本最低.

2.2 预优化阶段

在预优化阶段,客户点的集货需求是不确定的,难以准确估计,实际集货需求一般在某个范围内.通常使用三点法估计每个客户的集货需求:最小集货需求量、最可能集货需求量和最大集货需求量,所以对于表示不确定集货需求的节点的模糊变量采用三角模糊变量=(p1,i,p2,i,p3,i)表示.其中p1,i,p2,i,p3,i分别表示三角模糊数的下界、最可能的估计值及上界.

那么车辆kr在为节点w完成配货服务后的剩余容量为∆Quwkr=Qr−Quwkr+dw.因为客户s,u的集货量为三角模糊数,也为三角模糊数,则有

其中:

基于可信度理论,待服务节点w的集货需求小于车辆kr的剩余容量的可信度为

式中:

本文对所研究问题作出如下假设:

1) 每辆车从配送中心出发,配送完毕后返回配送中心.

2) 配送中心有足够的车辆来满足客户需求.

3) 配送和收集的货物可以混装.

4) 每辆车装载货物量不超过车辆容量,每个客户点的配货需求和集货需求不超过最大车型的容量,且客户点的配送以及收集的货物不能拆分.

5) 客户的配送需求缺乏有效数据或数据没有典型特征.

6) 车辆的油耗和车辆的载重成线性关系,则车辆kr从节点i驶向节点j过程中的单位距离油耗成本为

相应的HFVRPSDDFP模型如下:

目标函数式(2)为最小化成本,第1项为车辆派遣成本,第2项为车辆油耗成本;式(3)表示车辆kr从客户点i驶向客户点j过程中的实载率;式(4)表示车辆kr服务完客户点j后的承载量不超过其容量的可信度大于或等于预设偏好值α;式(5)为车辆kr访问客户点s前后的车辆负载平衡约束;式(6)表示车辆kr的初始装载量;式(7)表示车辆kr的初始装载量不超过r型车的容量Qr;式(8)表示每个客户只被一辆车服务;式(9)为车辆进出平衡约束;式(10)–(11)保证客户点被车辆服务时一定有路径与其连接;式(12)表示车辆被使用时只有一条服务路径且从配送中心出发,并最终回到配送中心;式(13)为标准支路消除约束,即消去构成不完整线路的行车路线,其中S为车辆k的服务路线客户集合;式(14)为决策变量取值约束.

2.3 重优化阶段

预优化路径(见图2(a))得到之后,由于客户点的集货需求是模糊的,很可能会使得车辆在对某个客户点进行服务时,客户点的集货需求超过车辆的剩余容量,导致车辆不能对此客户点进行服务.在重优化阶段,对在实际服务过程中未被完全服务的客户点进行第2阶段的优化.

针对失败点所导致的路径失败问题,现有文献多采用点返回策略进行重优化处理,主要包括:失败点返回策略,见图2(b);失败点前序点返回策略,见图2(c)所示.

图2 VRPSDDFP问题中不同失败点策略示意图Fig.2 Diagram of different failure point strategies in VRPSDDFP

文献[23]对传统的失败点返回策略做出改进,针对模糊需求车辆路径问题中出现失败点的现象,设计了一种重调度策略,在预优化方案全部执行完毕后,对所有失败点进行全局优化,并且通过允许车辆对失败点进行部分服务来减少成本,如图2(d)所示.以图2(b)中的预优化子路径0–1–2–3–0为例,传统失败点返回策略在判定失败点2时,直接返回车场,此时车辆还装有30单位的货物未配送,造成了车辆资源的浪费,而且此时失败点3的集货需求仍然不能确定,后续对失败点3的配送仍然可能出现失败,增加了调度难度,可能造成成本的增加.同样,失败点前序点返回策略和文献[23]失败点返回策略都存在上述不足.另外,在失败点前序点返回策略中,选取合适的返回点较为困难,可能造成车辆不必要的返回,从而导致成本增加.鉴于上述3 种策略存在的不足,本文提出如图2(e)所示的失败点服务策略:在按照预设路径进行配送时,如果车辆不能满足某一客户点i的集货需求,就只对客户点i进行配货服务,然后继续对路径中i点的后续客户点进行配、集货服务,最后对所有失败点统一考虑,此时问题转化成了小规模的HFVRP问题,采用文献[12]中的方法,即先找到一条包含所有失败点的最短路径,再根据车载率将最短路径截成若干子路径,分成不同规模的旅行商问题进行求解,最后得到重优化阶段的配送路径.从图2可以看出,本文失败点服务策略使用了最少的车辆,这是因为,在图2(b)–2(d)中,车辆在服务客户2时,由于剩余容量不足以满足客户2的集货需求,满足客户点2的配货需求后直接承载30单位的未配送货物从客户2处返回车场,将路径中客户3留给后续车辆服务,未充分利用车辆的装载能力,而且图2(b)缺少对失败点2,3,5和6的统一规划;在2(c)中,车辆仅服务客户1即返回车场,将路径中客户2和3留给后续车辆服务,同样缺少对失败点的统一规划;在图2(e)中,对客户点2进行配货服务后,接着对路径中客户点3服务,仅将客户点2的集货需求留给后续车辆服务,最后对失败点2和5进行了统一规划,充分地利用了车辆的装载能力.

由于此时顾客的集货需求由模糊变为确定,且配货需求在上阶段都已满足,重优化阶段的模型需在预优化模型的基础上修改后得到.

其中式(2)(8)–(14)保留不变,删除式(4).将式(3)修改为

式(15)表示车辆kr从客户点i驶向客户点j过程中的实载率.

将式(5)修改为

式(16)为车辆kr访问客户点S前后的车辆负载平衡约束,其中ps为客户点s确定的集货需求.

将式(6)修改为

式(17)表示车辆kr的初始装载量为0.

将式(7)修改为

式(18)表示车辆kr返回车场时的装载量不超过r型车的容量Qr.

3 遗传变邻域算法

遗传算法(genetic algorithm,GA)使用概率机制进行迭代,具有随机性,有较好的全局搜索能力,而且具有可扩展性,容易与其他算法相结合,但该算法有局部搜索能力较差、易早熟等缺点.变邻域搜索算法(variable neighborhood search,VNS)可以利用不同的邻域结构进行局部搜索,有强大的局部搜索能力.本文结合遗传算法和变邻域搜索算法的优点,设计了遗传变邻域算法(genetic algorithm–variable neighborhood search,GA–VNS).对于现有结合遗传和变邻域算法的混合算法[22,24–27],本文遗传变邻域算法设计了新的邻域结构,引进了自适应搜索策略,使得算法在迭代前期快速提升解的质量,迭代后期不易陷入局部最优,此外本文还根据问题特征设计了编解码方式,使得算法总能生成可行解.算法采取先预优化再重优化的策略.在预优化阶段,引入可信度理论并设置偏好值确保方案的可行性,通过遗传变邻域算法求解形成预优化方案.在重优化阶段,采用随机模拟算法(stochastic simulation algorithm,SSA)确定集货需求,通过变邻域搜索算法对失败点进行求解,生成重优化阶段的配送方案.算法流程如图3所示.

图3 GA–VNS流程图Fig.3 The basic flow of GA–VNS

3.1 初始种群的生成及编解码方式

初始种群的生成方式通常分为随机生成和启发式生成两种,本文采取随机生成和最近邻插入法相结合的方式,采用这种方式可以在保证初始解质量的基础上提高种群的多样性.

本文采用整数编码,在由n个客户,1个配送中心组成的配送网络中,数值1∼n为客户编号,0 为配送中心编号.解码过程分为两个阶段,第1阶在可信度约束和车辆容量约束下,分别为不同车型的车辆分配客户,计算车载率并选择车载率最大车型的车辆进行配送,记录车辆服务的起始客户位置.第2阶段根据子路径起始位置,记录配送中心以及所有客户点,完成解码.以图4为例进行说明,配送网络中共有10个客户,1个配送中心,3种车型车辆的集合分别为K1,K2,K3,每种车型的容量的大小关系为Q1>Q2>Q3,客户矩阵pop_route的排列为3–5–8–4–6–1–7–2–9–10,从客户3开始服务,K1,K2和K3的车辆一次性可以服务客户分别为3–5–8–4–6,3–5–8–4和3–5–8(以K1为例说明其服务客户3,5,8,4和6必须满足的条件:1)客户3,5,8,4和6的配货需求之和不超过K1的标准容量Q1;2)服务完顾客i(i∈{3,5,8,4}),车辆能成功得为后续顾客服务的可信度(其中k1∈K1)不小于给定偏好值α,计算车载率有w1>w2>w3,选取具有最大车载率w1的车辆对客户3,5,8,4和6进行服务,分别将其车型及服务的起始客户位置记录到矩阵中:

图4 编解码方式Fig.4 The encoding and decoding method

下一个判断从第6个客户开始,同理分别得出剩余两条子路径所用车型及起始客户位置:

最后根据矩阵Cus_first中车辆的首客户位置添加车场0,得到子路径Route1:0–3–5–8–4–6–0,Route2:0–1–7–2–0,Route3:0–9–10–0,完成解码.

由以上分析可知,只需将每辆车服务首个顾客的位置记录下来,就可以结合pop_route得出该车辆服务路径,在后面的交叉变异操作以及局部搜索中只对编码长度固定的pop_route进行操作.采用将客户排列顺序、车辆服务的客户和车辆所属车型分离编码的方式,可以使得在后续的扰动时,总能生成可行解,避免了不可行解的修复困难问题.

3.2 选择操作

选择操作采用轮盘赌和精英保留策略相结合的方式.轮盘赌可以保证适应度高的个体更容易被选中,使种群向好的方向进化,提高解的质量.精英保留策略可以防止种群的最优个体在下一代丢失.

3.3 交叉算子和变异算子

在遗传算法中,交叉算子的作用是产生新的个体,增强算法的全局搜索能力.本文采用顺序交叉的交叉方式,顺序交叉操作可以在生成新个体的同时顺序保留父代中的可能比较优秀子排列.以图5(a)为例,箭头指向的点为随机产生的交叉点,以子代的生成为例,将父代R1中序列3–5–7作为子代的第1段,将父代R2中去除点位3,5和7后的序列6–4–1–2顺序作为子代的第2段,同理生成子代

变异算子的作用是产生新的个体,增强算法的全局搜索能力.本文选择反转逆序的变异方式,这种变异方式对个体的扰动较大,能更好地跳出局部最优.以图5(b)加以说明,箭头指向的点为随机在个体R3上选取的变异点,将所选部分反转得到新个体R4.

图5 交叉算子和变异算子Fig.5 The crossover operator and mutation operator

3.4 邻域结构构造

邻域结构构造包括如下问题:邻域结构集的形式及邻域结构集的个数;邻域结构之间的顺序;邻域结构间移动策略[28].

传统的邻域结构主要是两点交换和插入,这两种类型的邻域结构较为简单且容易实现,因此对于生产调度问题,许多算法都采用这两种邻域结构[27],为了提升算法的搜索能力,本文采用了包括两点交换和插入的4种邻域结构:

1) 两点交换:如图6(a)所示,随机选取两个点,将两点的位置互换.

2) 单点插入:如图6(b)所示,随机选取两个点,将位置靠前的客户点插入到位置靠后客户点的前面.

3) 反转逆序:随机选取两个点,将中间部分的客户点翻转,具体操作见图5(b).

4) 两点插入:如图6(c)所示,先随机选择连续位置的两个点,再随机选择一个点,将连续的两个点插入到单点的前边.

图6 邻域结构Fig.6 The neighborhood structures

除了邻域的结构形式,邻域结构之间的顺序是决定算法搜索能力的另一个重要因素,经过测试,本文的邻域结构之间的顺序为两点交换–单点插入–反转逆序–两点插入.

常见邻域之间的移动策略主要分为两种,一种为首先进入第一个邻域结构N1(邻域结构Nj,j=1,2,···,m)进行局部搜索,当次没有出现更优解时,跳出邻域结构N1,进入邻域结构N2,直到跳出最后一个邻域结构Nm,完成全部邻域动作.另一种为首先进入第一个邻域结构N1,当Sn次没有出现更优解时,进入邻域结构N2,当出现最更优解时,重新从N1开始进行搜索,直到跳出Nm最后一个邻域结构并没有更优解出现时,完成全部邻域动作.经过测试,本文采用第2种移动策略,如图7所示.

图7 邻域间移动策略Fig.7 The move strategy in the neighborhoods

3.5 自适应搜索策略

将自适应搜索范围应用到变邻域搜索的过程中,在迭代前期,缩小搜索范围,快速提升解的质量;在迭代后期,扩大搜索范围,提升种群的多样性,使算法不易陷入局部最优.

基于以上考虑,本文设计了自适应搜索范围策略:在变邻域过程中,新引进的弧(i,j)需满足式(19)

式中:lij表示(i,j)的弧长,D为距离矩阵L将每行元素按照从小到大的顺序排列之后得到的矩阵,αis为矩阵D中第i行第s个数,其中s需满足式(19a)

式中:n为客户数目,gen表示当前迭代次数,MaxGen为最大迭代次数,β1和β2为参数.可以看出,在迭代初期搜索范围s趋近于β1·n,小的搜索范围使得在变邻域操作的过程中让实际距离较近的客户点相邻,加快解收敛的速度,迭代后期s趋近于(β1+β2)n,搜索范围扩大,允许选择距离较远的客户点进行变邻域操作,使解不易陷入局部最优.

3.6 随机模拟算法(SSA)

在本文研究的问题中客户的集货需求是模糊的,为了验证预优化阶段路径制定策略和失败点重优化策略的性能,采用SSA随机模拟算法来确定客户的集货需求:对于客户i的集货需求在[pi1,pi3]范围内随机生成一位数σ,计算其隶属度接着在[0,1]内随机生成一位数λ,若有µ(σ)λ,则模拟生成客户i的集货需求为σ,若不满足µ(σ)λ,则重新生成σ和λ,比较µ(σ)和λ,直至满足µ(σ)λ,确定客户点i的集货需求σ.

4 算例分析

由于还没有HFVRPSDDFP问题的算例,因此本文选择VRPSDP和HFVRPSDP算例验证算法的有效性,生成HFVRPSDDFP算例,以验证模型和算法的有效性.编程工具采用了MATLAB R2016a,操作系统为Windows 10,电脑内存为8.00 GB,CPU为Intel Xeon E5–1630,主频为2.80 GHz.经过测试,本文算法参数设置如下:最大迭代次数MaxGen=100∼3000;种群规模PopSize=30∼100;交叉概率pc=0.5;变异概率pm=0.05;参数β1=0.5∼0.8,β2=0∼0.5;最大邻域循环次数MaxSn=1000;邻域搜索次数Sn=20∼30;最优解连续未改进最大次数MaxNum=30∼50.

4.1 确定型VRPSDP算例

实验1文献[29]对同时配集货车辆路径问题进行研究,同本文研究的HFVRPSDDFP问题的不同之处在于,文献[29]中研究问题的配、集货量均为确定的,是本文研究的HFVRPSDDFP的基础问题,因此本文首先选择文献[29]中的算例对本文算法进行验证.在文献[29]中的VRPSDP算例,客户规模为20,含有一个配送中心,每个客户的配、集货量均在2 t 内,物流中心有10 辆车,车辆的载重量均为8 t,车辆行驶一次最大距离为50 km.表1给出改进的模拟退火算法(simulated annealing,SA)[30]、自适应粒子群算法(adaptive particle swarm optimization based on swarm delivery,SDAPSO)[31]、蚁群系统(ant colony system,ACS)和2–opt结合算法[32]、协同粒子群–模拟退火算法(PSO–SA)[33]以及本文的遗传变邻域算法(GA–VNS)求解10次的结果.其中:“Best”表示求解10次的最优解,“Avg”表示求解10次的平均值.由表1可以看出,最优解方面,本文遗传变邻域算法求得的最优解100.5比SA改进了13.4%,比SDAPSO改进了0.6%,比ACS 与2–opt结合算法改进了7.3%,而且求得的10个结果全都为最优解.PSO–SA取得了此算例的当前最优解100.3,较本文算法改进了0.2,但PSO–SA使用车辆数比本文多一辆,车辆的使用不仅有固定成本,还有油耗等变动成本,所以应减少车辆的使用.另外PSO–SA计算10次的平均值104.6要劣于本文算法的100.5.验证了本文算法的有效性和稳定性.图8给出了本文求解的最短路径变化趋势图,可以看出本文求解算法可以在较少的迭代次数内快速收敛,当算法陷入局部最优时,可快速跳出局部最优,具有较好的寻优性能.

表1 VRPSDP问题的计算结果Table 1 The results of VRPSDP

图8 最短路径变化趋势Fig.8 Change trend of the shortest route

4.2 HFVRPSDP算例

实验2选择文献[34]中的HFVRPSDP算例对本文算法进行测试.该算例有1个配送中心和21个客户点,配送中心有A和B两种车型,载重量分别为8.5 t和5 t,A 车型有两辆,B车型有两辆.表2为本文遗传变邻域算法求解10次的结果,表3 和图9分别给出了文献[34]中遗传算法(GA)、禁忌搜索算法(tabu search,TS)与混合遗传算法(hybrid genetic algorithm,HGA)和本文遗传变邻域算法(GA–VNS)计算10 次的求解情况和最优配送路线.由表2可以看出,本文所使用的遗传变邻域算法求得的结果平均使用3 辆车,其中车型A 一辆,车型B 两辆,最优解为134.61 km,总里程的均值为135.80 km,最差解为138.37 km,仅比最优解多2.79%,计算结果较为稳定.

表2 GA–VNS求解HFVRPSDP问题计算结果Table 2 The results of solving HFVRPSDP with GA–VNS

图9 GA,TS,HGA和GA–VNS求解最优路线图Fig.9 The best routes of GA,TS,HGA and GA–VNS

从表3和图9可以看出,求解质量方面,本文算法对现有最优解进行了改进,较原有文献求得的最优解改进了0.037%,在求解稳定性方面,本文算法和HGA均求得4次最优解,而且用本文算法求得结果的标准差为1.39,分别低于HGA的1.49、GA的2.24和TS的2.52,验证了本文算法的有效性.

表3 GA,TS,HGA和GA–VNS算法比较Table 3 Comparison of GA,TS,HGA and GA–VNS

实验3选择Avci[16]提出的使用车型数2–4,客户点规模10∼100的HFVRPSDP测试算例.表4给出了文献[16]中自适应混合局部搜索算法(hybrid local search,HLS)和本文的遗传变邻域算法(GA–VNS)在18个算例中运行10次的求解情况,其中:“Cou”为顾客点数,“Veh”为车型数,“CPU”为算法运行的时间,“%Dev”表示最优值同平均值的偏差.

由表4可以看出,在求解时间方面,当客户规模在10∼15时,本文遗传变邻域算法整体要优于HLS算法,当客户规模为20∼100时,本文算法用时要比HLS算法多4.2 s∼49.1 s,当客户规模为150∼200时,本文算法用时要比HLS算法多138.8 s∼254.1 s,随着客户规模的增多本文算法的计算时间增长速度更快;在求解质量方面,本文遗传变邻域算法求得其中12个最优解,HLS算法求得其中11个最优解,本文算法要略优于HLS算法;在求解稳定性方面,本文遗传变邻域算法求得的平均值比最优解平均只高1.69%,而HLS算法求得的平均值要比最优解平均高2.09%,本文的稳定性更好.可见,本文算法在可接受的时间范围内牺牲了部分求解时间,但求解结果更优且稳定性更强.

表4 HLS和GA–VNS算法比较Table 4 Comparison of results of HLS and GA–VNS

4.3 HFVRPSDDFP算例

实验4:本文通过随机生成客户坐标点并采用文献[7]中的车辆信息,设计如下算例:一个配送中心的车辆有3种车型,需要对100个同时具有配集货需求的客户点进行服务,车辆从配送中心出发,服务完成后返回配送中心,要求为客户点规划配送路线,使得完成服务的成本最低.为了生成客户点的需求量,Dethloff[35]提出随机产生VRPSDP问题中客户的配、集货量的方法:客户点i的配货需求di随机生成,并通过pi=(0.5+ri)di产生集货需求pi,其中ri随机生成,并且在区间[0,1]上均匀分布.在Dethloff提出的随机方法的基础上,本文通过

得出客户i的模糊集货需求,其中γ=0.25.偏好值α∈(0,1],求解时令α按幅度0.1递增.表5给出了HFVRPSDDFP算例预优化阶段计算25次的统计数据和部分求解结果.

由表5可见,最优值较平均值的偏差较小,说明GA–VNS算法求解HFVRPSDDFP问题时的性能稳定.另外,偏好值α的取值不同,会导致求解结果的差异,从表5中可以看出,在α=0.2时取得最优解4718.24和最小平均值4840.84,随着α的数值逐步增大,配送成本逐渐增加.这是因为当α值增加,决策者偏向于保守型,为了尽可能减少失败点,在预配送阶段决策者不愿冒险让车辆服务更多的客户,导致成本较高;反之,当决策者趋向于冒险型,对配送失败的承受能力较高,允许车辆在尽可能多地服务客户,导致成本较低.

表5 HFVRPSDDFP算例的预优化结果Table 5 The pre-optimized results of the example of HFVRPSDDFP

为了对比各种返回策略在HFVRPSDDFP问题中的表现,分别将传统失败点返回策略、文献[23]失败点返回策略、失败点前点返回策略和本文失败点服务策略应用到HFVRPSDDFP算例中.但是在实验的过程中发现,当把传统失败点返回策略和失败点前点返回策略应用到此算例时,程序有时会陷入死循环,这是因为本文以车载率选择不同车型的车辆,车辆初始载货量较大,初始剩余容量较小,当车辆服务的第1个顾客的集货需求大于配货需求时,很容易导致车辆因不能满足顾客集货需求而服务失败,对路径上第1个客户服务失败后,未对顾客进行任何服务后便返回车场,安排后续相同车辆重新按原预优化配送计划进行配送,导致配送总是失败.验证了传统的失败点返回策略和失败点前点返回策略不适用于本文研究的HFVRPSDDFP问题.

表6给出了车辆按照不同α值的最优预优化方案对客户进行配送,并使用策略1(本文失败点服务策略)和策略2(文献[23]返回策略)时的配送成本.可以看到在不同的策略下,求解结果有明显的差别.策略2在α=1时取得最优解5408.07和最小平均值5737.26,策略1在α=0.4 时取得最优解5215.42,α=0.2最小平均值为5315.47,分别比策略2改进了2.72%和6.76%.

表6 α递增下各最优预优化方案下的总体成本Table 6 Total costs on different pre-optimization schemes under α increasing

本文发现,在不同失败点服务策略下,最优解和最优平均值的差别较大,这是由于策略2在遭遇失败点后直接返回配送中心的做法对车辆资源造成了浪费,造成配送成本的增加.本文还发现,在不同失败点服务策略下,取得最优解及最优平均值时的偏好值差别同样很大,这是因为策略1在遇到失败点后继续服务路径中后续顾客点,因服务失败而产生的失败点较少,在较小的偏好值下表现更好.而策略2从服务失败点处返回车场,路径中剩余未服务的客户点均为失败点,适用较大的偏好值.实验结果表明本文提出的失败点服务策略可以有效地降低配送成本.表7给出了取得最优解时的配送路径.

表7 总成本最小时的配送路径Table 7 The route with the smallest total cost

本文还将多车型和单车型的车型使用策略进行对比,由于6 t的车型容量要小于客户配货或集货需求的最大值,所以单车型使用策略不选用6 t的车型.如表6所示,在仅使用16 t的车型的情况下,当α=0.1时取得最优解5870.92及最小平均值为5967.85;在仅使用8 t的车型情况下,当α=0.2时取得最优解5519.78,α=0.1时取得最小平均值5653.91,均要劣于使用多车型时的最优解5215.42和最小平均值5315.47.通过对比可以发现,在不同的车型适用策略下,产生最优解及最小平均值时的偏好值并没有明显的不同.就最优解而言,使用多车型策略分别比仅16 t和8 t的车型单车型策略改进了11.14%和5.51%,就最小平均值而言,使用多车型策略分别比仅使用16 t 和8 t的车型改进了10.93%和5.99%.可以看出,在集货需求模糊的同时配集货车辆路径问题中,使用多种车型配送的优势依然可以体现.

5 结论

本文针对集货需求模糊的异型车同时配集货车辆路径问题进行了研究,主要结论如下:

1) 本文研究的HFVRPSDDFP问题不仅考虑了客户集货需求模糊性,而且考虑了车型不同、客户同时具有配货与集货需求的特点,是对VRPSDP,HFVRP及VRPFD问题的进一步深化和拓展,具有理论意义和现实意义;

2) 提出的失败点服务策略更适用于解决HFVRPSDDFP的需求不确定而产生的车辆路径调整问题,能有效降低企业配送成本;

3) 设计的遗传变邻域算法,将变邻域搜索算法引入遗传算法的局部搜索过程中,使两者优势互补,增强算法的寻优能力;通过反复测试,确定本文算法的邻域结构构造,能够提高算法的搜索能力;将设计的自适应策略运用到变邻域搜索的过程中,可以使算法在迭代前期提高收敛速度.

本文的研究能为集货需求模糊的异型车同时配集货车辆路径问题提供较好的解决方案.未来将对开发更有效的算法和多重不确定环境下的车辆调度问题进一步展开研究.