带时间窗的多中心半开放式车辆路径问题

辜 勇 袁源乙 张 列 段晶晶

武汉理工大学物流工程学院,武汉,430063

摘要针对多中心协同配送下的车辆路径问题,建立了总成本最小化模型,所建模型满足多中心、多需求点和半开放式的特征。考虑到问题的复杂性,设计了一种三阶段求解算法:将K-mediods聚类算法用于原始数据分解,将原规模较大的多配送中心路径问题转换成多个单配送中心路径问题;设计了改进多蚁群算法来求解单配送中心路径问题,得到初始方案;在调整阶段,利用节约算法优化初始方案。分析了算例,并同其他文献的算法求解结果进行对比,结果表明,所提算法比GA-ACO算法求解得到的单中心配送最优路径值减小32.16%,总成本减小30.42%;比狼群算法解得的最优路径值和总成本均减小8.99%;比蚁群算法求得的最优路径值减小24.76%,最小配送成本减小3.40%,从而验证了所建模型的合理性和所设计多阶段算法的有效性。

关键词多中心车辆路径问题;协同配送;时间窗;K-mediods聚类;多蚁群算法

0 引言

在企业联盟和拥有多个车场的大规模物流运输企业逐渐兴起的社会背景下,车辆路径问题(vehicle routing problem, VRP)可以演化为多中心开放式车辆路径问题(multi-depot open VRP,MDOVRP)、多中心闭合式车辆路径问题和多中心半开放式车辆路径问题(multi-depot half open VRP,MDHOVRP)[1]。MDHOVRP问题不同于开放式问题中车辆停车点随机,也区别于闭合式问题中车辆必须返回始发配送中心,该问题要求车辆完成任务后从客户处返回任意配送中心。考虑到现实中客户对配送时间的要求越来越严格,MDHOVRP还可以拓展为带时间窗的多中心半开放式车辆路径问题(multi-depot half open VRP with time windows,MDHOVRPTW)。

关于多中心车辆路径问题(MDVRP),国内外学者对其求解算法做了广泛而深入的研究。虽然精确算法能够求得问题的最优解,但其求解效率低且求解规模有限,故更多学者采用启发式算法进行研究。SOTO 等[2]用多邻域搜索与禁忌搜索相结合的算法求解MDOVRP。针对同样的问题,戴树贵等[3]基于2-opt优化策略和K邻域规则,提出了混合蚁群算法。对于闭合式MDVRP,FITRIANA 等[4]用改进遗传算法求解该问题。盛虎宜等[5]设计了改进蚁群算法求解该问题。陈呈频等[6]提出了多染色体遗传算法来求解多车型的闭合式MDVRP。对于MDVRPTW,HEECHUL等[7]将类似于最近邻启发式算法的解应用于初始种群的改进遗传算法来求解该问题。于滨等[8]结合基于聚集度的启发式分类算法和改进蚁群算法来求解该问题。肖玉徽等[9]设计了两阶段禁忌搜索算法来求解该问题。对于车辆返回任一中心的MDHOVRP,闫军等[10]设计了自适应调整交叉率和变异率的改进遗传算法来求解该问题。当考虑客户服务时间窗时,LI 等[11]、WANG等[12]利用改进遗传算法求解MDHOVRPTW。上述文献的求解思路主要分为两类:一是对启发式算法进行改进;二是采用“先分解,后优化”的思想。大多数文献集中于研究闭合式带时间窗的MDVRP,但关于MDHOVRPTW的研究成果相对较少。

VRP问题属于NP-hard问题,而本文讨论的MDHOVRPTW具有多中心、多需求点和半开放式等特点,需同时满足时间窗和车辆载重等条件,这进一步增加了问题的复杂性。为了更好地解决已有算法在求解MDHOVRPTW时解的质量不高、求解效率低等问题,本文借鉴分阶段求解思路,设计了三阶段求解算法,利用K-mediods聚类算法将多中心问题分解成单中心车辆路径问题,用改进多蚁群算法求解各单中心问题作为初始方案,最后使用节约算法对初始方案进行优化。

1 模型描述

1.1 变量定义

MDHOVRPTW的变量定义见表1。

1.2 模型的建立

根据表1的符号说明,以成本最小化为优化目标,建立MDHOVRPTW的数学模型如下:

(1)

约束条件如下:

(2)

(3)

(4)

(5)

UHC |U|≥2 ∀kK

表1 变量定义

Tab.1 The variable definitions

变量名定义H客户点集合,H={Hi|i=1,2,…,n}C配送中心点集合,C={Cj|j=1,2,…,m}K运输车辆的集合,K={Kk|k=1,2,…,l}W运输车辆的额定载重qi客户Hi的需求量,满足l≥∑qi/Wdij节点i与j之间的距离,∀i,j∈H∪CTik,Tjk车辆k从某一节点i、j的出发时刻[Ei,Ri]客户接受服务的时间范围[Si,Gi]客户接受服务的最佳时间范围[Ei,Si]产生等待成本的时间范围[Gi,Ri]产生缺货成本的时间范围M车辆到达客户点时间不在[Ei,Ri]范围内,此时惩罚成本设置一个无穷大值Di客户Hi接受服务所需的时间Fk车辆k的派遣成本c0车辆k的单位运输成本c1车辆k的单位等待成本c2车辆k的单位缺货成本v车辆行驶的平均速度xijk模型决策变量之一,表示车辆k是否从节点i行驶至节点j,若是,xijk=1;否则xijk=0yk模型决策变量之一,表示车辆k是否被派遣,若是,yk=1;否则yk=0

Tik<RiiHCkK

(6)

(7)

(8)

xijk∈{0,1} yk∈{0,1}

(9)

i,jHC kK

(10)

Fi(Tik)=c1xijkmax((Si-Tik),0)+
c2xijkmax((Tik-Gi),0)

(11)

iH,jHC,kK

目标函数式(1)为配送成本最小化,配送总成本由运输成本、车辆派遣成本与承运人惩罚费用组成;Fi(Tik)的计算公式为式(10),其中,EiRi分别为最早、最迟接受服务的时间,Si为产生等待成本的终止时间,Gi为产生缺货成本的开始时间;当Tik在[Ei,Li]范围内时,Fi(Tik)还可以用式(11)计算;式(2)为配送车辆的载重约束;式(3)表示任一客户只能由一辆车服务一次;式(4)表示车辆可以不被分派任务,被分派任务的车辆的运输路径必须途经配送中心与客户节点,完成任务后可返回任意配送中心;式(5)表示清除配送路径中的多余子路径;式(6)和式(7)表示车辆到达时间应满足客户时间窗限制;式(7)表示车辆当次出发节点时间会影响到达下一节点的时间;式(8)表示车辆数限制约束;式(9)为决策变量取值约束。

2 求解算法的设计

MDHOVRPTW问题存在m个配送中心,n个客户点,每个客户的需求量为qi,由k辆配送车辆从配送中心出发进行服务,车辆装载量不超过W,以平均速度v行驶,且到达客户点的时间应在[Ei,Ri]范围内,完成一次服务后需返回任一配送中心。MDHOVRPTW需要解决如何将上述n个客户分配到m个配送中心中,不仅要确定每个客户应该由哪个车场与哪辆配送车辆服务,而且要确定客户配送的先后顺序,在满足客户时间窗和车辆载重限制等约束条件下,使得配送总成本最小化。当实际配送系统中包含较多服务点时,问题的求解空间急剧扩大,求解过程更加复杂,现有的求解方法效率迅速下降。

本文设计了一种三阶段求解算法,第一阶段利用K-mediods聚类算法有效缩小问题规模,借鉴了GIOSA等[13]提出的三标准聚类算法原理逐一归类。第二阶段设计改进多蚁群算法求解归类后的各单中心车辆路径问题,设置的多蚁群算法中,将蚂蚁分成AB两组,A组采取全遍历策略,B组采取单回路策略,待两子蚁群均停滞后,更新交换蚁群间的信息素,引入2-opt邻域搜索算法更新可行解并作为初始解。第三阶段使用节约算法对初始解进行优化。下文主要对第二阶段改进多蚁群算法和第三阶段节约算法的基本规则加以说明。

2.1 改进多蚁群算法规则设计

(1)转移规则设计。改进蚂蚁选择下一节点的转移概率公式。定义参数如下:τij表示节点ij之间的信息素浓度,ηij表示节点ij之间的可见度,ηij=1/dijAk表示蚂蚁k的可访问点集合,表示蚂蚁kt时刻从节点i转移至j的概率,其计算公式为

(12)

其中,α表示信息素参数;β表示可见度参数,γ表示节约距离参数;Uij表示节约距离,考虑当蚂蚁从配送中心出发时,节约距离设定为1,其计算公式为

Uij=Uji=di1+dj1-dij

(13)

除此之外,为防止蚂蚁只通过概率转移规则选择路径,引入随机变量q0,当q<q0时,蚂蚁k转移至使转移概率为最大值时的节点;否则,蚂蚁k随机转移至一个可访问节点,其数学表达式如下:

(14)

其中,q表示随机数,q∈(0,1),q0为设定的上限变量,考虑算法迭代的不同阶段具有不同的特点,q0的值随迭代过程变化,q0先变大再变小有利于使蚂蚁在全局范围内搜索最优解,并保证算法收敛速度在可接受范围内,q0的计算公式为

(15)

式中,N为当前迭代次数;Nmax为最大迭代次数。

(2)信息素更新规则设计。定义信息素为标量,不具方向性,改进的信息素更新规则如下:

τij(t+1)=(1-ρ)τij(t)+Δτij(t)+Δτji(t)

(16)

其中,ρ表示信息数挥发因子,根据算法迭代规律,ρ的计算公式为

(17)

Δτij(t)表示在当次循环中节点ij之间路径上的信息素增量,其表达式为

(18)

其中,表示蚂蚁k当次迭代过程中在路径ij上分泌的信息素含量,其表达式为

(19)

其中,Q表示每只蚂蚁携带的信息素总量,Lk表示蚂蚁k当次迭代走过的总路径,e(i,j)为节点i到节点j的路径。全局信息素更新时,DLk;局部信息素更新时,Ddij

(3)可行解更新规则。在可行解全部生成后,引入2-opt邻域搜索策略对每次迭代后的较优解进行优化,以此提高解的质量。

2.2 改进多蚁群算法步骤

改进多蚁群算法的流程如图1所示。

2.3 节约算法

节约里程算法作为一种经典的启发式算法,已有文献将其引入并改进蚁群算法以求解路径问题,本文将其设计为第三阶段算法。与以往不同的是使用第二阶段的改进多蚁群算法解得单个配送中心的配送路径后,第三阶段用节约算法打开单个配送中心独立配送的封闭性,合并多个配送中心间路线,实现多个中心联合配送。具体步骤如下:

图1 改进多蚁群算法流程图
Fig.1 The flow chart of improved multiple ant colony algorithms

(1)根据改进多蚁群算法求得的初始路径方案,对于分别属于两个不同车场CjCj的路径(Cj,…,i,Cj)和(Cj,…,j,Cj),合并后路径为(Cj,…,i,j,Cj),计算节约值Sij=diCj+djCj-dij。令G={Sij|Sij>0;i=1,2,…,n;j=1,2,…,m},将集合G内元素Sij按从大到小的顺序排列。

(2)按照降序节约值,依次判断两路径合并后是否构成可行路径,即计算连接ij合并后,车辆的载重是否满足约束条件式(2),并判断车辆到达时间是否在[Ei,Ri]区间内。若可以满足车辆容量约束且满足时间窗约束,则转步骤(3);否则转步骤(4)。

(3)连接点ij,构成新合并路径。

(4)在集合G中消去Sij元素,判定是否还有路径可以合并,若G=∅,则停止计算,输出结果;否则转步骤(2)。

3 算例验证与结果分析

3.1 算例描述

选用公共标准算例库中MDVRPTW算例pr2作为验证算例。算例中客户节点个数为96,配送中心节点个数为4,算例部分数据见表2。假设某企业拥有4个协同工作且货物充足的配送中心,每个配送中心拥有若干型号相同的车辆,车辆载重为0.6 t,车辆行驶的平均速度为60 km/h,车辆行驶成本为2元/km,车辆的派遣成本为200元/辆,车辆开始工作的时间为6点,每辆车的工作时长为10 h;某日该企业需给96个客户送货,客户服务时间Di由需求量决定,按照0.5 h/t计算,客户时间窗由客户自身决定,属于混合时间窗,时间限制为前后2 h,客户单位等待成本与迟到成本设置为30元/h。

表2 pr2算例部分数据

Tab.2 Partial data of pr2 example

序号节点信息节点坐标x(km)y(km)需求量(t)Di(h)Ei(h)Ri(h)1配送中心1-29.72424.26800002配送中心242.175-22.28400003配送中心377.75955.81700004配送中心433.58830.75000005需求点139.270-33.0570.150.0757.317.16需求点2-23.37086.8530.100.0507.617.97需求点348.13295.5930.120.0606.916.68需求点4-16.35793.3110.150.0757.116.39需求点5-57.703-65.6010.160.0806.217.910需求点67.14732.6840.180.0906.117.911需求点742.95068.7010.090.0456.316.512需求点837.085-2.1120.050.0257.617.913需求点948.80748.7920.190.0956.916.714需求点10-17.462-56.5670.110.0556.817.115需求点1158.57559.8880.120.0606.016.716需求点1257.77615.3440.130.0656.417.717需求点13-22.32736.0720.080.0406.117.318需求点14-7.0830.4930.140.0706.417.619需求点1555.65860.4250.090.0457.717.520需求点166.22910.590.250.1256.816.621…………………

3.2 算例聚类处理

使用K-mediods聚类算法对案例数据进行分类处理,考虑配送中心的数量为4,故设样本初始中心数量K=4,得到初始的聚类结果,并对异常点进行修正,最终得到聚类结果。4个配送中心分别被分到4个不同的类簇中,故各类簇能以配送中心名命名,分类结果见表3。

表3 案例节点分类结果表

Tab.3 Case node classification results table

类簇节点数目节点序号配送中心1251,6,8,10,17,18,20,21,28,38,39,40,45,56,63,65,69,70,74,75,82,85,87,93,94配送中心2272,5,9,12,14,22,27,29,35,36,41,42,44,46,50,53,59,60,62,64,71,78,80,83,90,91, 98配送中心3213,7,15,19,25,37,49,51,52,54,57,67,68,72,76,77,81,84,97,99,100配送中心4274,11,13,16,23,24,26,30,31,32,33,34,43,47,48,55,58,61,66,73,79,86,88,89,92,95,96

3.3 蚁群算法求解与排程优化

经聚类算法处理后,原多中心路径问题被分解成多个单配送中心的路径问题,运用改进多蚁群算法逐一对4个单配送中心的路径问题进行求解。经过大量实验测算,设置改进多蚁群算法的主要参数取值如下:α=1,β=1,γ=5,ρ=0.6,Q=10,b=2,Nmax=100,W=0.6 t,考虑4个类簇中包含的节点数目不同,将4个配送中心按序分别设置l=36、l=40、l=30和l=40。

在操作系统为Windows 7,CPU为Inter(R)Core(TM)i5-3230M,主频为2.60GHz的系统环境下使用MATLAB R2016a软件对上述算例进行反复求解,运行多次后,求出的最优路径值、总成本、所需车辆数见表4,最优路径如图2所示。

表4 各类别算例求解结果

Tab.4 Calculating results of each sub-example

类别最优路径值(km)总成本(元)车辆数配送中心1692.872 287.112配送中心2725.322 235.122配送中心3528.741 516.621配送中心4547.332 012.392

图2 各类别算例最优路径
Fig.2 Optimal route of each category

经改进多蚁群算法求解得到各配送中心独立提供配送服务的方案后,利用节约算法进行排程优化,优化后的车辆配送路径值及成本结果见表5,配送车辆服务各节点的信息见表6,联合配送的最优路径如图3所示。

表5 优化后算例求解结果

Tab.5 Calculating results of the example after optimization

序号车辆配送路径值(km)总成本(元)1配送车辆1450.921 181.862配送车辆2499.391 377.963配送车辆3530.691 582.254配送车辆4400.391 245.745配送车辆5439.721 300.32合计52 321.116 688.13

3.4 算例对比

根据文献[14]设计的遗传算法-蚁群算法(GA-ACO),选择pr2算例中配送中心4作为单配送中心,客户节点数据同pr2算例中的96个客户节点,通过反复运行求得最优配送路线,如图4所示,其结果对比见表7。可以看出经聚类处理后,多配送中心问题转化为多个单配送中心问题后求得的最优路径值比GA-ACO算法对应值减小27.10%,成本降低16.24%;而再经排程优化后,各单配送中心协同配送,求得的最优路径值比多中心独立配送结果减小6.94%,成本降低16.93%;比单中心独立配送路径值减小32.16%,成本降低30.24%,证明了本文算法的有效性。

表6 配送车辆服务信息

Tab.6 Distribution vehicle service information

车辆服务信息配送车辆1配送线路:2-14-9-93-94-75-1-17-65-18-1-45-38-1-28-69-39-1到达时间:6.0-7.1 -7.9 -9.3 -9.7 -9.9 -10.2 -10.4 -10.5 -10.8 -11.3 -11.7 -11.9 -12.4 -13.3 -13.8 -14.1 -14.5配送车辆2配送线路:1-8-6-40-1-70-10-1-56-82-20-85-87-21-1-63-74-61-33-4-89-34-48-4-95-32-4到达时间:6.0-7.2 -7.4 -8.4 -9.4 -9.9 -10.1 -10.8 -11.0 -11.5 -11.6 -11.9 -12.1 -12.4 -12.7 -13.1 -13.3 -13.7 -13.9 -14.1 -14.2 -14.4 -14.6 -14.7 -15.0 -15.3 -15.6配送车辆3配送线路:3-54-100-77-51-7-52-3-97-57-86-43-4-96-30-55-58-4-73-88-66-4-79-11-4-47-26-71-62-2到达时间:6.0-6.3 -6.7 -6.9 -7.3 -7.8 -8.2 -8.7 -9.1 -9.4 -9.6 -9.8 -10.6 -10.9 -11.1 -11.2 -11.4 -11.9 -12.2 -12.4 -12.6 -12.7 -12.9 -13.4 -14.1 -14.6 -15.3 -15.7 -16.1 -16.3配送车辆4配送线路:4-16-31-24-92-4-13-23-72-84-76-3-15-68-19-99-49-25-81-3-67-37-3到达时间:6.0-6.5 -6.8 -6.8 -7.2 -7.8 -8.2 -8.5 -8.9 -9.5 -10.0 -11.0 -11.4 -11.5 -11.5 -11.7 -11.9 -12.3 -12.3 -12.8 -13.2 -13.3 -13.7配送车辆5配送线路:2-41-50-35-5-2-59-60-42-44-2-80-98-90-2-46-53-2-36-83-27-22-29-12-2-91-64-78-2到达时间:6.0-6.7 -7.0 -7.3 -7.9 -8.2 -8.7 -9.0 -9.2 -9.5 -10.2 -10.5 -10.6 -10.7 -11.2 -11.4 -11.6 -12.0 -12.1 -12.3 -12.5 -12.6 -12.8 -12.9 -13.3 -13.5 -14.0 -14.5 -14.8

图3 联合配送的最优路径
Fig.3 Optimal route of joint distribution

为进一步证明本文算法的有效性,利用文献[15]的算例做实验。该算例包括3个配送中心和30个客户点。文献[15]要求车辆从一个配送中心出发,完成任务后返回原出发配送中心,属于闭合式MDVRP,为在同等条件下与文献[15]结果进行比较,本文根据文献[15]的约束条件进行实验,先求出闭合式MDVRP的最优解作为初始解,再使用节约算法将闭合式MDVRP转化为MDHOVRP,获得优化后的结果。由于文献[15]的目标是求最短距离,故本文设置单位距离运输成本为1元/km。算法运行10次后,实验结果见表8,最优解路径见图5,配送车辆服务信息见表9。

图4 实验1单中心配送路径
Fig.4 Single depot distribution route of experiment 1

表7 实验1结果对比

Tab.7 Comparison of the results of experiment 1

问题特点算法成本(元)路径长度(km)车辆数单中心配送文献[14]算法9 612.363 421.617多中心独立配送本文算法8 051.252 494.267多中心联合配送本文算法6 688.132 321.115

表8 实验2结果对比

Tab.8 Comparison of the results of experiment 2

算法成本(元)最优路径值(km)车辆数本文算法111.42111.424文献[15]算法122.42122.424

图5 实验2最优解配送路径
Fig.5 Optimal distribution route of experiment 2

表9 实验2配送车辆服务信息

Tab.9 Distribution vehicle service information of experiment 2

车辆具体配送路径行驶里程(km)配送车辆13-30-12-26-23-27-5-15-8-19-329.75配送车辆23-20-28-29-21-6-9-226.04配送车辆31-7-10-13-25-17-22-24-334.82配送车辆42-4-18-11-16-31-32-14-220.81

根据本文算法得到的结果,启用车辆数与文献[16]相同,最优配送路径值和总成本均减少8.99%。不仅证明了多中心联合配送方式的经济性,也验证了本文算法的有效性。

为进一步证明本文算法的有效性,再利用文献[16]的算例做实验。该算例包括4个配送中心和48个客户点,采用联合配送方式。算法运行10次后,本文求解结果与文献[16]算法所得结果对比见表10。

表10 实验3结果对比

Tab.10 Comparison of the results of experiment 3

算法总成本(元)路径最优值(km)车辆数本文算法32 3781 081.886文献[16]算法33 5181 437.905

由表10可知,本文算法派遣车辆数虽然比文献[16]多1,但最优配送路径减少24.76%,最小配送成本减少3.40%。最优解配送路径如图6 所示,配送车辆服务信息见表11。实验结果证明本算法具有更强的寻优能力,在求解MDHOVRPTW问题时效果更好。

图6 实验3最优解配送路线
Fig.6 Optimal distribution route of experiment 3

4 结论

本文针对MDHOVRPTW问题设计了改进多蚁群算法,能够避免每一个配送中心都对所有客户点进行重复搜索所带来的超大计算量,在一定程度上缩小了求解空间,提升了收敛速度,实现了提高解质量的目的。通过与相关文献算法求解结果进行对比,证明了多中心共同配送的经济性,同时验证了本文设计的多阶段算法良好的优化性能。

表11 实验3配送车辆服务信息

Tab.11 Distribution vehicle service information of experiment 3

车辆服务信息行驶里程(km)配送车辆1配送线路:2-46-50-49-15-14-2-26-31-7-10-52-2到达时间:6-6.72 -7.96 -9.75 -10.70 -11.03 -11.72 -11.93 -13.19 -14.04 -14.62 -14.98 -15.80270.95配送车辆2配送线路:2-38-41-11-39-13-36-48-35-45-1到达时间:6-6.16 -7.10 -7.60 -8.29 -8.93 -9.61 -10.15 -10.40 -10.99 -11.63118.02配送车辆3配送线路:4-34-43-47-25-28-51-16-42-6-4到达时间:6-6.14 -6.85 -7.52 -8.67 -9.65 -10.35 -11.16 -11.51 -12.59 -12.95129.32配送车辆4配送线路:4-19-44-21-22-29-27-30-40-3到达时间:6-6.36 -7.02 -8.36 -8.98 -9.87 -10.56 -11.27 -11.86 -12.55222.61配送车辆5配送线路:3-24-23-37-17-12-9-33-3到达时间:6-6.57 -8.12 -9.31 -10.44 -11.16 -11.98 -12.58 -13.78268.70配送车辆6配送线路:3-20-5-8-18-32-3到达时间:6-6.09 -7.22 -7.91 -8.30 -8.66 -9.2072.28

参考文献

[1] 刘冉,江志斌,耿娜,等. 半开放式多车场车辆路径问题[J].上海交通大学学报,2010,44(11):1539-1545.

LIU Ran, JIANG Zhibin, GENG Na, et al. Semi-open Multi-depot Vehicle Routing Problem [J]. Journal of Shanghai Jiaotong University, 2010, 44 (11): 1539-1545.

[2] SOTO M, SEVAUX M, REINHOLZ A,et al. Multiple Neighborhood Search, Tabu Search and Ejection Chains for the Multi-depot Open Vehicle Routing Problem[J].Computers & Industrial Engineering,2017,107:211-222.

[3] 戴树贵,陈文兰,潘荫荣,等.多配送中心车辆路径安排问题混合蚁群算法[J].四川大学学报(工程科学版),2008,40(6):154-158.

DAI Shugui, CHEN Wenlan, PAN Yinrong, et al. A Hybrid Ant Colony Algorithm for Multi Depot Vehicle Routing Problem [J]. Journal of Sichuan University(Engineering Science Edition),2008,40(6):154-158.

[4] FITRIANA R, MOENGIN P, KUSUMANINGRUM U. Improvement Route for Distribution Solutions MDVRP (Multi Depot Vehicle Routing Problem) Using Genetic Algorithm[J]. IOP Conference Series: Materials Science and Engineering, 2019, 528(1): 12-42.

[5] 盛虎宜,刘长石,鲁若愚.基于共同配送策略的农村电商集送货一体化车辆路径问题[J].系统工程,2019,37(3):98-104.

SHENG Huyi, LIU Changshi, LU Ruoyu. Vehicle Routing Problem with Simultaneous Pick-up and Delivery in Rural Electronic Commerce Based on Joint Distribution Strategy [J]. System Engineering, 2019,37(3): 98-104.

[6] 陈呈频,韩胜军,鲁建厦,等.多车场与多车型车辆路径问题的多染色体遗传算法[J].中国机械工程,2018,29(2):218-223.

CHEN Chengpin, HAN Shengjun, LU Jianxia, et al. A Multi-chromosome Genetic Algorithm for Multi-depot and Multi-type Vehicle Routing Problems[J]. China Mechanical Engineering, 2018,29(2):218-223.

[7] HEECHUL B, ILKYEONG M. Multi-depot Vehicle Routing Problem with Time Windows Considering Delivery and Installation Vehicles[J]. Applied Mathematical Modelling, 2016, 40(13/14):6536-6549.

[8] 于滨,靳鹏欢,杨忠振.两阶段启发式算法求解带时间窗的多中心车辆路径问题[J].系统工程理论与实践,2012,32(8):1793-1800.

YU Bin, JIN Penghuan, YANG Zhongzhen. Two Stage Heuristic Algorithm for Multi-depot Vehicle Routing Problem with Time Windows [J]. System Engineering Theory and Practice, 2012,32(8): 1793-1800.

[9] 肖玉徽,楼振凯,戴晓震.带时间窗的多配送中心协同配送问题研究[J].数学的实践与认识,2018,48(14):171-177.

XIAO Yuhui, LOU Zhenkai, DAI Xiaozhen. Study on Collaborative Distribution Problem of Multiple-distribution with Time Windows [J]. Mathematics in Practice and Understanding, 2018,48(14): 171-177.

[10] 闫军,董海鹰,王亚楠,等.电子商务条件下城市物流协同配送车辆路径问题研究[J].兰州交通大学学报,2019,38(1):37-42.

YAN Jun, DONG Haiying, WANG Yanan, et al. Research on Vehicle Routing Problem of Logistics Collaborative Distribution under the Condition of E-commerce[J]. Journal of Lanzhou Jiaotong University, 2019,38(1): 37-42.

[11] LI Jian, LI Yang, PARDALOS P M. Multi-depot Vehicle Routing Problem with Time Windows under Shared Depot Resources[J]. Journal of Combinatorial Optimization, 2016,31(2):515-532.

[12] WANG Xuping, ZHAN Hongxin, ZHANG Jun. Research of Oil Product Secondary Distribution Optimization Based on Collaborative Distribution[J]. Procedia Computer Science,2015,60:1367-1376.

[13] GIOSA I D, TANSINI I L, VIERA I O. NewAssignment Algorithms for the Multi-depot Vehicle Routing Problem[J]. Journal of the Operational Research Society, 2002, 53(9):977-984.

[14] 辜勇,张列,李志远,等.基于GA-ACO的带时间窗车辆路径问题[J].物流技术,2019,38(3): 53-60.

GU Yong, ZHANG Lie, LI Zhiyuan,et al. Vehicle Routing Problem with Time Window Based on GA-ACO [J]. Logistics Technology, 2019,38(3): 53-60.

[15] 叶勇,张惠珍.多配送中心车辆路径问题的狼群算法[J].计算机应用研究,2017,34(9):2590-2593.

YE Yong, ZHANG Huizhen. Wolf Swarm Algorithm for Multi-distribution Center Vehicle Routing Problem [J]. Computer Application Research, 2017,34(9): 2590-2593.

[16] 范厚明,杨翔,李荡, 等. 基于生鲜品多中心联合配送的半开放式车辆路径问题[J].计算机集成制造系统,2019,25(1):256-266.

FAN Houming, YANG Xiang, LI Dang, et al. Semi-open Vehicle Routing Problem Based on Fresh Products Multi-center Joint Distribution [J]. Computer Integrated Manufacturing System, 2019, 25(1): 256-266.

Multi-depot Half Open Vehicle Routing Problem with Time Windows

GU Yong YUAN Yuanyi ZHANG Lie DUAN Jingjing

School of Logistics Engineering,Wuhan University of Technology,Wuhan,430063

Abstract: Aiming at the vehicle routing problem under multi-depot collaborative distribution, a minimization model of total costs was established. The model satisfied the characteristics of multi-depot, multi-demand points and half-open. Considering the complexity of the problem, a three-stage solution algorithm was designed. K-mediods clustering algorithm was used to decompose the original data. The original large-scale multi-depot VRP was transformed into multiple single distribution center routing problems. Then, an improved multi-ant colony algorithm was designed to solve the single distribution center routing problem, and the initial scheme was obtained. In the adjustment stages, the initial scheme was optimized by using the saving mileage method. At last, the simulation results were compared with ones of the other methods. The results show that the proposed algorithm is better than GA-ACO algorithm, wolf pack algorithm and ant colony algorithm. The optimal path is optimized by 32.16%, 8.99% and 24.76% respectively, and the total cost is optimized by 30.42%, 8.99% and 3.40% separately, which verifies the rationality of the model and the effectiveness of the multi-stage algorithm design.

Key words: multi-depot vehicle routing problem(VRP); collaborative distribution; time windows; K-mediods clustering; multi-ant colony algorithm

中图分类号F252;TP301.6

DOI:10.3969/j.issn.1004-132X.2020.14.013

收稿日期2019-09-20

基金项目国家重点研发计划资助项目(2018YFC1407405)

开放科学(资源服务)标识码(OSID):

(编辑 陈 勇)

作者简介辜 勇,男 ,1975年生,副教授、博士。研究方向为系统分析与优化、智能物流规划与仿真。E-mail:guyong@whut.edu.cn。袁源乙(通信作者),女,1994年生,硕士研究生。研究方向为物流系统分析与优化。E-mail:460915419@qq.com。