基于遗传算法的快递配送路径优化问题研究

杨粟涵　于蕾

摘  要：以数字型基础设施为代表的“新基建”目前处在起步阶段，面对经济下行的压力，夯实物流产业基础，可合理规划配送路线来提高物流配送效率。以合肥市某知名快递企业配送路径优化问题为研究对象，分析该企业配送问题，建立以配送网络成本最小为优化目标的数学模型，采用基本遗传算法的流程为模型设计算法，仿真运行得出结论。

关键词：配送路径;遗传算法;优化模型

中图分类号：TP18;F252       文献标识码：A 文章编号：2096-4706（2020）09-0099-03

Research on Optimization of Express Delivery Route Based on Genetic Algorithm

YANG Suhan，YU Lei

（Hefei Technology College，Hefei  230011，China）

Abstract：“New infrastructure” represented by digital infrastructure currently in its infancy. In face of economic downward pressure，laying solid foundation of logistics industry，a reasonable planning route can be distributed to improve the efficiency of logistics distribution. A famous express enterprises in Hefei distribution route optimization problem as the research object，analyzing the enterprise distribution problems，establishing a distribution network，and the mathematical model of objective function is minimum cost，using the basic process of genetic algorithm for the model to design algorithm，and simulation in order to draw the conclusion.

Keywords：delivery route;genetic algorithm;optimal model

0  引  言

電商产业的蓬勃兴盛及O2O商业模式的不断成熟，促进了物流行业的飞速发展，物流业的发展程度已然成为衡量我国现代化程度的重要指标之一。特别是目前新冠肺炎疫情时期，基于人工智能的物流网络展现出惊人的效率，避免了灾难性的物资短缺。打赢疫情防控阻击战，物流产业基础是重要因素，不仅依赖于物流快递业的个体担当、企业情怀，也要依赖国家的产业支撑、政策扶持。面对日前经济下行的压力，我国多次提出加快“新基建”、培育新动能，然而以数字型基础设施为代表的“新基建”却处在起步阶段。因此加快“新基建”可以对冲疫情不利影响，为应对经济下行压力、推动高质量发展提供着力点。

在物流行业的“最后一公里”物流配送环节上，数字化智能化水平不尽如人意，配送成本居高不下，而配送安全性和时效性又是影响客户满意度的重要因素，因此关于物流配送的路径优化问题一直受到不少学者的关注并取得一定成效。如赵娜研究餐饮领域的配送问题，设计配送路线，在车辆路径优化的基础上加入时间窗，建立了VRPTW问题模型，并且设计遗传算法进行优化求解[1];詹斌等借助云计算和大数据对电商物流末端配送进行分析，提出可视化配送服务一系列创新思路[2];涂汉江针对TSP问题（Travelling Salesman Problem）对外卖配送路径优化进行建模，用分支限界法求解，建立一个外卖订餐系统[3]。针对我市蜀山区某知名快递企业的现状，文章用遗传算法研究其辖区配送路径优化问题。

1  快递企业配送路径优化问题分析

1.1  问题描述

以安徽省合肥市蜀山区某知名快递企业的直营站点配送路径优化为对象进行研究。通过调研得知，该企业在蜀山区设1个配送中心、15个站点，主营业务范围为末端配送，依据辖区顾客电子订单的物品种类、规格、数量、时间、地点等顾客信息需求来进行扫描、分类、装卸搬运、调度等，最终将物品送往各站点。由于该企业并未形成完善的配送体系网络，物流装备的标准化程度低，极大地影响了配送效率，并且合理配送计划的缺乏造成配送成本虚高，因此亟需建立数字化智能化的物流网络。

该企业的一个配送中心处在蜀山区各站点的中心区域，占地面积大，配送业务主要集中在各类网购的快递包裹，并且具备一定数目的配送员和配送车辆，一名配送员驾驶一辆车给若干个站点送货，每名配送员根据分配到的目标执行配送任务，且都是从配送中心出发，完成配送任务后返回配送中心。15个站点的门店分布不均，处在不同的地理位置，具有不同的经营状况，送货时间和货物需求量也不尽相同，所有物流点的地理位置和货物需求量都是已知的，如表1所示。配送到达站点的停滞时间忽略不计，主要考虑的是配送过程所消耗的时间，配送员配送时也需要完成退货等逆向物流货物的处理，并且带回配送中心。各个配送员的工作内容不交叉，可以看作是MTSP多旅行商问题（Multiple Traveling Salesman Problem）或者分成M个TSP问题[4]。

1.2  模型建立