快递企业“最后一公里”快件收派优化方案研究

贺冰倩, 李昆鹏, 成幸幸

(华中科技大学 管理学院,湖北 武汉 430074)

0 引言

网络购物的迅猛发展给我国快递业带来了前所未有的发展契机，而日益激烈的行业竞争，不断上升的客户要求，促使快递企业在提高服务水平的同时关注运作效率与成本。从理论和实践角度看，实现收派路径的智能选择，提高收派效率，提高服务水平，降低运营成本，对于企业提高竞争力具有十分重要的意义。

本文以A快递公司为例，研究公司日常快件收派中路径优化问题。面对日益增长的快件服务需求，快递公司的作业活动是一个复杂的、充满随机性的动态调度过程，简化如图1所示，收件请求随机到达，配送快件固定到达，每个批次开始时，收派员执行已知的收派任务，收派过程中灵活处理临时到达的收件请求，如图2所示，任务完成后返回网点，整个批次受时长与运输工具荷载限制。A快递公司在派送处理方面主要以客户为中心，尽可能最大化客户满意程度，但目前业务水平已到达瓶颈阶段，希望寻求进一步提升，主要突破口在于以下两个方面：首先是需要提升路线行走效率，经验决定路线、业务生疏、订单的随机性，都导致了现阶段配送耗时增加；其次是时间反馈精确性需要加强。目前实际派送过程与进展程度反馈存在偏差，客户无法准确获知收派员上门服务时间，公司无法根据目前的派送效率设计人员安排规则及批次周期时长。本文以此为背景，深入研究快件“最后一公里”收派流程，综合考虑收派混合、动态性、时间窗和容量约束四个最主要的因素，找寻适用于实际问题的流程优化及高效的路线设计。

图1 快递公司快件实际收派流程

图2 灵活处理收件请求

关于快递公司收派问题的研究，除了从流程角度[1,2]、配送量[3]、客户群体划分[4]等方面展开，在路径设计方面，丁浩等[5]针对目前快递车辆运输成本问题，采用Dijkstra快速找出快递配送派件过程中的最短路；刘欣萌等[6]研究了单个配送中心带时间窗的车辆路径问题；饶卫振等[7]研究了大规模具有能力约束的车辆路径问题；贺政纲等[8]提出了物流配送系统中存在的车辆负载不均衡问题；张如云等[9]提出了低碳、节能和成本节约最小化的城市车辆配送问题模型；熊浩等[10]研究需求可拆分车辆路径问题，提出三阶段禁忌算法用于计算双层规划模型。

侧重这四类约束的VRP问题，一直是国内外研究的重点。在建模优化方面，Ninikas等[11]针对动态装卸混合VRP问题，提出再优化模型；Chabrier等[12]对基础最短路径的生成提出了若干优化方法；Feillet等[13]针对基础最短路径问题，放松约束条件实现路径生成；Gendreau等[14]将原来用于计算静态问题的模型，改进成为计算动态问题的模型。在算法设计方面，Clarke等[15]针对不同容量的一组车辆服务若干客户的问题，设计了一种迭代算法；针对带时间窗问题，Desrochers等[16]运用动态规划、LP松弛、列生成来逐步求解；Taillard等[17]用禁忌搜索迭代求解；Athanasopoulos等[18]研究分支定界框架下的带时间窗的多周期车辆路径问题的有效方法。在策略选择方面，Gelinas等[19]提出策略并评估了分支节点选择的标准；Bent等[20]研究有随机客户的带时间窗的车辆路径问题，提出多情景法预测未来的客户；Yang等[21]考虑空载成本，任务延迟，任务未完成等成本，研究实时多车装卸混合问题，提出了一种再优化策略；Angelelli等[22]针对动态多周期路径问题，提出了几种短期路径策略。

国内外关于快递企业收派研究偏重于问题分析与流程质量评估。路径设计方面，由于VRP问题非常灵活，针对不同情况背景，有不同的侧重点。快递收派属于偏实际应用且特点鲜明的一类问题，以往文献只是在部分方面与本文研究的情况类似。所以针对快递公司实际派送情况，如何将收派混合、动态性、时间窗和容量约束四个要求结合起来，并采用改进的禁忌搜索算法，灵活处理动态需求，得出适用于实际情况的结果，将是本文研究的重点。

1 问题模型构建与分析

1.1 数学模型

模型目标函数：

(1)

约束条件：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

ai≤wi≤bi;∀i∈A,∀k∈K

(13)

(14)

其中(1)为模型的目标函数，即总路线行走时间最短；(2)～(3)表示必须完成所有已安排的收派任务；(4)～(5)表示收派员必须从服务网点出发并返回；(6)为线路平衡约束，表示任一收派任务完成后，收派员必须前往下一个客户点；(7)为单次收派时间约束；(8)～(9)为载重约束，(8)表示车辆装载快件总重量的变化，(9)表示在收派过程中任何时候车辆都不超重；(10)～(11)为体积约束，(10)表示车辆装载的快件总体积的变化，(11)表示收派过程中车辆不能超过最大装载体积；(12)表示车辆到达相邻两个客户点的时间关系；(13)为时间窗约束，表示收派员必须在客户所要求的时间范围内到达地点；(14)表示0-1变量，若收派员k在服务完客户i后服务客户j，值为1，否则为0。

1.2 区域热点划分

实际收派过程中快件数量多，若以每件为单位输入算法进行运算，会使算法运算时间及运算难度呈指数型上升。因此，本文引入“热点”的概念，以有效合并相近点，达到优化运算效率的目的。

所谓热点，具体指一个地址，以这个地址为中心的一定范围内覆盖了若干快件的收货地址，在运算中，本文统一默认将属于覆盖范围内的快递送往对应的热点地址，这样可大大降低运算中点的数量，对结果的质量也不会产生很大影响。热点的具体划分规则如下：①收集某服务区域一段时间内的收派件数据；②将快件地址信息根据距离进行聚类，每个类别的中心为热点，覆盖周围直径为20米的区域；③找出不重复的热点地址，利用电子地图建立热点间的距离矩阵；④快件和热点匹配，根据快件地址信息将其分配到距离最近的热点。

通过以上四个步骤就能对派件问题的数据进行初步处理，合并距离相近的点，减少点的数量，从而提升运算效率。

2 “最后一公里”收派优化方案算法说明

本节对区域收派流程进行优化设计，设计内容包括数据处理和计算机编程实现路径智能化计算。方案的整体框架图如图3所示。

图3 收派流程优化方案框架图

当一批快件到达配送网点，先在数据库中找到当前批次快件信息。根据快件地址信息，动态划分热点。每个热点，依次与快件匹配后，计算热点总的快件重量、体积，作为该热点的需求信息。然后计算各热点之间的距离矩阵，作为距离信息，输入算法。同时根据实际情况，输入当前可用的人员车辆信息、历史单票快件的服务时间，从而保证输出结果的可用性与准确性。在收派件过程中，当新的动态需求到达，利用优化算法再次优化收派路径。最后根据算法得到路径结果，合理安排人员及对应行走路径。

2.1 收派路径问题求解基本框架

本算法主要通过时间片的分割，转动态需求为静态需求，实时计算收派员当前点及以后的可行路径，最小化时间消耗，并将生成的行走路线结果实时反馈到收派员，将快件到达时间实时反馈给客户，保证收派工作顺利展开。

算法首先读入相应的快件信息和人员信息，初始解的生成采用贪婪算法。虽然贪婪算法可能获得较好的可行解，但随机性较强，所以需要做进一步优化。

本文之所以采用禁忌搜索算法作为后续优化算法，主要是基于研究问题本身的特点，问题本身的限制条件不多，不易产生冲突，禁忌搜索算法搜索范围广泛，产生可行解的空间广，能最大可能性的找到最优解，适用性相对较好。

图4 区域收派优化路线生成算法整体工作流程图

针对动态到达的收件需求，由于已经分配给收派员的任务无法再分给别的收派员，只能在每条路径已有的任务上，加入新的任务，采取基于临近原则处理动态需求的TSP问题求解即可满足。

基于此，区域派送优化路线的生成算法整体工作流程如图4所示。

2.2 基于时间窗要求的贪婪算法求解初始解

在算法求解的第一阶段，本文首要目标是产生一个可行解，在此基础上尽可能获得较优的解。产生可行解的方法为基于时间要求的贪婪算法，对于时间要求高的客户，先进行装车安排，依次搜索与它距离近的客户订单，装入同一辆车，直到达到容量约束上限，然后安排下一辆车。需注意，派件和收件对车容量的影响，不仅要保证出发时的车装载量不超过车容量，还要保证途中的车装载量不超过车容量。具体的操作流程如图5所示。

在使用基于时间窗要求的贪婪算法获得初始解的方法外，考虑到希望在后续优化迭代中，获得更大的搜索广度，本文还用随机的方法生成了一组初始解。上述方法生成的初始解，通过实例测试，可行度高且质量较好(尤其是第一种)，为随后的迭代优化提供了好的基础。

2.3 改进的禁忌搜索算法

由于优化的目的是找到总行驶时间最短的方案，所以改进的禁忌搜索算法的搜索空间在一个较大范围内进行，以跳出局部最优来寻找全局最优，并舍弃不可行解。算法在当前搜索区域内进行了一定次数的搜索后，若不能发现更好的解，就执行分散搜索策略，将禁忌表清空，从一个新的初始解开始搜索。如果最好解的记录被更新，就执行集中搜索策略，且清空禁忌表，可以在当前区域更自由的搜索。

关于邻域解的获得。邻域解生成方法对于搜索效率有很大的影响。考虑到问题规模，每批次收派工作量不会很大，即服务点个数有限，所以本文尽可能在邻域搜索时，全面计算各个邻域。为了节省运行时间，在生成邻域解前设定一个评判标准，例如时间和容量等硬性约束，若不能满足约束，则舍弃。具体实现方法为：①移动点选择。从当前解第一条路径的第一位客户开始，将其抽出；②移动位置选择。遍历其他有容量剩余的路径，将之前抽出的点依次插入这条路径每两个客户之间以及最后一个客户之后；③可行性判断。若满足约束则计算当前解的目标值；④记录与调整。遍历所有的情况后，保留结果最好的两个解，若该解为明显劣解，则将其舍去，随机生成一个可行解代替。⑤邻域解优化。生成的邻域解不一定达到了最优状态，对其中的每条路径分别进行调整能进一步提升邻域解的质量，在此本文采取Gendreau等[23]提到的路径调整US算法进一步优化邻域解。

关于终止条件。在改进的禁忌搜索算法中采用总分散搜索次数和连续没有找到更好解次数来控制，分别记作N和M，每当连续未提升次数达到M时执行分散搜索，当分散搜索次数达到N时，搜索停止。详细步骤如图6所示。

图6 改进的禁忌搜索算法

2.4 基于临近原则处理动态需求

当收派员在派件途中，会随机到达若干收货请求。请求反馈到系统，系统中有各个收派员的实时位置和容量信息，管理人员需要让收派员在完成原来任务的基础上，灵活加入新收件任务， 具体的安排方式如下：

(1)当每个动态请求到来时，系统自动获取收货位置和各个收派员当前未完成任务点的集合，算出其间距离，并按升序排列；(2)选定第一个未完成任务点；(3)将该动态收货请求加入该任务点之后，更新路径长度、时间，以及各个节点车的装载量；(4)判断路径是否可行，考虑容量约束、时间(距离)要求。若可行，将该收派员的新路径信息发送到本人，处理结束；若不可行，选定下一个未完成任务点，转至步骤(3)。

3 A快递公司快件收派案例分析

3.1 案例背景

为了验证所提出的优化方案在实际问题中的有效性，本文结合A快递公司实际案例进行模拟。A快递公司是一家著名快递企业，经营国内外快递业务，于九十年代初成立。随着客户配送需求的增加，A快递公司的服务网络延伸开来。目前A快递公司希望进一步提升竞争力，在“最后一公里”快件收派上提升效率，并且完善对收派员作业的管理。A公司现存的问题简要概括为：收派路线行走效率低下，时间反馈精确性不高。

将本文提出的优化方案用于A快递公司，首先是考虑到与其他快递企业相比较，A快递公司管理模式较规范，信息传递系统较先进，有更好的实施性和比较性。其次是通过优化方案结果和实际派送情景比较，找出本研究的意义及提升空间，为后续研究做铺垫。

图7 深圳市南头区

本文利用A快递公司2015年10月份位于深圳市南头区的实际收派件数据，来说明收派路径优化的处理流程及实施效果。深圳市南头区位于深圳市西南部，如图7，是深圳经济特区，覆盖面积约182平方公里。这一整个月的快件收派历史数据包含了3621个收件任务和2793个派件任务，一共安排了三位收派员，都使用同样的交通工具二轮电动车进行收派活动，每个批次开始时，从派送网点出发，结束任务后，返回派送网点。该企业中有一个“收1派2”的规则，即客户下单后1小时完成收件，快件出仓后2小时完成派件，作为衡量结果的一个标准。

3.2 小规模路线优化方案实施效果

本组数据选取部分小规模的批次，客户数量在5～10之间，包含收件和派件，由最多三名收派员完成。收派员的交通工具均为二轮电动车，标准载重为60kg，速度为24km/h，本文假设这三个收派员的操作水平、行走速度、服务速度一定，即看作相同的员工来完成这次工作。

为衡量模型的有效性及改进禁忌搜索算法的高效性，采用CPLEX软件求解本数据中的六组小规模算例，并与改进禁忌搜索算法得到的解作比较，结果如表1所示。

表1 CPLEX与改进禁忌搜索对小规模算例测试结果

测试结果显示，所有客户均能在时间窗要求内被服务。由表1可以看出，对于客户数目为5～9的算例，改进的禁忌搜索算法和CPLEX得到相同的最优解；对于客户数目为10的算例，改进的禁忌搜索算法得到近似于CPLEX的最优值。在计算时间上，改进的禁忌搜索算法较CPLEX快很多。由此可见，对于小规模算例，改进的禁忌搜索算法可以在短时间内获取最优解或近似最优解。

3.3 大规模路线优化方案实施效果

随着客户数目的增加，CPLEX的运行时间会急剧增加，无法在可行时间内获得最优解。故对于大规模算例，本文采用实际收派数据与算法得到的解作比较，以体现算法的高效性。

本文从10月份的数据中，挑选了50组情景各异的批次，它们的数据量不同、时间点不同、动态请求到来的规律不同。本文仍然把他们放在相同外在条件下，即三名能力相似的收派员，交通工具均为二轮电动车。

首先将每组数据提取出来进行整理，设定派件开始时间，对应开始派件时已知的收派任务，以及需求到达时间，对应后续派件过程中接收到收件任务。然后对地址进行热点划分，将同一热点的多个数据合并到一个点，并计算该点的快件重量和快件数量。在得到所有热点信息后，计算热点距离矩阵。然后带入程序运算，得到初始路径规划。在收派员派送过程中随时更新收件请求，添加进行走路径中，从而得到最终的收派任务完成结果。

测试结果分为两个方面：任务完成时间和任务完成情况。通过这两个指标来比较实际操作与算法计算的结果，可全面反映优化方案的提升效果。任务完成时间与历史数据时间比较可以展现时间上的优化性能，任务完成比例可以展示方案的实用性，满足时间窗任务比例可以展示方案的柔性。

表2展示了优化方案结果，其中静点和动点分别表示路径生成前的热点数和派件过程中接到的总收件请求数，完成率为最终服务客户的比例，时间窗比率为完成的任务中，满足“收1派2”的客户比例，用时为所有参与派件的人员用时总和，比率为程序结果用时与实际用时之差比上实际用时，为负值表示实际用时更短，为正值表示程序结果用时更短。结果表明，随着点数的增加，用时增加，算法在绝大多数批次的结果优于历史数据的结果，在点数较小的时候(例如批次2、4、13、32)，算法得到的结果劣于现实操作的概率较大，这可能由于人工对于较简单的路径依靠经验判断可以完成的更好，而算法存在波动性与随机性，随着点数的增多，人工无法进行规划，算法的优势性可明显体现。虽然每批数据的特点不同，优化的程度也不同，但是平均保持在百分之十，有了一定的提升。另外结果还说明，动态点的比例越高，对总用时的影响越大，因为在相同总点数的情况下，动态点越多，优化空间越少，导致了用时的增加。

任务完成率与满足时间窗的任务比例，如表3所示。上述50个批次一共包含1739个点，其中完成了收派任务的点数是1626，任务完成率是93.5%，有113个动态请求没有在当批次完成，占总的动态需求的28.83%。导致这些请求没有完成的原因是，收件任务到达时间太晚，或者位置相距太远，完成时间超出了当批次收派员的时间约束。在完成的任有务里，131个快件未在“收1派2”的建议规定时间内完成，其中大多数为收件请求，来源于总点数较多的批次，因为收件请求的时间要求较高，且受静态路径状况的影响较大，容易造成延迟。满足时间窗的任务比例占总任务的85.97%，这一比例虽然没有非常高，但是相对于历史数据里的派送情况，还是有一定的提升效果。

表2 多情境下优化方案实施效果

表3 任务完成情况

3.4 优化方案实施效果总结

关于程序运行方面，程序采用C++编码，使用2GB内存、2.8GHz英特尔双核处理器运行。所有的算例运行表明：对于静态路径的计算，最长用时不超过3min；对于实时订单插入的计算，最长用时不超过2s。故可以满足实际操作中的时间要求。

优化方案的结果表明该方案能够满足大部分收派任务，并且保证“收1 派2”的要求，在路径方面，明显降低了路径行走的长度，保证了收派任务进行的效率。

方案的不足之处有以下几点：(1)没有考虑人员负载的均衡性，下一步可以将最小化路径最长的线路作为一个指标，来满足这一要求；(2)新需求的处理。算法中新需求的处理，是与未完成任务点相联系，若新需求到来太晚，或者收派员效率太高导致任务点已处理完，新需求很容易被搁置，等到下一周期处理。

4 结论

本文深入研究了快递企业 “最后一公里”收派环节的实际收派现状，对其区域收派路线规划问题进行研究，优化了收派流程及路径生成算法，并结合A快递公司实际操作中具体案例进行分析，给出了适合快递业派送中路径规划的热点划分法，并综合考虑装卸混合、动态性、时间窗和容量约束这四个最主要的因素，建立数学模型，通过改进的禁忌搜索算法在短时间内得到最优路径结果，设计了一套基于算法的派送流程优化方案，并运用到实际情境中，数据表明，通过提出的相应流程和算法能比实际操作获得更好的解，保证收派工作的有效进行。但是也发现了一些不足之处，人员负载的均衡性和新需求的处理有待提升。

本文研究考虑的四个最基本因素，对动态性的处理稍显薄弱，有一定局限性，后期可以进一步研究，提升对动态请求处理的灵活性。除此之外，在实际中会遇到一系列不确定因素：客户需求的变化、交通状况、车辆故障等。所以在未来的研究中，整体的优化可以在本文的基础上建立动态模型，将不确定因素加入模型以预防突发情况，使生成的解的适用性及抗干扰性更强。