带时间窗的多中心半开放式VRPSDP问题研究.pdf

系统仿真学报系统仿真学报Journal of System Simulation第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023带时间窗的多中心半开放式带时间窗的多中心半开放式VRPSDP问题研究问题研究张颖钰1，吴立云1*，贾胜钛2(1.河南理工大学 工商管理学院，河南 焦作 454003；2.河南理工大学 能源科学与工程学院，河南 焦作 454003)摘要摘要：针对带时间窗的多中心半开放式同时送取货车辆路径问题，构建了配送中心车辆进出平衡且以车辆配送距离最小化为目标的带时间窗的多中心半开放式同时送取货车辆路径问题的数学模型。设计了混沌变异头脑风暴算法求解该问题，采用顺序交叉策略增加种群多样性，设置2种混沌映射进行混沌变异操作，利用混沌变异的多样性、遍历性和随机性，增强算法全局搜索能力。通过多组算例对比，不仅验证所提算法求解多种车辆路径问题的有效性与稳定性，还验证了带时间窗下的多中心半开放同时送取货配送模式优于多中心闭合式同时送取货配送模式。研究成果不仅拓展了车辆路径类的模型，还为相关物流企业提供一种决策参考。关键词关键词：车辆路径问题；多中心；同时送取货；时间窗；混沌变异头脑风暴算法中图分类号：TP391.9；F252 文献标志码：A 文章编号：1004-731X(2023)11-2464-12DOI:10.16182/j.issn1004731x.joss.22-0727引用格式引用格式:张颖钰,吴立云,贾胜钛.带时间窗的多中心半开放式VRPSDP问题研究J.系统仿真学报,2023,35(11):2464-2475.Reference format:Zhang Yingyu,Wu Liyun,Jia Shengtai.Multi-depot Half-open Vehicle Routing Problem with Simultaneous Delivery-pickup and Time WindowsJ.Journal of System Simulation,2023,35(11):2464-2475.Multi-depot Half-open Vehicle Routing Problem with Simultaneous Delivery-pickup and Time WindowsZhang Yingyu1,Wu Liyun1*,Jia Shengtai2(1.School of Business Administration,Henan Polytechnic University,Jiaozuo 454003,China;2.School of Energy Science and Engineering,Henan Polytechnic University,Jiaozuo 454003,China)Abstract:To solve the multi-depot half-open vehicle routing problem with simultaneous delivery-pickup and time windows,this paper builds a mathematical model of a multi-depot half-open vehicle routing problem with simultaneous delivery-pickup and time windows by balancing the vehicle in and out of the distribution center and minimizing vehicle delivery distance as the goal.According to the characteristics of the problem,a brain storm algorithm based on chaotic mutation is designed to solve this problem,and the sequential crossover strategy is adopted to increase the population diversity.Meanwhile,the algorithm selects two chaotic maps for chaotic mutation operation,which employs the diversity,ergodicity,and randomness of chaotic mutation to enhance the overall search capability of the algorithm.Multiple numerical example comparison not only verifies the effectiveness and stability of the proposed algorithm for solving various vehicle routing problems but also indicates the distribution mode of multi-depot half-open simultaneous delivery-pickup and time windows is superior to that of multi-depot simultaneous delivery-pickup and time windows.The research results expand the vehicle routing problem and provide a decision-making reference for related logistics enterprises.收稿日期：2022-06-24 修回日期：2022-08-22基金项目：国家自然科学基金(51874121)；NSFC-河南联合基金重点项目(U1904210)；河南省高校基本科研业务费专项资金(NSFRF180104)第一作者：张颖钰(1997-)，女，硕士生，研究方向为现代物流与供应链管理。E-mail：通讯作者：吴立云(1973-)，女，教授，博士，研究方向为现代物流与供应链管理、质量与安全管理等。E-mail：第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023张颖钰,等:带时间窗的多中心半开放式VRPSDP问题研究http:/www.china-Keywords:vehicle routing problem;multi-depot;simultaneous delivery-pickup;time windows;brain storm optimization algorithm based on chaotic mutation0引言引言近年来电商联盟发展迅速，人们对物流的服务要求逐渐提高，针对电商退换货的逆向物流也随之备受关注。因此国内外众多学者对车辆路径问题展开广泛研究，衍生出了多中心半开放式车辆路径问题(multi-depot half open vehicle routing problem,MDHOVRP)以及同时送取货车辆路径问题(vehicle routing problem with simultaneous delivery and pickup,VRPSDP)等众多 VRP 的拓展问题。为了提升服务质量和客户满意度，物流企业不仅要满足客户需求，还要考虑客户的服务时间窗。因此，本文研究了带时间窗的多中心半开放式同时送取货车辆路径问题(multi-depot half open vehicle routing problem with simultaneous delivery-pickup and time windows,MDHOVRPSDPTW)。该问题描述的配送网络包括多个配送中心和客户点，每个客户点同时具有送取货需求，所有配送车辆从配送中心出发对客户点执行送取货服务，且必须在客户点要求的访问时间内完成服务。相对于闭合式的配送中心，半开放式配送中心允许车辆完成配送任务后在保持配送中心车辆均衡的原则下可就近返回任意配送中心。MDHOVRPSDPTW问题更加符合现实物流配送的复杂情况，如在一个区域内含有多家配送公司负责多个小区的快递配送及揽收服务，通过配送中心与车辆之间的共享，缩短配送距离、减少用车数量，进而降低配送成本。MDHOVRPSDPTW问题是由带时间窗的同时送取货车辆路径问题(vehicle routing problem with simultaneous pickup-delivery and time windows,VRPSDPTW)和 MDHOVRP 结合而来。目前，针对该问题的研究涉及较少。但其包含的VRPSDPTW，MDHOVRP等问题仍是当前的研究热点。关于VRPSDPTW，MDHOVRP国内外学者都对其模型和求解方法进行了广泛和深入的研究。VRPSDPTW问题由Angelelli等提出，针对该问题设计精确算法进行算例规模为20 的小型算例求解1。但是精确算法会随着客户规模增大导致求解效率变低，故更多学者采用启发式算法对其进行求解。文献2对于VRPSDPTW问题采用协同进化遗传算法求解，并在经典算例Solomon的基础上设计了测试算例。文献3设计离散布谷鸟搜索算法求解VRPSDPTW问题，并与文献2做对比验证且更新了5个国际已知最优解。于次年又设计回溯搜索优化算法有效求解 VRPSDPTW 问题4。文献5为解决VRPSDPTW问题，提出基于模拟退火与自适应大规模邻域搜索结合的混合算法，对 56 个 大 规 模 算 例 进 行 验 证。关 于MDHOVRP问题的研究，文献6提出一种自适应局部搜索的混合遗传算法来求解带时间窗的多中心半 开 放 式 车 辆 路 径 问 题(multi-depot half open vehicle routing problem with time windows,MDHOVRPTW)。文献7针对 MDHOVRPTW 问题建立混合整数规划模型，提出一种基于3种有效局部搜索的构造型启发式算法并求得满意解。文 献 8 将 粒 子 群 算 法 与 遗 传 算 法 结 合 求 解MDHOVRP问题。文献9基于生鲜品的物流配送提出MDHOVRPTW配送模式，构建多目标优化模型并设计蚁群算法求解该问题。文献10将多中心联合配送与电动车辆结合，构建带时间窗的多中心半开放式纯电动车辆路径优化模型，并改进蚁 群 算 法 对 其 进 行 求 解。文 献 11 针 对MDHOVRPTW问题，设计了一种三阶段求解算法，并改进多蚁群算法求解该问题。文献12考虑软 时 间 窗 约 束 和 车 辆 速 度 变 化 情 况，针 对MDHOVRP问题，设计了改进粒子群算法和变邻域搜索算法的两阶段求解算法。综 上 所 述，国 内 外 文 献 主 要 集 中 在 对 2465第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023系统仿真学报Journal of System Simulationhttp:/www.china-VRPSDPTW问题及MDHOVRP问题分开的研究，将 VRPSDPTW 与 MDHOVRP 问题结合考虑的文献较少。此外在模型构建方面，多中心车辆路径文献中车辆大多数按照就近原则返回配送中心，容易造成配送中心车辆不均衡，甚至导致配送中心无车可用。本文在模型构建中加入车辆进出数量守恒约束，即车辆返回配送中心时应先满足配送中心车辆进出平衡，再实行就近原则。由于MDHOVRPSDPTW问题约束条件复杂，使求解难度进一步增加，为了提升求解效率和解的质量，本文设计了一种针对MDHOVRPSDPTW问题特点的混沌变异头脑风暴算法，采用k-means聚类操作，按照适应度值将相似的个体聚成k类，并引入顺序交叉策略，增强个体之间交流，增加种群的多样性。当算法陷入局部最优时，随机选取混沌映射，利用混沌变异的多样性、遍历性和随机性生成新的解集合，平衡搜索时的收敛和发散操作，进而提高算法跳出局部最优的能力。1MDHOVRPSDPTW数学模型数学模型1.1 问题描述问题描述本文研究的MDHOVRPSDPTW问题可以描述如下：在配送网络中存在多个配送中心和客户点，客户点同时具有送取需求，同一类型的车辆从任意配送中心以负载状态出发，对客户点执行送取任务，在一次服务中完成客户点的所有需求，车辆在配送路径中均满足自身载重约束、客户点与配送中心服务时间窗要求，当车辆完成配送任务后在保证配送中心车辆均衡的情况下就近返回任意配送中心。目标是找到一条满足所有约束条件的配送路径，并使配送距离最小化。模型假设如下：(1)配送中心、客户点的地理信息已知；(2)配送中心、客户点的服务时间窗信息已知；(3)客户点的送取需求已知；(4)同一类型车辆的最大装载已知；(5)车辆对客户点无服务顺序要求；(6)车辆匀速行驶。1.2 模型构建模型构建以配送距离最小化为优化目标，建立如下MDHOVRPSDPTW模型。最小化配送距离：Zmin=iVyVkKcijxijk(1)式中：cij为节点i到节点j的距离，ijV；xijk为车辆k是否从节点i到节点j，如果是，则xijk=1，否则，xijk=0。客户点需求不能被拆分且只能被一辆车服务：s.t.iVkKxijk=1jN(2)式中：N为客户户点合集，N12,n。车辆在路径上货物进出平衡：jVxijk=1kK(3)式 中：k 为 车 辆 标 号（车 辆 型 号 统 一），k12,K；K为车辆总数。iVxijk=iVxjikjNkK(4)车辆k从客户i到客户j的行驶时间等于客户i到客户j之间的距离与车辆行驶速度比值：tij=cijGijV(5)式中：cij为节点i到节点j的距离，ijV；G为车辆行驶速度；V为所有节点合集，V=NM。车辆行驶时间的连续性：wik+si+tij-wjkB(1-xijk)(6)式中：wik为车辆k对节点i开始服务时间，iV；si为客户户i的服务时间，iN；tiy为从节点i到节点j的行驶时间，ijV；B为足够大的正数。保证车辆满足客户点和配送中心的时间窗要求：ai(jVxijk)wikbi(jVxjik)iVkK(7)2466第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023张颖钰,等:带时间窗的多中心半开放式VRPSDP问题研究http:/www.china-式中：ai为节点i的左时间窗，iV；b为节点i的右时间窗，iV。车辆初始装载：L0k=iNdijNxijkkK(8)式中：di为客户户i的送货需求，iN。车辆完成任意客户点后的车辆载重及完成后不超过自身载重：LjLi-di+pj-B(1-kKxijk)iNjN(9)式中：Lj为车辆对客户j服务后的装载量，jN；pj为客户i的取货求量，jN。LjQ+B(1-iVxijk)jNkK(10)式中：Q为车辆最大载重；车辆从任意配送中心出发且仅离开一次，并最终返回任意配送中心：iMjNxijk=iNjMxijk=1kK(11)从配送中心出发的车辆数等于返回该配送中心的车辆数：jNkKxijk=jNkKxjikiM(12)决策变量取值：xijk01i.jVkK(13)2混沌变异头脑风暴算法混沌变异头脑风暴算法MDHOVRPSDPTW问题是NP-Hard问题，其多中心、半开放式以及时间窗等特点增加了求解难度。为了求解该问题，本文将头脑风暴优化(brain storm optimization,BSO)13算法和混沌变异策略14相结合，设计了混沌变异头脑风暴(brain storm optimization based on chaotic mutation,CMBSO)算法。传统头脑风暴算法是模拟人类求解问题集思广益的行为，由量变到质变的过程，其基本流程包含解码、聚类及迭代搜索。本文设计的CMBSO算法采用非0自然数编码，两段式解码，提高可行解的产生。在迭代搜索中采用顺序交叉策略与混沌变异策略，不仅扩大了算法的搜索空间，还增强了算法全局搜索能力，旨在获得高质量的满意解。2.1 编码与解码编码与解码本文采用非0自然数编码，将客户点随机全排列，所有客户点储存在C_Num中，18为客户点，记录服务顺序如图1所示。解码过程分为2个阶段。第1阶段，车辆依照从左到右顺序依次服务客户点，并进行载重、时间窗约束检验。若满足约束，则对客户点分配路径；否则，结束分配，由新派车辆进行服务。第2阶段，对每辆车服务首尾客户点随机分配配送中心，并进行车辆进出平衡约束检验，满足约束再按照就近原则，确定每辆车的始末配送中心。举例对图1进行求解。假设车辆k1在满足载重和时间窗约束下服务客户点4、客户点1，当对客户点3服务时不满足载重约束，则退出路径分配，由车辆k2继续服务客户点3、客户点2、客户点7和客户点6，车辆k2不满足客户点5的时间窗约束退出路径分配，由车辆k3进行余下客户点的服务。当路径分配完毕后，先对车辆服务的初始客户点按照就近原则分配配送中心，满足车辆进出平衡情况下，再对末尾客户点按照就近原则分配配送中心，911为配送中心。求解过程如图2所示。2.2 适应度函数适应度函数解码过程第2阶段确定始末配送中心时不一定满足时间窗需求，为保证解码的配送路径都是可行解，加入违反时间窗惩罚条件，以达到配送路线满足约束，惩罚函数为图1 编码示意图Fig.1 Encoding diagram 2467第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023系统仿真学报Journal of System Simulationhttp:/www.china-t(s)=i=1nmaxai-bi0(14)式中：ai为车辆到达客户点i(iN)的时间；bi为配送中心或客户点i的右时间窗，计算出违反时间窗约束之和的惩罚函数t(s)后，由目标函数确定适应度函数，个体S的适应度函数为fs=1Zs+t(s)(15)式中：Zs为个体s的目标函数值。2.3 聚类操作聚类操作CMBSO算法采用k-means聚类操作，具体步骤如下：step 1：随机选择m个个体作为聚类中心；step 2：依次计算每个个体的适应度值，与m个聚类中心适应度的差值的绝对值，将其差值的绝对值最小的聚类中心归到一个类中；step 3：求出每个类中的平均适应度值，将类中最接近平均适应度值的个体作为新类中心；step 4：判断是否达到终止条件(循环是否达到20次)，若是，则终止循环；否则转到step 2。2.4 更新操作更新操作本文采用交换、交叉操作增加种群多样性，加强个体间交流，快速形成稳定的下一代。交换规则如图3(a)所示，将客户点3和客户点6交换产生新个体。交叉操作的对象为2个个体，采用传统遗传算法中的顺序交叉策略，规则如图3(b)所示。随机选取客户点3和客户点6之间的客户点作为交叉片段，将g2交叉片段移动到g1前面，g1交叉片段移动到g2前面，然后从左到右将重复客户点删除，形成新个体g11和g22。图2 解码示意图Fig.2 Decoding diagram图3 交换和交叉操作Fig.3 Swap and cross operation 2468第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023张颖钰,等:带时间窗的多中心半开放式VRPSDP问题研究http:/www.china-2.5 局部搜索操作局部搜索操作本文设置更新操作完最优个体适应度值最大循环次数Dmax来判断个体是否陷入局部最优。当判断为否时，执行高斯变异操作，新个体为Xdnew=Xdold+N()(16)=logsig(Dmax/2-D)/k)rand(01)(17)式中：Xdold为选中个体；N()为均值是方差是的高斯随机函数；为高斯随机函数的系数；logsig()是S形变换函数；Dmax为最大迭代次数；D为当前迭代次数；k为改变logsig()函数的斜率；rand为(0,1)之间的随机数。高斯变异算子局部搜索能力较强，侧重于搜索局部区域，但是容易导致种群搜索停滞。当判断为是时，执行混沌变异操作，混沌解具有随机性和遍历性。本文选取2个混沌映射，分别为Sine混沌映射与Logistic混沌映射15，选取公式为x(n)i=randx(1)ix(2)i(18)Xdnew=Xdold+R(X(n)di-0.2)(19)R=Xdold-Xdcenter(20)式中：n12是选取混沌序号；i为混沌迭代次数；R为搜索半径；Xdcenter为原个体所在类的类中心的d维值。Sine混沌映射为正弦映射：x(1)i+1=sin(x(1)i)(21)式中：01。当越趋近于1时，混沌性越强，x(1)i(-11)，取x(1)i的绝对值。Logistic映射为x(2)i+1=x(2)i(1-x()2i)(22)式中：(14。当=4时，系统则处于完全混沌状态，x(2)i(01)。混沌映射的选取采用随机策略，既保留了个体多样性，也避免了算法复杂性的增加。算法流程图如图4所示。3实验与结果分析实验与结果分析MDHOVRPSDPTW 问 题 是 由 MDVRP、VRPSDPTW等问题衍生而来，本文所提算法释放部分约束可对 MDVRP、VRPSDPTW 问题求解。为验证本文算法的有效性，选用 MDVRP 算例、VRPSDPTW算例以及MDHOVRPSDPTW算例对其验证。本文在 Matlab2016B 中编程，并使用图4 CMBSO算法流程图Fig.4 CMBSO algorithm flow 2469第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023系统仿真学报Journal of System Simulationhttp:/www.china-InterCorei5-9400F CPU 2.94GHz计算机系统在Windows 10上执行，该系统具有16 GB内存。实验基本参数见表1，n为客户规模；N为种群数量；T为迭代数；J为聚类数目；Jmax为聚类最大循环次数；Dmax为局部最优解次数、Po为选取1个聚类的概率；Pt为选取2个聚类的概率。3.1 MDVRP算例验证算例验证实验实验 1：为验证 CMBSO 算法有效性，选取标准算例库中 MDVRP 算例中的 p01-p06 算例进行 验 证(算 例 集 来 源：http:/neumann.hec.ca/chairedistributique/data/mdvrp/old/)，并将本文算法运行10次的最优解与文献16的迭代局部搜索(iterated local search,ILS)算法、文献17的协同进化(co-evolutionary algorithm based on evolution strategies,CoES)算法以及文献18的自适应变邻域 文 化 基 因(adaptive memetic algorithm and variable neighborhood search,AMAVNS)算法作对比，结果见表 2。表中BKS为算例已知最优解，Best为算法运行 10 次的最优解，Dev为最优解偏差。由表2得出，粗略比较4种算法获得最优解个数，可得算法有效性 CMBSO(2)=AMAVNS(2)CoES(1)ILS(0)。比较4种算法的平均路程可得算法 有 效 性 CMBSO(742.67)CoES(722.86)AMAVNS(732.61)ILS(755.49)，比较4种算法最大Dev%可 得 算 法 稳 定 性 CMBSO(0.72)CoES(0.98)AMAVNS(3.80)ILS(6.09)。比较算法的平均Dev%可得算法的稳定性 CMBSO(0.21)CoES(0.36)AMAVNS(1.61)ILS(4.91)，通过比较验证了本文算法求解多中心车辆路径问题的优势与稳定性。3.2 VRPSDPTW算例验证算例验证VRPSDPTW算例选用Wang等在2012年公布的标准算例(算例集来源：http:/oz.nthu.edu.tw/d933810/test.htm)。该算例集共包含 65 个算例，分为9个中小规模算例和56个大规模算例。实验实验2：中小规模算例的验证中，选取9个算例，将本文算法与文献3提出的离散布谷鸟(discrete cuckoo search,DCS)算法与文献19提出的模因(memetic algorithm,MA)算法作对比，结果见表3。表1参数设置Table 1Parameter settingn0n2525n5050n100N50100100T100300100300100500J510510510Jmax202020Dmax205020502050Po0.50.80.50.80.50.8Pt1-Po1-Po1-Po表2实验1结果对比Table 2Result comparison of experiment 1算例P01P02P03P04P05P06Ave客户规模505075100100100719.95BKS576.87473.53641.191 001.59750.03876.50ILSBest606.11496.45675.321 062.60782.34910.13755.49Dev/%5.074.845.326.094.313.844.91CoESBest576.87475.06643.571 011.42752.39877.86722.86Dev/%0.000.320.370.980.310.160.36AMAVNSBest576.87473.53646.331 039.69765.98902.27734.11Dev/%0.000.000.803.802.132.941.61CMBSOBest576.87474.53642.271 001.59877.86882.88742.67Dev/%0.000.210.170.000.160.720.21 2470第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023张颖钰,等:带时间窗的多中心半开放式VRPSDP问题研究http:/www.china-由表4可知，本文算法求解VRPSDPTW问题中小规模算例均取得了最优解，验证了本文算法求解带时间窗的同时送取货车辆路径问题中小规模客户问题的有效性。实验实验3：为进一步测试本文算法性能，选取6个大规模算例进行验证，选取算例特点见表4。将本文算法与文献3提出的DCS算法、文献4提出的回溯搜索优化(bachtracking search optimization algorithm,BSA)算法以及文献20提出的变邻域双结构禁忌搜索(variable neighborhood search and bi-stracture based tatu seach,VNS-BSTS)算法作对比，结果见表5。由表5可知，对Cdp201算例，4种算法均取得了最优解；对Rcdp101算例的求解，本文算法弱于 DCS 算法与 BSA 算法，强于 VNS-BSTS 算法；对Rdp201算例的求解，本文算法弱于VNS-BSTS 算法，强于 DCS 算法与 BSA 算法；对Rdp101 算例、Cdp101 算例，本文算法与 VNS-BSTS 算法求解能力相同，均强于 DCS 算法与BSA算法；对于Rcdp201算例，本文算法求解结果均优于其他算法。另外，通过最大Dev与平均Dev对比可知，CMBSO(7.34)VNS-BSTS(8.39)BSA(12.94)DCS(14.66)，CMBSO(2.59)VNS-BSTS(3.20)BSA(4.26)DCS(4.54)，比较平均路程可 得 CMBSO(1 259.99)VNS-BSTS(1 269.78)BSA(1 280.72)DCS(1 284.17)，从而验证了本文算法求解带时间窗的同时送取货车辆路径问题中大规模客户问题的有效性与稳定性。表4大规模算例特点Table 4Characteristics of large-scale examples算例Rdp101Cdp101Rcdp101Rdp201Cdp201Rcdp201客户规模100100100100100100客户位置分布分散聚集分散与聚集混合分散聚集分散与聚集混合时间窗宽紧较紧较紧较紧较宽较宽较宽表5实验3结果对比Table 5Result comparison of experiment 3算例Rdp101Cdp101Rcdp101Rdp201Cdp201Rcdp201AveBKS1 650.20963.961 652.901 181.73591.561 326.191 227.81DCSBest1 658.65998.291 654.321 281.63591.561 520.561 284.174.54Dev/%0.513.560.088.450.00514.66BSABest1 659.77992.881 655.771 286.55591.561 497.801 280.724.26Dev/%0.583.000.178.870.0012.94VNS-BSTSBest1 650.80976.041 708.211 254.57591.561 437.481 269.783.20Dev/%0.041.253.356.160.008.39CMBSOBest1 650.80976.041 666.121 268.52591.561 406.941 259.992.59Dev/%0.041.250.807.340.006.09表3实验二结果对比Table 3Result comparison of experiment 2算例Rcdp1001Rcdp1004Rcdp1007Rcdp2501Rcdp2504Rcdp2507Rcdp5001Rcdp5004Rcdp5007客户规模101010252525505050BKS349.98216.69310.81551.05473.46540.87994.18725.59809.72BestDCS349.98216.69310.81551.05473.46540.87994.18725.59809.72MA349.98216.69310.81551.05473.46540.87994.18725.59809.72CMBSO349.98216.69310.81551.05473.46540.87994.18725.59809.72 2471第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023系统仿真学报Journal of System Simulationhttp:/www.china-3.3 MDHOVRPSDPTW算例验证算例验证实验实验4：MDHOVRPSDPTW问题相关约束较多，目前没有通用算例，本文选用标准算例库中MDVRPTW 算例 pr01-pr02(算例集来源：http:/neumann.hec.ca/chairedistributique/data/)，并 按MDHOVRPSDPTW问题的特点修改后进行验证。pr01算例包括48个客户点(编号为148)，4个配送中心(编号为4952)，车辆容量为200。pr02算例包括96个客户点(编号为196)，4个配送中心(编号为97100)，车辆容量为195。客户点的送取需求由文献21提出的需求分离规则产生：xi，yi为客户点的坐标，di，pi为客户点送货、取货需求，qi为客户点原始需求，ri=min(xi/yiyi/xi)计算每个客户点比率，由di=qiri和pi=qi(1-ri)，计算得出各个客户点的送取需求。将带时间窗的多中心半开放同时送取货配送模式与带时间的多中心闭合式同时送取货配送模式作对比，计算结果稳定，结果见表 6，Best，Avg，Num，Cpu为平均解和平均车辆数及平均算法运行时间。由表6可以得出，CMBSO算法求解两类配送模式的最优解偏差最小值为 1.01，最大值为6.54，能够有效的求出最优解且求解速度较快。在车辆总行驶距离方面，MDHOVRPSDPTW配送模式比MDVRPSDPTW配送模式分别优化了8.3与6.7。由图5最优解迭代图看出，CMBSO算法能够以较少的迭代次数快速收敛，具有较强的寻优能力。由表7可以看出，从MDVRPSDPTW配送模式到 MDHOVRPSDPTW 配送模式，配送中心由闭合式变为半开放式，实现了各配送中心间车辆共享，大幅度减少了车辆频繁往返同一配送中心产生的多余路径，进而降低物流企业的配送成本。表6实验4结果对比Table 6Result comparison of experiment 4算例pr01pr02客户规模4896MDHOVRPSDPTWNum59Best1 201.261 977.52Avg1 285.312 073.01Cpu/s4.313.6Dev/%6.544.61MDVRPSDPTWNum59Best1 310.312 118.88Avg1 351.472 140.52Cpu/s3.720.4Dev/%3.051.01图5 MDHOVRPSDPTW模式下最优解迭代图Fig.5 Optimal solution iteration under MDHOVRPSDPTW mode 2472第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023张颖钰,等:带时间窗的多中心半开放式VRPSDP问题研究http:/www.china-4结论结论本文针对提出的MDHOVRPSDPTW问题主要进行了以下研究。构建车辆进出平衡且以配送距离最小化的带时间窗的多中心半开放式同时送取货车辆路径数学模型。设计混沌变异头脑风暴算法对该模型求解，通过多组算例验证了算法的稳定性与有效性。对MDHOVRPSDPTW配送模式与MDVRPSDPTW配送模式作对比，验证了前者大幅度减少了车辆频繁往返配送中心产生的配送路径，降低了配送成本。随着生活质量的提高，人们对于物流配送的质量、时效等需求越来越高，MDHOVRPSDPTW配送模式可更好地满足客户的配送需求，在车辆路径中考虑碳排放约束、客户满意度等多方面因素将是下一步研究的方向。参考文献参考文献：1Angelelli E,Mansini R.The Vehicle Routing Problem with Time Windows and Simultaneous Pick-up and DeliveryC/Quantitative Approaches to Distribution Logistics and Supply Chain Management.Berlin,Heidelberg:Springer Berlin Heidelberg,2002:249-267.2Wang H F,Chen Y Y.A Genetic Algorithm for the Simultaneous Delivery and Pickup Problems with Time WindowJ.Computers&Industrial Engineering,2012,表7实验4最优解路径Table 7Optimal solution paths of experiment 4模式MDHOVRPSDPTWMDVRPSDPTW算例pr01pr02pr01pr02车辆行驶路线49-42-46-39-2-15-25-26-23-36-32-4951-33-13-8-29-20-4-19-22-5050-9-47-24-12-30-40-38-21-43-5252-44-31-41-7-37-28-14-1-5-17-