ABSTRACT This work considers branch‐price‐and‐cut algorithms for variants of the vehicle‐routing problem in which subset‐row inequalities (SRIs) are used to strengthen the linear relaxation. SRIs often help to substantially reduce the size of the branch‐and‐bound search tree. However, their use is computationally costly because SRIs modify the structure of the respective column‐generation subproblem, which is a shortest‐path problem with resource constraints (SPPRC). Each active SRI requires the addition of a resource to the labeling algorithm that is invoked for solving the SPPRC in every iteration. In the context of time‐window constraints, the concept of unreachable customers has been used for preprocessing (time‐window reduction, arc elimination, precedence identification) as well as for improving the dominance between labels in the elementary SPPRC and its relaxations. We show that the identification of unreachable customers can also help to improve the dominance due to a modified comparison of SRI‐related resources. Computational experiments with a fully fledged branch‐price‐and‐cut algorithm for the (standard and electric) vehicle‐routing problem with time windows demonstrate the effectiveness of the approach: Overall computation times decrease; for some difficult instances, they may even be cut in half, while the required modifications of a computer implementation for combining SRIs with unreachable customers are minor.

ABSTRACT The global demand for sustainable waste management has spurred initiatives to improve the efficiency of urban waste collection, discussing the advantages and disadvantages of different systems. We analyze a new combined waste collection problem that uses two systems simultaneously: a point‐to‐point system, in which waste is collected using trucks, and an automated system, where waste from inlets is transported through a network of pipes. The resulting combined waste collection problem is a two‐stage decision problem: At the first stage, for each collection point, it must be decided whether it is served by truck or the pneumatic system. At the second stage, a Capacitated Vehicle Routing Problem (CVRP) must be solved for the collection points served by truck, and a cost‐minimal tree must be determined for the collection points assigned to the pneumatic system. Both stages and the respective problems are interdependent, making the optimization of the whole system a difficult task. We develop a holistic solution approach based on a set‐partitioning formulation utilizing route and tree variables. Because of the large number of variables, we solve the formulation heuristically using a column‐generation‐based matheuristic. The resulting subproblems are an elementary shortest‐path problem with capacity constraints and a variant of the node‐weighted Steiner tree problem. Our approach is empirically evaluated on two datasets, an extended variant of the well‐known CVRP benchmark and real‐world data from Vienna. The results indicate that the proposed matheuristic can provide high‐quality solutions to realistic instances of the combined waste collection problem.

Dynamic-radius search, formerly known as sequential search, is an effective neighborhood exploration technique for standard edge-exchange neighborhoods such as 2-opt, 2-opt*, swap, relocation, Or-opt, string exchange, etc. Up to now, it has only been used for vehicle routing problems with a homogeneous fleet and in the single-depot context. In this work, we extend dynamic-radius search to the multi-depot vehicle routing problem, in which 2-opt and 2-opt* moves may involve routes from different depots. To this end, we equip dynamic-radius search with a modified pruning criterion that still guarantees to identify a best-improving move, either intra-depot or inter-depot, with little additional computational effort. We experimentally confirm that substantial speedups of factors of 100 and more are achieved compared to an also optimized implementation of lexicographic search, another effective neighborhood exploration technique using a feasibility-based pruning criterion. As one would expect, better local optima are found on average when allowing inter-depot moves in radius search (positive result). Against intuition, we do however not end up with a better ILS metaheuristic regarding best found solutions, i.e., better average results do not translate into better overall results. We can at least partly explain the latter negative result, which might be useful for other researchers and their attempt to algorithmically optimize their neighborhood exploration procedures.

Many routing and scheduling problems are modeled through variables that represent paths (routes, schedules, etc.). For such extensive formulations, branch-price-and-cut (BPC) algorithms nowadays constitute the leading exact solution technique, and most of the time, the pricing problem is a shortest-path problem with resource constraints that can be solved by a dynamic-programming labeling algorithm. For this setting, variable fixing techniques based on the reduced costs of the paths have been proposed with the aim of eliminating arcs from the underlying network and speeding up the solution process of the pricing problem as well as of the overall BPC algorithm. For an efficient variable fixation, bidirectional labeling must be possible. We move one step forward and show how the reduced costs of paths can also be exploited to reduce the resource windows for many types of resources, including the time resource and a load-related resource. This can be achieved without modifying the pricing problem network and altering the structure of the pricing problem itself. Moreover, different resources can be considered simultaneously. A straightforward reduction of the resource windows associated with the vertices of the network can tighten them, but this reduction does not translate into savings in computation times. On the contrary, the reduction of the resource windows is effective when distinct forward and backward resource windows are defined for each arc and reduced independently based on the traversal direction of the arc itself. Moreover, an arc can be eliminated when one of its arc-specific resource windows becomes empty, and the explicit use of variable fixing techniques can be avoided. Computational results obtained for benchmark instances of the vehicle-routing problem with time windows show that the overall computation times of the BPC algorithm can be significantly reduced compared with a fully fledged BPC algorithm using variable fixing techniques. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This research was supported by the Deutsche Forschungsgemeinschaft (DFG) [Grants GS 83/1-1 and IR 122/10-1] of Project 418727865. This support is gratefully acknowledged.

We present a new modeling approach for the single-picker routing problem with scattered storage (SPRP-SS) for order picking in warehouses. The SPRP-SS assumes that an article is, in general, stored at more than one pick position. The task is then the simultaneous selection of pick positions for requested articles and the determination of a minimum-length picker tour collecting the articles. It is a classical result of Ratliff and Rosenthal that, for given pick positions, an optimal picker tour is a shortest path in the state space of a dynamic program with a linear number of states and transitions. We extend the state space of Ratliff and Rosenthal to include scattered storage so that every feasible picker tour is still a path. The additional requirement to make consistent decisions regarding articles to collect is not modeled in the state space so that dynamic programming can no longer be used for the solution. Instead, demand covering can be modeled as additional constraints in shortest-path problems. Therefore, we solve the resulting model with a mixed-integer (linear) programming (MIP) solver. The paper shows that this approach is not only convenient and elegant for single-block parallel-aisle warehouse SPRP-SSs but also generalizable: the solution principle can be applied to different warehouse layouts (we present additional results for a two-block parallel-aisle warehouse) and can incorporate further extensions. Computational experiments with other approaches for the SPRP-SS show that the new modeling approach outperforms the available exact algorithms regarding computational speed. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms—Discrete. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2023.0075 .

We consider the exact solution of the basic version of the multiple-compartment vehicle-routing problem, which consists of clustering customers into groups, routing a vehicle for each group, and packing the demand of each visited customer into one of the vehicle’s compartments. Compartments have a fixed size, and there are no incompatibilities between the transported items or between items and compartments. The objective is to minimize the total length of all vehicle routes such that all customers are visited. We study the shortest-path subproblem that arises when solving the problem with a branch-price-and-cut algorithm exactly. For this subproblem, we compare a standard dynamic-programming labeling approach with a new one that uses a partial dominance. The algorithm with standard labeling already struggles with relatively small instances, whereas the one with partial dominance can cope with much larger instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research was supported by the Deutsche Forschungsgemeinschaft [Grant IR 122/10-1 of Project 418727865]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.1255 .

We study the family of problems of partitioning and covering a graph into/with a minimum number of relaxed cliques. Relaxed cliques are subsets of vertices of a graph for which a clique-defining property—for example, the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices—is relaxed. These graph partitioning and covering problems have important applications in many areas such as social network analysis, biology, and disease-spread prevention. We propose a unified framework based on branch-and-price techniques to compute optimal decompositions. For this purpose, new, effective pricing algorithms are developed, and new branching schemes are invented. In extensive computational studies, we compare several algorithmic designs, such as structure-preserving versus dichotomous branching, and their interplay with different pricing algorithms. The final chosen branch-and-price setup produces results that demonstrate the effectiveness of all components of the newly developed framework and the validity of our approach when applied to social network instances.

Abstract Driven by environmental considerations, regulations on vehicle emissions, and the offer of major subsidies, electric commercial vehicles (ECVs) are receiving ever stronger attention in logistics companies. Route planning for ECV fleets requires consideration of the special characteristics of ECVs, like limited driving range and the potential need to recharge en route at dedicated recharging stations. From a practical viewpoint, the number of recharge operations of each vehicle can very often be restricted to one recharge per route because (i) typical route distances in the most important application areas of ECVs, like small package shipping and food or beverage distribution, do not require more than one recharge given the current driving range of ECVs, and (ii) operations managers are very reluctant to plan vehicle routes with two or more recharges because recharging operations are perceived as unproductive idle times. We develop a simple hybrid of large neighborhood search and granular tabu search to solve the resulting electric vehicle‐routing problem with time windows and single recharge (EVRPTWS), considering the possibility of both full and partial recharge. The heuristic works on routes represented as customer sequences, and recharge operations are implicitly considered by determining the recharging position in the route, the recharging station to visit, and the amount to be recharged in optimal fashion. We discuss how our algorithm can be extended to handle nonlinear recharging times, different recharging times per station, and time‐dependent waiting times at stations. In numerical studies on EVRPTWS instances from the literature, the method provides optimal or near‐optimal solutions for instances with up to 100 customers within reasonable runtimes. Additional studies investigate the cost savings potential of partial recharges in comparison to full recharges in the presence of time‐window constraints, and examine the factors that influence this cost saving potential.

Column generation (CG) models have several advantages over compact formulations: they provide better linear program bounds, may eliminate symmetry, and can hide nonlinearities in their subproblems. However, users also encounter drawbacks in the form of slow convergence, also known as the tailing-off effect, and the oscillation of the dual variables. Among different alternatives for stabilizing the CG process, Ben Amor et al. [Ben Amor H, Desrosiers J, Valério de Carvalho JM (2006) Dual-optimal inequalities for stabilized column generation. Oper. Res. 54(3):454–463] suggest the use of dual-optimal inequalities (DOIs) in the context of cutting stock and bin packing problems. We generalize their results, provide new classes of (deep) DOIs, and show the applicability to other problems (vector packing, vertex coloring, bin packing with conflicts). We also suggest the dynamic addition of violated dual inequalities in a cutting-plane fashion and the use of dual inequalities that are not necessarily (deep) DOIs. In the latter case, a recovery procedure is needed to restore primal feasibility. Computational results proving the usefulness of the methods are presented.

In many branch-and-price algorithms, the column generation pricing problem consists of computing feasible paths in a network. In this paper, we show how, in this context, path-reduced costs can be used to remove some arcs from the underlying network without compromising optimality, and we introduce a bidirectional search technique to compute these reduced costs. This arc elimination method can lead to a substantial speedup of the pricing process and the overall branch-and-price algorithm. Special attention is given to variants of shortest-path problems with resource constraints. Computational results obtained for the vehicle routing problem with time windows show the efficiency of the proposed method.

This paper presents a new unified modeling and heuristic solution framework for vehicle-routing problems (VRPs) with complex side constraints. The work is focused on strong modeling capabilities as well as efficient solution procedures to be used in all kinds of metaheuristics. From the modeling point of view, the framework covers a variety of standard VRP types with classical constraints such as capacity, distance, route length, time window, pairing, and precedence constraints, but also nonstandard “rich” VRPs. From the methodological point of view, local search (LS) is the key solver engine to be used in heuristic solution procedures. First and foremost, the framework introduces two generic techniques for the efficient exploration of edge- and node-exchange neighborhoods. New preprocessing methods allow 𝒪(nk) neighborhoods to be searched in time complexity 𝒪(nk), i.e., without an additional effort for feasibility testing in the worst case. Moreover, for accelerating LS in the average case, Irnich et al. [Irnich, S., B. Funke, T. Grünert. 2006. Sequential search and its application to vehicle-routing problems. Comput. Oper. Res. 33 2405–2429] have introduced sequential search that is here adapted to cope with rich VRPs (complex side constraints). Computational tests on different types of VRPs indicate that the proposed techniques are highly efficient. Sequential search procedures outperform the currently most efficient search methods, which are based on lexicographic search, on large-scale instances and for nearly all types of neighborhoods by factors of between 10 and 1,000.

The elementary shortest-path problem with resource constraints (ESPPRC) is a widely used modeling tool in formulating vehicle-routing and crew-scheduling applications. The ESPPRC often occurs as a subproblem of an enclosing problem, where it is used to generate implicitly the set of all feasible routes or schedules, as in the column-generation formulation of the vehicle-routing problem with time windows (VRPTW). As the ESPPRC problem is NP-hard in the strong sense, classical solution approaches are based on the corresponding nonelementary shortest-path problem with resource constraints (SPPRC), which can be solved using a pseudo-polynomial labeling algorithm. While solving the enclosing problem by branch and price, this subproblem relaxation leads to weak lower bounds and sometimes impractically large branch-and-bound trees. A compromise between solving ESPPRC and SPPRC is to forbid cycles of small length. In the SPPRC with k-cycle elimination (SPPRC-k-cyc), paths with cycles are allowed only if cycles have length at least k + 1. The case k = 2 forbids sequences of the form i − j − i and has been successfully used to reduce integrality gaps. We propose a new definition of the dominance rule among labels for dealing with arbitrary values of k ≥ 2. The numerical experiments on the linear relaxation of some hard VRPTW instances from Solomon’s benchmark show that k-cycle elimination with k ≥ 3 can substantially improve the lower bounds of vehicle-routing problems with side constraints. The new algorithm has proven to be a key ingredient for getting exact integer solutions for well-known hard problems from the literature.