随着互联网以及电商的普及，由于网购能够提供更多的商品信息，并且不受时间地点的约束，省事省力，因此越来越多的人选择在网上购物。但是相对于传统的上街购物模式，网购商品需要一定的时间到达客户手中，而这段时间的长短是影响客户网购体验最重要的因素之一。因而电子商务的发展需要健全的物流体系大力支持，同时也必然带动以快递业务为基础的电商物流业的快速发展。根据中国快递协会公布的最新数据，2014年我国快递业务量达140亿件，同比增长52%，跃居世界第一。快递业务量连续46个月累计同比平均增幅超过50%，在从“快递大国”向“快递强国”转变的道路上迈出了坚实的一步。但与此同时，“最后一公里”投递难题依然存在^[1]。

电子商务的发展以及物联网和大数据时代的来临，给全球物流带来了物流信息化的新发展。与传统的物流配送服务不同，物流设施、商品包装的标准化，物流的社会化、共同化都是电子商务下物流模式的新特点。此外电商物流配送的运作重心后移，愈加偏重前台物流，更直接地面向消费者，更加注重物流的效率以及用户的体验^[2]，因此在物品由配送中心到客户手中这一段过程，即末端物流显得尤为重要。

电商末端物流的主体是车辆路径问题。相比于传统的车辆路径问题，电商物流中的末端物流具有如下特点：1)客户数量多，分布广；2)每次产生需求的客户数量以及位置是不确定的；3)快递配送由订单生成到配送过程是有滞后性的^[3]。因此配送过程应当结合每日订单，实现信息流、物流、资金流的有效结合^[4]。物流配送中心要根据消费需求“多品种、小批量、多批次、短周期”的特色，灵活组织和实施物流作业。面对这些客户需求的不确定性，弹性化的物流正是适应生产、流通与消费的需求而发展起来的一种新型物流模式。

车辆路径问题(vehicle routing problem，VRP)来源于交通运输，由Dantzig等^[5]于1959年提出。它是组合优化问题中一个典型的NP-hard问题。它通过对车辆的运输路线进行优化，在满足客户需求的前提下，尽量以最低的运输成本与费用将货物送达目的地。自VRP问题提出以来，吸引了众多学者进行研究。1995年出版的《运筹学与管理科学手册》在第八章专门讲解了车辆路径问题^[6]；2002年, Paolo等^[7]全面分析了当时VRP的研究内容及展望。相对而言，国内的研究起步较晚。郭耀煌等^[8]首次详细讲解了VRP问题；之后掀起了国内VRP的研究热潮，冯辉宗等^[9]通过对汽车运输的特点和成本的分析，采用了遗传算法求解；刘小兰等^[10]针对带时间窗的车辆路径问题(VRPTW)，通过引入短路径优先策略，构造了改进的大规模邻域搜索算法求解；温惠英等^[11]以车辆配送的总费用最小为目标，对带时间窗协同车辆路径问题(CVRP)构建了数学规划模型，并采用自适应离散粒子群算法求解，验证了模型的正确性和合理性；李妍峰等^[12]对实时交通信息下的城市动态网络车辆路径优化问题，结合初始路径安排与实时路线调整构建了模型，验证了新实时路线更新机制的优越性。这些对于传统车辆路径问题的研究提供了很多种不同的VRP模型，以及各种各样的解决方案，但是并没能很好地解决电商物流问题的模型以及方案。电商物流的配送过程中，由配送中心到客户手上这一过程对客户的不满意度有着极大的影响，并且其成本占了物流配送成本中极大的一部分；更主要的是相对于传统车辆路径问题，它在客户需求上具有极大的不确定性，因此无论是路径优化，还是成本计算，传统车辆路径问题的解决方案都无法完美解决。

相应的，目前国内关于电商物流的研究主要有：杨建功^[2]针对电商物流与传统物流的区别，提出了前台物流与后台物流的概念；杨聚平等^[13]对电商物流配送中的最后一公里问题提出了若干解决方案；张昕^[14]分析了多种末端物流共同配送模式及决策路径下的方案研究，并对这些方案进行对比，以及在面对特定问题时对这些方案进行组合提出最优解决方案；席运江等^[15]对于快递网络这种典型的混合轴辐式网络，提出了快递企业配送网络系统的多层、多维、多标准以及整体性特征，选用超网络模型理论对其进行研究和分析；黄建华等^[16]分析了快递网络在分别遭遇了人工破坏以及蓄意破坏时，所表现出的鲁棒性以及脆弱性。这些快递网络的研究，大部分是针对电商物流的定性研究，从运营策略上来解析问题；而对于电商物流的定量的研究中，又没有真正地结合电商物流配送本身的特性解决问题。

因此，本文综合传统车辆路径问题与电商物流配送的实际问题，结合电商物流的信息化以及需求不确定性的特点，提出电商末端物流的弹性管理措施；并设计基于极值动力学的改进蚁群算法，针对客户需求数量不确定的问题，将人均成本作为成本计算方式，制定配送计划，通过与普通蚁群算法的对比验证了算法的有效性，并通过仿真验证了模型在面对不同客户需求下的弹性，对实际的电商物流运作具有一定的指导作用。

1 问题描述

弹性概念最早产生于弹性力学研究中，属于物理学科的范畴。1973年，Holling^[17]将弹性概念引入生态学，并将其定义为系统在均衡改变前吸收扰动的能力；之后在供应链中断事件背景下，Christopher等^[18]提出了供应链弹性的框架，并指出弹性是指系统在中断后回到原始(或新的更理想)状态的能力。随后弹性概念逐渐被引入不同的学科来描述复杂动态系统的关键特征，如生态学、工程学、经济学、心理学、社会学等。综合各学科关于弹性的定义可以看出，弹性作为系统的内在属性，包含承受扰动、缓解风险、恢复中断等多维度概念，反映了系统在面临风险事件时的适应性和调节能力。

在电商物流配送过程中，面对的主要干扰类型为每天不确定的客户需求以及促销等情况下的需求量剧增。如果日常成本有着大幅变动，将使企业管理变得十分困难。而通过电子商务的物流信息化，系统能够掌握每天的客户需求情况；通过对每天的需求进行分析并制定合理的配送方案，进而实现电商物流的弹性管理。本处将电商物流的弹性配送定义为系统缓解小扰动以及大干扰之后的恢复能力，即适应性和敏捷性。

适应性是系统对干扰的响应能力^[19]，表现为配送过程随着客户需求的变动及时调整以满足客户需求的灵活性。由于电商中消费需求的产生是一个动态的过程，因此每天的物流配送必然也是一个动态的过程，需要根据客户的需求采取合理的配送措施，在节约成本的同时使系统每天处于一个较稳定的状态，表现为系统的适应性。

敏捷性是系统面对大扰动时恢复到较稳定状态的能力。当店家大促销导致订单生成量剧增进而产生大量客户需求时，配送中心往往无法在当天完成任务从而导致配送延迟以及快件积压，而快件积压的影响将在之后的配送过程逐渐消除，表现为系统的恢复能力，即敏捷性。

2 模型建立

对于电商物流配送而言，在保证服务质量的同时，降低物流配送成本才能获得更大的竞争优势。电商物流配送的弹性配送核心是一个复杂的、多目标、多约束的优化问题，模型中存在客户数量、客户分布、车辆运载能力、员工工作时间、成本构成等复杂因素的约束。根据电商物流配送的特点，为了方便模型的建立，作如下假设：1)城市中所有可能产生需求的客户是均匀分布的，某一个区域的客户分布用一个m×n的点阵表示；2)任意两个客户之间是可以到达的，它们之间的距离是欧氏距离；3)所有车辆的型号都相同；4)只考虑单一区域中一个配送中心的情况。

2.1 配送中心的选取

在代表区域客户的m×n点阵中，其中每个点代表一个可能购买的客户，客户i在点阵中的坐标(x_i，y_i)即代表客户的位置。由于顾客需求随机性大的特点，配送中心可以依据需求的历史数据，获取每个节点平时产生需求的概率p_i，然后以p_i为权值采用重心法^[20]选址，则配送中心的坐标为：

(1)

这样在面对个体随机的客户需求时，可以使总体的需求分布期望相对于配送中心处于一个较均衡的状态，能够增加配送过程对不同客户需求的适应性。

2.2 配送过程及成本计算

模型实际配送的过程如下：1)依据客户购买几率p_i，随机生成客户需求；2)配送中心依据产生的需求信息，寻找最优配送路径；3)车辆对其下对需要配送的节点实施配送。

模型的约束来自于客户以及车辆的约束，具体描述如下。

1) 每个车辆有一个载货上限Q_W，每条线路上的客户点需求量之和不超过汽车载重量，以q_i^k表示路径k上客户i的货物需求量，即：∑q_i^k < Q_W。

2) 每个配送车辆一次行驶的最大距离为L_M，从而每条配送路径长度不超过L_M。

在普通车辆路径问题^[21]的基础上，针对客户需求数量不确定的特点，以人均成本作为优化目标函数。当总共有s名客户产生需求时候，整个配送过程的成本由4个部分组成：车辆行驶油费，人工费，延迟库存成本，延迟造成客户不满意度的额外成本。具体如下。

1) 每公里的运输成本为a，总的运输长度为l，那么运输成本z₁=a×l。

2) 初始每辆车的成本为b₁，初始的车数目为nv₁，额外添加的每辆车的成本为b₂，额外添加的车辆数目为nv₂，那么车辆的成本为z₂=b₁×nv₁+b₂×nv₂。

3) 每天未完成配送的客户数量为s₁，每个客户由于延迟一天的不满意度产生的额外成本为c₁，每个快件延迟的库存产生的额外成本为c₂，那么当天由于延迟产生的额外成本为

z₃=(c₁+c₂)×s₁。

当天实际配送的人均成本为

(2)

2.3 弹性评估

上文中提到的弹性主要由适应性以及敏捷性构成。由于配送过程的不确定性，模型的弹性以每天人均成本相对于历史人均成本的波动进行评估。假设总共有day天的成本数据，依次为{ZA₁, ZA₂，…，ZA_i，…，ZA_day-1, ZA_day}，则第j天的成本波动系数

(3)

如果在当天发生了很大的扰动，则当天的wav会变得很大，并且在后面的dy天的时间逐渐恢复到正常水平。定义第j天的恢复系数

(4)

适应性为配送过程随着客户需求的变动及时调整以满足客户需求的灵活性，以wav值的大小作为衡量指标。如果每天的wav越小，表示系统的适应性越强，在不同客户需求下表现出良好的稳定性；wav越大，表明系统适应性越弱，配送成本容易受到客户需求的影响。

敏捷性是系统面对大扰动时恢复到较稳定状态的能力，以rec的大小，以及恢复到正常的天数dy作为衡量指标。如果dy以及rec的值越小，表明系统在干扰之后能够很快地恢复正常运作，即敏捷性越强；dy以及rec越大，表明系统恢复时间越长，即敏捷性越弱。

3 算法设计 3.1 极值动力学与自组织临界

自组织临界状态是由Bak等人于1987年首次提出来的概念, 用于说明控制广延耗散动力系统的普遍组织原则。在自组织临界模型中, 最值得关注的是1993年Bak等^[22]提出的Bak-Sneppen生物演化模型(下文简称BS模型)。在BS模型的生态系统中, 不同个体间相互关联, 个体的变异会影响邻近其他个体的状态。其突出的特点为非平衡性(准平衡性), 不会收敛到一个平衡态, 而出现断续平衡, 产生的波动性使算法具有更好的持续搜索和跳出局部最优解的能力。

极值优化算法的基本思想是通过不断以新的随机组元替换个体中的最差组元, 最终使整个系统演化到一个临界状态。此过程中, 所有的组元都能协同进化, 个体的构造不断得到改善, 最终可以找到近似最优解或最优解, 达到寻优的目的^[23]。它不需要调整参数, 易于实现, 计算量小, 算法效果好, 因此得到了广泛的应用。

3.2 改进算法原理

蚁群算法是一种由于受自然界生物的行为启发而产生的“自然”算法。它是从对蚁群行为的研究中产生的, 最初由Dorigo等^[24-25]提出用于解决旅行商问题。由于蚁群算法是一种正反馈的自组织优化算法，通过信息素的不断累积寻找最优解，因此相对而言容易陷入局部最优解，而且可能使得更优解由于信息素的累积过低而很难被再度选取；而极值优化算法通过寻找最差个体及其领域优化系统，是一种“去差”算法，拥有很强的局部搜索能力，并且由于优化过程的随机性，因而具有良好的跳出局部最优解的能力。因此，通过极值优化算法的局部搜索能力，配合蚁群算法的全局搜索能力，能使算法具有更强的跳出局部最优解的能力，避免算法早熟、停滞，使算法的收敛效率大幅提高。

本文主要在路径搜索以及信息素更新两个方面，对蚁群算法进行改进，通过定义节点的局部适应度在蚁群算法中引入极值优化算法。对于客户i，取其当前所在路径中的前向边长度为d_if，后向边长度为d_ib，与它相连节点的最短距离为d_i1，次短距离为d_i2。定义该客户的局部适应度为

(5)

如果f_i越小，表明该解更优。在蚂蚁搜索路径之后，对其中适应性最差的节点及其领域进行优化。由于解中的各条边之间是强耦合的，因此改变一个节点的适应度会影响到其他与他关联的节点的适应度，即实现极值优化算法的过程。而且在该网络结构中, 任意两个节点是可达的, 即可以通过有限步的邻域操作从一个可行解搜索到另一个可行解^[26]。因此通过邻域搜索不断改变具有较高局部适应度的节点的状态, 使优化系统逐步达到自组织临界状态。

此外，信息素更新策略是蚁群算法的关键步骤之一，信息素的更新方案直接影响了蚁群算法的求解速度以及解的好坏。因此，本文在蚁群算法的信息素更新时，也加入局部适应度的影响。对于解中的路径i→i′，第u次循环更新规则如下：

(6)

(7)

其中τ_ii’ 表示路径上的信息素浓度，ρ为信息素残留系数，Δτ_ii’为每次的信息素增量，θ为信息素增量与局部适应度的指数关系。

3.3 算法实现

依据以上特点，本文构建算法的具体实施步骤如下。

1) 配送中心的选址以及客户需求的产生。

在一个20×20的点阵模型中，根据每个节点的购买概率p以及重心法选择配送中心，每个点依据购买的概率p随机选择是否购买。

2) 蚂蚁寻找路径。

依据基本的蚁群算法，用蚂蚁代替车辆对客户点进行配送，蚂蚁在i客户点选择服务的下一个客户点i′时，主要考虑2个因素：1)i，i′两顾客点之间的亲密程度，称为可见度，记为η_ii’，其中：η_ii’=d_ii’；2)由迄今完成的循环所得路径方案体现出来的由i到i′的可行性，即信息素浓度τ_ii’。在第u次循环时候，蚂蚁h由客户点i转移到客户点i′的概率：

(8)

其中nh表示蚂蚁当前尚未经过的路径，α、β作为信息素浓度与可见度的指数，表明了在转移过程中它们的相对重要程度。当下一个要服务的客户点会使运载总量超出汽车载重量，或者使运距超过一次最大行驶距离L_M时，就返回到配送中心。蚂蚁代表下一辆车出发，直到遍历所有的客户节点。

3) 路径极值优化。

计算蚂蚁路径中每个客户的局部适应度。并将局部适应度由大到小排序为长度为list_len的序列List，则适应度最大的客户为该序列中的第1个元素, 而适应度最小的客户为该序列中的第list_len个元素。对于List中的第r个元素，根据文献[27]的结果，它被选中的概率p’(r) ∝ r^-3时候，系统能取得最优解。因此，定义第r个元素被选中的概率为

(9)

采用轮盘法选择客户Customer_n，对Customer_n实施2-opt优化，该领域定义策略会产生list_len-1个解，选择最小的结果作为当前最优路径。

4) 更新信息素。

当一次循环结束后，蚂蚁遍历了所有客户点，完成一次配送。当所有蚂蚁完成一次循环后，根据各蚂蚁遍历结果的好坏(目标函数值)，计算信息素增量，更新相关路径上的信息素。

5) 重复2)~4)，直到满足算法的终止条件，输出最优解。

3.4 算法分析

基于极值动力学的改进蚁群算法以当前路径与最小路径的距离差定义局部适应度，能更直接地反映该节点路径的优劣性，局部适应度值越大表明解越劣；搜索之后的信息素更新过程中，对于局部适应度越小的点，信息素的增量越大，表明系统对优解的保留性更强。此外，搜索过程中在全局上依据信息素搜索下一个节点，同时局部上依据局部适应度对适应度较差的节点进行极值优化，实现全局与局部、寻优与弃差的搜索相结合，大幅提高算法的收敛效率。同时由于模型的配送中心是基于客户的购买几率采取重心法选址，并且客户的基数足够大，因此配送中心总是处于客户需求的期望中心从而使需求相对于配送中心的分布呈现一定的稳定性。采取人均成本最小化作为目标函数，可使系统在面对客户数量变化时，最终优化结果能表现出很好的稳定性。因此算法在面对不同的客户需求进行求解时候能表现出良好的弹性。

4 算例分析

在快递配送的最后一公里，通常是每个区域以一个配送中心负责该区域的客户需求的配送。而且城市中某一个区域的客户，是零散而且比较均匀地分布于其中。可以以一个m×n点阵模拟该区域的客户分布，每个点代表了一个可能购买的客户，相邻两点间的距离为1，任意两点间的距离为欧式距离。然后每个客户根据自身可能购买的几率p，随机选择是否购买：没有购买则无需实行配送，购买了则需要配送。依据上文模型，本处实例分析以Matlab为平台，在20×20的点阵中模拟区域中的客户分布，并对模拟进行仿真。

4.1 残留系数对改进算法的影响

在算法的搜索过程中，信息素残留系数ρ对算法性能有着重要影响。ρ的值变大时，表明前次的信息素残留越多，每次搜索完信息素的增量越少，会削弱全局搜索能力，算法容易停滞；当ρ的值变小时，由于信息素残留过小又会影响算法的收敛速度。为了验证ρ的取值对算法的影响，以num=99，循环次数Circ=200，ρ分别取0.4, 0.6, 0.8时，根据以往的蚁群实验对蚁群算法的初始数据设置如下：信息素浓度与可见度的指数分别为α=1，β=2，θ=1，车辆载货上限Q_W=40，车辆一次行驶的最大距离L_M=70。画出优化过程曲线如图 1所示。

如图 1所示，在曲线前半段，当ρ的值越大时候，优化过程曲线下降速度越快，表明算法具有更快的收敛速度；在曲线后半段，当ρ的值越小时候，获得的优化结果越优，表明算法的搜索能力越强。因此，综合考虑收敛速度以及优化结果，取ρ=0.7进行之后的实验。

4.2 算法比较

为了验证基于极值动力学的改进蚁群算法的有效性以及优势，分别采用传统蚁群算法和本文算法，对电商物流配送问题进行求解。首先依据初始的客户购买几率p，选择配送中心，并生成客户需求。为比较两种算法的特性，随机生成5天的客户分布如图 2，依次表示num=96, 99, 93, 95, 89时的客户分布。

对蚁群算法的初始数据设置如下：信息素残留系数ρ=0.7，信息素浓度与可见度的指数分别为α=1，β=2，车辆载货上限Q_W=40，车辆一次行驶的最大距离L_M=70。循环次数Circ=500时，得出实验结果如表 1所示。表 1中的优化曲线a、b、c、d、e分别见图 3的5个小图。

为方便观测，依次画出这5天前200次循环的优化过程曲线如图 3所示。

如图 3曲线所示，相对于传统蚁群算法，改进蚁群算法曲线的收敛速度更快、更平滑，表明改进后的算法收敛更快，寻优能力更强。根据表 1以及图 3的结果，虽然引入极值优化后，由于算法运算量变大增加了一定的计算时间，但是总体的优化速率与优化结果都得到了大幅提升，总体而言大幅提升了算法的求解效率与精度。

以num=99为例，分别画出Circ=500时，两种算法最终生成的路径如图 4，图 5。

如图 4、5可见，在同样的搜索过程以后，基于极值动力学的改进蚁群算法结果更平滑，而蚁群算法中的路径明显存在可以继续优化的边角部分。综合以上实验结果，在引入极值优化后，在优化过程中能针对蚁群算法寻得路径中较差的部分进行优化，相当于给蚁群寻找路径时候增添了寻优指引，同时能够避免蚁群寻优时候，某些更优路径由于信息素太少而很难再被选取，从而导致算法陷入局部最优解。因此，改进后的算法拥有更好的搜索能力与收敛速度，可以更快地求得最优解。

4.3 弹性验证

为了验证弹性配送策略在不同客户需求情况下具有良好的适应性以及敏捷性，以人均成本作为目标函数对系统的不同状态进行仿真求解。

依据上部分的案例，如图 2可见，每天的客户需求分布零散多变，但是总体的需求数量波动较小。分别采用弹性管理策略对这5个不同的需求求解得到的结果如表 2所示。

由表 2可见，虽然每天的客户分布完全随机，但是最终的配送路径的长度都在195±10的范围内，而且每天客户的人均成本也均在一个小范围内波动。

做出每天的人均成本与5天的平均成本曲线如图 6，以及人均成本波动系数wav的曲线如图 7所示。

如图 6、7所示，在5天的配送过程中，每天的人均成本在小于4%的范围内波动，表明在面对不确定的客户需求时，系统表现出良好的适应性。证明了采用基于购买几率的重心法选址以及人均成本作为目标函数构建模型时，有效地降低每天需求变化的扰动，从而提升系统适应性。

如果在第1天的时候商家举行了大促活动，那么第1天的客户需求量会剧增。假定客户购买几率变为平时的3倍，模型随机生成了267名客户需求。此时最大化当天配送额能造成最少的库存积压以及客户不满意度。假定单位库存以及客户不满意度的成本为CE，运行模型得到的配送结果如表 3所示。

由于CE是个不确定参数，画出CE在1~3之间，每隔0.2取一个值，模型求得的人均成本及wav的曲线如图 8、图 9所示。图 8、图 9中，由下至上的曲线分别表示CE=1.2, 1.4, 1.6, 1.8, 2.0, 2.2, 2.4, 2.6, 2.8, 3.0时的结果。

如图 8所示曲线画出了正常运行情况下的历史均值，以及CE取不同值时的成本曲线。分别求出CE取不同值时候，第1天的rec的值如表 4所示。

因为模型都在第5天缓解了系统的扰动，因此rec的大小就反映了系统的弹性，其中rec越小，表明恢复越快。可见，当客户需求量剧增时，通过合理的调度使系统维持每天效率最大化，wav都能很快恢复到正常水平，尤其在CE较小时候。当CE逐渐变大时，系统的恢复速度逐渐变慢，基本在0.5左右，表明系统前一天的恢复速度是后一天的2倍，依然能很快在前期缓解系统的大干扰。因此系统在面临剧增的客户需求时，也能表现出很好的敏捷性。

5 结论

本文在车辆路径问题的基础上，分析电商物流配送与传统车辆路径问题的区别，并以此建立了模型。针对客户需求空间不确定的特点，对配送中心提出以客户历史购买几率为权值的重心法选址，使需求相对于配送中心分布的期望较为稳定；针对客户需求数量不确定的特点，以客户的人均成本作为优化的目标函数，缓解每天需求数量变化对目标函数的影响。此外本文还设计了基于极值动力学的改进蚁群算法对模型进行了仿真，通过实验验证了改进算法在面对同样的问题时拥有更好的搜索能力与收敛速度，可以更快的求得最优解。最后本文通过对不确定性客户需求问题的求解，验证了系统具有良好的适应性以及敏捷性，即增强了电商末端物流配送的弹性。之后的工作将考虑多种电商物流模式结合的问题、带时间窗以及指定配送的客户需求问题。