0 引言

随着电子商务的发展，未来将进入“新零售”时代，线上线下和物流结合在一起，产生新的零售方式^[1]。在“新零售”方式下，物品由企业统一配送到各个门店(便利店、超市等)，客户的需求由离客户最近的门店进行服务，以实现“当日达”，甚至“小时达”，能极大地提高客户的物流体验。对企业而言，门店数量将增加，门店每天需求量将急速增加，如何使用一组车辆对大规模门店进行货物配送，如图 1所示，是亟待解决的问题。

大规模门店物流配送本质上是解决一个车辆路径问题(Vehicle Routing Problem, VRP)，最早由学者Dantzig等于1959年提出^[2]，指一组车辆从物流总仓出发对一系列在地理上无规律分布的客户进行服务，要求每个客户的需求必须被满足且只能由一辆车提供服务，每辆车的路线开始于物流总仓，并且最终结束于物流总仓。VRP已被证明是NP-hard问题，使用动态规划法、分支界限法等精确算法只适用解决100个客户规模以内的VRP^[3]，不适用于大规模物流配送问题。根据约束条件不同，如车辆最大容量约束、门店服务时间窗约束等，可将VRP分为不同类型的扩展问题^[3]。

在本文研究的企业案例中，企业拥有8 000多家门店，配送车队拥有多达37种车型。目前企业仍处于人工调度派车阶段，线上和线下的订单分开处理，存在车辆空载率高、配送成本偏高、客户物流体验差等问题，制约了企业的进一步发展。企业急需进行配送调度自动化，配送算法要能在限定时间内计算可行的配送方案，同时充分利用企业自身的配送资源。因此，本文考虑以下VRP要素：多种车型，每种车型车辆数量有限，不同车型固定费用、可变费用和最大装载容量不同，每个门店的订货需求必须被满足且只能由一辆车服务。根据要素确定本文研究的问题是一个具有固定车辆数的多车型车辆路径问题(Heterogeneous Fixed Fleet Vehicle Routing Problem, HFFVRP)^[3]。同时，本文提出的算法需在限定的时间内得到较好的解。

1 相关研究

大规模物流配送问题具有网络拓扑结构复杂、数据处理规模大等^[4]特点，难以直接解决。现实中企业一般将门店按行政区域进行划分，从而将大规模VRP转化为多个小规模VRP进行解决。但按行政区域进行划分并不是最合理的划分方式，有学者提出改进的基于基地启发式算法(Location Based Algorithm)解决门店分区问题^[4]。近年来，随着大数据处理技术的成熟，聚类分析被广泛应用到各个领域，不少学者将聚类分析应用于VRP中。Ewbank等^[5]使用无监督模糊聚类技术对客户点进行聚类分组，然后构建分组的旅行商问题(Travelling Salesman Problem, TSP)路线；Shin等^[6]提出一种基于几何中心(centroid-based)聚类的三阶段算法，先围绕g个种子客户点进行聚类，然后根据类的几何中心和车辆容量约束对客户进行聚类再分配，最后构建每个类内部的TSP路线。但是，上述算法需指定聚类个数，而在实际应用中，聚类个数往往难以确定。本文拟采用DBSCAN(Density-Based Spatial Clustering of Applications with Noise)密度聚类算法，该算法根据用户输入的密度参数定义稀疏数据和稠密数据, 只将稠密数据集作为聚类^[7]。该算法可以克服其他基于距离的聚类只能发现类圆形类簇的缺点，并且无需指定聚类个数，适合用于对配送路线进行聚类分析。

基于邻域搜索的算法解决CVRP(Capacitated VRP)取得了较好的效果，一方面在多个国际基准测试案例上求得已知最优解，另一方面可扩展多种约束条件解决复杂的现实问题。但是，随着问题规模的增大，已有算法容易陷入局部最优。邻域搜索求解质量取决于邻域映射的方式。传统的邻域映射方式主要分为路径间交换或路径内交换，如Shift(1, 0)^[8]、Swap(1, 1)^[8]、2-opt^[8]等，算法每次迭代时对配送方案中1个或者2个节点进行操作，邻域搜索范围较小，当问题的解空间较大时，求解结果容易陷入局部最优。自适应大规模邻域搜索(Adaptive Large Neighborhood Search, ALNS)^[9]扩展了传统邻域搜索的邻域概念，设计的邻域结构对多个节点进行操作，从而扩大了邻域搜索的范围，更有可能求得全局最优的解。目前，国内外学者基于自适应大规模邻域搜索解决HFFVRP的研究很少，并且在问题规模较大、车型种类较多、算法求解时间有限的情况下，现有自适应大规模邻域搜索算法不能有效解决实际问题。

目前，ALNS中的毁灭移除算法分为workday、route和customer^[11]三个层次，workday按工作日对配送方案进行移除，route对配送方案中的配送路线进行移除，customer对配送路线上的门店进行移除。本文研究和实现customer层的毁灭移除算法。Random Removal^[9]是最简单的毁灭移除算法，可在解空间中产生任意的邻域集合；该算法易于实现但随机性较大，不能保证ALNS求解质量。Shaw Removal^[9]定义了相关度函数，邻域映射方式由相关度函数决定；由于相关度函数计算复杂，导致该移除算法执行时间较长，容易造成ALNS算法整体执行时间过长的问题。Worst Removal^[12]定义了一个门店从当前配送方案移除的开销函数，开销值越大，门店越需被移除，毁灭时移除开销值最大的q个门店；该算法移除效果好，但时间复杂度高。在门店规模大且聚集的应用场景下，对配送方案进行门店移除时，已有毁灭移除算法每次移除一个门店，门店可能来自不同的聚集域，这造成移除的节点插入原聚集域代价最低，在重建阶段该移除门店将被重新插入原聚集域。由于执行一轮毁灭和重建操作后，配送方案没有发生变化，ALNS算法需执行多轮毁灭和重建操作才能移除整个聚集域，从而增加了ALNS算法的迭代次数和执行时间，面对大规模门店配送时，ALNS算法无法在有限时间内求得较优解。

因此，本文在ALNS算法中设计了一种基于密度聚类的毁灭移除算法。在毁灭阶段使用密度聚类算法对配送路线进行聚类分簇，移除时以簇为单位，能在一次迭代中达到其他移除算法多次迭代的效果，而且密度聚类算法实现简单，时间开销较少，在执行一轮毁灭与重建操作上该算法时间开销比其他移除算法少。在国际基准测试案例上进行实验，结果表明采用密度聚类的毁灭移除算法执行相同的迭代次数只需更短时间，而且能得到更优的解，验证了基于密度聚类的毁灭移除算法的有效性。应用于本文研究的企业案例中，与人工调度派车相比，本文设计的ALNS算法减少了1/3的车辆使用，总开销不到其1/3，极大地降低了企业的配送成本。

2 问题描述及定义

在企业实际物流配送的车队中，费用计算复杂，包括司机津贴、车辆加油费、过路过桥费、车辆维修费、停车费等，为方便研究，拟将车辆费用分为可变费用和固定费用，可变费用由每公里油耗与行驶里程数决定，固定费用是除可变费用外的其他一切费用。本文考虑多种因素形式化为HFFVRP数学模型，该模型目标是确定一组车辆对门店进行配送服务，包括每辆车的车型，每辆车应服务的门店、访问门店的顺序和路线。模型目标函数由两部分费用组成：固定成本和可变成本。固定成本为所有车辆的固定费用累加和，可变成本为所有车辆可变费用累加和。目标函数约束条件为本文考虑的现实因素，配送方案优劣通过目标函数值大小进行判定。

HFFVRP定义如下：设无向图G=(V, E), V={0, 1, …, n}代表图中所有的节点，其中物流总仓编号为0，所有车辆必须从0节点出发最终回到0节点；其余编号为各个门店，每个门店对货物的需求量为d_i。E={(i, j)|i, j∈V, i≠j}是任意两个节点的边，权值为实际门店之间的距离d_ij。假设企业拥有的m种车型M={1, 2, …, m}，第k种车型拥有的车辆集合为φ_k，固定费用为f_k，每公里油耗费用为v_k，该车型最大装载量为Q_k。规定每个门店的需求必须被满足且只能由一辆车进行服务，问题的目标是：确定一组车辆对n个门店进行配送服务，使得总开销最小。

本文定义HFFVRP模型使用的参数和决策变量如表 1所示。建立具有固定车辆数的多车型车辆路径问题数学模型如下所示:

$ \begin{array}{*{20}{c}} \begin{array}{l} \min {\kern 1pt} {\kern 1pt} f(x) = \sum\limits_{k \in M} {\sum\limits_{l \in {\varphi _k}} {({f_k}\sum\limits_{i, j \in V/\{ 0\} } {{x_{ijkl}}} ) + } } \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\sum\limits_{i \in v} {\sum\limits_{j \in V} {\sum\limits_{k \in M} {\sum\limits_{l \in {\varphi _k}} {{x_{ijkl}}} {d_{ij}}{v_k}} } } \end{array} \end{array} $

(1)

$ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\sum\limits_{k \in M} {\sum\limits_{l \in {\varphi _k}} {\sum\limits_{i \in V} {{x_{ijkl}} \ge 1{\kern 1pt}, } } } \forall j \in V/\{ 0\} $

(2)

$ \sum\limits_{i \in V} {{x_{ipkl}}}-\sum\limits_{j \in V} {{x_{pjkl}} = 0{\kern 1pt} }, \forall p \in V, k \in M, l \in {\varphi _k} $

(3)

$ \sum\limits_{k \in M} {\sum\limits_{l \in {\varphi _k}} {{y_{ikl}} = 1{\kern 1pt}, \forall i \in V/\{ 0\} } } $

(4)

$ \sum\limits_{i \in V/\{ 0\} } {{d_i}{y_{ikl}} \le {Q_k}} {\kern 1pt}, \forall k \in M, \forall l \in {\varphi _k} $

(5)

$ {y_{jkl}} = \sum\limits_{i \in V/\{ 0\} } {{x_{ijkl}}}, \forall j \in V/\{ 0\}, k \in M, l \in {\varphi _k} $

(6)

其中: f(x)是目标函数; 约束(2) 表示各门店至少被一辆车服务一次; 约束(3) 确保一辆车对一个门店服务后，离开这个门店; 约束(4) 表示每个门店只能由一辆车提供服务; 约束(5) 表示被同一辆车服务的门店需要货物总和不能超过该车型最大的装载量; 约束(6) 表示门店j只能由一辆来自其他门店的车辆提供服务。

3 算法设计

设I为组合优化问题的实例，满足I中所有约束条件的可行解为S(I)，衡量一个解好坏的开销函数为式(1)，目标是求解式(1) 中最小值。对任意一个解X上的映射：

$ N:X \in S(I) \to N(X) \subseteq S(I) $

(7)

称为一个邻域映射，又叫邻域结构。其中:N(X)为解X的邻域集合，称X′∈N(X)为X的一个邻居。在传统的邻域搜索中，邻域集合的映射方式主要对当前解中一个或者两个元素进行操作。ALNS是传统邻域搜索的一种扩展，通过对多个元素进行操作，从而扩展了邻域的空间，在解空间中更大的范围内搜索最好解^[9]。ALNS算法求解的质量和速度主要受邻域映射的方式影响，对不同的问题实例，最优的邻域映射方式不同。对于同一个问题实例，设计不同的邻域映射方式，算法求解质量也不相同。ALNS邻域映射方式由毁灭阶段算法决定，重建阶段则在邻域结构对应的邻域解集合中搜索最佳可行解。ALNS在一次迭代中主要需要经历毁灭与重建两个阶段:毁灭阶段选择一个简单的移除算法，从当前配送路线中移除q个节点，将q个节点插入配送路线形成的所有可行解为邻域集合; 重建阶段选择一个构造算法从邻域集合中搜索最好解形成新解，最后由接受准则决定是否采纳新解。

设计一个ALNS算法需要注意以下三点：1) 一组简单有效的毁灭移除算法；2) 一组能快速构造可行解的重建算法；3) 决策层选择合适的接受准则。

在毁灭阶段本文根据实际情况提出并实现了基于密度聚类的毁灭移除算法(Cluster Removal, CR)，这是一种新的邻域映射方式。同时还实现了Shaw Removal(SR)^[9]、Worst Removal(WR)^[12]和Random Removal(RR)^[9]三种毁灭移除算法。在重建算法上本文实现了贪婪插入法^[11]和Regret-2插入法^[11]。本文借鉴模拟退火算法^[13]设计和实现接受准则。

3.1 算法框架

算法1  ALNS框架。

输入 迭代次数IterMax，周期R，毁灭变量个数q；

输出 当前最优解X^*。

过程：

1) 初始化参数，构造初始解决方案X，令X^*=X

2) for j=1 to IterMax do       //执行设定的迭代次数

3)  for i=1 to R do       // R次迭代一个周期

4)   使用轮盘赌选择法从L中选择一个算法组合a_i

5)   使用a_i中的毁灭算法移除X方案中q个变量

6)   使用a_i中的重建算法为q个变量重新赋值得到新方案X′

7)   if满足接受准则then

8)    X^*=X′

9)    记录a_i改善当前方案的情况

10)   end if

11)   end for

12)   根据本周期各算法组合a_i改善情况更新其分数π_i

13) end for

14) 输出X^*

算法1中ALNS框架基本流程包括：产生初始解，自适应选择算法组合，毁灭当前解，重建可行解，根据接受准则判断是否采纳新的可行解。设毁灭与重建算法的全组合为L={a₁, a₂, …, a_n}，相对应的分数集合为P={π₁, π₂, …, π_n}，每种组合a_i包括一种毁灭算法和一种重建算法，对应分数为π_i，π_i将决定组合a_i在轮盘赌选择法被选中的概率。算法1中，第1) 行构造初始方案时应选择简单的VRP构造算法，本文实现插入法^[12]求得初始可行路线集合X，并设为当前能找到的最好解X^*。第2)~12) 行是主循环，算法执行指定的迭代次数。在循环内部，算法每执行R次迭代将对P进行更新，以保证对当前解改善较多的算法组合能被更大概率地选中。在每次迭代中(第4)~9) 行)，毁灭算法根据移除规则破坏当前解X，使得q个门店未被服务，重建算法将q个门店重新插入到路线集合中得到可行的新路线集合X′，如果X′满足接受准则，将成为当前能找到的最好路线组合。当执行次数达到最大迭代次数，输出X^*。

3.2 基于密度聚类的毁灭移除算法

在本文研究的企业案例中，每天需要处理来自各地300多家门店的订单，问题规模较大。在地理分布上，同一个行政区域内门店分布相对密集，但企业物流总仓距离大部分门店较远，基本在30 km以上，因此配送路线上的门店具有聚集的特点，适合应用聚类算法。

在图 2中，假设毁灭阶段选择路线2进行移除。对于路线2中距离较近的门店j、k、l和m，使用其他毁灭算法进行移除时，算法随机移除其中一个门店，例如门店k。然后在重建阶段将k重新插入到配送路线中，由于在门店j和门店l之间插入代价最低，k将被重新插入到路线2中。算法执行一轮毁灭与重建操作后，路线1和路线2并未发生任何变化，从图 2左边的配送方案变换为右边的配送方案，算法将需要执行多次迭代。若使用聚类技术，将对路线2通过聚类得到(g, h, i, n)和(j, k, l, m)两个门店簇，每个簇被移除概率为0.5。被移除的门店簇在重建阶段被重新插入配送路线时可得到图 2右边的配送方案，这是一个比图 2左边更优的配送方案，并且只执行一轮毁灭与重建操作，因此，使用聚类技术的邻域映射方式更适合应用于门店规模大且聚集的场景，能减少ALNS算法执行的迭代次数，降低ALNS算法执行的时间，提高ALNS求解质量。

毁灭阶段需要设计一个简单的移除算法从当前配送方案中移除q个门店，若移除算法过于复杂将影响ALNS算法整体性能。在customer层实现基于聚类的移除算法时，聚类对象为每辆车的配送路线。文献[5]使用的模糊聚类技术和文献[6]使用的基于几何中心的聚类技术需事先指定聚类的个数g，g由车辆最大装载量和客户需求量总和决定，最终配送方案将派g辆车进行配送，应用于单条配送路线聚类时，k将难以确定。由于DBSCAN聚类算法具有实现简单、无需指定聚类个数、发现任意形状的空间聚类等特点，因此，适合应用于配送路线聚类。在eclipse平台下实现该算法时可使用开源数学包org.apache.commons.math3.ml.clustering，需指定邻域半径参数EpsDistance和核心对象个数参数MinPts。本文在文献[7]的基础上实现参数的设置方式，EpsDistance由式(8) 决定，其中d_avg为随机选取的10个门店之间的平均距离，d_min为10个门店之间的最短距离，控制因子ξ在本文使用的测试案例中均取值0.8，MinPts每次随机取值{2, 3, 4}。由于本文研究的企业案例只提供门店的经纬度信息，门店之间的距离计算需要借助高德地图开发者平台进行查询，因此需要自定义门店间的距离计算方式，并把实现类作为参数传入开源数学包的DBSCANClusterer函数中。

$ EpsDistance({d_{{\rm{avg}}}}-{d_{{\rm{min}}}}) * \xi $

(8)

基于密度聚类的毁灭移除算法基本思想是随机从当前配送路线集合中选择一条路线，对该路线进行密度聚类得到簇集合，然后随机选择一个簇集合进行移除，直到移除了q个门店。设门店集合S={s₁, s₂, …, s_n}，对一条配送路线使用DBSCAN聚类后得到簇集合C={c₁, c₂, …, c_p}，每个簇集合拥有的门店c_i={s_i1, s_i2, …, s_ik}，其中i取值范围从1到p，查询一个门店s_i所在路线使用操作ShopInRoute [s_i]，伪代码如算法2所示。

算法2  Cluster Removal。

输入 门店集合S，移除门店个数q；

输出 v; 移除门店集RemovalShops。

过程:

1) while q > 0 do

2)   if targetRoute== NULL then

3)   从S中随机选择一个门店s_i

4)    targetRoute= ShopInRoute [s_i]

5)    else

6)    从LastRemoval中随机选择一个门店s_i

7)     其他门店到s_i距离从小到大排序

8)    选择离s_i最近的门店s_ij且该门店所属路线未执移除操作

9)    targetRoute= ShopInRoute [s_ij]

10)     清空LastRemoval={}

11)   end if

12)   C=DBSCANClusterer (targetRoute, MinPts, EpsDistance)

13)  随机从C中选择一个簇c_i

14)  for每个s_il∈c_i，其中l从1到k do

15)   若q为0，跳到21)

16)   把s_il 加入LastRemoval中

17)   把s_il加入RemovalShops中, q自减1

18)  end for

19)  把C_i加入RemovalRoutes中

20) end while

21) 输出RemovalShops

算法分两种情况选择聚类的目标路线targetRoute，通过变量LastRemoval记录最近被移除的门店。刚开始targetRoute为空时，随机选择第一条路线进行聚类移除操作，时间复杂度是O(1)。当targetRoute不为空且已移除门店数量不足q个门店时，在第5)~10) 行，将从最近移除的门店集合中随机选择一个门店s_j，假设其他门店到s_j按距离从小到大排序后为集合N={s_j1, s_j2, …, s_jn－1}，从中选择一个未被移除的门店且该门店所属路线未曾执行移除操作，将targetRoute设置为该门店所属的路线。在具体实现时，由于其他模块也需要N集合，在Cluster Removal算法中无需重新计算N，并且选择门店时最多遍历N中q个门店，所以第5)~10) 的时间复杂度与常量q相关，为O(q)。在算法第12) 行对targetRoute路线进行密度聚类，DBSCAN聚类算法在最优的情况下时间复杂度为O(n log n)，在最坏情况下时间复杂度为O(n²)。因此，Cluster Removal算法时间复杂度取决于DBSCAN聚类算法，在最优情况下时间复杂度为O(q·n log n)，在最坏情况下时间复杂度为O(q·n²)。

3.3 重建算法

重建算法将毁灭阶段移除的q个门店重新插入到配送路线中，使每个门店的需求都被满足，且不违反各车型车辆数量有限的约束与车辆最大装载容量的约束，形成可行的配送方案。本文根据HFFVRP的特点设计了插入代价的计算方式，实现贪婪插入和Regret-2插入两种常用的构造算法。

3.3.1 贪婪插入法

算法基本思想是在每次迭代中为一个移除门店寻找插入代价^[12]最低的路线进行插入。根据车型可变成本，本文设计了如式(9) 所示的插入代价函数：

$ \Delta {f_{i, k}} = (C_{ai}^k + C_{ib}^k-C_{ab}^k)-\gamma (C_{0i}^k + C_{i0}^k) $

(9)

式(9) 表示对k车型配送路线上的门店a和门店b之间插入i。Δf_{i, k}的值由两部分代价组成，分别是i插入a与b之间的开销和新增一辆车服务i的开销。通过控制因子γ可以在插入当前路线或新增一辆车上取得平衡。当门店距离仓库较近且插入当前路线代价较高时，应新增一辆车对门店进行服务；当门店距离仓库较远时，应避免新增一辆车。控制因子γ在迭代中每次随机取值{0.00, 0.05, 0.10, …, 1.50}。当出现违反车辆容量约束而无法将门店i插入路线k的情况时，先判断该车型是否还有可用车辆，若存在可用车辆，则Δf_{i, k}为新增一辆车服务该门店的代价，否则Δf_{i, k}=∞。算法每次迭代寻找式(10) 中门店与路线的组合：

$ (i, k) = \mathop {\arg \min }\limits_{i \in S, k \in R} \Delta {f_{i, k}} $

(10)

然后，将门店i插入k路线中，更新车辆的可用容量。迭代一直进行，直到q个门店全部被插入配送路线中。该算法实现简单，计算Δf_{i, k}操作最多需要进行n次，因此算法的时间复杂度为O(q·n)。但是，对于插入开销最大的门店，算法在最后一次迭代进行处理，此时每条路线对应的车辆可用容量低，插入任何路线都容易违反车辆的最大装载容量约束，唯有新增一辆车对该门店进行服务，从而增加了车辆数，总开销变大。

3.3.2 Regret-2插入法

Regret-2算法解决了贪婪插入法存在的问题。假设Δf _i¹代表门店i插入最优路线的代价，Δf _i²代表门店i插入次优路线的代价，两者之间的差值越大说明该门店越不适合插入次优的路线中。Regret-2插入法在每次迭代中寻找式(11) 差值最大的门店i进行插入处理：

$ i = \mathop {\arg \max }\limits_{i \in S} (\Delta f_i^2-\Delta f_i^1) $

(11)

式(11) 保证了门店i插入到最合适的路线上，算法迭代后期处理的是最优路线与次优路线之间差值不大的门店，能有效避免贪婪插入法在迭代后期容易出现违反车辆容量约束的问题。

3.4 决策层

经过毁灭与重建两个阶段，算法产生一个新的配送方案，决策层需决定是否接受新的方案。在本文实现的ALNS算法中，决策层做了两件事情：1) 采用模拟退火接受准则决定是否接受新的配送方案；2) 自适应选择下一次迭代的算法组合。

3.4.1 接受准则

模拟退火算法应用在车辆路径问题上取得了很不错的效果^[13]，本文借鉴模拟退火算法实现接受准则，算法接受比当前解更好的新解，也以一定概率接受比当前解更差的新解。

在ALNS算法第7) 行，接受新解X′的概率为：$ {{\rm{e}}^{-\frac{{f(x')-f(x)}}{T}}} $其中: f(x)为式(1) 定义的总开销函数；T代表温度，由T_start开始降温，降温公式为T=T·c，冷却速率为c，取值范围0 < c < 1。初始温度T_start的设置对算法影响较大，本文根据文献[13]提供的方法，修改总开销函数，然后通过计算插入法产生的初始方案的总开销对T_start进行设置。

3.4.2 自适应选择算法

毁灭与重建阶段各需一个简单的算法，在本文实现的ALNS算法中将有8种算法组合，不同的组合适用于不同的数据集，为使算法能自适应地选择合适的算法组合进行毁灭与重建，对每种组合设计了相应的分数，根据分数采用轮盘赌选择法^[9]进行选择。假设第i种组合分数为π_i，有H种组合，则第i种组合被选择的概率为：$ {\pi _i}/\sum\limits_{i = 1}^H {{\pi _i}} $。分数在每个迭代周期结束后进行更新，假设π_{i, j}代表第i种组合在迭代周期j的分数，更新规则为：

$ {\pi _{i, j + 1}} = {\pi _{i, j}}(1-r) + r\frac{{{\theta _i}}}{R} $

(12)

其中：r为选择因子，取值0 < r < 1，如果历史分数对下一周期分数较为重要，r设置为接近0的数字，否则设置为接近于1的数字；R代表一个周期进行迭代的次数；θ_i为通过组合i计算得到的可行方案在周期j内被采纳的次数。

4 实验与分析

本文算法在eclipse平台下采用Java语言编程实现，测试环境为PC，配置为Intel Core i5-3470 @ 3.2 GHz，8.00 GB内存，32位Windows 7操作系统。为方便描述，毁灭阶段使用Cluster Removal机制的ALNS算法简称C_ALNS，未使用该机制的算法简称ALNS。仿真实验使用的国际标准测试案例可以从网站http://neo.lcc.uma.es/vrp/vrp-instances/^[14]下载。

4.1 基准测试案例验证有效性

本文提出的C_ALNS适用于具有大规模客户，且客户在地理位置上具有聚集特点的场景。在网络上公开的HFFVRP数据集中客户点并没有聚集特点，不符合本文需要研究的场景。因此，本文采用符合场景应用的CVRP(国际基准测试案例进行测试，CVRP可看成只有一种车型的HFFVRP。该测试案例为Augerat等提供的B类型的数据集^[14]，客户点具有聚集的特点，规模从31到78不等。

算法参数设置如下:在C_ALNS和ALNS中，每种毁灭与重建算法组合初始分数π_i都设为0.5，以保证每种组合被选中的概率相同；分数更新选择因子r设为0.2。根据文献[12]给出的建议：在小规模问题中，将毁灭阶段需要移除的客户数量q设置为min {0.1n, 30}，其中n代表客户总数；大规模问题则设置为min {0.4n, 60}。迭代次数IterMax设为2 000。

Augerat数据集的客户规模较小，能在较短时间内得到稳定解，对每个测试案例均进行5次实验，分别记录C_ALNS算法和ALNS算法取得的解及花费的时间，记录各移除算法产生的满足接受准则解的次数，结果如表 2所示。在表 2中：第一列为测试案例编号；第二列为该案例目前已知的最优解；cost列为相应算法取得的解；time列为相应算法的执行时间(单位为s)；gap/%列表示相应算法取得的解与公认最优解之间的误差，计算公式为:

$ gap = ({Z_{{\rm{C\_ALNS/ALNS}}}}-{Z_{{\rm{best}}}})/{Z_{{\rm{best}}}} * 100\% $

(13)

其中：Z_{C_ALNS/ALNS}代表C_ALNS算法或者ALNS算法取得的解，Z_best代表该案例已知最优解。SR、RR、WR、CR列为本文实现的移除算法的贡献率，各移除算法贡献率计算方式为：ALNS执行2 000次迭代，由该移除算法产生满足接受准则的解的次数除以所有满足接受准则的解的总次数。测试案例移除算法贡献率越高，对应的邻域映射方式越适合应用于解决该问题实例。从表 2中可知，两种算法取得的最好解与案例已知最优解之间误差均在1%以内，误差较小。在23个测试案例上，C_ANS算法需要更短的时间，所需时间加黑表示该案例下C_ALNS算法求解质量比ALNS算法更优，占19个案例，说明在相同迭代次数下，C_ALNS算法能在更短的时间内求得更优的解，比ALNS更高效。在4个例外的案例中，结合各毁灭移除算法贡献率可知，SR或者WR毁灭移除算法更适合应用于这些案例，但C_ALNS产生的解与ALNS产生的解相差不超过1%，C_ALNS需要时间更短。在C_ALNS表现更好的19个案例中，CR算法贡献率最高，ALNS则是SR或者WR算法贡献率高，这说明CR是比SR或WR时间复杂度更低的毁灭移除算法，定义的邻域映射方式更适合应用于客户具有聚集特点的VRP场景下，验证了基于密度聚类的毁灭移除算法的有效性。

表 3给出C_ALNS算法与Hassani等的混合蚁群算法H_ACS^[15]、Tasan等的遗传算法(Genetic Algorithm, GA)^[16]、文献[17]公布的粒子群优化(Particle Swarm Optimization, PSO)算法、Ewbank等的无监督模糊聚类算法^[5]、Shin等的Centroid-based 3-phase算法^[6]的结果比较，Average行表示每种算法求解结果与案例已知最优解之间的平均误差, 符号“—”表示该算法没有提供对应测试案例求解结果。

从表 3中可知，C_ALNS求解23个测试案例得到的最好解比两种使用了聚类技术的算法^[5-6]求解的结果更优，说明DBSCAN聚类算法适合应用于配送路线聚类。与案例已知最优解相比，C_ALNS算法平均误差为0.77%，H_ACS算法平均误差为1.66%，GA的平均误差为25.03%，PSO算法平均误差为0.30%，Centroid-based 3-phase算法平均误差为6.28%，Ewbank等的无监督模糊聚类算法平均误差为4.58%。GA的平均误差较大的原因是算法求解质量取决于测试案例的上界和下界，下界为案例已知最优解，但由于GA使用CPLEX在Augerat数据集上求解的上界较大，故求解结果较差。对比结果表明C_ALNS算法求解质量优于H_ACS算法、GA，Centroid-based 3-phase算法和Ewbank等的无监督模糊聚类算法，稍逊于PSO算法，但C_ALNS算法在给定迭代次数下求得最好解，以满足时间限制要求，PSO算法以最优解为目标，并未限定时间约束，因此，本文设计的C_ALNS算法能有效解决车辆路径问题。

4.2 企业实际案例

本文研究的企业案例每天凌晨前汇总当天所有门店的订单，并在凌晨后处理部分订单，在白天处理大部分订单。企业需要算法在有限时间内求得较好的配送方案，指导货物装车，并使车辆按指定路线进行配送。

4.2.1 数据提取

企业业务部门提供以下数据：每个门店详细地址信息，包括每个门店的经纬度；37种车型详细数据信息，包括车辆最大装载量、车辆固定开销费用、车辆每公里油耗；一个月的订单历史数据和人工派车调度处理的结果数据。本文对订单历史数据按日进行处理，每天有350个左右的门店下单。利用门店的经纬度信息，通过高德开放平台可查询2个门店之间的最短距离或用时最少距离，从而得到每2个门店之间的距离。

4.2.2 参数设置

本文随机选取一天订单进行处理，涉及345个门店，规模较大，因此毁灭阶段需移除门店个数q设为60。对C_ALNS和ALNS中每种算法组合初始分数设为0.5，保证每种组合选择概率相同，分数更新选择因子r设为0.2。算法分别进行1 000、2 000、4 000、8 000、16 000次迭代，以说明算法求得的最好解、迭代次数和时间开销三者之间的关系。同时选取5、10、15、20、25、30、35辆车进行一组实验，迭代次数为5 000，以说明车辆规模与时间开销的关系。最后选取C_ALNS和ALNS迭代5 000次的配送方案与企业人工调度配送方案进行对比。

4.2.3 结果对比与分析

图 3对比了C_ALNS与ALNS算法配送方案总开销，总开销为式(1) 定义的目标函数。从迭代次数与总开销关系中可知，算法在执行相同次数情况下，C_ALNS算法求解效果更优，说明CR算法适用于门店规模大且聚集特点的应用场景，能提高C_ALNS求解质量。两条曲线下降的趋势表明两种算法随着迭代次数增加，求解质量更优，并最终达到稳定值，因此，在有限时间内，对大规模问题应尽量增加算法执行次数以取得较优的配送方案。

图 4对比了两种算法的执行时间。在执行相同迭代次数下，C_ALNS算法需要更少时间，说明CR是一个简单算法，相比其他算法组合，使用CR算法的组合只需花费更短时间执行一轮毁灭与重建的操作，从而缩短了C_ALNS算法整体执行时间。两种算法执行时间曲线走势说明迭代次数与花费时间呈正相关关系，若企业需要在1个小时内得到较好的配送方案，在门店规模为345、车型数目为37种的情况下，执行5 000次迭代是较好的选择。

图 5说明车辆规模与算法时间开销的关系。图中曲线走势表明在给定迭代次数下，车辆规模越大，算法执行时间越长。在实际应用中，应根据需要选择合适车型，以减少车队规模。例如，对生鲜商品进行配送，只需考虑具有冷藏功能的车型，从而减少配送车辆规模，降低算法执行时间，在有限时间内增加算法执行次数，以求得更优的配送方案。

表 4对比企业人工调度、ALNS算法和C_ALNS算法计算的配送方案。车型数为每种配送方案使用车型的种数，车辆数为每种配送方案使用的车辆总数，车辆平均装载率为所使用的车辆装载率之和除以使用车辆总数。相比人工调度计算的配送方案，C_ALNS算法与ALNS算法使用了更多的车型，C_ALNS算法减少接近1/3的车辆使用，平均车辆装载率提高了20%，总开销不到其1/3，有效地降低了企业配送成本。因此，C_ALNS算法能在有限时间内求得较优配送方案，适合应用在多车型大规模企业物流配送问题中。

5 结语

为解决多车型大规模物流配送问题，本文在ALNS算法框架下设计和实现了一种基于密度聚类的毁灭移除算法。使用国际标准测试案例进行仿真实验，通过C_ALNS与ALNS算法求解结果对比可知，基于密度聚类的毁灭移除算法定义的邻域映射方式更适合门店规模大且聚集的场景，能有效降低ALNS算法整体执行时间，提高ALNS求解质量，从而验证所提移除算法的有效性。与Ewbank等的无监督聚类算法^[5]、Shin等的Centriod-based 3-phase算法^[6]、H_ACS算法^[15]、GA^[16]、PSO算法^[17]相比，C_ALNS求解质量优于H_ACS算法、GA、Ewbank和Shin的算法，稍逊于PSO算法，但C_ALNS算法在限定时间内求解，PSO算法以最优解为目标，并未限定时间约束，因此，C_ALNS算法能有效解决物流配送问题。应用于企业实际数据集的结果表明，C_ALNS算法能在有限时间内得到较优的配送方案，极大地降低了企业的物流配送成本。在新零售模式下，本文提出的算法能有效解决企业对大规模数量的门店进行货物配送的问题，下一步将研究门店到各顾客之间的物流配送问题。