《基于不同车型的城市快递配送车辆路径优化研究》-工学论文，工程论文-论文范文参考-科学狗论文网

标题

基于不同车型的城市快递配送车辆路径优化研究

范文

邓学平　孙芹　田帅辉

摘要：在城市快遞配送的业务中，车型的不同以及配送线路的选择都会影响企业的成本、效益。如何能够在不同车型的情况下，选择合理的配送线路，保质保量的完成快件的配送。在此背景下，本文建立了基于时间窗、多车型城市快递配送路径优化的成本最小化数学模型。使用两点互异和两点交叉改进的遗传算法对模型进行计算。运用Matlab软件对城市快递配送算例进行仿真，验证模型的有效性及适用性。

Abstract： In the business of urban express delivery， the different models and the choice of distribution routes will affect the cost and benefit of the enterprises. How to choose a reasonable distribution route in the case of different models， and complete the delivery of express mail with quality and quantity guaranteed？ In this context， this paper establishes a mathematical model of cost minimization based on time window and multi-model city express delivery route optimization. The model is solved by an improved genetic algorithm with two points crossing and two different points. The Matlab software is used to simulate the urban express delivery example to verify the applicability and effectiveness of the model.

关键词：城市快递配送;时间窗;多车型;遗传算法

Key words： urban express delivery;time windows;multi-model;genetic algorithm

中图分类号：F570.5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文献标识码：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章编号：1006-4311（2020）12-0275-06

0? 引言

近几年，随着知识的进步，科技日新月异的发展，人们迅速步入了信息社会。为了便捷，热衷于网购的人逐年增多，快递也渐渐成为网购者日常生活的一部分。据国家邮政管理局最新统计数据显示：2019年1月至9月全国快递业务量达439.1亿件，同比增长26.4%;业务收入为5271亿元，同比增长24.1%。其中，同城业务量为78.3亿件，同比下降1.7%;异地业务量为350.7亿件，同比增长35%;国际/港澳台业务量为10亿件，同比增长27.2%。快递公司为了提升自身行业竞争力，往往在快递配送过程中把客户满意度和配送成本作为首要目标，然而目标的实现需要在配送路径上体现。因此如何选择合适的配送线路，既能在客户要求的时间内将快件准时无误送达，又能为企业节约成本显得尤为重要。

对于车型不同车辆路径问题方面的相关研究，葛显龙[1]等人根据动态信息产生的时间点不同，提出时间轴的概念，建立多车型车辆调度模型。仝凌云[2]等人从低碳环保角度出发，建立以油耗费用和固定发车费用为优化目标的低油耗多车型的数学模型。陈呈频[3]等人针对解的质量差和求解效率低的问题，建立了多车型多车场的整数规划模型。

对于城市快递配送问题方面的研究，张晓[4]根据在城市快递配送过程中存在的许多特点，构建双类别快递配送模型。杨志清[5]考虑到时间的不确定性以及车型的因素，构建了带时间窗的多目标车辆路径问题模型。

对于VRPTW，国内外对此也进行了研究，文献[6]构建了基于时间窗的逆向物流车辆路径模型，采用混合优先级嵌套遗传算法进行求解。文献[7]在设计局部优化框架的基础上，结合遗传算法来解决带时间窗的车辆路径问题。文献[8]构建了关于硬时间窗的随机动态问题模型。

本文主要研究基于车型不同的带时间窗的城市快递配送路径优化问题，建立配送成本最小化为目标的车辆路径优化模型，并采用改进的遗传算法对其模型进行求解。

1? 问题描述及模型

1.1 问题描述

基于不同车型的城市快递配送车辆路径优化研究可以详细描述为：快递企业根据区域内每个站点需要派件的快件数量，在已知转运中心条件下，寻找最佳快递配送线路，不仅使企业的快递配送成本最小而且又能在站点要求的时效内将快件送达。

实际场景：将快递配送系统中的节点简化为转运中心、站点。配送网络结构图如图1所示，不同车型的配送车辆从转运中心出发，按照一定的线路经过各个站点为其提供服务，最后回到转运中心，形成一个闭环环路。在快递的实际配送过程当中，我们不能把所有的配送车辆都认为是同种车型，车型不同，车辆的油耗不尽相同，产生的运输成本也就不同。因此，我们必须考虑不同车型产生的油耗成本即运输成本。本文的目标函数是实现企业的快递配送成本最小，包含配送车辆的时间惩罚成本和运输成本。

1.2 模型假设（表1）

1.3 参数定义

1.3.1 参数定义

本文模型中的已知参数含义如表2。

1.3.2 决策参数定义

本文模型中的已知参数含义如表3。

1.4 目标函数定义

目标函数：右边第一部分表示车型为r的车辆空载时的耗油成本，第二部分表示车型为r的车辆k从站点i行驶到站点j的耗油成本，第三、四部分为时间惩罚成本。

2? 模型求解

为解决不同车型城市快递配送车辆路径优化问题，使用改进的遗传算法对模型进行计算。车辆的配送路线用染色体编码来转化，基因则代表转运中心、配送站点，形成初始种群;对超过配送站点时间限制的车辆进行对应的惩罚，计算目标函数的最小值，得到个体适应度;再对种群进行选择、交叉、变异和多次迭代后，最终形成最优路径。

2.1 染色体编码

對于城市快递配送车辆调度问题而言，遗传算法主要是解决快递车辆服务的客户群问题，所以序列编码的方法比较适合文献[9]。用数字0表示转运中心，1，2，…，n表示n个站点，将2个数字0分别作为染色体的头部和尾部，剩余的数字0嵌插到1，2，…n之间，形成0，1，2，3，4，0，5，6，0，…，n，0这样的染色体编码结构，两个0之间的部分代表染色体的一条子路径。例如染色体编码（02560840317090）所代表的实际含义为车辆一从转运中心出发，依次经过配送站点2，5，6，最后返回到转运中心，是第一条子路径;车辆二也是从转运中心出发，依次经过站点8，4，返回到转运中心，是第二条子路径;车辆三从转运中心出发，依次经过站点3，1，7，返回到转运中心，是第三条子路径;车辆四从转运中心出发，经过配送站点9返回到转运中心，是第四条子路径。

相对应的配送路径如下所示（0表示转运中心）：

第一条路径：0-2-5-6-0

第二条路径：0-8-4-0

第三条路径：0-3-1-7-0

第四条路径：0-9-0

2.2 初始种群

虽然初始群体的解分布不影响目标函数的最优解，但是如果初始群体的解是均匀分布的，则会大大减少算法陷入局部最优的可能性，所以本文在保证多样性的同时，随机产生初始群体。

2.3 适应度函数

本文的适应度函数为目标函数的倒数，其中fi是染色体的适应度值，Zi是染色体i的目标函数值[10]。

2.4 选择算子

本文采用轮盘赌[11]选择算子的方法来保证种群的多样性同时避免适应度高的个体被后续的遗传操作改变。详细选择操作如表4。

2.5 交叉操作

本文交叉操作选用两点交叉法[12]，具体的操作描述如下：假设存在两个父代个体为“5，4，1，6，2，9，7，8，3”和“1，3，7，4，6，8，2，9，5”。首先确定交叉的起始位置，对两个位置中间的数据执行交叉操作。其次为冲突检测。最后形成新的染色体。交叉操作的过程图如图2。

2.6 变异操作

本文采取两点互异[12]的变异操作。变异操作简单来说就是等位基因的替换，以此来形成新的个体。一个父代染色体的基因为“1，3，7，4，6，8，2，9，5”，变异基因节点为7和2，变异操作的过程只需要交换节点7和2的位置，就形成了新的基因。变异操作的示意图如图3。

2.7 算法终止条件

运用遗传算法进行计算的时候，当出现以下几个规则时，停止运行算法：①算法运行到事先设定的迭代次数或者达到实现预设的时间值;②连续进行若干次迭代，但都没有更好的适应目标值;③根据设定的问题边界，并结合偏差值来进行运算，当所求结果的偏差水平处在合理范围时，则停止运行算法并将求解的数值输出。

2.8 遗传算法参数

①种群规模：200;②迭代次数：300;③变异概率：0.01;④交叉概率：0.8。

2.9 算法灵敏度分析

遗传算法中有许多参数设置，参数不同，出现的最终结果也不尽相同。参数设置包括：种群规模、迭代次数、变异概率、交叉概率。以下详细阐述不同参数设置对算法的影响。

①种群规模。

分别选取100、150、200、250、300的种群规模，运行5次，取其平均值，其他参数设置为：停止迭代次数200次，变异概率0.01，交叉概率为0.8。详细数据如表5。

种群规模为100、150、200、250、300，目标函数收敛图如图4、图5、图6、图7、图8。

从表5可以看出，收敛代数以及最优解都随着种群规模的变化而变化，但没有明显的变化趋势。

②迭代次数。

分别选取300、400、500、600、700的迭代次数。其他参数设置为：种群规模为200，变异概率0.01，交叉概率为0.8。具体数据如表6。

从表6可以看出，收敛代数以及最优解也是随着迭代次数的变化而变化，但没有出现明显的变化趋势。

③变异概率。

分别选取0.01、0.04、0.08、0.1、0.12的变异概率。其他参数设置为：种群规模为200，停止迭代次数300，交叉概率为0.8。具体数据如表7。

从表7可以看出，随着算法变异概率的改变，迭代次数没有一个固定的变化趋势，最优解的呈现先减小后增大。

④交叉概率。

对于算法中的交叉概率，分别取0.4、0.5、0.6、0.8、0.9。其他参数设置为：迭代次数为300，变异概率为0.01，种群规模为200。具体数据如表8。

从表8可以看出，随着算法交叉概率的改变，迭代次数先增大后减小，最优解没有固定的变化趋势。

3? 算例验证

3.1 数据生成与处理

以百世快递重庆分公司为例，整个大重庆市内，只有1个转运中心，69个下属站点。假设转运中心有三种不同的车型，载重量分别为3t，5t，8t，载容量分别为2000，3000，5000，不设定三种配送车型的最大行驶距离，三种车型的费用参数见表9，转运中心数据见表10，69个站点的坐标和快件量见表10。假设配送车辆早于站点要求的时间内到达的成本5元/小时，晚于客户要求时间到达的成本10元/小时，计算的距离为两个站点之间的直线距离，该距离可以通过百度APP计算得到。

根据转运中心及各个站点自身的经纬度，利用地图慧App，把每个点在百度地图上表示出来，如图9。

3.2 结果分析

①利用MATLAB軟件对该模型进行求解，基于不同车型的城市快递配送车辆路径优化研究问题的详细结果可以表述表述为：总共需要11辆配送车辆，即3辆车型一的配送车辆，4辆车型二的配送车辆，4辆车型三的配送车辆，最小配送成本为4074元。具体的如表11所示。

最优的目标函数收敛图10。

从图10可以得出，在最初算法优化阶段，迭代次数达到10时最优个体适应值急速下降，但随着迭代次数的逐渐增加，最优个体适应值的下降逐渐平缓，并在第196代收敛于最优解4074。

4? 结束语

本文针对不同载重的城市快递配送车辆，采用以百世快递为主体，把重庆市内每个配送站点的时间要求转化为时间成本加入目标函数中，建立一个不同车型的受时间窗约束的配送车辆路线模型，最终目标是求解配送车辆的最小成本。运用改进的遗传算法对其模型进行求解，同时对遗传算法进行灵敏度分析，并用Matlab软件对其案例进行仿真，得到本文车型不同的城市快递车辆路径问题的最优路径。本文提出的观点为快递企业的快递配送问题提供参考依据。本文在研究不同车型的城市快递配送的问题中，没有考虑速度的变化，文章假定的是相同速度，可在以后的研究中进行改进。

参考文献：

[1]葛显龙，许茂增，王伟鑫.多车型车辆路径问题的量子遗传算法研究[J].中国管理科学，2013（1）：125-133.

[2]仝凌云，王琳.低油耗多车型车辆路径问题及算法[J].河北工业大学学报，2019，48（02）：94-100.

[3]陈呈频，韩胜军，鲁建厦，等.多车场与多车型车辆路径问题的多染色体遗传算法[J].中国机械工程，2018，29（02）：96-101.

[4]张晓.城市快递配送车辆路径规划研究[D].2016.

[5]杨志清.城市快递配送条件下的多目标车辆路径优化研究[D].

[6]Ma Y ， Li Z ， Yan F ， et al. A hybrid priority-based genetic algorithm for simultaneous pickup and delivery problems in reverse logistics with time windows and multiple decision-makers[J]. Soft Computing - A Fusion of Foundations， Methodologies and Applications， 2019.

[7]Ursani Z， Essam D， Cornforth D， et al. Localized genetic algorithm for vehicle routing problem with time windows[J]. Applied Soft Computing Journal， 2011， 11（8）：5375-5390.

[8]Chang T S， Wan Y W， Ooi W T. A stochastic dynamic traveling salesman problem with hard time windows[J]. European Journal of Operational Research， 2009， 198（3）：748-759.

[9]胡乃平，于丰平.基于混合遗传算法的车辆路径优化问题研究[J].计算机与数字工程，2018，46（6）：1123-1129.

[10]陈婷.基于带时间窗的快递车辆路线安排问题研究[D].

[11]宋汶轩.城市快递配送车辆路径规划研究[D].北京邮电大学，2019.

[12]邓学平，周昔敏，田帅辉.B2C电子商务物流中心选址-路径综合优化研究[J].重庆邮电大学学报（自然科学版），2016，28（04）：593-600.

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。