小件快递配送路径优化研究

（东北林业大学 交通学院，黑龙江 哈尔滨 150036）

1 引言

在电商的大环境下，网购已经成为消费主流，自2009年以来“双十一”网上零售额呈井喷式增长，2016年达到1 207亿元，且有继续增长态势[1]。中国青年报社社会调查中心通过问卷网对2 000人进行了一项调查，调查显示，87.8%的受访者遇到过快递延误送达的情况，其中10.0%的受访者经常遇到。58.4%的受访者表示会联系快递员询问原因，50.7%的受访者会催促快递员赶快配送，18.1%的受访者坦言会向快递员发火或言语威胁[2]。这充分说明快递配送问题很大程度上会影响消费者选择快递公司。

王磊通过对国外配送方式的介绍，指出了国内配送方式的不足，提出了推进O2O与社区便利店紧密结合的运营模式，注重城市末端物流配送商业价值，搭建自提柜服务信息平台，打通“最后一公里”服务的信息流等措施[3]。蔡稳提出通过构建末端共同配送联盟整合线下终端资源，建立以提高末端配送服务质量为核心的智能化末端共同配送站点[4]。尹玉纯提出使用最短距离策略和聚类策略对客户点进行聚类，将多配送中心问题转化为多个单配送中心问题；基于遗传算法和禁忌搜索算法设计混合遗传禁忌搜索算法，并对末端配送网络集配一体化VRP问题求解[5]。张茂秋和刘克岩提出自提柜的末端物流配送模式，介绍该模式的配送流程，分析该模式目前所存在的问题并提出建议[6]。吴竞鸿和吕能芳设计快递企业末端配送众包模式的总体框架结构，提出快递企业构建末端配送众包模式的关键策略[7]。王冬良和杨彩梅基于二维码的智能末端配送系统将二维码作为客户与订单的对应码，利用二维码的快速识别与防伪特性，结合配送柜的按条码开箱功能实现末端配送系统的智能化[8]。李小芳提出了两种收益分配方式，即服务水平补偿方式、收益共享—成本共担方式，以期通过模型计算和比较分析，从中筛选出能有效协调快递服务链的收益分配方式[9]。陈永平和李赫结合大数据时代的物流末端配送需求变化，提升大数据时代物流末端配送的价值创造能力[10]。

Yang Bin提出了一种非线性惯性权重和时变加速度系数自适应粒子群优化（APSO）算法，以实现配送中心选址问题的自适应。根据假设和约束建立物流配送中心选址的数学模型，然后以平均粒子间距作为种群多样性的指导因子建立非线性惯性权重，采用反余弦函数设计非线性对称加速度系数，以控制配送中心选址问题的全局搜索能力和局部搜索能力的平衡[11]。同时还提出一种评估物流服务有效性的新方法，以及一个实现该方法的特定计算机系统-一个复杂的推理系统，即Mamdani概率模糊系统的扩展。Katarzyna Rudnik和Iwona Pisz提出了模糊规则形式的有效性指标与模糊事件边际和条件概率之间关系的具体知识，还显示了推理图，提出了Yager参数化t-范数族作为推理算子。它有利于系统参数的优化，并实现了系统对经验数据的灵活调整[12]。Liu Hui和Chen Min研究基于旅行商问题解决方案的物联网（IoT）下物流配送系统的大型公司物流模拟，指出实时交通协同效益总体上优于传统的分配策略，并对不同目标情况下的仿真结果和起始时间分布进行验证和比较，证明信息协同对系统运行效率有明显提升作用，充分利用信息价值，把信息协同提高到最佳水平，对系统运行效率具有不可替代的作用[13]。Julian Becker提出配送物流的设计对公司物流成本和业绩有着决定性的影响，并介绍了一种分析物流成本和绩效方面分销物流潜力的方法，将分销物流整体映射到变量分配结构下，该方法具有高度的实用性和适用性，有助于更有效地设计配送物流[14]。Yong Ming针对交通组织时间受限的城市物流配送优化问题，提出了考虑企业配送成本、环境成本和配送时间的双层规划模型。上层模型的主要功能是最小化配电企业的一般成本，并确定优化城市物流配送的方案。下层模型是城市交通均衡分布模型，用于分析由上层模型给出的城市物流配送优化方案的选择行为确定的配送路径[15]。Sun Jie和Wang Xin提出物流配送方式一直是制约鲜活农产品电商发展的瓶颈因素。在研究传统物流配送模式的基础上，指出了如何建立电子商务物流配送系统的五个问题；分析了鲜活农产品电子商务物流配送模式和业务流程，总结了鲜活农产品电子商务物流配送的优势和问题;最后提出了合理的农产品电子商务物流配送模式建议[16]。Tang Ruixue和Qin Yongbin提出物流配送问题是现代物流系统的重要组成部分，并通过对现有物流系统的特点分析，建立数学模型，提出了基于并行多群体的多供应商物流配送优化算法和启发式物流配送算法。第一种算法考虑到客户的要求，充分利用车辆的载荷，合理选择配送路线，运输成本较低，但时间成本较高。第二种算法加入了启发式算法，引入了可度量比，从而得到更快的收敛速度和更高质量的全局最优解[17]。Zhang Qingyun和Liu Junhui提出联合配送能够整合社会资源，提高物流配送效率，缓解城市交通，减少环境污染，改善城市物流[18]。

从学者们的研究可知，对于快递企业而言，解决配送问题始终是降低成本的最有力的途径。在城市物流配送的问题上，很多研究都是在单目标优化的思路上来展开的，很少考虑多目标的优化，大部分只是将目标函数赋予相应的权重直接线性相加，忽略了量纲和权重影响因子不统一的问题，从而导致多目标效果的弱化。因此需要对目标函数进行特殊和严谨的处理，消除量纲的影响作用，转化为一般常数进行求解得出较佳的结果。

基于此本文针对小件快递末端配送，提出了在客流量大的地铁站设立自提点的方式，主要以降低运输成本、减少货物到达客户手中的时间和降低汽车尾气碳排放量为目标，建立多目标VRP模型，合理安排车辆的配送路线和行车时间，针对建立的模型用遗传算法求得问题的最优解，实现总成本最小、运输所花时间最短以及车辆碳排放量最小，并将本文所建立的多目标优化模型用于某公司的货物配送，验证得出将货物配送至自提点更能降低总成本，从而提高顾客满意度和物流效率。

2 问题描述及模型建立

2.1 问题描述

小件快递配送时需要考虑货物、配送中心和车辆等要素，配送中心的工作就是装运货物、集中分类整理、短途运输等，在大客流量地段如地铁站等创建自提点，配送中心将货物送至自提点，这种配送方式可以减少能源的损耗，选择合适的配送点并且节省大量的时间，最终实现总成本最低、时间最少和碳排放量最少的多目标。

（1）多目标优化问题。多目标优化问题可以定义为：设有K个优化目标，使得目标函数向量最小，即：

（2）非劣最优解。设δ为所有可行解的集合，若∈δ，即称为非劣最优解，对于任意∈δ，至少存在一个使得：

那么，由所有非劣最优解构成的集合P，即：

（4）非劣最优目标集。非劣最优目标集由所有非劣最优解对应的目标函数所构成的集合PF，即：

2.2 模型的建立

2.2.1 VRP问题概述

（1）要素分析。多目标VRP模型包括货物、配送中心、车辆和运输网络等因素，其中货物直接影响车辆的选择，配送中心是连接上下游的通道，车辆由货物需求量、最大装载量和货物需求区域分配情况决定。

（2）目标分析。多目标VRP模型要达到配送总成本最低，追求利益最大化，以最小的成本完成作业，同时要使配送时间最少、碳排放量最少。

2.2.2 多目标VRP模型建立。本文多目标VRP模型的优化目标是假设自提点位置确定整体的行车方案，以实现总成本(A)最小，运输所花时间(B)最短以及车辆碳排放量(C)最小，其相应的数学模型可表示为：

式中K—车辆的总数；k—车辆的编号；i,j—自提点的位置；cij—自提点i到自提点j的单位运输成本；dij—自提点i到自提点j的距离；λ0—快递员递送一件小件快递的提成；Qs—车辆行驶每千米单位耗油量；Vk—车辆k行驶的平均速度；δ—车辆耗油量转换的碳排放量；Dmax—每辆车最大行驶距离；Cmax—每辆车的最大承载量。

目标函数（8）中分别表示运输成本（包括总行程路费和快递员的提成）、配送总时长以及总碳排放量；式（9）中前两个公式表示车辆途经所有的自提点；第三个公式表示自提点i仅有一名快递员k服务一次；第四个公式表示最大行驶距离，即快递员配送的路径行程不能超过所用车型允许的最大行驶距离；最后一个公式表示车辆配送的快递数目不能超过所用车型允许承载的最大数目。

3 遗传算法设计及实例分析

3.1 实例分析

3.1.1 小件快递配送至自提点实际算例。本部分的实例是通过调查得到北京某快递公司日平均市内的送货量，配送中心设置在朝阳区成寿寺路，至于地铁站自提点选择问题，是通过A快递公司小件快递配送量最大的25个地区进行选择，分别为：

北京地铁1号线：公主坟，王府井；

北京地铁2号线：宣武门，雍和宫；

北京地铁4号线：新街口，人民大学，北京大学东门；

北京地铁5号线：立水桥南；

北京地铁6号线：花园桥，车公庄西；

北京地铁7号线：湾子；

北京地铁9号线：丰台科技园；

北京地铁10号线：西局，首经贸，角门西，双井，亮马桥，惠新西街南口，北土城，车道沟；

北京地铁14号线：东湖区，高家园，东方北桥；

北京地铁15号线：六道口，安立路。

自提点编号，位置以及各个自提点的需求量见表1。

表1 自提点坐标需求量

本文将自提点坐标限制在长为50、宽为45的矩形中，配送中心在坐标（40,10），其他自提点的位置经统计之后得到，如图1所示。

图1 自提点位置分布图

3.1.2 小件快递配送至地铁站周边各小区实际算例。由于本文自提点的选择是A公司配送小件快递最多的地区的地铁站附近，所以本章选择的小区都是基于配送地铁站自提点附近的配送快递量较大的小区，这样更能验证本文所建立的模型以及遗传算法的可行性，配送的所有小区在与配送自提点横纵坐标相同的坐标里体现，各小区的坐标以及需求量见表2。

表2 各小区的坐标及需求量

同时将数据中所有的坐标显示在长为50、宽为45的矩形中，配送中心在坐标（40,10）。自提点附近小区分布如图2所示。

3.2 遗传算法设计

（1）编码方式。将本文所建模型的目标编码为长度k+m+1的自然数数组，其中编码的每一条染色体表示所有解里面的初始解之一。

图2 自提点附近配送小区分布图

（2）初始化群体。给出一条初始染色体；构造字符串；构造染色体；查验染色体是否符合所有的约束条件，若满足条件，则将产生的新染色体进入种群；否则放弃；反复操作第二步、第三步、第四步，一直到产生的新染色体的总数为M-1为止；最后，与初始染色体结合，构成了大小为M的初始种群。

（3）适应度函数评价。首先根据原目标函数式（8）将模型的目标作如下转换，将各目标函数值转化为无量纲变量：

式中A∗,B∗,C∗分别为无量纲的目标函数值，其取值范围都是在[0，1]；Amax,Bmax,Cmax和Amin,Bmin,Cmin分别是目标函数所求的每一代GA种群的最大值和最小值。

（4）选择算子。选择算子的方式采用适应值比例选择，运用轮盘赌(roulerre wheel)方式来实现。基于给定规模为N的群体，个体aj∈P的适应值为f(aj)，其选择概率如下：

本文中杂交概率Pc取0.7,变异率为0.01。

（5）终止准则判定。计算地铁站自提点配送路径时，采用的是设置最大迭代次数的方法。计算配送小区的路径时，采用按照每代最佳个体适应值的方法。

3.3 应用遗传算法求解实例

3.3.1 小件快递配送至自提点

（1）参数设置。本文对出发时间的控制比较特殊，所以车速就设置为平均车速。同时，主要参数设置为车辆总数K=6，自提点总数为25，种群规模大小popsize=200；交叉率Pc=0.7，变异率pm=0.01；大迭代次数Maxgen=1 000，本实验在Matlab中运行。在适应度函数选择上，f(A,B,C)=αA∗+βB∗+γC∗-p(x)。其中α取值0.1，β取值0.3，γ取值0.6，分别是目标函数值A∗,B∗,C∗的权重系数。

具体录入数据见表3。

表3 目标函数求解录入数据

（2）运算结果。采用精华种群中的最优个体最少保持代数作为算法的停止依据，所以以1 000代为终止目标，当迭代到750次之后函数的目标值取得最优，迭代到1 000次时目标值没有发生变化，得到最优目标函数。将通过调查得到的数据带入所建立的模型中，运用遗传算法进行迭代，通过迭代1 000次得到的车辆路线、每辆车的载重量最佳方案，见表4。

表4 配送至各自提点最佳配送方案

通过遗传算法迭代得出最佳配送方案后，为了更直接的了解配送路线，绘制了小件快递配送至各个自提点的配送路径图，如图3。

3.3.2 小件快递配送至小区

（1）参数设置。主要参数设置为车辆总数K=6，自提点总数为25，种群规模大小Popsize=100；交叉率Pc=0.7，变异率pm=0.01，从大迭代次数Maxgen=2 000，本实验在Matlab中运行。在适应度函数选择上，f(A,B,C)=αA∗+βB∗+γC∗-p(x)。其中，α取值0.1，β取值0.3，γ取值0.6，分别是目标函数值A∗,B∗,C∗的权重系数。

（2）运算结果。由于配送的小区数目较多，当迭代到1 000代的时候发现还有波动，所以将迭代次数设置到2 000代为止，迭代曲线趋于平缓，并同时取得小件快递配送至小区的最佳配送方案，见表5。

图3 配送至自提点最佳配送路径图

表5 配送至各小区最佳配送方案

通过运用遗传算法迭代出配送方案，发现线路5有两条，意味着第五条路径车辆B行驶了2次，实际上是会发生这种情况的，由于车辆行驶距离、车载量以及本文对行驶距离没有限制等原因，一辆车行驶两次能得到最优结果也是合理的，车辆行驶路线图如图4。

图4 配送至小区车辆行驶路线图

3.4 运算结果分析

对A快递公司配送至本文所假设的地铁站自提点以及其附近小区的小件快递数量进行统计，分别求得A快递公司从配送中心配送小件快递至自提点与小区的目标数据，即花费的总成本、花费的总时长以及碳排放量，运算结果见表6。

表6 运算目标结果

通过计算，配送至小区的总成本为1 945.54元，配送至自提点总成本为1 817.95元，节省了7.0%；配送至小区的总时长为15.14h，配送至自提点的总时长为10.13h，节约了49.5%，可见建立地铁站自提点大大节约了配送时间；配送至小区的碳排放量为130.44g，配送至自提点的碳排放量为87.12g，节约了49.7%。由此可见，本文设计的配送至地铁站自提点的方案是可行的。

4 结论

本文通过在地铁站附近设立自提点来取件的方式，建立以时间长短、成本多少和总碳排放量为目标的关于小件配送的多目标VRP模型，以某快递公司为例，通过运算结果可以得出，各个目标的情况比之前改善很多，配送至自提点的总成本、总时长、总碳排放量的数据都远远小于配送至小区的数据，从而验证了设置自提点的方式有效，实现了运输成本降低、货物到达客户手中的时间减少和汽车尾气碳排放量降低的目标，使物流服务让顾客满意，且提高了物流效率。

[参考文献]

[1]李伟,朱语葶,周江,等.“双十一”网络购物节大学生的消费特点研究[J].对外经贸,2017,(1):138-141.

[2]周易.87.8%受访者曾遇到快递延误[N].中国青年报,2017-03-30(007).

[3]王磊.国外城市末端物流配送发展经验及其借鉴[J].物流工程与管理,2017,39(7):16-19.

[4]蔡稳.电子商务物流末端共同配送的利益分配问题研究[D].杭州:浙江财经大学,2015.

[5]尹玉纯.电子商务环境下快递企业末端配送车辆路径问题研究[D].合肥:合肥工业大学,2015.

[6]张茂秋,刘克岩.基于自提柜的末端物流配送模式研究[J].河北企业,2016,(5):96-97.

[7]吴竞鸿,吕能芳.基于众包的快递企业末端配送模式研究[J].西昌学院学报(自然科学版),2016,30(2):69-73.

[8]王冬良,杨彩梅.二维码智能末端配送系统的实现[J].电子测试,2014,(23):63-64,51.

[9]李小芳.基于末端共同配送的快递服务链收益分配研究[D].西安:长安大学,2015.

[10]陈永平,李赫.大数据时代物流末端配送、消费体验需求满足及其价值创造能力提升[J].财经论丛,2017,(1):95-104.

[11]Hua X,Hu X,Yuan W W.Research optimization on logistics distribution centerlocation based on adaptive particle swarm algorithm[J].Optik-International Journal for Light and Electron Optics,2016,127(20),8 443-8 450.

[12]Rudink K,Pisz I.Probabilistic Fuzzy Approach to Evaluation of Logistics Service Effectiveness[J].Management and Production Engineering Review,2014,5(4):66-75.

[13]Liu H,Chen M.Research on the Distribution System Simulation of Large Company’s Logistics under Internet of Things Based on Traveling Salesman Problem Solution[J].Cybernetics and Information Technologies,2016,16(5):78-87.

[14]Becker J,Gorke M,Felix C,et al.Model-based potential analysis of the distribution logistics:a case study[J].Production Planning&Control,2016,27(9):698-707.

[15]Ji X F,Pu Y M,Liang F W,Qin W W,et al.Programming Model for City Logistics Distribution Optimization under Time Restriction Caused by Traffic Organization[J].Journal of Highway and Transportation Research and Development(English Edition),2015,9(3):94-101.

[16]Sun J,Wang X.Study on the E-Commerce Logistics Distribution Modes of Fresh Agricultural Products[J].Applied Mechanics and Materials,2015,3 843(744):1 895-1 901.

[17]Tang R X,Qin Y B,Zhang L.Research on Heuristics Logistics Distribution Algorithm Based on Parallel Multi-ant Colonies[J].Journal of Software,2011,6(4):612-619.

[18]Zhang Q Y,Chen J H,Tao Y M.Researches on Joint Distribution in Urban Logistics[J].Advanced Materials Research,2012,1 671(472):3 240-3 243.