英语原文共 15 页

一种用于求解同时取货送货的车辆调度问题的混合离散粒子群算法

摘要

车辆路径问题(VRP)是许多运输物流配送系统中遇到的一个重要而著名的组合优化问题。根据所执行的任务和一些限制，VRP有几个变化型态，如时间窗、多辆车、回程、同时交付和提货等。本文研究了具有同时提货和配送的车辆路径问题。VRPSPD处理的是在对必须执行的操作的顺序没有优先级限制的情况下，求解集成货物分发和收集的最优方案。由于VRPSPD是一个NP-难问题，我们提出了一种基于粒子群优化(PSO)的启发式求解方法，该方法采用变邻域下降算法(VND)进行局部搜索。并采用退火策略来保持种群的多样性。一个对文献中已有的基准问题实例的实验验证了该算法的有效性。计算结果表明，该算法可与已有的启发式算法相媲美，并对已有的几种最优解进行了改进。

关键词：车辆调度问题 同时交货和提货 粒子群算法 变邻域深度搜索算法

介绍

在当今竞争激烈的环境下，企业为了更有效地优化和管理物流系统中的流程，显然应该做出战略和运营决策。最重要的运营决策之一是寻找最佳的车辆路线，因为它具有降低成本和提高服务质量的巨大潜力。经典车辆布线问题(VRP)可以定义为对于需要为一组客户提供服务的车辆车队的最佳路线集合的确定。自Dantzig和Ramser(1959)提出VRP以来，人们的注意力一直集中在现实生活中出现的更复杂的VRP变体上，如时间窗、多辆车和回程车。在Toth和Vigo(2002)中对经典的VRP及其变体、公式和求解方法进行了全面的综述。

VRP的一个变种是车辆路径问题与同时拾取和交付(VRPSPD)。在VRPSPD中，车辆不仅需要送货给客户，还需要在客户地点取货。VRPSPD的普遍假设是，所有交付的货物都必须来自仓库，所有的提货货物都必须运回仓库。当一辆汽车只拜访每一个客户一次，并且在客户处装货之前卸货时，必须同时满足交付和提货(Chen amp; Wu，2006)。

VRPSPD的定义如下：令为一个完整的有向网络，其中为顶点集，其中代表客户，“0”代表仓库。是弧的集合，每个弧和成本(距离)非负相关。库房内有容量为Q的相同车辆，车辆数量不受限制。在VRPSPD中，每个客户需要一个给定的数量来交付和提货。VRPSPD要求查找一组满足如下要求的路径：每条路线的起点和终点都在车场，每一位顾客都被一辆车准确地拜访一次；任何弧内的车辆总负载不超过车辆的能力，总路由成本最小化(Montane amp; Galvao，2006)。问题的关键在于，取货和送货活动应由同一辆车同时进行。因此，当针对该问题开发解决方案时，应该在其中加入一种机制，检查每个客户的车辆上的波动负载，以防止车辆超载。对于VRPSPD的数学公式，感兴趣的读者可以参考Ai和Kachitvichyanukul (2009a)、Dethloff(2001)、Nagy和Salhi(2005)以及Tang和Galvao(2006)的研究。VRPSDP与回程车辆路线问题(VRPBs)有关，在该问题中，所有交付到线路运输客户的货物必须在从回程客户取货之前完成。当允许以任意顺序送货或取货时，该问题称为混合取货和取货的车辆路径问题(VRPMPD)。VRPMPD可以看作是VRPSPD的一种特殊情况，因为当每个客户的交付或提货需求为0时，问题就会归结为VRPMPD。因此，已有的VRPSPD解决方案可以直接用于求解VRPMPD (Wassan，Wassan，amp; Nagy 2007；Wassan，Nagy，amp; Ahmadi 2008)。

VRPSPD在食品杂货连锁配送系统中的应用较为普遍。每家杂货店都可能有送货(如新鲜食品或软饮料)和提货(如过期物品或空瓶子)的需求，而且服务只需一站(Chen amp; Wu，2006)。逆向物流也是VRPSPD的另一个应用领域，因为企业对控制其产品的整个生命周期越来越感兴趣。例如，在一些国家，立法强制公司对其产品终身负责，特别是涉及环境问题(Dethloff，2001；Montane amp; Galvao，2006)。

VRPSPD是NP难问题(Salhi amp; Nagy，1999)，因为当只考虑送货或提货时，它可以被认为是VRP问题，即众所周知的NP难问题。因此，在Min(1989)引入VRPSPD之后，对这个问题的重新研究主要集中在启发式和元启发式方法上，这些方法可以在有限的计算时间内求得高质量的解(Berbeglia，Cordeau，Gribkovskaia，amp; Laporte 2007；Parragh，Doerner，amp; Hartl 2008)。

近年来，组合优化的研究重点已转向元启发式的结合。据推测以互补的方式结合不同启发式的特征可以产生更有鲁棒性和更有效的优化工具(Talbi，2002)。因此，以往的实验表明，混合算法的有效性和效率往往优于简单算法。将混合算法应用于各种VRPs的实例如下：Tan，Lee，Ou(2001)采用TS、模拟退火(SA)和遗传算法(GAs)的不同结合方法求解具有时间窗的VRP。Lee，Lee，Lin，and Ying(2010)通过结合蚁群优化(ACO)和SA求解限量供给的VRP。Reoussis，Tarantilis，Braysy，and Ioannou(2010)为开放式VRP提出了另一种基于进化策略和基于记忆的局部搜索的混合算法。

在本文中，我们的目的是提出一种有效的解决方案来处理VRPSPD。求解方法是粒子群优化(PSO)和变邻域下降(VND)的混合算法，这两种算法在文献中都是非常著名的元启发式算法。PSO的实现是为了在解空间中搜索高质量的解，VND的实现是为了改进PSO每次迭代中从总体中随机选取的解。同时采用退火策略来保持粒子群的多样性。设计一个基于粒子群算法的关键问题之一是粒子在求解表示中承载与问题域相关的必要信息。因此，将基于粒子群算法应用到VRPSPD中，最重要的问题是开发一种有效的问题映射和解决方案生成机制。因此，在h_PSO中我们使用没有分隔符置换编码即一个大型路径来表示问题的解。因此，我们将Prins(2004)提出的分离程序应用于限量供给的VRP，以从一个大型路径中获得一个可行的解。据我们所知，这是大型路径首次实现代表VRPSPD的解。进一步解决VRPSPD的困难在于检查负载的可行性，这是一个耗时的过程。因此，我们在VND实现的邻域结构中采用了一种恒时可行性检验方法。将提出的混合算法(h_PSO)与文献中已有的VRPSPD及其特例VRPMPD的求解方法进行了比较。计算结果表明，h_PSO效果不差于文献中已有的方法，并改进了一些已知的基准问题的解。

本文组织如下：第2节对VRPSPD及其特殊案例VRPMPD的研究进行综述。第3节包含了关于PSO和VND的简要信息，第4节给出了针对VRPSPD的启发式方法。第5节给出计算结果，结论仿放在第6节。

文献综述

近年来，由于VRP在实际应用和逆向物流中的重要作用，它越来越受到业内人士和研究人员的关注。该问题的变体有：带回程的VRP、提货和配送的VRP、同时提货和配送的VRP、带拨号的问题。本文简要回顾了近年来国内外对同时提货VRP及其特殊情况的研究，即混合提货VRP。因此，有关皮卡和配送VRP及其变体的更多信息，我们建议感兴趣的读者参阅Berbeglia等(2007)和Parragh等(2008)的综述论文。

Min(1989)在20年前提出了VRPSPD，用于解决现实生活中图书馆之间的图书运输问题。解决这一问题的办法包括下列各阶段：(1)客户首先以不超过每一辆车容量的方式分组；(2)每组分配一辆车；(3)每一分组的客户都作为一个单独的旅行商问题(TSP)求解。Dethloff(2001)提出了一种插入启发式算法，该算法根据三个标准：出行距离、剩余容量和距离仓库的距离，将客户插入到新兴路线中。这个方法不需要补充额外的例程。作者还考虑了VRPSPD与其他VRP变体之间的关系。Nagy和Salhi(2005)为单站和多站VRPSPD和VRPMPD开发了一种复合启发式方法。启发式算法以一种有序的方式结合了不同例程的功能。这些例程是VRP的例程的修改版本，比如2-Opt，3-Opt，转向，交换，扰动，还有一些专门为VRPSPD开发的方法比如实现路径反向的反向算法和允许访问客户两次，第一次送货，第二次拣货的算法。Gajpal和Abad(2010)提出了基于针对VRPSPD的Clark和Wright算法的节约里程法和并行方式的节约里程法。作者开发了一种累积网络拾取方法来分析合并两个现有路径的可行性。Dell #39;Amico等人(2006)提出了一种基于分支定价法的求解VRPSPD的精确算法。该方法采用两种不同的策略来解决定价子问题：(1)精确动态规划；(2)状态空间松弛技术。提出的精确算法可为多达40个实例找到最优解。

启发式方法在求解VRPSPD和VRPMPD中也得到了成功的应用。Crispim和Brandao(2005)是为VRPSPD提出一种元启发式方法的第一批作者。该方法是一种基于禁忌搜索和变邻域下降的混合算法。作者使用扫描法来获得初始解。如果初始解中的任意一条路径由于某些中间弧的过载而不可行，则通过交换该路径上的客户订单来确定该路径的可行性。改进阶段实现插入和交换代替原有路径。不可行的路径方案通过他们超载的层度添加惩罚函数。Ropke和Pisinger(2006)开发了一种大型邻域搜索(LNS)启发式算法来解决VRP的多种变体，包括VRPSPD。Chen和Wu(2006)还提出了一种将禁忌搜索算法和记录更新算法结合起来的混合方案。在该方案中，通过基于距离和负载的准则的插入方法得到初始可行解。在混合算法的改进阶段，应用了2交换、交换、转向、2-opt和Or-opt算法。Montane和Galvao(2006)提出了一种基于禁忌搜索算法的启发式方法，这个算法将转向、交换、交叉和2-opt作为邻域结构。作者还使用了一种弧频率惩罚方法，以提供分散搜索和集中搜索之间的平衡。Bianchessi and Righini(2007)提出了构造启发式算法和局部搜索启发式算法，并提出了一种使用可变邻域结构的禁忌搜索算法，该算法将基于节点交换的方法和基于弧交换的方法结合起来。Wassan等(2007)开发了一种具有如下邻域结构的响应式禁忌搜索算法：重新定位一个客户，在两条不同的路线之间交换两个客户，并交换路线方向(交换)。为了在分散搜索和集中搜索之间取得有效的平衡，作者提出了对禁忌列表大小的动态控制。Zachariadis、Tarantilis和Kiranoudis(2009)提出了另一种基于禁忌搜索算法和广义最小二乘法的混合算法。在混合算法中，利用基于成本节约的构造启发式算法得到初始解，并实现了搜索过程的分散。Gajpal和Abad(2009)提出了一种基于蚁群算法的启发式算法。这个启发式算法有两个步骤：(1)使用由最近邻域构造启发式获得的初始解初始化轨迹密度和参数；(2)使用轨迹密度为每只蚂蚁生成一个蚂蚁路径，然后在每一个路径中进行局部搜索，更新精英蚂蚁和轨迹密度。

Catay(2010)、Subramanian、Drummond、Bentes、Ochi和Farias(2010)、Zachariadis、Tarantilis和Kiranoudos(2010)、Zachariadis和Kiranoudos(2011)提出了基于元启发式的最新启发式方法。Zachariadis等人(2010)提出的启发式方法基于自适应记忆规划方法。该方法将高质量的VRPSPD的解存储自适应记忆中，并且定期提取其中的客户访问序列，形成新的初始解来优化搜索。同时，使用补充的记忆要素驱动算法利用存储在自适应内存中的各种路径信息，消除了精英策略的风险。该方法采用加权节约启发式方法生成初始解。Zachariadis和Kiranoudos(2011)提出了一种本地搜索方法，通过静态地将编码移动到特殊的数据结构中，可以有效地搜索复杂解邻域。这种方法通过使用基于禁忌搜索的期望标准的分散搜索来搜索解空间。作者也同样用加权节约启发式方法来生成初始解。Subramanian等人(2010)提出了一种嵌入多启动启发式算法的并行算法，该算法由集成在迭代局部搜索框架中的VND组成。该方法的主要特点是一些参数的自动标定，以及探索当前多核集群所固有的高水平并行性的能力。该方法运用一种贪婪插入策略来构造问题的初始解。Catay(2010)提出了另一种基于蚁群算法的启发式算法，实现了一种新的基于节约的可视函数和信息素更新规则。该方法采用最近邻域启发式算法生成基于初始化信息素的解，并利用局部搜索改进每只蚂蚁在算法的每次迭代中得到的解。局部搜索在路径的两段之间实现交换和插入。

从上述简短的综述中可以看出，群智能算法在解决VRPSPD方面做了一些尝试，而禁忌搜索算法被广泛用于解决这个问题。同时，文献中所有求解方法的两个主要性质如下：(1)使用启发式方法获得一个好的初始解或初始解的解集；(2)将元启发式方法与另一种方法进行混合，以改进搜索过程中寻找到的解。粒子群算法是近年来发展起来的一种新兴的进化元启发式算法，已成功地应用于求解各种VRPs问题。Ai和Kachitvichyanukul (2009a，2009b)，Chen，Yang，和Wu (2006)，Marinakis和Marinaki (2010)，和Marinakis，Marinaki，和Dounias(2010)对粒子群算法在VRP中的应用进行了研究。Ai和Kachitvichyanukul (2009a, 2009b)是第一批提出将粒子群算法应用于VRPSPD的学者。Ai和Kachitvichyanukul (2009a)的粒子群算法使用了一种实值编码结构，在路径构建过程中采用最简单的插入启发式和2-opt方法优化了问题的解。针对VRPSPD，提出了一种基于PSO和VND的求解方法。所提出的粒子群算法(h_PSO)与Ai和Kachitvichyanukul (2009a)的粒子群算法在粒子位置的定义、使用

资料编号：[3446]