多中心半开放式同时送取货的车辆路径问题研究

陈荣虎,张建宏,徐 祯

(安徽工业大学 管理科学与工程学院,安徽 马鞍山 243032)

近年来,物流行业发展迅速,很多物流企业拥有多个配送中心,并采用第三方租赁的车辆进行配送服务,因此多中心半开放式车辆路径问题(Multi-depot Half Open Vehicle Routing Problem, 下文简称MDHOVRP)得到了更多的关注.半开放式配送模式是指车辆服务完路线中所有客户点后,不一定返回原发出配送中心,而是根据车辆服务路线中最后一个客户点离各个配送中心的欧式距离,就近返回某一配送中心.在许多实际问题中,客户点同时具有送取两种需求,且两种需求分开服务在操作上具有一定的复杂性,为了减少这种复杂性,顾客要求只能被服务一次.如某个区域由多个快递总站给各小区快递站点提供送取快递服务,在考虑各个快递站点的服务时间窗的情况下,租赁第三方物流公司的车辆,实现各快递总站之间的车辆共享,可以减少车辆的配送距离,使得各种资源都能得到合理的配置.因此,为了更好地满足现实复杂的物流配送情况,寻求一种在已有多个配送中心的条件下,考虑客户点的时间窗进行同时送取货的一种半开放式配送模式十分必要.

针对带时间窗的多中心车辆问题,Cordeau等[1]设计了禁忌搜索算法对其求解,引入了一种自适应的惩罚系数,可以把原来不可行的解变为可行解;Liu等[2]设计了融合人工蜂群算法的一种混合遗传算法对此类问题进行求解,并通过仿真对比实验,证明该算法求解效果较优.辜勇等[3]根据MDHOVRP问题的复杂性,提出一种三阶段的算法处理方式,同时采用多蚁群算法解决MDHOVRP问题.范厚明等[4]将生鲜品的配送和MDHOVRPTW问题联立了起来,建立了多目标模型,并采用蚁群算法进行求解.张颖钰等[5]设计了一种与大变异邻域相结合的遗传算法,有效地解决了送取可以进行拆解的MDHOVRP问题.马冰山等[6]为改善生态环境,采用纯电动汽车进行配送服务,设计了一种改进的蚁群算法求解纯电动车配送的MDHOVRPTW问题.针对带时间窗同时送取车辆路径问题(Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows, 下文简称VRPSDPTW)Wang等[7]设计一种共同进化的遗传算法进行求解,同时还结合了Solomon算例,创造了VRPSDPTW基准实例.袁晓建等[8]研究VRPSDPTW问题时,设计了一种改进的量子算法,并对Wang的基准实例进行了测试.王超等设计了离散布谷鸟搜索算法[9]、回溯搜索优化算法[10]有效的求解了VRPSDPTW问题.张家善等[11]将差分进化算子与蜂群算法相结合,有效的求解了VRPSDP问题.黄务兰等[12]为研究VRPSDPTW问题,设计了一种经过仿真实验,来获取算法里具体参数的改进全局人工鱼群算法去求解该问题.李珺等[13]为研究VRPSDPTW问题,设计了一种自适应大规模邻域搜索与模拟退火结合的混合算法,对56个大规模算例进行验证.

综上所述,目前已有很多学者对MDHOVRP问题和VRPSDPTW问题进行了深入研究,但很少有学者将两个问题结合一起研究.因此本文从实际出发,研究了MDHOVRP问题和VRPSDPTW问题相结合的带软时间窗的多中心半开放式同时送取货车辆路径问题 (Multi-depot Half Open Vehicle Routing Problem with Simultaneous Delivery-Pickup and Soft Time Windows, 下文简称MDHOVRPSDPSTW),采用租赁第三方物流公司的车辆对客户点同时进行送取服务,车辆配送完路线上的所有客户点后,就近返回任意配送中心,缩短了配送路径,节约了配送成本.针对MDHOVRPSDPSTW问题的特点及其复杂性,设计了一种自适应精英算法求解,引入自适应机制和精英保留策略,既可以保护优秀个体,又增强了算法的全局搜索能力.通过具体的案例分析,验证了模型和算法的有效性.

1 数学模型

1.1 问题描述

本文所研究的MDHOVRPSDPSTW问题,定义如下:已知多个配送中心和若干个客户点的具体数目及坐标位置,采用租赁的外部车辆为客户点提供送取服务,每辆配送车辆相同,且为提高送取货效率,车辆载货空间可分为送货取货两个独立空间.车辆从任意配送中心出发,装载着配送路线所需配送的所有货物,对其配送路线上的所有客户点执行同时送取任务.车辆在配送过程中必须满足自身载重约束,当车辆服务完配送路线上所有客户点后,根据车辆服务路线中最后一个客户点离各个配送中心的欧式距离,就近返回某个配送中心.最后,车辆在其所返回的配送中心卸完所取的货后,自行返回第三方车辆租赁公司,决策的目标是求解得到既符合所有约束条件,又能使总配送成本最低的配送方案.

1.2 模型假设

为了求解MDHOVRPSDPSTW问题,建立了如下基本假设:

1)配送中心、客户点的坐标和数量已知;

2)客户点的送取需求和服务的具体时间窗均已知;

3)所有租赁车辆载重量和车型已知且完全一样;

4) 每个客户点由同一辆车同时提供送取服务,且送取需求能在1次配送中得到满足;

5)车辆匀速行驶;

6)采用原有配送中心进行配送不考虑其建设成本.

1.3 符号说明

1.3.1 模型参数

M{i|i=n+1,n+2,…,n+m}为配送中心集合,N{j|j=1,2,…,n}为客户点集合,V{k|k=1,2,…,K}为车辆集合,G为配送网络所有节点集合,即G={M}∪{N}.Zi为配送中心i(i∈M)的最大容量;cj为客户j(j∈N)的送货需求;wj为客户点j(j∈N)的取货需求;dab为节点a(a∈G)与节点b(b∈G)之间的距离;Ok为车辆k(k∈V)的派遣成本;F为单位距离车辆行驶成本;Q1为车辆k(k∈V)的送货装载容量;Q2为车辆的取货装载容量,tab为车辆k(k∈V)从节点a(a∈G)到节点b(b∈N)的行驶时间;[Ej,Lj]为客户点j的时间窗.Tbk为车辆k(k∈V)到达节点b(b∈N)的时间,ta为车辆在节点a(a∈N)处等待时间,t′a为车辆在节点a(a∈N)处的服务时间,Tbk=Tak+tab+ta+t′a,若b∈M时,Tbk=0.α为单位时间提前到达的惩罚成本,β为单位时间迟到惩罚成本.

1.3.2 决策变量

其中:a,b∈G,a≠b.

其中:k∈V,i∈M.

1.4 模型构建

(1)

(2)

(3)

(4)

(5)

(6)

xabk(Tbk-Tak)≥0, ∀a,b∈G,k∈V

(7)

Tbk=Tak+tab+ta+t′a,

∀a∈G, ∀b∈N, ∀k∈V

(8)

ta=max{Ea-Tak, 0}, ∀a∈G, ∀k∈V

(9)

yik={0,1}, ∀i∈M, ∀k∈V

(10)

xabk={0, 1}, ∀a,b∈G,k∈V

(11)

目标函数式(1)表示使总成本最小,其中包括运输成本、车辆租赁成本以及早到和迟到的惩罚成本;约束式(2)、(3)分别使得每辆车送货量、取货量小于其送货装载容量和取货装载容量;式(4)表示车辆只从其派遣的配送中心出发一次,服务完路线上所有客户点后,可以返回任意配送中心;式(5)表示配送车从哪个客户点进,也要从哪个客户点出;式(6)表示所有的客户点都只有1辆车服务;式(7)表示车辆提供送取服务有一定顺序;式(8)～(9)为客户点时间窗约束;式(10)～(11)表示0-1决策变量.

2 改进遗传算法设计

遗传算法(Genetic Algorithm)是美国John Holland教授在1975年率先提出的,是一种模拟自然环境中生物的遗传和进化过程搜索得到最优解的方法.该算法的特点是运算速度较快,相较于一般的精确算法更为简单,针对一般的复杂组合问题能得到较优的结果.

根据MDHOVRPSDPSTW问题的复杂性,本文设计了一种自适应精英遗传算法对其求解,引入了自适应交叉、变异算子与精英保留策略,不仅增强了算法的全局优化能力,还均衡了算法的局部搜索能力.自适应精英遗传算法的流程图如图1所示.

图1 自适应精英遗传算法流程图

2.1 编码与解码

2.1.1 编码

为更好的求解MDHOVRPSDPSTW问题,本文设计了一种双层编码的方式.假设有m个配送中心和n个客户点,第一层n个编码表示客户点的服务次序,第二层n个编码表示客户点为相应的配送中心的车辆进行配送.以下表示一个配送中心为2个,受灾点为10个的解的编码方式.

第一层编码19756321084

2.1.2 解码

如上述编码所示,由配送中心1发出的车辆服务的客户点有5、6、10、8,由配送中心2发出的车辆服务的 客户点1、9、7、3、2、4.本文所研究的路径是半开放式的,因此可先引进配送中心0,作为每条路径所服务的最后一个点距离最近的配送中心.以配送中心1发出的车辆路径为例,根据客户点的送取货量以及各种约束,假设分成两条路径并将配送中心0插入到上述路径中,则其对应的配送次序可为

156011080

若在第一条路径中,客户点6是路线里最后一个客户点,又与配送中心1的欧式距离最短,则配送车根据就近原则返回配送中心1,反之返回配送中心2.假设客户点6离配送中心1近,客户点8离配送中心2近则解码为

就近返回配送中心11561

2.2 初始种群的生成

由于使用随机的方法生成的初始种群,容易形成多个劣质方案,影响整体解的质量,故本文采用扫描法[14]生成初始种群,能使种群一开始就表现较优.具体步骤如下:1)建立一个极坐标系,并以配送中心为原点,过原点连接任一客户点形成射线并逆时针转动;2)叠加射线扫过扇面所包含客户点的送取量,当已扫过的客户点的送取量之和满足车辆送取量约束后停止转动,得到一个客户点分群;3)重复操作,建立新的客户点分群,直到所有客户点全部被覆盖.

2.3 适应度函数

本文针对MDHOVRPSDPSTW问题,建立了以总配送成本最小为目标的优化模型.令U=minZ,为使适应度函数最大化,则适应度函数可表示为f(x)=1/U.

2.4 遗传操作

2.4.1 选择操作

本文采用轮盘赌选择法来进行选择操作.

2.4.2 交叉操作

本文采用的是双层编码的方式,两层编码均可进行独立的交叉变异.在交叉操作中,第一层采用顺序交叉法,随机选择两条染色体,后对两条之中的任意一条染色体随机切片,并任意复制一个片段到子代的同样的位置,后在另一条染色体上将子代片段中没有的基因根据顺序填进去,另一个子代也采用同样的方法获得.第二层编码采用的是单点交叉法,随机选取两条染色体作为父代染色体,后在两条父代染色体上任意选择位置点进行切割,然后相互交换切割的右侧部分,以此获得两条不相同的子染色体.

2.4.3 变异操作

在变异操作中,本文两层编码均采用动态变异策略.即在父代染色体上,任意选择两个或以上的基因位,进行动态置换,经过置换的基因即为变异基因可遗传给子代,再继续进行后续进化.

2.5 自适应机制

本文引入自适应机制[15],该机制可以自适应地调动交叉概率pc与变异概率pm,能够防止算法局部收敛和早熟,提高了算法的全局搜索能力,缩短了算法的寻优时间.

(12)

(13)

2.6 精英保留策略

3 实例分析

3.1 基础数据

某企业有3个配送中心,租赁外部车辆,对20个客户点进行同时送取货服务.每辆车的租赁成本为480元,车辆的载货空间分为送货、取货两种空间,且送货、取货的空间容量均为100,配送车平均速度为60 km/h,单位行驶成本为3元.本文采用软时间窗约束,提前到达和迟到均惩罚100元/h,假定所有客户点的送取货的服务时间均为0.3 h.3个配送中心分别用A、B、C表示,其他数据见表1.

表1 配送中心和客户点数据

3.2 结果分析

本文利用Matlab R2021a软件进行案例仿真,算法参数设置如下:种群规模为100;最大迭代次数为500;基础交叉概率k1=0.8,基础变异概率k2=0.2.经过多次实验求解,求解得到最优总成本为4 534.99元,路线总长为704.12 km,共使用5辆车进行配送,时间窗惩罚成本为22.63元,见表2.图2、3分别为本方案的算法迭代图和配送路径图.从图2可以看出本文所设计自适应精英遗传算法,全局搜索性能较强,易跳出局部最优,收敛速度快.从图3可以看出半开放式配送路径的特点,车辆在服务完路线所有客户点后,不一定返回起始配送中心.每辆车具体服务的客户点及配送路径方案见表3.

表2 输出数据

表3 配送路径方案

图2 算法迭代图

该结果符合总成本最低的原则,减少了车辆的配送距离,使得资源得到合理的配置,证明了模型和算法的有效性.

4 结 语

本文将MDHOVRP问题和VRPSDPTW问题相结合,研究了MDHOVRPSDPSTW问题.构建了以配送总成本最小为目标的优化模型,更好地满足了物流企业运营的实际需求.该模型从全局的角度出发,有利于物流系统的整体优化,采取半开放式的配送方式,减少了车辆的配送距离,使资源得到合理的配置.在求解模型时,采用扫描法的方式生成初始种群,并引入精英保留策略和自适应机制,设计了自适应精英遗传算法.通过案例仿真实验验证了模型和算法的有效性.此外,在今后的研究中,可通过考虑时间窗的模糊性、交通运输的动态性和客户满意度使模型更好地满足不同情景的客户需求.