1.2 国内外研究现状

自从Dantzig和Ramser（1959）首次提出并定义了车辆路径问题，此问题就一直是研究的热点。Campbell等（2002）、Moin和Salhi（2007）、Bertazzi等（2008）以及Liu等（2011）分别对VRP的研究成果进行了总结与归纳。孙丽君等（2006）总结了有关VRP的模型及算法研究。当前文献中与本课题相关的3个问题分别是供需匹配关系未知的取送货车辆路径问题、分批次取送货车辆路径问题、允许多次访问的取送货车辆路径问题。故本章接下来对这3个相关问题已取得的研究成果进行归纳与总结。

1.2.1 供需匹配关系未知的取送货车辆路径问题研究现状

当前文献关于供需匹配关系事先已知的取送货问题的研究较多（Toth and Vigo，2002；Lin et al.，2011；Pandelis et al.，2013；Parragh and Schmid，2013；Simonin and Sullivan，2014；Masmoudi et al.，2016）。在此类问题中，网络中各客户点之间的供需匹配关系事先已确定，即任意两点之间需转运的产品类型及数量已确定。相对此类问题，供需匹配关系事先未知的取送货车辆路径问题为节约运输成本提供了机遇，因为后者相对前者松弛了网络中各客户点之间已固定的供需匹配关系，使网络中各客户点之间的供需匹配关系变成一项决策，因此可以通过寻找更好的供需匹配关系来获得更好的运输方案，进而降低运输成本。最近几年，供需匹配关系未知的取送货车辆路径问题吸引了许多学者的目光（Battara et al.，2014），接下来将对文献中关于此类问题的研究进行分类与归纳。

1.2.1.1 单车运输情况下供需匹配关系未知的取送货车辆路径问题

单车运输情况下的供需匹配关系未知的取送货车辆路径问题在当前文献中被称作“取送货旅行商问题”（Pickup and Delivery Traveling Salesman Problem，PDTSP），以运输网络中产品类型数目划分以下两种情况讨论。

（1）单产品

单产品取送货旅行商问题（1-PDTSP）是对经典旅行商问题（TSP）的扩展，Hernández-Pérez和Salazar-Gonzalez（2004a）引进了此问题。在此问题中，所有的客户点根据需求类型不同（送货需求或取货需求）被划分为两个不同的团体。每个有送货需求的客户点通常需要一定数量的产品，每个有取货需求的客户点通常可以供应一定数量的产品，且每个有取货需求的客户点均可以向任何一个有送货需求的客户点提供任何数量的产品。目标是如何设计一个运输成本最小的产品调运方案，在满足车容量约束条件的前提下，通过访问每个客户点一次性满足所有客户点的需求。此问题普遍存在于多个现实行业中，如在银行系统中，对各个支行之间的现金存量重新分配（Hernández-Pérez and Salazar-Gonzalez，2004a）；在共享单车系统中，对各站点之间自行车库存重新布局（Chemla et al.，2013）。针对该问题，Hernández-Pérez和Salazar-Gonzalez（2004a）建立了0～1整数线性规划模型，并提出了一个分支切割算法来求解该问题；Salazar-Gonzalez（2004b）提出了两个启发式算法：一个是基于提高k-optimality的贪婪算法，另一个是基于分支切割进程的局部最优算法；Hernández-Pérez和Salazar-Gonzalez（2007）改进了有能力约束的车辆路径问题（CVRP）的有效不等式，并提出了一些新的有效不等式和一个分支切割算法。实验结果表明，提出的算法如果使用新的有效不等式就能够求解100个客户点的算例，否则只能够求解50个客户点的算例；Hernández-Pérez等（2009）提出了一个贪婪式随机自适应搜索（Greedy Randomized Adaptive Searching，GRASP）和变量领域下降法（Variable Neighborhood Descent，VND）的混合算法，并把计算结果与Hernández-Pérez和Salazar-Gonzalez（2004b）的结果做比较，对比结果表明Hernández-Pérez等（2009）提出的算法具有明显的优势；Zhao等（2009）提出了一个遗传算法，该算法能够对500个客户点的算例求得最优解；Mladenović等（2012）提出了一个变邻域搜索算法，该算法能够对文献中客户点数为200～500的标准算例提供更好的解；Chemla等（2013）提出了一个嵌入禁忌搜索的分支切割算法来改善问题的上界；Ho和Szeto（2014）提出了一个迭代的禁忌搜索算法；Vogel等（2014）提出了一个嵌入大邻域搜索的元启发式算法；Kadri等（2016）提出了一个分支定界算法。Erdogğan等（2015）、Salazar-Gonzalez和Santos-Hernández（2015）探索了允许多次访问每个客户点的情况，其中Salazar-Gonzalez和Santos-Hernández（2015）只研究了允许每个客户点最多被访问2次和3次的情况。

（2）多产品

Hernández-Pérez和Salazar-Gonzalez（2014）引进了多产品取送货旅行商问题（m-PDTSP）。在该问题中，运输网络中有多种产品，任何一种产品的供应客户点都可以向任何需求该种产品的客户点供应任何数量的产品。他们提出了一个混合整数线性规划模型，讨论了经典的分解技术，提出了一些有效不等式及一系列分离算法来提高线性松弛规划模型的性能。实验结果表明提出的分支切割算法能够求解30个客户点，3种产品的算例。紧接着，Hernández-Pérez等（2016）针对此问题提出了一个三阶段的混合启发式算法，并基于随机产生的算例检验了此算法的性能。Li等（2016）基于共享单车系统，对多种类型的自行车重新布局问题提出了混合遗传算法，实验结果表明，此算法在较短时间内能够对所研究的问题提供高质量的解。

1.2.1.2 多车运输情况下供需匹配关系未知的取送货车辆路径问题

多车运输情况下的供需匹配关系未知的取送货车辆路径问题在当前文献中被称作“取送货车辆路径问题”（Pickup and Delivery Vehicle Routing Problem，PDVRP）。相对于PDTSP，文献中关于PDVRP的研究较少，同样分为以下两种情况讨论：

（1）单产品

Shi等（2009）首次引进单产品取送货车辆路径问题（1-PDVRP）。自Raviv等（2013）通过探索共享单车系统的自行车重新布局问题（Bike Rebalancing Problem，BRP），研究了1-PDVRP以来，针对此问题的相关研究逐渐增多。Rainer-Harbach等（2013）针对此问题提出了一个变邻域搜索算法，并基于现实的算例做了一系列实验分析。Dell' Amico等（2014）提出了4个不同的混合整数规划模型和一系列标准算例。Angeloudis等（2014）提出了一个被称作“重新构建匹配关系”（repair）的算法。Forma等（2015）提出了一个三阶段启发式算法。Dell' Amico等（2016）提出了一个被称作“破坏后重新构建匹配关系”（destroy and repair）的元启发式算法，该算法能够对文献中的算例求出更好的解。Di和Urli（2016）建立了一个新颖的模型，实验结果表明提出的分支定界精确算法和大邻域搜索启发式算法均优于当前文献中的算法。

（2）多产品

Chen等（2014）通过考虑单次访问和无限供应（每个供应客户点的产品供应量无限大）引进了多产品取送货车辆路径问题（m-PDVRP）。提出的变邻域搜索算法在1800秒内能够对研究的问题提供高质量的解。本书研究的问题是对Chen等（2014）的多次访问和有限供应的扩展，这些扩展使本书研究的问题虽更复杂但更接近现实。

1.2.2 分批次取送货车辆路径问题研究现状

基于企业实际需求，取送货车辆路径问题一直受到广泛关注（Dumas et al.，1991；Røpke et al.，2006；Røpke and Cordeau，2009；Pelikán and Fábry，2012；Yu and Liu，2014；Wang et al.，2015；Kalayci and Kaya，2016）。众所周知，允许分批次送货和允许分批次取货为企业节省运输成本提供了可能。接下来将依次总结文献中关于分批次送货车辆路径问题、分批次取货车辆路径问题及分批次取送货车辆路径问题的研究现状。

1.2.2.1 分批次送货车辆路径问题

分批次送货车辆路径问题（Split Delivery Vehicle Routing Problem，SDVRP）是指允许客户点的需求通过多次投放来满足，相对经典VRP为降低运输成本和节约运输车辆提供了机遇。Dror和Trudeau（1989）首先提出了可分批次送货车辆路径问题，即在经典VRP的基础上，允许每个客户点的需求分批次满足。他们提出了两阶段搜索的启发式算法。实验结果表明，允许需求分批次满足，相对需求一次性满足的情况节约了近14%的运输成本，且只需要较少的车辆来完成运输任务。紧接着，Dror等（1990，1994），Frizzell和Griffin（1992），Sierksma和Tijssen（1998），Belenguer等（2000），Archetti等（2006a，2008，2014），Chen等（2007），Jin等（2007，2008），谭家美和徐瑞华（2008），Derigs等（2009），孟凡超等（2010），Archetti和Speranza（2012），Wilck IV和Cavalier（2012a，2012b），Silva等（2015）对此问题分别做了相关研究。其中，Dror等（1990）提出了混合整数线性规划模型，验证了SDVRP是一个NP-难题，且只要运输距离满足三角不等式原则，被分批次满足的客户点就不可能出现在最优解的不同路线中。Frizzell和Griffin（1992）提出了三种构建式启发算法。Dror等（1994）提出了几类新的有效约束，并通过实验验证了选择合适的约束组合可以获得更紧的上下界。Sierksma和Tijssen（1998）提出了一个基于列生成（column generation）的启发式算法。Belenguer等（2000）提出了新的建模方法并对此问题的解空间进行了探索。Archetti等（2006a）首次提出了客户点分批次送货的定义与概念，即服务一个客户点的实际车辆数多于服务该客户点所需的最小车辆数。如车辆的容积为1个单位，针对需求量为3.6个单位的客户点，如果使用5辆车或更多的车来满足该客户点的需求，那么此客户点被称作“分批送货”。Chen等（2007）首先对当前阶段SDVRP的应用背景、模型和求解算法等相关研究进行了总结，然后通过结合整数规划和禁忌搜索提出了一个新的启发式算法。Archetti等（2008）通过一系列实验验证了当网络中客户点之间的需求量差别较小且平均需求量刚刚超过车容量的一半时，分批次送货节约的运输成本最大。Jin等（2007）提出了一个基于有效不等式的两阶段算法，实验结果表明该算法优于文献中已有的精确算法。Jin等（2008）提出了一个列生成算法。谭家美和徐瑞华（2008）基于蚁群算法原理设计了相应的优化算法。Derigs等（2009）提出了基于局部搜索的元启发式算法。孟凡超等（2010）提出了禁忌搜索算法，通过数值实验同样得出允许客户点需求分批满足可以减少运输成本、减少所需车辆数和提高车辆装载率的结论。Archetti和Speranza（2012）回顾了SDVRP的数学模型、主要特性、求解算法研究，并对文献中SDVRP的衍生问题进行了总结。Wilck IV和Cavalier（2012b）提出了一个构建式启发算法，并基于32个标准算例与文献中列生成方法和两阶段方法做比较，实验结果表明提出的构建式启发算法优于这两个方法，且能够为其他启发算法或精确算法提供较好的初始可行解。Wilck IV和Cavalier（2012b）提出了一个混合遗传算法。Archetti等（2014）基于两个松弛模型提出了两个精确算法，并针对4类标准算例做了实验，实验结果表明提出的方法能够对17个新算例求得最优解。Silva等（2015）通过考虑波动机制提出了反复迭代的局部搜索算法。该算法能够改善文献中324个标准算例中243个算例的解质量。解的质量最大提高了2.81%，平均提高了1.15%。随着对SDVRP研究的相继深入，目前出现了如下几个SDVRP的变种：

（1）考虑时间窗约束的SDVRP（SDVRPTW）

Frizzell和Griffin（1995）通过考虑客户点的送货时间要求，引进了SDVRPTW，并首先提出了一个构建式启发式算法来获得初始解，然后提出了两个启发算法来改善初始解的质量。接下来，Mullaseril等（1997）提出了构建式启发算法；Ho和Haugland（2004）用100个客户点的算例来检验提出的禁忌搜索算法的效果；Gendreau等（2006）提出了分支定界（branch and bound）算法；Desaulniers（2010）、Salani和Vacca（2011）提出了分支定价切割（branch price and cut）算法。Archetti等（2011）采用禁忌搜索算法求解子问题，提出有效不等式，引进新的分离算法进而设计了更强的分支定价切割算法；Yan等（2015）提出了两阶段求解算法，并通过求解现实问题验证了所提出算法的有效性。McNabb等（2015）检验了局部搜索对问题求解的影响。

（2）考虑最少投货量约束的SDVRP（SDVRP-MDA）

Gulczynski等（2010）通过考虑最低投货量约束研究了SDVRP-MDA。他们基于文献中标准的VRP和SDVRP算例来验证提出的启发式算法的效果。针对此问题，Han和Chu（2016）提出了基于多个初始解的变邻域搜索方法，并基于文献中32个标准算例和4个不同标准的最低取货量做了一系列测试，测试结果表明提出的算法能够对128个算例中43个算例求得更好的解。

（3）考虑多车场的SDVRP（MDVRP）

Gulczynski等（2011）引入了多车场情况下的分批次送货车辆路径问题（Multi-Depot SDVRP，MDVRP），并提出了基于整数规划的启发式算法来求解该问题。此外，他们还分析了在相同车场允许分批次送货和不同车场允许分批次送货减少的运输成本情况。针对此问题，Ray等（2014）研究了一个更有效的模型和算法；Wang等（2016）研究了每个客户点都有特定服务时间限制的情况，并设计了相应的启发式算法。该算法除了能够对文献中37个标准算例求得当前最好解外，还能够对其他21个新算例求得近似最优解。

（4）考虑多商品的SDVRP（MCSDVRP）

据我们所知，只有Archetti等（2015）与Moshref-Javadi和Lee（2016）研究了多商品分批次送货车辆路径问题（Multi-commodity Vehicle Routing Problem with Split Delivery，MCSDVRP）。其中，Archetti等（2015）在研究分批次送货时考虑了商品类型限制，即限制只有当客户需求多种不同商品时才允许分批送货，同种商品不允许分批送货。测试结果表明提出的分支定价切割算法在两小时内能够求解40个客户点，3种商品的算例。Moshref-Javadi和Lee（2016）相对于Archetti等（2015）松弛了商品类型限制，提出了两个混合整数规划模型，并通过改进文献中模拟退火和变邻域搜索算法设计了相应的启发式算法。

1.2.2.2 分批次取货车辆路径问题

在分批次送货研究的基础上，Lee等（2006）研究了一个分批次取货车辆路径问题（Vehicle Routing Problem with Split Pick-ups，VRPSP）。在该问题中，网络中有许多客户点和唯一的车场（depot），每个客户点都向车场供应一定数量的产品，每个客户点所供应的产品都允许分批次取货，目标是如何安排成本最低的运输方案使所有客户点供应的产品都运送到车场。Nowak等（2008）分析并验证了允许分批次取货能够为取送货车辆路径问题节省运输成本和运输车辆。另外，通过数值实验验证了分批次取货带来的利益大小与取货数量、取货点和送货点之间的运输成本，以及在同一客户点取送货的频繁程度密切相关。紧接着，Nowak等（2009）基于现实中的算例，探索了允许分批次取货带来的利益大小与客户平均取货量、取货点相对送货点的数量、取货点和送货点的聚集程度的关系。实验结果表明，当客户点的平均取货量恰好超过车容量的一半时，允许分批次取货带来的利益最大。Nowak等（2012）研究了带优先顺序约束的VRPSP，即在访问任何送货点之前都必须访问所有的取货点。Lai等（2015）基于集装箱运输研究了一个类似的问题。Flisberg等（2009）基于卡车在森林伐木操作的优化路径需求研究了此类问题。Korsvik等（2011）和Andersson等（2011）在海上运输系统中对现货分批次运输做了研究。Mar-Ortiz等（2013）以搜集浪费的电子设备（Waste of Electric and Electronic Equipment，WEEE）为背景对此问题做了研究。Oncan等（2011）研究了一个一对一取送货的VRPSP，并提出了一个分支切割（branch and cut）算法。Sahin等（2013）进一步针对Oncan等（2011）研究的问题提出了一个禁忌搜索和模拟退火的混合启发式算法。Wang等（2013）研究了一个带时间窗约束的VRPSP，并提出了线性规划模型和混合启发式算法。

1.2.2.3 分批次取送货车辆路径问题

当前文献关于分批次取送货车辆路径问题（Vehicle Routing Problem with Split Deliveries and Pickups，VRPSDP）的研究相对较少，Mitra（2005）通过探索一个回程车辆路径问题（Vehicle Routing Problem with Backhauling，VRPB）研究了此问题。在VRPB中，需要用一系列车辆把一些产品从车场运送到各个客户点，再把各个客户点中剩余的产品运送到车场，每个客户点的取货和送货请求允许分批次满足。显然，此问题属于VRPSDP。针对此问题，Mitra（2005）首先提出了混合整数线性规划模型和路径构建式启发算法；Mitra（2008）进一步提出了一个并行集群技术（parallel clustering technique）来构建路径；杨亚璪等（2010）设计了一个三阶段启发式算法；王科峰等（2011）通过实例验证了允许分批次取送货车辆路径问题和不允许分批次取送货车辆路径问题在最优解的结构和性质上存在的差异。Hennig等（2012）基于原油运输背景研究了此问题，并提出了列生成算法。Izuno等（2012）、Asefeh和Reza（2012）、Wang等（2014）针对此问题提出了包含初始解算法和混合算法的两阶段启发式算法。杨鹏等（2015）、Nagy等（2015）为更好地理解此问题，对该问题的精确求解算法和启发式求解算法进行了深度分析。Pelikan（2015）为此问题提供了新的数学模型并证明了此问题是NP-难题。

1.2.3 允许多次访问的取送货车辆路径问题研究现状

从车辆路径的角度来看，导致本研究涉及的问题高度复杂的主要原因是考虑了“多次访问”。由于“多次访问”给车辆路径规划带来了很大挑战，因此在取送货车辆路径问题的相关领域中，考虑“多次访问”的研究相对较少。通过查阅相关文献可知，考虑“多次访问”的取送货车辆路径问题的研究几乎都集中在海上路径规划问题（Maritime Routing and Scheduling Problem，MRSP）。Mckay和Hartley（1974）受美国军方的邀请研究了如何优化国防燃料供应中心向分布在不同地区的军队运输石油问题，进而提出了海上路径规划问题。此问题也受到许多学者的关注，如Miller（1987）、Dror和Ball（1987）、Bausch等（1991）。接下来将对文献中允许多次访问的取送货车辆路径问题的研究进行分类与总结。

1.2.3.1 允许多次访问带库存约束的取送货车辆路径问题

针对海上路径规划问题，考虑库存约束的研究较多，此类问题在文献中被称作“海上库存路径问题”。接下来分以下两种情况讨论：

（1）单产品

Christiansen和Nygreen（1998a）研究了单产品的海上库存路径问题，在此运输网络中，有些港口生产氨，有些港口消耗氨，生产和消耗速率恒定。在每个港口的取货或送货操作都必须在特定时间内进行，每个生产港口都可以向任何其他消耗港口提供任何数量的氨，每个港口在计划周期内都允许被相同或不同船只访问多次，目标是设计一个总成本最低的运输方案，使得各港口的需求得到满足。他们针对此问题提出了一个数学规划模型和一个嵌入分支定界的列生成方法。紧接着，Christiansen和Nygreen（1998b）提出了一个路线流模型。Christiansen（1999）研究了类似的问题，不同处在于限制每个港口最大被访问次数和非同质的运输船只，并提出了一个弧流模型。Song和Furman（2010）通过考虑日常变化的生产速率和消耗速率扩展了Christiansen（1999）的研究成果。Engineer等（2012）通过考虑船只的停靠时间、生产速率随时间变化、消耗速率随时间变化、库容随时间变化等，研究了一个更普遍的单产品海上库存路径问题。Agra等（2013a）探索了两个离散时间模型。Papageorgiou等（2014）对文献中单产品海上库存路径问题的研究进行了回顾。Jiang和Grossmann（2015）提出了几个可替代的混合整数线性规划模型。Mirzaei和Seifi（2015）研究了综合考虑运输成本、库存成本及滞销成本的情况，他们提出的模型能够精确求解小规模问题，提出的元启发式算法对大规模问题能够提供较好的解。

（2）多产品

Al-Khayyal和Hwang（2007）以液态气体运输为背景，引入了多产品的海上库存路径问题：通过把每艘轮船隔成多个不同的舱来运输不同的产品；考虑同质的船只，允许每个港口被相同或不同的轮船访问多次。目标是在计划周期内设计一个总运输成本和装卸成本最低的路径规划方案。他们先建立了一个混合整数非线性规划模型，然后提出了一个等价的混合整数线性规划模型。由于研究的问题很复杂，他们并没有设计求解算法，只是借助优化软件CPLEX用小规模算例来验证问题求解难度随“访问次数”的增加而呈指数增长。针对同样的问题，Siswanto等（2011）研究了不隔舱的情况。针对水泥工业中存在的类似问题，Christiansen等（2011）提出了一个嵌入构建式启发的遗传算法。Agra等（2013b）探索了一个近海原油分配问题并提出了几个混合整数规划模型。Agra等（2014）针对Agra等（2013b）的问题提出了一个混合启发式算法。Agra等（2015）通过考虑随机航行和停靠时间进一步扩展了Agra等（2013b）的研究工作。Hemmati等（2016）同样基于近海运输研究了类似的问题，提出了一个两阶段的混合启发式算法，并基于小规模算例，把此混合算法与文献中的精确算法做了比较。

1.2.3.2 允许多次访问不带库存约束的取送货车辆路径问题

Hennig等（2012a）研究了原油运输路径规划问题，该问题可以被看作允许多次访问不带库存约束的取送货车辆路径问题。它虽然与海上库存路径问题类似，但不同处在于此问题研究运输时不考虑生产，不考虑库存约束。因此在该问题中，网络中每个港口针对每种产品的供应信息和需求信息确定。他们的研究以原油提炼行业为背景，网络中各个港口生产不同规格的原油，一些港口只供应一种规格的原油，另一些港口可以供应多种规格的原油。在每个港口取货或送货需在特定的时间窗内进行。他们建立了此问题的线性规划模型，并提出了路径生成算法来求解小规模问题。紧接着，Hennig等（2012b）针对此问题提出了嵌套的列生成算法来求解更大规模的问题。Hennig等（2015）比较了两个可替代的路线流模型。Siddiqui和Verma（2015）研究了每个港口有多个时间窗约束的情况，并提出了复合粒子群算法。实验结果表明，此算法优于简单的粒子群算法和遗传算法。针对类似问题，De等（2015）建立了一个鲁棒性较好的数学模型并提出了一个分支定界算法。De等（2016）探索了以操作成本和运输风险成本为双目标的情况，并提出了复合粒子群算法。

1.2.4 取送货车辆路径问题求解算法研究现状

1.2.4.1 分批次取送货车辆路径问题求解算法

（1）启发式算法

针对分批次送货车辆路径问题（SDVRP），Dror和Trudeau（1989）、Yan等（2015）提出了两阶段启发式算法；Frizzell和Griffin（1992，1995）、Mullaseril等（1997）、Wilck IV和Cavalier（2012a）提出了构建式启发算法；Sierksma和Tijssen（1998）提出了一个基于列生成的启发式算法；Chen等（2007）、Ho和Haugland（2004）以及孟凡超等（2010）提出了禁忌搜索算法；谭家美和徐瑞华（2008）基于蚁群算法思想设计了启发式算法；Gulczynski等（2011）提出了基于整数规划的启发式算法；Wilck IV和Cavalier（2012a）提出了一个混合遗传算法；Silva等（2015）和McNabb等（2015）提出了一个反复迭代的局部搜索算法；Han和Chu（2016）提出了一个基于多个初始解的变邻域搜索算法；Moshref-Javadi和Lee（2016）基于文献中的模拟退火和变邻域搜索设计了启发式求解算法。

针对分批次取货车辆路径问题（VRPSL），自Nowak等（2008）研究了一个启发式算法以来，Korsvik等（2011）探索了一个大邻域搜索算法；Mar-Ortiz等（2013）提出了一个贪婪式随机自适应搜索算法；Sahin等（2013）提出了一个禁忌搜索和模拟退火相结合的启发式算法；Lai等（2015）研究了一个自适应启发式算法。

针对分批次取送货车辆路径问题（VRPSDP），Mitra（2005）和Mitra（2008）提出了一个路径构建启发式算法；杨亚璪等（2010）提出了一个三阶段启发式算法；Izuno等（2012）、Asefeh和Reza（2012）、Wang等（2014）提出了一个两阶段混合启发式算法。

（2）精确算法

针对SDVRP，Dror等（1990，1994）和Gendreau等（2006）探索了分支定界算法；Belenguer等（2000）提出了一个切平面算法（Cutting Plane Algorithm）；Jin等（2007）基于有效不等式设计了一个两阶段求解算法；Jin等（2008）提出了一个列生成算法；Desaulniers（2010）、Salani和Vacca（2011）、Archetti等（2011）和Archetti等（2015）提出了一个分支切割算法。

针对VRPSL，Lee等（2006）基于最短路思想设计了动态规划算法；Nowak等（2012）提出了一个前向搜索的最短路算法；Andersson等（2011）提出了一个分支定界算法；Oncan等（2011）提出了一个分支切割算法。

1.2.4.2 供需匹配关系未知的取送货车辆路径问题求解算法

（1）启发式算法

针对单车、单产品的情况，Salazar-Gonzalez（2004b）提出了两个启发式算法：一个是基于提高k-optimality，另一个是基于分支切割进程的局部最优；Hernández-Pérez等（2009）提出了一个GRASP和VND的混合启发式算法；Zhao等（2009）提出了一个遗传算法；Mladenović等（2012）提出了一个广义的变邻域搜索算法；Ho和Szeto（2014）提出了一个反复迭代的禁忌搜索算法；Vogel等（2014）提出了一个嵌入大邻域搜索的元启发式算法。针对单车、多产品的情况，Hernández-Pérez等（2016）设计了一个三阶段的混合启发式算法；Li等（2016）设计了一个混合遗传算法。针对多车、单产品的情况，Rainer-Harbach等（2013）提出了一个变邻域搜索算法；Angeloudis等（2014）和Dell'Amico等（2016）提出了一个重新构建匹配关系的元启发式算法；Forma等（2015）提出了一个三阶段启发式算法；Di和Urli（2016）探索了一个大邻域搜索算法。针对多车、多产品的情况，Chen等（2014）提出了一个变邻域搜索算法。

（2）精确算法

针对单车、单产品的情况，Hernández-Pérez和Salazar-Gonzalez（2004a，2007）、Chemla等（2013）、Erdogğan等（2015）、Salazar-Gonzalez和Santos-Hernández（2015）探索了一个分支切割算法；Kadri等（2016）提出了一个分支定界算法。针对单车、多产品的情况，Hernández-Pérez和Salazar-Gonzalez（2014）提出了一个分支切割算法。针对多车、单产品的情况，Raviv等（2013）、Di和Urli（2016）探索了分支定界算法；Dell'Amico等（2014）提出了一个分支切割算法。

1.2.4.3 允许多次访问的取送货车辆路径问题求解算法

（1）启发式算法

针对单产品、带库存约束的情况，Song和Furman（2010）提出了一个基于优化的启发式算法（An Optimization based Heuristic Method）；Mirzaei和Seifi（2015）提出了一个基于模拟退火和禁忌搜索的元启发式算法。针对多产品、带库存约束的情况，Siswanto等（2011）提出了一系列贪婪式启发式算法；Christiansen等（2011）提出了一个嵌入构建式启发的遗传算法；Agra等（2014）提出了一个混合启发式算法；Hemmati等（2015）提出了一个被称作“ICGR”（Iterative Cargo Generating and Routing）的启发式算法；Hemmati等（2016）提出了一个改进的大邻域搜索算法。针对不带库存约束的情况，Siddiqui和Verma（2015）、De等（2016）提出了一个复合粒子群启发式算法。

（2）精确算法

针对单产品、带库存约束的情况，Christiansen和Nygreen（1998a，1998b）、Christiansen（1999）提出了一个嵌入分支定界的列生成方法；Engineer等（2012）探索了一个分支定价切割算法；Jiang和Grossmann（2015）提出了一个分支定界算法。针对多产品、带库存约束的情况，Al-Khayyal和Hwang（2007）、Agra等（2013b）提出了一个分支定界算法；Agra等（2015）提出了一个列生成算法。针对不带库存约束的情况，Hennig等（2012a，2012b）提出了一个嵌套的列生成算法。