多隔间车辆路径优化问题的局部搜索混合果蝇优化算法求解

吴剑来,刘加林

(湖南人文科技学院 商学院,湖南 娄底 417000)

现代物流业中,物流配送具有运输货物种类繁多和运输需求快速增长两个重要特点。 为提高运输效率和降低配送成本,配送系统必须对车辆行进路线进行规划和优化,尽可能减少车辆行进的路径长度。 这引发了针对车辆路径问题(Vehicle Routing Problem, VPR)的研究。 VRP 主要研究在确保车队从配送中心向客户运送货物的同时,尽可能减少车队所走的路径总长度,以最低运输成本满足客户需求。 在实际操作过程中,物流配送需要考虑车辆容量的限制,于是引发了对容量受限车辆的路径问题(Capacity Constraints VRP, CVRP)的研究。CVRP 假设每辆车都有一个恒定的容量Q,每辆车对每个客户只访问一次,并且任何一条路径需要运送的货物总量都不会超过车辆的总容量;每个客户需要运送的货物不同,运输中不同类型的货物存放在同一辆车的不同隔间中,每辆车都有固定数量的隔间,每个隔间都有容量限制。

在CVRP 研究的基础上,近年来业界逐渐关注具有容量约束的多隔间车辆路径问题(Multi-Compartment VRP, MCVRP)[1]。 MCVRP 研究的目的是在车辆存在多个隔间约束下,找到车队配送货物的最小总距离。 多隔间对运输不能混合在一起的货物是非常重要的。 例如,MCVRP 方式常用于食品配送,将冷藏食品和非冷藏食品储存在同一辆车的不同隔间。 Chajakis 和Guignard 探讨了两厢车的规划模型, 并讨论了车辆的配送路径[2]。MCVRP 也被应用于燃料运输,多种不同类型的燃料储存在不同容量的储罐中[3-4]。 为了获得更好的效果,MCVRP 经常通过本地搜索和启发式算法进行增强,如迭代局部搜索算法[5-6]、仿生优化算法中的蚁群算法[7-8]以及蚁群算法与插值方法[9]、禁忌搜索算法[10]和2-opt 方法[11]形成的融合算法。

综上可知,仿生优化算法已逐渐成为解决MCVRP 更好的选择。 相比于其他仿生优化算法,果蝇优化算法(Fruit-fly Optimization Algorithm,FOA)是一种新兴的进化算法,易于理解、操作和实现[11-15]。 然而,常规的FOA 容易陷入局部收敛,而且在搜索后期收敛速度特别慢。 为了解决这一缺陷,一些学者通过采用混沌理论等方法来改善FOA[16-17]。 尽管FOA 及其改善版本效果良好,但现有对FOA 的研究多集中在解决空间连续优化问题上,对离散优化问题(如组合优化问题)的研究则相对较少。

本文利用混合果蝇优化算法(Hybrid FOA,HFOA),并引入局部搜索策略,解决多隔间车辆路径优化问题。 受Reed 等人的启发,本文使用多重比较法将MCVRP 扩展到新的问题中。 本研究设定车队中的所有车辆都从配送中心出发将各种类型的货物运输到客户处,所有车辆的容量都是相同的,每辆车都可以访问特定的一组客户,每个客户只能被访问一次。 本文通过局部搜索来提高FOA的搜索能力,确定每辆车所访问的客户,以及访问的先后顺序,从而形成车辆路径。

一、MCVRP 问题的描述与分析

图1 给出了一个物流配送网络。 从图1 可以看出MCVRP 包含以下要素:配送中心(唯一的)、多隔间车辆(MCV)车队和多个需要配送的客户。每个客户的货物是不同的,每个货物的配送地点是已定的,每个车辆的隔间都有固定的容量。 每辆车离开配送中心、访问一些客户后,最后又返回配送中心,每个客户只能被访问一次。 在给定配送点之间的距离后,车辆路径问题就是要是优化每辆车的路径,使所有车辆的总行驶距离最短。

图1 MCV 网络示意图

二、利用局部搜索混合果蝇算法求解MCVRP 问题

类似于粒子群算法,FOA 同时考虑当前最优个体和个体状态更新过程中的最优个体。 通过这种方式,该算法确保果蝇最终聚集在全局最优解的周围,并同时继承了每一次迭代的局部最优。 在迭代的过程中,一旦一个个体到达了一个更好的全局最优位置,其他个体会聚集到该个体的周围。 这样的个体更新方式降低了种群的多样性,因为个体信息没有被共享和继承,增加了局部最优值和早熟的风险[18-19]。 Zheng 提出了混合果蝇优化算法(HFOA)[20],该算法的每次进化分为4 个阶段:嗅觉搜索、视觉搜索、合作进化和退火。 HFOA 通过以下步骤实现。

步骤1:创建初始解并初始化路径强度。

步骤2:重复以下操作,直到达到终止条件。

步骤2.1:为每只果蝇创建路径。

步骤2.2:进行局部搜索,以改善每只果蝇生成的解。

步骤2.3:更新最优解。

11月16日，云南电网公司解除了金沙江白格堰塞湖泄洪自然灾害Ⅱ级响应，转入灾后重建阶段。自11月14日金沙江白格堰塞湖溃泄进入云南，两天来，一路气势汹汹，迪庆、丽江遭受重创，丽江更是遭遇了有水文记录以来的最大洪灾，沿江两岸数万名群众紧急转移安置。

步骤2.4:根据最优解更新所有边的路径强度。

步骤3:终止算法并记录最佳解决方案。

可以看出,HFOA 算法本质是利用果蝇的觅食原理来构建MCVRP 的路径解。 在建立路径的每次迭代中每只果蝇轮流进行5 项基本活动。 第一,果蝇基于路径吸引概率选择下一个客户,该概率由味觉强度和路径强度组成。 第二,果蝇访问当前路径的客户禁忌列表。 第三,果蝇更新车辆隔间的剩余容量。 第四,果蝇更新已访问的路径强度,其中,果蝇将采取局部搜索的方法来提高解的质量。 第五,删除禁忌列表,并标记下一次迭代开始。

基于上述算法流程,利用局部搜索HFOA 求解MCVRP 问题的4 个主要环节设计如下。

(一)初始化

HFOA 首先生成初始解,并初始化每个解的路径强度。 初始解分两步生成。 首先,根据网络的拓扑结构随机生成客户;其次,如果车辆容量足以满足客户需求,将客户随机添加到车辆的行进路径中,否则车辆会在接近下一个客户之前返回配送中心。

(二)路径创建

假设HFOA 中的每一只果蝇都生成一条完整的路径(完整的MCVRP 解)。 为了实现解的多样化,每只果蝇应该在离开配送中心后随机选择第一个客户。 接下来,每只果蝇都应该基于路径的吸引概率转移到下一个客户。 味觉强度是当前位置到果蝇起点之间距离的倒数。 因此,果蝇倾向选择离出发地更近的客户以实现最小化路径长度。

根据以上的论述,标号为ij的边的吸引力包括两部分:路径强度τij(取该条边在迭代过程中被访问的频率)和味觉强度μij(即边长的倒数)。 味觉强度也代表果蝇从i移动到j的趋势。 因此,路径吸引力可以表示为:

其中,α和β分别是路径强度指数和味觉强度指数。 客户i在客户j之后被果蝇访问的概率记为Pij:

其中,Ni是当前车辆尚未访问的所有客户,其总需求不超过车辆容量。 根据式(10),下一个客户的选择概率与边ij的吸引力成比例。

每只果蝇都根据上述规则继续增加客户,直到没有客户剩余。 然后,果蝇回到配送中心,并启动新路径。 根据式(10)果蝇选择新路径上的第一个客户,必须是配送中心的相邻顶点。

(三)局部搜索

果蝇每次旅行本质上可表征为数学领域的旅行商问题(Traveling Salesman Problem, TSP),旨在在确保每条路径的总需求不超过容量限制的前提下,尽可能缩短旅行距离。 在创建所有路径后,为提高解的质量,需要进行局部搜索,局部搜索包括2-opt、交换和插入。

2-opt:在路径上选两个点将路径分为三个部分,将中间线段反向。 将所有线段连接起来进行重建。 假设i和j是一条路径上的两个不相邻的客户,i+和j+是路径中的下一个相邻顶点。 2-opt 表示删除边(i,i+)和(j,j+),添加边(i,j)和(i+,j+),这样可以得到一条新的道路。

交换:当前路径上的客户i和j的位置被交换以生成新的一组路径。 交换后客户i和j可能会也可能不会落在同一条路径上。

插入:客户i从p1位置移动到位置p2以通过当前路径生成一组新的可行路径。p1和p2可能会也可能不会落在同一条路径上。

通过上述局部搜索操作,可获得所有可行解,并从中选择最短路径。

(四)路径强度更新

该步骤基于在局部搜索过程中得到的最优解进行路径更新。 为了模拟实际情况,假设路径强度随着时间的推移而衰减。 路径强度分两步更新。首先,路经的强度都因时间的推移而衰减;其次,增加最佳路径的强度,以驱使果蝇走最短路径。 设为路径持久性系数,满足0≤ρ＜1,1-ρ为在迭代过程中的路径强度衰减比,则边ij的强度可以通过下式进行更新:

其中,Lbest是每次迭代中最佳路径的总长度,路径强度与ρ的乘积是衰减后路径的剩余强度。

三、求解结果与分析

本节首先利用基准问题对HFOA 方法的算法优势进行验证,为后续应用验证提供技术准备;然后对HFOA 方法处理MCVRP 问题的有效性与优越性进行验证。

(一)算法优势验证

为了验证HFOA 方法的有效性和优势,利用Laporte[21]提出的7 个基准问题展开研究,将HFOA算法与混合AC 算法(HAC)[22]进行了对比,并将问 题 记 为 VRPNC1—VRPNC7。 VRPNC1—VRPNC5 中的客户服从随机均匀分布,而VRPNC6—VRPNC7 中的客户服从聚集分布。 这些问题共涉及50—199 名客户。

假设每辆车有2 个隔间,其容量比为1∶3,即如果车辆容量为Q,那么两个车厢的容量分别为0.25Q和0.75Q。 HFOA 中的果蝇数量记为m,该数值直接关系到最佳路径质量和计算时间,经过反复测试,被设置为20。 其他参数如下:α=1,β=2,ρ=0.9,q0=0.9,实验进行100 次迭代。

对HAC 和HFOA 进行对比仿真的结果见表1。 从表1 中可以看出,采用HAC 和HFOA 算法,得到的平均总路径长度为分别为986.99 和985.60,采用HAC 算法得到的平均总路径长度改善了6.36%,而采用HFOA 算法得到的平均总路径长度改善了6.49%,且HFOA 总路径长度的改善率随着客户数量的增加提高得更快,改善率从50 个客户的3.21%提高到199 个客户的9.21%。这表明当问题越复杂时,HFOA 比HAC 效果更好。进一步计算分析可知,在解决大规模的路径问题上,HFOA 的总路径长度逐渐变短,从572.69 收敛到551.27,能够解决大规模问题,而且相对于HAC,HFOA 具有更高的改善程度,这主要归因于其强大的局部搜索能力。

表1 HFOA 算法与HAC 算法对比

进一步,为了说明HFOA 解决多隔间车辆(Multi-Compartment Vehicle, MCV)问题的优势,本文使用两种模式解决基准问题。 第一种模式使用容量为Q的单隔间车辆(Single-Compartment Vehicle,SCV),而第二种模式采用拥有2 个隔间的车辆,2 个隔间的容量分别为Q1和Q2;两辆车的总容量相同,即Q=Q1+Q2。 要交付给客户的货物有两种不同类型,分别表示为1 和2,这两种货物必须分开存储,可以通过不同的路径访问客户两次以运输货物1 和2。 在这种情况下,车辆路径问题(VRP)可分解为两个子问题分别求解,将它们的最短路径相加得到结果。 7 个基准问题运用两种模式解决的结果如表2 所示。 从表2 可以看出,当只有1 个隔间时,车辆行驶的总路径长度显著增加,这是因为为了运输某个客户不同类型的货物,同一位客户需要被拜访两次,重复访问增加了总旅行距离。 在第二种模式中,车辆可以在每条路径上为更多的客户提供服务,从而减少总行程长度。MCV 的优势体现在两隔间车辆的总行程比单隔间 车辆的总行程平均缩短49.26%。

表2 两种模式下车辆路径长度对比

(二)MCVRP 问题的应用有效性验证

将HFOA 应用于前文所提出的MCVRP 问题求解,同时为了测试HFOA 的局部搜索效果,运用局部搜索操作的不同组合来解决MCVRP,并将结果与没有局部搜索的FOA 所得到的结果进行比较。 第一种组合是FOA 与2-opt 结合,第二种组合是FOA 与2-opt 和交换相结合,第三种组合是FOA与2-opt、交换和插入相结合。 每种组合都进行不同数量的迭代次数,以保证计算时间相等。 根据表3 中的结果,混合局部搜索操作可以缩短MCVRP的最佳路径长度。 第一种组合使解的质量提高了11.86%,但2-opt 操作的效果还不够好,因为它只适用于一次旅行操作;在第二种组合中,解的质量改善率从11.86%增加到13.04%,表明交换操作可以将客户转移到两条路径;第三种组合将解的质量从13.04%提高到17.16%,这证明了混合局部搜索对解的质量有积极影响。

表3 不同结合方式的改善率

四、结论

本文采取基于局部搜索的果蝇优化算法来解决物流配送中具有容量约束的车辆路径优化问题。其中,局部搜索操作是解决组合优化问题的基础,本文将三种局部搜索方法与常规的FOA 相结合,形成混合优化算法来处理MCVRP。 通过7 个基准问题验证了该算法的效果。 数值实验表明,HFOA算法提高了解的质量,尤其是在大规模问题上。 研究证明了将局部搜索与FOA 算法相结合的必要性,并分析了FOA 算法的优点。 通过仿真将所提出的算法有效性和稳定性与其他算法进行比较可知,HFOA 算法的整体性能较好。