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]

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2004.09.004 Byline: Stefan Ropke, David Pisinger Keywords: Metaheuristics; Vehicle routing problems; Large neighborhood search Abstract: The Vehicle Routing Problem with Backhauls is a generalization of the ordinary capacitated vehicle routing problem where goods are delivered from the depot to the linehaul customers, and additional goods are brought back to the depot from the backhaul customers. Numerous ways of modeling the backhaul constraints have been proposed in the literature, each imposing different restrictions on the handling of backhaul customers. A survey of these models is presented, and a unified model is developed that is capable of handling most variants of the problem from the literature. The unified model can be seen as a Rich Pickup and Delivery Problem with Time Windows, which can be solved through an improved version of the large neighborhood search heuristic proposed by Ropke and Pisinger [An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Technical Report, DIKU, University of Copenhagen, 2004]. The results obtained in this way are comparable to or improve on similar results found by state of the art heuristics for the various variants of the problem. The heuristic has been tested on 338 problems from the literature and it has improved the best known solution for 227 of these. An additional benefit of the unified modeling and solution method is that it allows the dispatcher to mix various variants of the Vehicle Routing Problem with Backhauls for the individual customers or vehicles. Author Affiliation: DIKU--Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen A, Denmark

In global liner shipping networks, a large share of transported cargo is transshipped at least once between container vessels, and the total transportation time of these containers depends on how well the corresponding services are synchronized. We propose a problem formulation that integrates service scheduling into the liner shipping network design problem. Furthermore, the model incorporates many industry-relevant modeling aspects: it allows for leg-based sailing speed optimization, it is not limited to simple or butterfly-type services, and it accounts for service-level requirements such as cargo transit time limits. The classic liner shipping network design problem is already a hard problem, and to solve the extended version, we propose a column-generation matheuristic that uses advanced linear programming techniques. The proposed method solves LINER-LIB instances of up to 114 ports and, if applied to the classic liner shipping network design problem, finds new best solutions to all instances, outperforming existing methods reported in the literature. Additionally, we analyze the relevance of scheduling for liner shipping network design. The results indicate that neglecting scheduling and approximating transshipments instead may result in the design of liner shipping networks that underestimate cargo transit times and their implications. [ABSTRACT FROM AUTHOR]

This paper introduces the vehicle routing problem with time windows and shifts (VRPTWS). At the depot, several shifts with nonoverlapping operating periods are available to load the planned trucks. Each shift has a limited loading capacity. We solve the VRPTWS exactly by a branch-and-cut-and-price algorithm. The master problem is a set partitioning with an additional constraint for every shift. Each constraint requires the total quantity loaded in a shift to be less than its loading capacity. For every shift, a pricing subproblem is solved by a label-setting algorithm. Shift capacity constraints define knapsack inequalities; hence we use valid inequalities inspired from knapsack inequalities to strengthen the linear programming relaxation of the master problem when solved by column generation. In particular, we use a family of tailored robust cover inequalities and a family of new nonrobust cover inequalities. Numerical results show that nonrobust cover inequalities significantly improve the algorithm. [ABSTRACT FROM AUTHOR]

Horizontal cooperation in logistics has attracted an increasing amount of attention in both industry and the research community. The most common form of cooperation in the tramp shipping market is the shipping pool, formed by a fleet of ships from different ownerships operated by a centralised administration. This paper studies such a centralised horizontal cooperation, a product tanker pool in Denmark, and addresses the operational challenges, including how to maximise the pool profit and how to allocate it fairly. We apply discrete event simulation and dynamic ship routing and speed optimisation in order to maximise the pool profit in a highly dynamic environment and apply methods derived from cooperative game theory when allocating the total profit. Through a large number of experiments on realistic data, we evaluate the benefit of cooperation under different scenarios, present the results from the profit allocation and analyse the effect of pool size on the total profit and ship utilisation rate. [ABSTRACT FROM AUTHOR]

This article studies the quay crane scheduling problem with non-crossing constraints, which is an operational problem that arises in container terminals. An enhancement to a mixed integer programming model for the problem is proposed and a new class of valid inequalities is introduced. Computational results show the effectiveness of these enhancements in solving the problem to optimality. [ABSTRACT FROM PUBLISHER]