This paper seeks to advance CVRP research by addressing the challenge of understanding the nuanced relationships between instance characteristics and metaheuristic (MH) performance. We present Instance Space Analysis (ISA) as a valuable tool that allows for a new perspective on the field. By combining the ISA methodology with a dataset from the DIMACS 12th Implementation Challenge on Vehicle Routing, our research enabled the identification of 23 relevant instance characteristics. Our use of the PRELIM, SIFTED, and PILOT stages, which employ dimensionality reduction and machine learning methods, allowed us to create a two-dimensional projection of the instance space to understand how the structure of instances affect the behavior of MHs. A key contribution of our work is that we provide a projection matrix, which makes it straightforward to incorporate new instances into this analysis and allows for a new method for instance analysis in the CVRP field.

The optimization community has made significant progress in solving vehicle routing problems (VRPs) to optimality using sophisticated branch-cut-and-price (BCP) algorithms. VRPSolver is a BCP algorithm with excellent performance in many VRP variants. However, its complex underlying mathematical model makes it hardly accessible to routing practitioners. To address this, VRPSolverEasy provides a Python interface to VRPSolver that does not require any knowledge of mixed integer programming modeling. Instead, routing problems are defined in terms of familiar elements, such as depots, customers, links, and vehicle types. VRPSolverEasy can handle several popular VRP variants and arbitrary combinations of them. History: Accepted by Ted Ralphs, Area Editor for Software Tools. This paper has been accepted for the INFORMS Journal on Computing Special Issue on Software Tools for Vehicle Routing. Funding: This work was supported by Faperj [Grant E-26/202.887/2017] and Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grant 305684/2022-1]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0103 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0103 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract In this article, we propose graph‐based models for several vehicle routing problems with intermediate stops: the capacitated multi‐trip vehicle routing problem with time windows, the multi‐depot vehicle routing problem with inter‐depot routes, the arc routing problem with intermediate facilities under capacity and length restrictions and the green vehicle routing problem. In these models, the set of feasible routes is represented by a set of resource constrained paths in one or several graphs. Intermediate stops are supported by the possibility to define negative resource consumption for some arcs. The models that we propose are then solved by VRPSolver, which implements a generic branch‐cut‐and‐price exact algorithm. Thus, a simple parameterization enables us to use several state‐of‐the‐art algorithmic components: automatic stabilization by dual price smoothing, limited‐memory rank‐1 cuts, reduced cost‐based arc elimination, enumeration of elementary routes, and hierarchical strong branching. For each problem, we numerically compare the proposed methodology with the best exact approach found in the literature. State‐of‐the‐art computational results were obtained for all problems except one.

In this work, the Vehicle Routing Problem with Time Windows (VRPTW) is addressed as a way of incorporating dynamic characteristics of the urban express delivery logistics chain, exploring theoretical aspects that best define the problem and its instances. The problem is to determine minimum cost routes that must be performed by a fleet respecting the capacities of vehicles and the time windows associated with each delivery. A strategy that uses the Branch-Cut-and-Price method through the VRPsolver tool was applied to two sets of instances, the first being Solomon’s artificial classical instances and, the second, real instances of Brazilian urban cities adapted from the loggiBUD benchmark.

In this paper we study a network design problem that consists in finding a minimum weight subgraph containing solutions for multiple Steiner Traveling Salesman Problems with Order constraints. We propose a layered compact ILP formulation for the problem. Experimental results show that it is reasonably effective and can solve to optimality medium-sized instances. Lage-scale instances are more difficult, and does not reach optimal solutions within a time limit of 3 hours. In order to improve our formulation, we investigate valid inequalities efficiency using a column-generation-based approach.

Major advances were recently obtained in the exact solution of Vehicle Routing Problems (VRPs). Sophisticated Branch-Cut-and-Price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This work proposes a BCP solver for a generic model that encompasses a wide class of VRPs. It incorporates the key elements found in the best recent VRP algorithms: ng-path relaxation, rank-1 cuts with limited memory, and route enumeration; all generalized through the new concept of “packing set”. This concept is also used to derive a new branch rule based on accumulated resource consumption and to generalize the Ryan and Foster branch rule. Extensive experiments on several variants show that the generic solver has an excellent overall performance, in many problems being better than the best existing specific algorithms. Even some non-VRPs, like bin packing, vector packing and generalized assignment, can be modeled and effectively solved.

Primal heuristics have become essential components in mixed integer programming (MIP) solvers. Extending MIP-based heuristics, our study outlines generic procedures to build primal solutions in the context of a branch-and-price approach and reports on their performance. Our heuristic decisions carry on variables of the Dantzig–Wolfe reformulation, the motivation being to take advantage of a tighter linear programming relaxation than that of the original compact formulation and to benefit from the combinatorial structure embedded in these variables. We focus on the so-called diving methods that use reoptimization after each linear programming rounding. We explore combinations with diversification-intensification paradigms such as limited discrepancy search, sub-MIP, local branching, and strong branching. The dynamic generation of variables inherent to a column generation approach requires specific adaptation of heuristic paradigms. We manage to use simple strategies to get around these technical issues. Our numerical results on generalized assignment, cutting stock, and vertex-coloring problems set new benchmarks, highlighting the performance of diving heuristics as generic procedures in a column generation context and producing better solutions than state-of-the-art specialized heuristics in some cases.

International audience

The vehicle routing problem with time windows (VRPTW) consists of finding least-cost vehicle routes to satisfy the demands of customers that can be visited within specific time windows. We introduce two enhancements for the exact solution of the VRPTW by branch-price-and-cut (BPC). First, we develop a sharper form of the limited-memory subset-row inequalities by representing the memory as an arc subset rather than a node subset. Second, from the elementary inequalities introduced by Balas in 1977, we derive a family of inequalities that dominate them. These enhancements are embedded into an exact BPC algorithm that includes state-of-the-art features such as bidirectional labeling, decremental state-space relaxation, completion bounds, variable fixing, and route enumeration. Computational results show that these enhancements are particularly effective for the most difficult instances and that our BPC algorithm can solve all 56 Solomon instances with 100 customers and 51 of 60 Gehring and Homberger instances with 200 customers.

Abstract The hop‐constrained survivable network design problem consists of finding a minimum cost subgraph containing K edge‐disjoint paths with length at most H joining each pair of vertices in a given demand set. When all demands have a common vertex, the instance is said to be rooted. We propose a new extended formulation for the rooted case, called hop‐level multicommodity flow (MCF), that can be significantly stronger than the previously known formulations, at the expense of having a larger number of variables and constraints, growing linearly with the number of edges and demands and quadratically with H . However, for the particular case where H = 2, it can be specialized into a very compact and efficient formulation. Even when H = 3, hop‐level‐MCF can still be quite efficient and it has solved several instances from the literature for the first time. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

Abstract We propose algorithms to compute tight lower bounds and high quality upper bounds (UBs) for the multilevel capacitated minimum spanning tree problem. We first develop a branch‐and‐cut algorithm, introducing some new features: (i) the exact separation of cuts corresponding to some master equality polyhedra found in the formulation; (ii) the separation of Fenchel cuts, solving LPs considering all the possible solutions restricted to small portions of the graph. We then use that branch‐and‐cut within a GRASP that performs moves by solving to optimality subproblems corresponding to partial solutions. The computational experiments were conducted on 450 benchmark instances from the literature. Numerical results show improved best known (UBs) for almost all instances that could not be solved to optimality. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

We present efficient algorithms that implement four local searches for the Steiner problem in graphs: vertex insertion, vertex elimination, key-path exchange, and key-vertex elimination. In each case, we show how to find an improving solution (or prove that none exists in the neighborhood) in O(m log n) time on graphs with n vertices and m edges. Many of the techniques and data structures we use are relevant in the study of dynamic graphs in general, beyond Steiner trees. Besides the theoretical interest, our results have practical impact: these local searches have been shown to find good-quality solutions in practice, but high running times limited their applicability.

The Team Orienteering Problem is a routing problem on a graph with durations associated to the arcs and profits assigned to visiting the vertices. A fixed number of identical vehicles, with a limited total duration for their routes, is given. The total profit gathered by all routes is to be maximized. We devise an extended formulation where edges are indexed by the time they are placed in the route. A new class of inequalities, min cut, and the triangle clique cuts of Pessoa et. al., 2007 are added. The resulting formulation is solved by column generation. Branching is done following the work of Boussier et al. 2007, to which the branch-cut-and-price algorithm here proposed is compared. A few new upper bounds were obtained. Overall the presented approach has shown to be very competitive.

Abstract Multicast routing problems are often modeled as Steiner Problems in undirected or directed graphs, the latter case being particularly suitable to cases where most of the traffic has a single source. Sequential Steiner heuristics are not convenient in that context, because one cannot assume that a central node has complete information about the topology and the state of a large wide area network. This article introduces a distributed version of a Dual Ascent primal‐dual heuristic, known for its remarkably good practical results, lower and upper bounds, in both undirected and directed Steiner problems. Complexity analysis and experimental results are also presented, showing the efficiency of the proposed algorithm when compared with the best distributed algorithms in the literature. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract This article presents a robust branch‐cut‐and‐price algorithm for the heterogeneous fleet vehicle routing problem (HFVRP), vehicles may have distinct capacities and costs. The columns in the formulation are associated to q‐routes, a relaxation of capacitated elementary routes that makes the pricing problem solvable in pseudopolynomial time. Powerful new families of cuts are also proposed, which are expressed over a very large set of variables. Those cuts do not increase the complexity of the pricing subproblem. Experiments are reported where instances with up to 75 vertices were solved to optimality, a major improvement with respect to previous algorithms. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

We propose and describe a hybrid GRASP with weight perturbations and adaptive path-relinking heuristic (HGP + PR) for the Steiner problem in graphs. In this multi-start approach, the greedy randomized construction phase of a GRASP is replaced by the use of several construction heuristics with a weight perturbation strategy that combines intensification and diversification elements, as in a strategic oscillation approach. The improvement phase circularly explores two different local search strategies. The first uses anode-based neighborhood for local search, while the second uses a key-path-based neighborhood. An adaptive path-relinking technique is applied to a set of elite solutions as apost-optimization strategy. Computational results on a broad set of benchmark problems illustrate the effectiveness and the robustness of our heuristic, which is very competitive when compared to other approximate algorithms.

Abstract VLSI layout applications yield instances of the Steiner tree problem over grid graphs with holes, which are considered hard to be solved by current methods. In particular, preprocessing techniques developed for Steiner problems over general graphs are not likely to reduce, significantly, such VLSI instances. We propose a new preprocessing procedure, extending earlier ideas from the literature and improving their application, so as to make them effective for VLSI problems. We report significant reductions within reasonable computational times, obtained with the application of this procedure to 116 instances of the SteinLib. These reductions allowed a branch and cut to solve 28 of 32 open instances of the SteinLib, some with more than 10,000 vertices and 20,000 edges. © 2002 Wiley Periodicals, Inc.