Search

The aim of this erratum is to correct an error in the computer implementation of the algorithm proposed by Dabia, Ropke, and van Woensel [Dabia S, Ropke S, van Woensel T (2013) Branch and price for the time-dependent vehicle routing problem with time windows. Transportation Sci. 47(3):295–454]. Section 6, "Computational Results," from the original paper is rewritten to reflect the corrected implementation, the new computational setup, and the updated results. [ABSTRACT FROM AUTHOR]

This paper describes an exact branch-and-cut (B&C) algorithm for the split delivery vehicle routing problem. The underlying model is based on a previously proposed two-index vehicle flow formulation that models a relaxation of the problem. We dynamically separate two well-known classes of valid inequalities, namely capacity and connectivity cuts, and use an in-out algorithm to improve the convergence of the cutting phase. We generate no-good cuts from feasible integer solutions to the relaxation using a recently proposed single-commodity flow formulation in the literature. The exact methodology is complemented by a very effective adaptive large neighborhood search (ALNS) heuristic that provides high-quality upper bounds to initiate the B&C algorithm. Key ingredients in the design of the heuristic include the use of a tailored construction algorithm, which can exploit the situation in which the ratio of the number of customers to the minimum number of vehicles needed is low, and the use of a route-based formulation to improve the solutions found before, during, and after the ALNS procedure. An earlier version of this work was submitted to the DIMACS (Center for Discrete Mathematics and Theoretical Computer Science) implementation challenge, where it placed third. On sets of well-known benchmark instances for limited and unlimited fleet variants of the problem, we demonstrate that the heuristic provides very competitive solutions, with respective average gaps of 0.19% and 0.18% from best-known values. Furthermore, the exact B&C framework is also highly competitive with state-of-the-art methods, providing solutions with an average optimality gap of 1.82%. History: This paper has been accepted for the Transportation Science Special Section on DIMACS Implementation Challenge: Vehicle Routing Problems. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2022.0353. [ABSTRACT FROM AUTHOR]

A New Family of Valid-Inequalities for Dantzig-Wolfe Reformulation of Mixed Integer Linear Programs In "Consistency Cuts for Dantzig-Wolfe Reformulation," Jens Vinther Clausen, Richard Lusby, and Stefan Ropke present a new family of valid inequalities to be applied to Dantzig-Wolfe reformulations with binary linking variables. They show that, for Dantzig-Wolfe reformulations of mixed integer linear programs that satisfy certain properties, it is enough to solve the linear programming relaxation of the Dantzig-Wolfe reformulation with all consistency cuts to obtain integer solutions. An example of this is the temporal knapsack problem; the effectiveness of the cuts is tested on a set of 200 instances of this problem, and the results are state-of-the-art solution times. For problems that do not satisfy these conditions, the cuts can still be used in a branch-and-cut-and-price framework. In order to show this, the cuts are applied to a set of generic mixed linear integer programs from the online library MIPLIB. These tests show the applicability of the cuts in general. This paper introduces a family of valid inequalities, which we term consistency cuts, to be applied to a Dantzig-Wolfe reformulation (or decomposition) with linking variables. We prove that these cuts ensure an integer solution to the corresponding Dantzig-Wolfe relaxation when certain criteria to the structure of the decomposition are met. We implement the cuts and use them to solve a commonly used test set of 200 instances of the temporal knapsack problem. We assess the performance with and without the cuts and compare further to CPLEX and other solution methods that have historically been used to solve the test set. By separating consistency cuts, we show that we can obtain optimal integer solutions much faster than the other methods and even solve the remaining unsolved problems in the test set. We also perform a second test on instances from the MIPLIB 2017 online library of mixed-integer programs, showing the potential of the cuts on a wider range of problems. [ABSTRACT FROM AUTHOR]

We consider a variant of the berth allocation problem—that is, the multiport berth allocation problem—aimed at assigning berthing times and positions to vessels in container terminals. This variant involves optimizing vessel travel speeds between multiple ports, thereby exploiting the potentials of a collaboration between carriers (shipping lines) and terminal operators. Using a graph representation of the problem, we reformulate an existing mixed-integer problem into a generalized set partitioning problem, in which each variable refers to a sequence of feasible berths in the ports that the vessel visits. By integrating column generation and cut separation in a branch-and-cut-and-price procedure, our proposed method is able to outperform commercial solvers in a set of benchmark instances and adapt better to larger instances. In addition, we apply cooperative game theory methods to efficiently distribute the savings resulting from a potential collaboration and show that both carriers and terminal operators would benefit from collaborating. [ABSTRACT FROM AUTHOR]