基于两种随机规划方法的取送车一体化路径优化

文/王建婷

引言

物流配送在我们生活中起着重要作用，已经成为货物运输中必不可少的一个环节。配送路径的优劣程度直接关系到物流公司、客户和社会环境的利益。所以，求解最优的配送路径是至关重要的。取送货一体化可以提高车辆利用率，解决空载问题，广泛地应用于实际生活中[1]。目前，已经有许多的国内外学者研究了考虑不确定因素的物流配送的路径规划。孙华丽和李钰峰等考虑了需求的不确定，分别以建立了多物资应急物流定位-路径模型和生鲜农产品物流配送路径规划模型[2，3]。方伯芃等考虑了不确定性因素，建立了不确定规划模型，并使用混合遗传算法对其进行了求解[4]。朱泽国以路段通行时间为不确定因素，建立了多车型物流配送路径规划模型[5]。DaratDechampai和EshetieBerhan等用差分进化法解决了具有取送车一体化的车辆路径优化问题[6，7]。EdwarLujanSegura等使用定位-路线禁忌搜索法解决了取送一体化的物流配送问题[8]。马春玲建立以总成本最小为目标的高铁末端取送路径优化模型[9]。AgustínMontero等用ILP方法解决了取送车一体化的物流配送车辆路径问题[10]。在以往的研究中，缺少用两种随机规划方法对取送车一体化配送问题进行建模。本文将用随机机会约束规划和随机相关机会规划对物流配送路径优化问题进行建模，并设计一定的混合遗传算法解决该模型的实际问题。

1.物流配送路径优化模型构建

1.1 问题描述

本文研究的是一个企业派多辆车在多个服务点取送货物过程中的路径规划问题。已知服务点的位置，服务点的送货量和取货量为不确定因素，其目标是使得车辆取送货物完成后的总成本最小。

1.2 基本假设和模型变量说明

1.2.1 假设条件

（1）假设车辆的起点和终点都为企业。（2）假设个服务点的取货量和送货量都不超过车辆的最大载重量。（3）假设每个服务点只能由一辆车服务，且不会出现服务不足。

1.2.2 模型变量说明

N为客户i的集合；K为从配送中心出发的车辆数；ck为车辆k的单位固定成本；dij为客户i点与j点的距离；Vk为车辆的行车速度；Qk为车辆k的最大载重量；cfk为配送车辆单位距离运输成本；qi和pi分别为客户点的配送量和取货量；[ei，li]为客户i的时间窗；tik为车辆k到达客户i点的时间；xijk为车辆k从客户点i到j则为1，否则为0；yik车辆从访问客户点则为1，否则为0。

1.3 数学模型

目标函数是总成本最小，包括运输、固定和时间惩罚成本；约束条件分别为：车辆的起终点都是配送中心、车辆流守恒约束、客户点被服务次数约束、车辆服务路径数约束、决策变量之间的关系，保证车辆在客户点服务时有路径连接、车辆的载重量限制约束、车辆在相邻节点间的载重量的关系、车辆到达客户点的时间。

2.物流配送路径优化的两种随机规划模型

实际生活中，往往有许多的不确定因素，本模型中考虑了客户需求和取货量的不确定性。并且不确定变量均服从正态分布。将以上两个不确定因素加入到上节的模型中并解决。

2.1 随机机会约束规划

本小节采用随机机会约束规划解决含有不确定因素的不确定模型。则可建立的随机机会约束规划模型为在上述模型的基

础上对部分约束条件进行如下修改：

2.2 随机相关机会目标规划

本小节采用随机相关机会目标规划解决含不确定因素的不确定模型。则建立的随机相关机会目标规划模型为上述模型的基础上对目标函数和部分约束条件如下修改：

3.算法设计

根据建立的模型，本文在遗算法的基础上引入随机模拟求解建立的模型。具体步骤如下所示：

随着国家中长期铁路网规划中四纵四横铁路快速客运通道逐步建设完成，客运专线已成为主要城市之间的重要运输通道。同时随着经济和城市建设的发展，各地主要城市均在大规模修建地铁，不可避免铁路客运专线与城轨交通交叉的工程实例渐多。

Step1：用神经网络预测送货和取货量，采用0，1，2，…n的自然数进行编码，配送中心用0表示，客户点的编号用其它整数表示；

Step2：初始化PS个染色体，并检验染色体是否满足约束条件；

Step3：利用训练好的神经网络计算所有配送方案的总成本；

Step4：根据适应度函数fi=1000/zii=1，2，…ps，计算每个染色体的适应度；

Step5：通过轮盘赌法以一定的概率选择较好的染色体；

Step6：设计交叉和变异算子，更新染色体。交叉操作为配送中心位置不变，将两个父代染色体的客户点基因位置交换，变异算子为将随机选中位置的基因颠倒插入。

Step8：最终找到最优解。

4.计算举例和结果分析

4.1 算例描述

本文以某商品配送公司开展的配送业务为例，有一个配送中心和15个配送点。假设该公司总共派5辆车进行本次运输，具体的车型参数信息如表1所示。

表1：车型参数信息

4.2 运算结果分析

利用MicrosoftVisualC++对实例进行求解，并以迭代次数为100，种群数为30，交叉概率为0.8，变异概率为0.1，对问题进行仿真得到的曲线图如图2所示，在迭代前期，适应度上升较快，随着迭代次数的增加，曲线逐渐趋于平稳，在迭代46次以后，适应度值稳定到一个固定值，进而得到最优解。

图2：目标值收敛趋势图

通过混合遗传算法对取送车一体化配送问题的求解，得到本次配送业务的总成本为1267.47元，其中运输、固定和时间惩罚成本分别为473.767元、560元和233.7元。最优运输线路0→6→12→11→0→7→8→10→0→2→15→5→0→1→4→0→14→9→3→13→0。例如车辆1表示从配送中心出发前往客户点6再到客户点12再到客户点11，最后返回配送中心,其余车辆路径的表示也与车辆1相同。

5.结论

通过两种不确定规划方法，研究了考虑不确定因素（取送货量）的取送车一体化的车辆路径优化问题，以配送总成本最小为目标建立了数学模型，并使用混合遗传算法验证算例，找到最优的配送路径。在以后的研究中，可以考虑多个不确定因素的车辆路径优化问题，找到更符合实际情况的车辆路径。

引用出处

[1]孟鹭.考虑客户需求重叠的取送货一体化车辆路径优化问题[D].大连海事大学.2017,6.

[2]李钰峰李攀郭盼雨.不确定需求下生鲜农产品物流配送路径优化研究[J].科学技术创新.2021.27:177-179.

[3]孙华丽，曹文倩，薛耀锋，王循庆.考虑路径风险的需求不确定应急物流定位-路径问题[J].运筹与管理.2018.27（7）：0037-0042.

[4]方伯芃，孙林夫.不确定环境下的产业链生产与配送协同调度优化[J].计算机集成制造系统.2018.24(1):225-245.

[5]朱泽国,广晓平,郭敏.不确定环境下的多车型物流配送路径优化[J].交通科技与经济.2021,23(2):6-12.

[6]Darat Dechampai,Ladda Tanwanichkul,Kanchana Sethanan,Rapeepan Pitakaso.Adifferentiale volution algorithm for the capacitatedVRPwithflexibility of mixing pickupanddeliveryservicesand the maximumdurationofarouteinpoultry in dustry[J].Intell Manuf.2017.28:1357-1376.

[7]Eshetie Berhan,Pavel Kr¨omer,Daniel Kitaw,Ajith Abraham,and-VaclavSn?aˇsel.Solving Stochastic Vehicle Routing Problemwith Real Simultaneous Pickupand Delivery Using Differential Evolution[J].Advancesin Intelligent Systemsand Computing237:187-200.

[8]Edwar Lujan Segura,JoséRodríguez Melquiades,Flabio Gutiérrez Segura.Tabu Searchfor Locating-Routingin the Goods Deliveryand Waste Pickupin Trujillo-Peru[J].exclusivelicenseto Springer Nature Switzerl and AG2021.295:51-69.

[9]马春玲.高铁快递物流末端取送系统优化研究[D].西安建筑科技大学.2020,6.

[10]Agustín Montero, Juan JoséMiranda-Bront, Isabel Méndez-Díaz.AnILP-basedlocal search procedure for the VR Pwithpickupsand deliveries[J].Ann Oper Res.2017.259:327-350.