针对多中心场站下两级选址路径问题的双智能集成算法

唐 震 霆， 胡 志 华

(上海海事大学 物流研究中心，上海 201306)

0 引 言

两级选址路径问题(two-echelon location routing problem，2E-LRP)是近年来物流领域的热点问题，选址路径问题从结构上来说首先要完成选址，而后进行路径规划.在一个多级运输配送系统中，一条完整的运输配送链也被分成多级，货物从仓库运输至枢纽点整合并移交至最终客户，高效利用各枢纽点与车辆容量是降本提效的关键，而将客户点合理分配至每一个客户是枢纽点高效运作的条件之一[1].

截至目前，许多优秀的学者提出了多级车辆运输的相关选址路径规划方案以及方法论.有关2E-LRP的文献开始涉及城市物流中两级配送结构的运营和资源管理的短期综合调度问题[2-7]，在确定枢纽点之后问题转变为两级车辆路径问题(two-echelon vehicle routing problem，2E-VRP)；传统的车辆路径问题一般为单级物流系统，即车辆从中心场站直接向需求点提供服务.一般地，物流运输车辆体积较大、质量较重，加重了城市道路交通拥堵、噪声、污染等情况，地方政府对此也提出了限行条例：运输物资先通过大型运输车辆调配至企业位于郊区的中转设施中，而后通过污染较小、较为灵活的小型运输车辆进行配送，这也就是两级车辆路径问题的起源.Grangier等介绍了一个具有卫星同步的两级多行程车辆路径问题，并提出了一种自适应大邻域搜索(adaptive large neighborhood search，ALNS)算法[8].Boccia 等考虑了多中心场站的场景，针对不同类型的车队和两级物流网络路径之间的联系等要素采用了禁忌搜索算法对算例进行实验，实验结果证明了该算法的有效性[9].Yang等研究城市物流系统中带时间约束的两级选址路径问题，基于概率选择原则提出了一种综合考虑时间和空间可达性的元启发式算法来求解该类问题，并通过随机生成的实例来验证算法有效性[10].Pichka等认为多级分销系统普遍存在于人们的日常生活中，其提出3种基于流通路径的混合整数线性规划以及1种混合启发式算法来求解开放式选址与路径优化问题[11].

对于上述研究，两级设施选址与车辆路径规划问题的双层结构特征是其复杂性的核心，两级物流网络的搭建与布局一直是许多物流企业的痛点，如何从备选节点中选择有利于降低整体系统成本的节点来作为枢纽点、确定车辆经过节点的先后次序即车辆路径以及客户点、枢纽点与中心场站的对应关系是该问题的几个重大难点，也是物流企业进行多级物流网络建设所避不开的问题.在一些研究中将问题分割为两个阶段来进行求解[12-13]，这在一定程度上导致了求解问题的独立性，对于两级选址路径问题，双智能集成算法的表现优于其他传统启发式算法.本研究中进行节点资源配置的算法为ALNS的改进算法，拥有一组破坏与修复算子是其与常规ALNS算法[14]最明显的不同，而模拟退火算法则用于路径寻优.

1 多中心场站下两级选址路径问题的建模

基本的两级选址路径问题表述如下：从备选节点中选出若干个合适的节点作为枢纽点优化配送体系，降低系统成本；一组运输车辆从中心场站出发，将货物运输码放至枢纽点，而后由枢纽点委派运输车辆将货物交付给客户，所有运输车辆在完成配送后回到始发节点；每个客户点的坐标位置已知；配送车辆有荷载限制；要求合理配置资源、优化行车路径，以实现目标的优化.

多中心场站下两级设施选址与车辆路径规划问题的图论表述如下：D代表中心场站集合，通过τ∈D索引；N代表客户点集合，一般通过i∈N索引每个客户点，通过υ∈N索引枢纽点；候选枢纽点集合S⊆N；定义J=D∪N.Cij≥0为车辆从i∈J到j∈J的行驶成本；F1≥0与F2≥0分别为两级运输中单辆运输车的固定成本；F3≥0为设置一个枢纽点的固定成本；由客户需求Ri得出每一个枢纽点所需要的货物量.第一级和第二级配送车辆的容量上限为K1和K2.C1和C2表示第一级和第二级车辆配送的单位里程成本.Ud表示中心场站数量，Us表示枢纽点数量.

变量qijτ表示从中心场站τ∈D出发的车辆经过i∈N到达j∈N路段中车辆的载货量；变量pijυ表示从枢纽点υ∈N出发的车辆经过i∈N到达j∈N路段中车辆的载货量.

决策变量βijτ=1，表示客户点i分配给枢纽点j，并且j分配给中心场站τ；否则，βijτ=0.其中，i≠j.若节点i被选作枢纽点，则βiiτ=1.

决策变量xijτ=1，表示第一级配送车辆从中心场站τ出发，服务i∈N后下一个紧接的服务节点是j∈N；否则，xijτ=0.

决策变量yijυ=1，表示第二级配送车辆从枢纽点υ出发，服务i∈N后下一个紧接的服务节点是j∈N；否则，yijτ=0.

对2E-LRP问题中的变量与约束条件设置特点进行总结，完善数学模型的构建，所求得的解必须满足以下约束：

(1)每个被选作枢纽点的节点至少服务一个客户点；

(2)每次配送任务中任意车辆只运行一次；

(3)每条路径从设施出发，最后要回到出发的设施；

(4)每个客户点由且仅由一辆货车进行服务；

(5)车辆服务的顾客的需求总和不能超过车辆的容量约束；

(6)每个客户的需求Ri均为常量且已知；

(7)每个中心场站都至少辐射一个枢纽点.

首先，目标函数主要由两部分组成，分别是两级运输中的路径成本总和以及车辆、枢纽设施的固定使用成本，如下式所示：

minz=z1+z2

(1)

其中

针对枢纽点的选择以及客户点的分配这两个子问题，考虑两个层级下枢纽点集合与客户点集合的分配逻辑构造约束，以便于路径问题的求解，控制选址以及枢纽点分配的模型如下：

(2)

(3)

(4)

(5)

βikτ≤βkkτ；∀i，k∈N，τ∈D

(6)

其中，约束(2)表示任意节点i∈N都会被分配一个枢纽点，且归属于一个中心场站；约束(3)表示枢纽点个数等于Us；约束(4)表示任意枢纽点仅被分配给一个中心场站；约束(5)表示若节点i∈N不是枢纽点必会被分配给一个枢纽点；约束(6)表示仅当k∈N为枢纽点时才会将客户点分配至枢纽点k.

(7)

(8)

(9)

(10)

(11)

(12)

约束(7)～(9)去除了车辆从中心场站出发的无效路径，约束(10)～(12)表示第一级运输中的路径约束与流平衡限制，且第一级运输车辆经过的节点是被选作枢纽的节点.

(13)

(14)

qijτ≥xijτ；∀i∈J，j∈N，τ∈D

(15)

qijτ≤K1xijτ；∀i，j∈J，τ∈D

(16)

xijτ≤βjjτ；∀i∈J，j∈N，τ∈D

(17)

xjiτ≤βjjτ；∀i∈J，j∈N，τ∈D

(18)

(19)

约束(13)～(14)将车辆装载量、路径、分配问题相联立，保证了车辆运输过程中，经过枢纽点的顺序与车辆装载量同步变化，即当车辆经过任意枢纽点时装载量减少相应节点所需的货物量.约束(15)～(16)将变量qijτ与第一级运输路径xijτ建立联系；约束(17)～(18)将第一级运输路径限制在枢纽点与中心场站间；约束(19)表示车辆回到中心场站时的装载量为零.

(20)

(21)

约束(20)～(21)表示了第二级运输中车辆装载量与运输路径的联系，以确立运输顺序与车辆装载量的变化关系.

(22)

(23)

(24)

pijυ≤K2yijυ；∀i，j，υ∈N

(25)

pijυ≥yijυ；∀i，j，υ∈N，j≠υ

(26)

约束(22)～(24)对第二级运输路径进行约束，建立流平衡约束；约束(25)～(26)将变量pijυ与路径yijυ联立，确保车辆装载量不超过车辆容量.

(27)

(28)

(29)

(30)

(31)

约束(27)～(30)将第二级运输路径与节点分配逻辑保持统一，若客户点j由枢纽点υ服务且归属于中心场站τ，则允许在客户点j处存在入度与出度；约束(31)表示第二级运输车辆回到枢纽点时的装载量为零.该模型综合枢纽点选择、两级节点分配、车辆路径规划3个问题同时求解，保证了解决系统问题的连贯性、完整性.

2 双智能集成算法

2.1 算法设计依据与逻辑

黄凯明等通过对多层级设施选址路径规划问题的研究，提出一种双智能集成算法：量子进化算法负责设施选址和资源分配，而遗传算法负责子路径寻优[15].双智能集成算法在求解选址路径问题过程中体现出较大的优势，在应对不同问题时都可以选择针对问题具有较好求解性能的启发式算法来进行处理，通过信息交互、共同迭代来求解复杂问题是一种较为优秀的求解思路.由此，本文在算法设计时采用了改进的自适应大邻域搜索算法与模拟退火算法集成的双智能算法，该混合启发式算法通过两种不同类型算法的交互，将求解任务分解，从而有效求解问题.

算法设计依据：两级选址路径问题的复杂性主要是因为该问题不仅需要确定节点分配方案，确定运输工具遍历枢纽点以及客户点的次序，还需要留意运输工具容量限制及枢纽点必须有子节点等条件，本混合启发式算法能有效求解子问题并在算法内部交互迭代，因此该混合启发式算法适合解决两级选址路径问题.自适应大邻域搜索算法在多邻域迭代过程中有着较优秀的表现，因此选择自适应大邻域搜索算法作为算法主体框架，使用模拟退火算法求解子路径的最优排序，这也加快了问题整体的求解效率，算法逻辑如图1所示.

算法设计逻辑：两级自适应大邻域搜索(two-echelon adaptive large neighborhood search，2E-ALNS)算法控制两级节点分配方案，分别改变枢纽点被分配至中心场站的方案以及客户点被分配至枢纽点的方案，根据分配方案确定每个旅行商问题(TSP)的构成节点，但此时的分配方案中节点是无序的，经过模拟退火算法进行求解后，节点分配方案中的排序与TSP解的节点排序一致，因此两个算法分工明确且相辅相成.

2.2 模拟退火算法

采用模拟退火算法以解决车辆经过节点的次序问题，算法的输入集是主节点编号、子节点编号以及节点坐标位置.算法采用随机交换节点次序来进行路径排序问题的寻优，模拟退火算法初始温度设为50；冷却速率为0.98；算法以一定概率接受改造解，概率公式如下：

式中：ρ为接受改造解的概率；Sc为当前迭代中的局部最优解，Sn为算法产生的新解；E(S)代表解S的能量，在本例中即为路径成本；T为当前温度；ϑ为温度与能量差值的转换系数，本例中取ϑ=0.8.当改造解的运输成本小于局部最优解的运输成本以，将改造解替代局部最优解；当改造解的运输成本大于局部最优解的运输成本时，以一定概率接受改造解，将接受概率和当前温度相关联，使得该算法在运行初期搜索区域变大，加快收敛速度，而在后期削减其搜索区域进行精细搜索.

2.3 改进的自适应大邻域搜索算法

两级自适应大邻域搜索算法是在自适应大邻域搜索算法的机理上再加一组破坏与修复算子使其能解决两级问题，其中，通过第一级算子改变枢纽点至中心场站的分配方案，从而使得第一级的解改变，相似地，通过第二级算子改变非枢纽点的客户点至枢纽点的分配方案.为了保证每个枢纽点承担的中转工作尽量相当，在算子设计上，使每一级运输过程中每个主节点被分配的子节点数量尽量相当，这样才能确保每个枢纽点工作量差距不会太大，不会有废弃枢纽点的情况出现.

第一级算子设计逻辑有以下几种：

第二级算子设计如下：

本算法的时间复杂度与自适应大邻域搜索算法的运行过程极度相关，自适应大邻域搜索算法在迭代过程中会根据算子权重自主地选择算子，由于在该算法中包括破坏算子和修复算子，且每个算子都有不同的时间复杂度，故本算法的自身时间复杂度并不确定且处于一个区间中，因此本算法的时间复杂度并不稳定，且最坏情况为O(1952(3Ud+2Us)).

2.4 参与对比的启发式算法

2.4.1 基于聚类算法的贪婪程式 聚类算法常用于分类问题，一般地，同一簇中的任意个体与同簇个体具有较高的相似度，而不同簇中的个体往往有较大差异.本启发式的聚类算法以若干数据点为中心，将点集分为若干类，再根据中心点位置匹配距离较近的中心场站以提供配送服务.在贪婪程式中，将簇中距离中心场站以及簇中心位置最短的若干节点作为枢纽点并以此确定第一级运输中的节点分配方案，而第二级运输中的节点分配方案主要由K-means聚类的方法来控制，整个贪婪程式中蕴含了两层贪心法则，在节点簇地理位置分隔较为明显的案例下，该算法较为高效.

2.4.2 变邻域搜索算法 变邻域搜索算法是求解车辆路径问题的最有利算法之一，通过复现并设计对应本问题的算子以方便将双智能集成算法与之进行对比分析.

变邻域搜索算法的扰动算子设计如下：

(1)x′←ExchangeOneHub(x)：选择一个枢纽点将其与备选枢纽点中的剩余节点进行交换.

(2)x′←ChangeSequence1(x)：选择任意两个枢纽点进行次序变更.

(3)x′←ChangeSequence2(x)：变更任意车辆路径中服务的客户点先后次序.

(4)x′←AddOrDelete(x)：增加或删除从某个枢纽点出发的无人机路径.

变邻域搜索算法的邻域动作算子设计如下：

(1)x″←ChangeNodesSequence(x′)：选择一条第二级路径，将路径中相近的两个节点进行次序调换.

(2)x″←Remove&Insert(x′)：若子节点个数不少于1，去除任意子节点并将其插入其他路径中.

(3)x″←ExchangeNodes(x′)：选定两条不同路径，并选择两者中的任意节点进行交换.

(4)x″←WorstNodesRemove(x′)：选择任意第二级路径中相近的客户，去除其中任意一个并将其插入其他路径中.

(5)x″←WorstExchange(x′)：选择任意两条第二级路径，将各自距离枢纽点最远的节点进行交换.

3 实例验证

本研究求解的问题不同于常规的车辆路径规划问题，需要综合考虑枢纽点选址问题、客户点分配方案以及两级车辆的路径规划问题.选择车辆路径问题的经典数据集作为实验案例，对同一案例进行多次实验，主要进行了模型与算法求解的对比.通过将本文提出的算法与基于聚类算法的贪婪程式以及在路径优化问题领域较为成熟的变邻域搜索算法进行对比实验，证明算法的有效性.

3.1 实验环境和算法参数确定

实验环境如下：Intel i7-4720HQ 2.60 GHz CPU，8 GB内存，操作系统为Windows 7，编程环境为Python 3.7.

选择CVRPLIB中的P-n101-k4数据集进行第一组实验，增加中心场站位置数据，其余数据保持不变，数据集主要包含了3个中心场站、100个客户点的位置数据以及客户点的需求量数据，记录运行结果的最优值，考虑收敛速度和平均最优值.参数设置：初始温度50；温度冷却速率0.98；权重控制因子0.5.第二组实验的算例为P-n50-k4，其中包含3个中心场站和50个客户点，记录不同运行时间下的启发式算法运算结果与CPLEX求解数学模型的结果，并求出两者间的差距，证明算法应对中等及大规模算例的有效性.在第三组实验中，将本文提出的双智能集成算法与贪婪程式以及变邻域搜索算法进行对比实验.

3.2 实验结果与分析

将数据集P-n101-k4中各节点以及新增的中心场站进行编码，取不同枢纽点数量进行实验.在3组实验中取10个枢纽点的平均路程成本最小.在此情景下，第一级车辆使用数量与中心场站数量相同(本例中为3).最后，枢纽点数量的确定需要考量车辆成本、枢纽点设立费用等累加再比较总成本大小，使用本文算法求解算例所花费的时间较为稳定，在相同枢纽点数量下，5个样本在求解时间上的方差很小.同一算例下，枢纽点数量对成本的影响见表1.

表1 枢纽点数量对成本的影响

在完成枢纽点数量对整个两级物流系统的成本影响实验后，选取中等规模样本进行反复实验，将双智能集成算法与数学模型求解的结果进行对比.实验数据表明，双智能集成算法在有限时间内能普遍求得优于数学模型求解的结果，其在两级自适应算法外层还嵌套了模拟退火思想以控制整体迭代次数，外层框架中模拟退火初始温度的不同对最终结果产生影响，实验数据见表2.

表2 数学模型与双智能集成算法求解结果对比

在本实验中，将双智能集成算法中的算子在不同算例下的得分与权重记录下来，并分析修复与破坏算子的优劣，固定初始温度为50，且取枢纽点数量为6，算子顺序与前文介绍算子顺序一致.算子总得分结果表明，双智能集成算法中的算子得分均匀，并未出现使用次数极少或极多的算子.

而后，将前文提到的贪婪程式和变邻域搜索算法与本文的双智能集成算法进行对比分析，在该实验中，分别选取枢纽点数量为6、8、10进行实验，求解结果的对比见表3，实验编号为中心场站数量-客户点数量.

表3 贪婪程式、变邻域搜索算法与双智能集成算法求解结果对比

本实验表明，在P-n50-k4这个案例中取8个枢纽点较优.双智能集成算法与贪婪程式的平均差异为3.7%.此外双智能集成算法中的算子设计依附了实际的运用情景，例如在城市物流中每一个驿站的选址路径问题不仅涉及整体成本的多少，还应考虑单个枢纽点辐射客户点的数量、上级节点对其配送的难易等，因此在算子设计过程中需要尽量保持每一个枢纽点服务的下属节点均有一定量，也就是使得每个枢纽点的工作量差距不要太大.由此，双智能集成算法在实际场景具有一定的泛用性，对于不同规模的算例皆可直接进行计算并获取其解决方案.在与车辆路径问题中主流方法的对比中，双智能集成算法在多案例的求解结果中都略优于变邻域搜索算法，且在该次实验中，双智能集成算法的平均求解时间(24.92 s)略小于变邻域搜索算法的平均求解时间(26.54 s)，体现出该算法的高效性.此外，对于确定算例下枢纽点数量问题，也可通过改变选址数量的参数，运用双智能集成算法对比不同枢纽点数量的系统成本高低，给予决策者较大的便利，解决整体系统中枢纽点选择、节点分配及节点数量与系统最优性关系等问题.

在算例P-n50-k4中，实验表明选取8个枢纽点相较于选取6个或10个枢纽点都更优，贪婪程式也呈现出相类似的趋势，这也强有力地支持了本文算法的有效性以及对选址数量确定问题的求解效能.在算例p-n101-k4中，系统成本随枢纽点数量的增加而减少，清晰地呈现了选取枢纽点数量与系统成本的变化趋势.根据先前的实验经验，如果继续增加枢纽点，在某个阈值点，系统成本会不降反升.本研究中提到的算法不仅可以提供不同规模问题集的较优解决方案，还可以帮助决策者确定固定案例下枢纽点数量的较优选取数量与位置，功能集成化与泛用性是该算法的重要优势.

4 结 论

(1)本研究针对两级车辆路径与节点分配问题，提出了一种双智能集成算法，该算法能完整地求解节点分配与车辆路径这一系统问题，保证了问题求解的完整性.

(2)通过对自适应大邻域搜索算法中破坏、修复算子的设计，使得每一级运输下每一个主节点的工作量都相当，不会出现废弃枢纽点的情况，这样也比较符合该问题在现实中的应用.随着中国现代化进程的不断推进，人们对不同物资的需求越来越多，需求量的敏感性也越来越强，这势必带来物流网络的复杂化和多级物流网络的广泛应用，网络中不同层级的节点分配问题以及路径问题是该情景下的主要问题.

(3)运用双智能集成算法，决策者可以在较短时间内得到某个案例下选择不同枢纽点数量对整个物流系统的影响并提供决策方案.从实验结果来看，双智能集成算法在不同算例下都优于本研究中给出的贪婪程式、变邻域搜索算法，通过改变枢纽点数量生成多组实验数据得出枢纽点数量与总成本之间存在一定的效益悖反.