A公司快递配送车辆路径优化研究

王剑泽 廖仪佳 郭婷婷

A公司快递配送车辆路径优化研究

王剑泽，廖仪佳，郭婷婷

（西南石油大学，四川 成都  610500）

摘  要：经济的增长及电商行业的兴盛，促进了我国快递行业的高速发展。为解决日益增长的快递配送需求和效益低下的传统快递配送之间的矛盾，文章以A公司北京市顺义区的快递配送为例，综合考虑车辆配送成本和一般路径约束等条件，构建了以配送成本最小为目标的车辆路径问题的数学模型，并运用遗传算法对模型进行了求解，最终有效地降低了A公司配送成本，优化了配送车辆调度，证实了算法的可行性。

关键词：物流配送；快递配送；遗传算法；路径优化

中图分类号：TP18    文献标识码：A  文章编号：2096-4706（2023）02-0141-04

Research on Path Optimization of Express Delivery Vehicles of Company A

WANG Jianze， LIAO Yijia， GUO Tingting

（Southwest Petroleum University， Chengdu  610500， China）

Abstract： The economic growth and the prosperity of the E-Commerce industry have promoted the rapid development of our country's express delivery industry. In order to solve the contradiction between the growing demand for express delivery and the traditional express delivery with low efficiency， this paper takes the express delivery of company A in Shunyi District， Beijing as an example， and comprehensively considers the conditions of vehicle delivery cost and general path constraints， and constructs a mathematical model of the vehicle path problem with the minimum cost for delivery as the goal， and the genetic algorithm is used to solve the model， which finally effectively reduces the delivery cost of company A. It optimizes the delivery vehicle scheduling， and proves the feasibility of the algorithm.

Keywords： logistics delivery; express delivery; genetic algorithm; path optimization

0  引  言

作为电子商务的重要构成，快递行业的发展同样遇到了许多问题，面临着挑战。尤其是配送的“末端”“最后一公里”等问题需要去探索和研究。快递配送不同于一般意义上的传统物流配送。相比传统物流，快递配送最重要的也是最突出的特点是快递件数非常多，且快递的体积较小，重量更轻。

快递配送路徑优化的核心问题是VRP（Vehicle Routing Problem）问题。国内外学者采用多种智能算法对此类问题进行了求解，大部分算法的求解效率都比较高。宋娟在解决同城快递配送问题上，对遗传算法进行改进，加入了模拟退火机制改善了寻优过程[1]。麻存瑞通过加入快件数量、快递员配送时间等考虑因素对快递配送路径进行了优化[2]。杨粟涵基于遗传算法，对合肥市蜀山区的知名快递企业进行了配送路径优化研究并降低了成本[3]。都雪静考虑车型和自提点因素对小件快递配送路径进行研究，并应用于某企业验证了可行性[4]。李玲玉结合地图软件通过C-W节约算法对快递配送地点间的真实路径进行了距离优化，降低了配送成本[5]。目前，快递配送的路径优化研究涉及的问题和研究很多，但是针对企业真实运营状况做出分析后的快递配送路径优化的实例论证存在不足，本文将针对A公司快递企业的配送情况进行分析后，运用遗传算法进行路径优化研究，提高配送效率，降低配送成本。

1  A公司快递配送情况简介

该公司在北京市顺义区设有一个配送中心及30个网点，主营的业务范围为来自各个平台消费者网购的各种快递包裹，主要以小件包裹为主，依据区域内客户订单的物品种类、规格、地点等信息需求进行扫描、分类，装卸和调度等，最终将物品送往各网点。30个网点的店面规模大小不同，所处位置不同，也因位置周围情况不同，各个网点快递配送的需求量也有着较大差距。所有网点的位置经纬度信息和快递配送需求量如表1所示。

该公司为满足配送需求，在配送中心配备了多辆配送汽车和驾驶员。一辆配送汽车给多个配送网点送货，配送汽车根据配送需求进行快递配送。出发从配送中心，执行完配送目标点后回到配送中心。配送车辆的配送固定成本为50元，单位配送成本为每千米5元。如图1所示，按以往经营情况，A公司的平均配送成本3 200 元～3 500 元，配送车辆通常要调用7～8辆。

由于快递体积小和重量轻，结合实际情况，配送车辆的配送限制为载货量件数，为200件。如图2所示，八月初的每日载货量与图1对应的配送车辆数的载貨量上限总和相比，相差较大，超出200件，说明配送车辆的调度不够合理，载货率较低。由此可以看出，A公司采用传统的物流配送方式，物流配送没路径规划，极大地影响了配送效率，造成配送成本偏高，因此需要对快递配送路径进行规划以降低配送成本，合理调度车辆。

2  模型构建

2.1  假设条件及参数定义

在对A公司顺义区快递配送路径优化问题建模的过程中，为保证模型构建的准确性，做相关假设如表2所示。模型参数的定义如表3所示。

2.2  目标函数模型建立

（1）

s.t：

（2）

（3）

（4）

（5）

（6）

式（1）表示目标函数由两部分组成，车辆固定成本和运输成本。式（2）表示如果配送车辆n从网点i驶向网点j，则Xijn等于1，否则等于0；式（3）表示如果配送车辆n为网点i提供服务，则Yin等于1，否则等于0；式（4）表示配送车辆会给所有网点配送货物且只由一辆车配送；式（5）表示所有配送车辆都会从配送中心出发，且完成配送后返回配送中心；式（6）表示每条路径上的配送货物件数不能超过配送车辆的载货量件数限制。

3  A公司快递配送问题求解

3.1  遗传算法编码与解码

遗传算法的编码方式非常多，根据要解决的问题和模型的构建来进行选择。该公司快递配送属于典型的VRP问题，故采用序列编码。配送中心通过数字0来表示起点和终点，用1、2、3等数字来表示表格里对应标号的配送网点。从配送中心出发的车辆，根据配送需求前往对应标号的网点后返回配送中心，数字编码的顺序就是配送车辆先后前往网点的顺序。例如一串编码为0-5-7-2-4-0，就表示一辆配送车辆从配送中心出发，先前往网点5进行配送，然后依次前往网点7、网点2、网点4进行配送，最终回到配送中心。同时编码所得到的染色体还要进行解码，从配送中心0开始，按照配送车辆的快件数量约束放入染色体基因序列中。若到某一配送网点时发现不满足约束时，就需要取消当前车辆在此网点的编码并返回配送中心，由下一辆配送汽车为该网点提供服务。若解码后满足所有约束条件，所得到的基因序列便是符合要求的配送路径。

3.2  遗传算子设计

具体内容是：

（1）交叉算子，编码序列进行部分位置的交叉完成交叉操作。

选择两个染色体的编码序列的对应部分作为交叉的区域，如A=02|53618|740，B=03|17586|420；将选择好的交叉区域分别加入都彼此的染色体编码中，且加入位置要相同。A′=0|17586|253618740，B′=0|53618|317586420；分别在A′和B′的原染色体编码部分依次删除与交叉区域重复的编码信息，得到A″和B″。A″=0175862340，B″=0536187420。

（2）变异算子，通过对染色体中的基因逆序排列完成变异操作。

（3）选择算子，采用轮盘赌的选择策略.在选择完成后采用精英法则，强行将上一代的最优个体直接进入下一代。

3.3  问题求解及结果分析

该公司配送中心周围有30个网点，同时配备了足够的快递员和配送车辆，配送车辆载货量的限制为200件。由上面的表1可知配送网点的经纬度坐标和货物需求量，为算法求解更加直观和快捷，对数据进行了处理。形成如表4和表5所示的形式，内容更加直观，但表4和表5因内容过多，只列出10个网点的内容作为示例。采用遗传算法对处理过的数据进行求解，利用MATLAB进行实现，设置种群规模N为80，最大迭代次数为200，交叉概率Pc=0.9，变异概率Pm=0.09。

通过仿真计算结果得到如图3所示的配送路径图。同时根据仿真结果的数据得到如表6所示的配送计划，最优解的序列就是配送车辆前往配送网点的排列。根据配送网点的件数累计和可知，共需要6辆车来进行快递配送，配送距离的总和为471。计算可得配送总成本6×50+471×5=2 805。同时也可以看到每条配送路径上的配送车载货量均超过150件，载货率超75%，且5辆车超过180件，达到90%。相比于A公司往日配送成本和配送车辆的数量使用均有明显降低，且从车辆调度来看，配送车辆的载货量也饱和。证明了路径规划合理，算法可行。

4  结  论

针对具体企业的快递配送路径优化，本文以快递企业A公司北京市顺义区的网点快递配送问题作为研究对象，在分析了A公司的网点快递配送情况后，构建了以配送成本最小为目标的配送路径模型并运用遗传算法进行了优化，通过MATLAB仿真得到A公司快递配送的最优路径。通过结果分析可知，优化后的路径有效降低了A公司的快递配送成本，车辆调度更加合理，车辆载货率整体饱和。本文提出的观点可以为快递企业的快递配送问题提供参考依据。但在研究过程中也发现了不足，此模型相对简单，没有考虑配送时间、车辆速度等其他次要因素，可以在后续的研究中进行改进。

参考文献：

[1] 宋娟，崔艳.基于改进遗传算法的同城快递配送模型 [J].电子技术应用，2014，40（12）：136-139.

[2] 麻存瑞，柏赟，赵欣苗，等.快递配送车辆路径优化研究 [J].交通运输系统工程与信息，2017，17（4）：182-187.

[3] 杨粟涵，于蕾.基于遗传算法的快递配送路径优化问题研究 [J].现代信息科技，2020，4（9）：99-100+103.

[4] 都雪静，孙菲菲，王云浩.小件快递配送路径优化研究 [J].物流技术，2018，37（4）：29-35+40.

[5] 李玲玉，张昆.快递配送路径的优化研究与软件设计 [J].计算机工程与科学，2019，41（8）：1406-1412.

作者简介：王剑泽（1997.04—），男，汉族，河北廊坊人，硕士研究生在读，研究方向：物流系统规划与设计。

收稿日期：2022-08-29