Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies
Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies
复制标题
DOI：
10.1016/j.ejor.2019.01.041
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Christian Tilk;Michael Drexl;Stefan Irnich
中科院分区：
文献类型：
--
作者：
Christian Tilk;Michael Drexl;Stefan Irnich
本文认为车辆路径问题（VRP）与多个资源的相互依赖性和地址的发展和计算评估的一个精确的分支和价格和切割算法的解决方案。两种资源之间的相互依赖性意味着两种资源消耗以它们之间存在折衷的方式相互影响。这影响了解决方案的可行性和/或成本。分支和价格和切割过程中的子问题VRP通常是一个变种的最短路径问题与资源约束（SPPRC）。对于许多SPPRC变体的精确解，基于动态编程的标记算法是占主导地位的。然而，在多个资源相互依赖的问题的权衡，使标签算法的应用前景黯淡。这是因为管理权衡曲线的复杂数据结构是必要的，并且只有弱优势准则是可能的，使得标记算法几乎变成纯枚举。因此，我们建议也解决分支和价格和削减SPPRC子问题。这导致了一个两级嵌套的分支-价格-切割算法。我们分析了不同的变体的算法，使交换的列，也行之间的不同levels.To证明我们的方法的计算可行性，我们进行计算实验的时间窗口，最小和最大的交付量为每个客户，客户依赖的利润支付每个需求单位交付，和时间同步约束的一些对客户之间的一个原型VRP。在这个问题中，存在成本和负载之间以及成本和时间之间的权衡。
This paper considers vehicle routing problems (VRPs) with multiple resource interdependencies and addresses the development and computational evaluation of an exact branch-and-price-and-cut algorithm for their solution. An interdependency between two resources means that the two resource consumptions influence one another in such a way that a tradeoff exists between them. This impacts the feasibility and/or the cost of a solution.The subproblem in branch-and-price-and-cut procedures for VRPs is very often a variant of the shortest-path problem with resource constraints (SPPRC). For the exact solution of many SPPRC variants, dynamic-programming based labeling algorithms are predominant. The tradeoffs in problems with multiple resource interdependencies, however, render the application of labeling algorithms unpromising. This is because complex data structures for managing the tradeoff curves are necessary and only weak dominance criteria are possible, so that the labeling algorithm becomes almost a pure enumeration. Therefore, we propose to solve also the SPPRC subproblem with branch-and-price-and-cut. This results in a two-level, nested branch-and-price-and-cut algorithm. We analyze different variants of the algorithm to enable the exchange of columns and also rows between the different levels.To demonstrate the computational viability of our approach, we perform computational experiments on a prototypical VRP with time windows, minimal and maximal delivery quantities for each customer, a customer-dependent profit paid for each demand unit delivered, and temporal synchronization constraints between some pairs of customers. In this problem, tradeoffs exist between cost and load and between cost and time.