Routing electric vehicles with a single recharge per route
Networks : an international journal (2020). doi:10.1002/net.21964
Branch-and-price-and-cut for a service network design and hub location problem
In the context of combined road-rail freight transport, we study the integrated tactical planning of hub locations and the design of a frequency service network. We consider a number of real-world constraints such as multiple transshipments of requests at hubs, transport time limits for requests, request splitting, and outsourcing possibilities. To our knowledge, the combination of problem features we deal with has not been described before. We present a path-based model and solve it with a branch-and-price-and-cut algorithm. Computational experiments show that large realistic instances from a major German rail freight company can be solved close to optimality within one hour on a standard …
Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem
Abstract In the commodity-constrained split delivery vehicle routing problem (C-SDVRP), customer demands are composed of sets of different commodities. The C-SDVRP asks for a minimum-distance set of routes such that all customer demands are met and vehicle capacities are respected. Moreover, whenever a commodity is delivered by a vehicle to a customer, the entire amount requested by this customer must be provided. Different commodities demanded by one customer, however, can be delivered by different vehicles. Thus, the C-SDVRP is a relaxation of the capacitated vehicle routing problem and a restriction of the split delivery vehicle routing problem. For its exact solution, we propose a branc…
Large multiple neighborhood search for the clustered vehicle-routing problem
Abstract The clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem in which customers are partitioned into clusters, and it is assumed that each cluster must have been served completely before the next cluster is served. This decomposes the problem into three subproblems, i.e., the assignment of clusters to routes, the routing inside each cluster, and the sequencing of the clusters in the routes. The second task requires the solution of several Hamiltonian path problems, one for each possibility to route through the cluster. We pre-compute the Hamiltonian paths for every pair of customers of each cluster. We present a large multiple neighborhood…
The Split Delivery Vehicle Routing Problem with Time Windows and Customer Inconvenience Constraints
In classical routing problems, each customer is visited exactly once. By contrast, when allowing split deliveries, customers may be served through multiple visits. This potentially results in substantial savings in travel costs. Even if split deliveries are beneficial to the transport company, several visits may be undesirable on the customer side: At each visit the customer has to interrupt his primary activities and handle the goods receipt. The contribution of the present paper consists in a thorough analysis of the possibilities and limitations of split delivery distribution strategies. To this end, we investigate two different types of measures for limiting customer inconvenience (a m…
Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies
Abstract 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 predomi…
Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems
Abstract For the exact solution of many types of vehicle-routing problems, column-generation based algorithms have become predominant. The column-generation subproblems are then variants of the shortest-path problem with resource constraints which can be solved well with dynamic-programming labeling algorithms. For vehicle-routing problems with a pickup-and-delivery structure, the strongest known dominance between two labels requires the delivery triangle inequality (DTI) for reduced costs to hold. When the direction of labeling is altered from forward labeling to backward labeling, the DTI requirement becomes the pickup triangle inequality (PTI). DTI and PTI cannot be guaranteed at the sam…
Maximum weight relaxed cliques and Russian Doll Search revisited
Trukhanov et al. [Trukhanov S, Balasubramaniam C, Balasundaram B, Butenko S (2013) Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations. Comp. Opt. and Appl., 56(1), 113–130] used the Russian Doll Search (RDS) principle to effectively find maximum hereditary structures in graphs. Prominent examples of such hereditary structures are cliques and some clique relaxations intensely discussed and studied in network analysis. The effectiveness of the tailored RDS by Trukhanov et al. for s-plex and s-defective clique can be attributed to their cleverly designed incremental verification procedures used to distinguish feasible from infeasible struct…
Two-phase branch-and-cut for the mixed capacitated general routing problem
The Mixed Capacitated General Routing Problem (MCGRP) is defined over a mixed graph, for which some vertices must be visited and some links must be traversed at least once. The problem consists of determining a set of least-cost vehicle routes that satisfy this requirement and respect the vehicle capacity. Few papers have been devoted to the MCGRP, in spite of interesting real-world applications, prevalent in school bus routing, mail delivery, and waste collection. This paper presents a new mathematical model for the MCGRP based on two-index variables. The approach proposed for the solution is a two-phase branch-and-cut algorithm, which uses an aggregate formulation to develop an effective …
Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows
The split delivery vehicle routing problem with time windows (SDVRPTW) is a notoriously hard combinatorial optimization problem. First, it is hard to find a useful compact mixed-integer programming (MIP) formulation for the SDVRPTW. Standard modeling approaches either suffer from inherent symmetries (mixed-integer programs with a vehicle index) or cannot exactly capture all aspects of feasibility. Because of the possibility to visit customers more than once, the standard mechanisms to propagate load and time along the routes fail. Second, the lack of useful formulations has rendered any direct MIP-based approach impossible. Up to now, the most effective exact algorithms for the SDVRPTW hav…
Formulations for an inventory routing problem
In this paper, we present and compare formulations for the inventory routing problem (IRP) where the demand of customers has to be served, over a discrete time horizon, by capacitated vehicles starting and ending their routes at a depot. The objective of the IRP is the minimization of the sum of inventory and transportation costs. The formulations include known and new mathematical programming formulations. Valid inequalities are also presented. The formulations are tested on a large set of benchmark instances. One of the most significant conclusions is that the formulations that use vehicle-indexed variables are superior to the more compact, aggregate formulations.
Branch-and-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs
Two critical yet frequently conflicting objectives for logistics and transportation service companies are improving customer satisfaction and reducing transportation cost. In particular, given a network of customer requests with preferred service times, it is very challenging to find vehicle routes and service schedules simultaneously that respect all operating constraints and minimize the total transportation and customers’ inconvenience costs. In this paper, we introduce the vehicle routing problem with time windows and convex node costs (VRPTW-CNC), in which we model each customer’s inconvenience cost as a convex function of the service start time at that customer. The VRPTW-CNC combine…
The last-mile vehicle routing problem with delivery options
AbstractThe ongoing rise in e-commerce comes along with an increasing number of first-time delivery failures due to the absence of the customer at the delivery location. Failed deliveries result in rework which in turn has a large impact on the carriers’ delivery cost. In the classical vehicle routing problem (VRP) with time windows, each customer request has only one location and one time window describing where and when shipments need to be delivered. In contrast, we introduce and analyze the vehicle routing problem with delivery options (VRPDO), in which some requests can be shipped to alternative locations with possibly different time windows. Furthermore, customers may prefer some deli…
A note on symmetry reduction for circular traveling tournament problems
Abstract The traveling tournament problem (TTP) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. Easton et al. (2001) introduced the so-called circular TTP instances, where venues of teams are located on a circle. The distance between neighboring venues is one, so that the distance between any pair of teams is the distance on the circle. It is empirically proved that these instances are very hard to solve due to the inherent symmetry. This note presents new ideas to cut off essentially identical parts of the solution space. Enumerative solution approaches, e.g. relying on branch-and-bound, benefit from this reduction. We…
A new branch-and-price algorithm for the traveling tournament problem
Abstract The traveling tournament problem ( ttp ) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. For solving the problem exactly, we propose a new branch-and-price approach. The starting point is a new compact formulation for the ttp . The corresponding extensive formulation resulting from a Dantzig-Wolfe decomposition is identical to one given by Easton, K., Nemhauser, G., Trick, M., 2003. Solving the traveling tournament problem: a combined interger programming and constraint programming approach. In: Burke, E., De Causmaecker, P. (Eds.), Practice and Theory of Automated Timetabling IV, Volume 2740 of Lecture Notes i…
The shortest-path problem with resource constraints with -loop elimination and its application to the capacitated arc-routing problem
Abstract In many branch-and-price algorithms, the column generation subproblem consists of computing feasible constrained paths. In the capacitated arc-routing problem (CARP), elementarity constraints concerning the edges to be serviced and additional constraints resulting from the branch-and-bound process together impose two types of loop-elimination constraints. To fulfill the former constraints, it is common practice to rely on a relaxation where loops are allowed. In a k-loop elimination approach all loops of length k and smaller are forbidden. Following Bode and Irnich (2012) for solving the CARP, branching on followers and non-followers is the only known approach to guarantee integer …
In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem
Recently, Bode and Irnich [Bode C, Irnich S (2012) Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60(5):1167–1182] presented a cut-first branch-and-price-second algorithm for solving the capacitated arc-routing problem (CARP). The fundamental difference to other approaches for exactly solving the CARP is that the entire algorithm works directly on the typically sparse underlying graph representing the street network. This enables the use of highly efficient dynamic programming-based pricing algorithms to solve the column-generation subproblem also known as the pricing problem. The contribution of this paper is the in-depth analysis of the CARP pricing…
Dual Inequalities for Stabilized Column Generation Revisited
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 th…
Strategic Planning for Integrated Mobility-on-Demand and Urban Public Bus Networks
App-based services and ridesharing in the field of mobility-on-demand (MoD) create a new mode of transport between motorized individual transport and public transportation whose long-term role in the urban mobility landscape and within public transport systems is not fully understood as of today. For the public transport industry, these new services offer new chances but also risks, making planning models and tools for integrated intermodal network planning indispensable. We develop a strategic network planning optimization model for bus lines that allows for intermodal trips with MoD as a first or last leg. Starting from an existing public transport network, we decide simultaneously on th…
Stabilized branch-and-price algorithms for vector packing problems
Abstract This paper considers packing and cutting problems in which a packing/cutting pattern is constrained independently in two or more dimensions. Examples are restrictions with respect to weight, length, and value. We present branch-and-price algorithms to solve these vector packing problems (VPPs) exactly. The underlying column-generation procedure uses an extended master program that is stabilized by (deep) dual-optimal inequalities. While some inequalities are added to the master program right from the beginning (static version), other violated dual-optimal inequalities are added dynamically. The column-generation subproblem is a multidimensional knapsack problem, either binary, boun…
A new compact formulation for the discrete p-dispersion problem
Abstract This paper addresses the discrete p -dispersion problem (PDP) which is about selecting p facilities from a given set of candidates in such a way that the minimum distance between selected facilities is maximized. We propose a new compact formulation for this problem. In addition, we discuss two simple enhancements of the new formulation: Simple bounds on the optimal distance can be exploited to reduce the size and to increase the tightness of the model at a relatively low cost of additional computation time. Moreover, the new formulation can be further strengthened by adding valid inequalities. We present a computational study carried out over a set of large-scale test instances i…
Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem
The soft-clustered capacitated arc-routing problem (SoftCluCARP) is a variant of the classical capacitated arc-routing problem. The only additional constraint is that the set of required edges, that is, the streets to be serviced, is partitioned into clusters, and feasible routes must respect the soft-cluster constraint, that is, all required edges of the same cluster must be served by the same vehicle. In this article, we design an effective branch-price-and-cut algorithm for the exact solution of the SoftCluCARP. Its new components are a metaheuristic and branch-and-cut-based solvers for the solution of the column-generation subproblem, which is a profitable rural clustered postman tour …
Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows
In this paper, we present a new branch-and-price-and-cut algorithm to solve the truck-and-trailer routing problem with time windows (TTRPTW) and two real-world extensions. In all TTRPTW variants, the fleet consists of one or more trucks that may attach a trailer. Some customers are not accessible with a truck-and-trailer combination, but can however be serviced by one if the trailer is previously detached and parked at a suitable location. In the first extension, the planning horizon comprises two days and customers may be visited either on both days or only once, in which case twice the daily supply must be collected. The second extension incorporates load transfer times depending on the …
Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem
This paper presents a branch-and-price-and-cut algorithm for the exact solution of the active-passive vehicle-routing problem (APVRP). The APVRP covers a range of logistics applications where pickup-and-delivery requests necessitate a joint operation of active vehicles (e.g., trucks) and passive vehicles (e.g., loading devices such as containers or swap bodies). The objective is to minimize a weighted sum of the total distance traveled, the total completion time of the routes, and the number of unserved requests. To this end, the problem supports a flexible coupling and decoupling of active and passive vehicles at customer locations. Accordingly, the operations of the vehicles have to be s…
Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and multiple stacks
Abstract This paper proposes models and algorithms for the pickup and delivery vehicle routing problem with time windows and multiple stacks. Each stack is rear-loaded and is operated in a last-in-first-out (LIFO) fashion, meaning that when an item is picked up, it is positioned at the rear of a stack. An item can only be delivered if it is in that position. This problem arises in the transportation of heavy or dangerous material where unnecessary handling should be avoided, such as in the transportation of cars between car dealers and the transportation of livestock from farms to slaughterhouses. To solve this problem, we propose two different branch-price-and-cut algorithms. The first sol…
Hybridizing large neighborhood search and exact methods for generalized vehicle routing problems with time windows
International audience; Delivery options are at the heart of the generalized vehicle routing problem with time windows (GVRPTW) allowing that customer requests are shipped to alternative delivery locations which can also have different time windows. Recently, the vehicle routing problem with delivery options was introduced into the scientific literature. It extends the GVRPTW by capacities of shared locations and by specifying service-level constraints defined by the customers' preferences for delivery options. The vehicle routing problem with delivery options also generalizes the vehicle routing problem with home roaming delivery locations and the vehicle routing problem with multiple time…
Exact solution of the soft-clustered vehicle-routing problem
Abstract The soft-clustered vehicle-routing problem (SoftCluVRP) extends the classical capacitated vehicle-routing problem by one additional constraint: The customers are partitioned into clusters and feasible routes must respect the soft-cluster constraint, that is, all customers of the same cluster must be served by the same vehicle. In this article, we design and analyze different branch-and-price algorithms for the exact solution of the SoftCluVRP. The algorithms differ in the way the column-generation subproblem, a variant of the shortest-path problem with resource constraints (SPPRC), is solved. The standard approach for SPPRCs is based on dynamic-programming labeling algorithms. We s…
A branch-and-price framework for decomposing graphs into relaxed cliques
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…
Schedule-Based Integrated Intercity Bus Line Planning via Branch-and-Cut
This work addresses integrated line planning for intercity bus lines, which differs in several respects from line planning in public transit. Passengers in intercity transportation decide on specific timetabled services to get to their destination. This is a contrast to an urban setting with higher frequencies, where it is generally sufficient to choose a line. Furthermore, intercity bus transportation in deregulated markets is usually characterized by fierce competition within and across modes. Customers are highly sensitive to price, time of day, duration, convenient access to stations, and service quality. Hence, bus line operators need to decide thoroughly on every single timetabled se…
Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster
Abstract With their paper “Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints” [Discrete Optimization 3, 2006, pp. 255–273] Righini and Salani introduced bounded bidirectional dynamic programming (DP) as an acceleration technique for solving variants of the shortest path problem with resource constraints (SPPRC). SPPRCs must be solved iteratively when vehicle routing and scheduling problems are tackled via Lagrangian relaxation or column-generation techniques. Righini and Salani and several subsequent works have shown that bounded bidirectional DP algorithms are often superior to their monodirectional counterparts, s…
Combined column-and-row-generation for the optimal communication spanning tree problem
Abstract This paper considers the exact solution of the optimal communication spanning tree problem (OCSTP), which can be described as follows: Given an undirected graph with transportation costs on every edge and communication requirements for all pairs of vertices, the OCSTP seeks for a spanning tree that minimizes the sum of the communication costs between all pairs of vertices, where the communication cost of a pair of vertices is defined as their communication requirement multiplied by the transportation cost of the unique tree path that connects the two vertices. Two types of compact formulations for OCSTP were presented in the literature. The first one is a four-index model based on …
Heuristics for a Real-World Mail Delivery Problem
We are solving a mail delivery problem by combining exact and heuristic methods. The problem is a tactical routing problem as routes for all postpersons have to be planned in advance for a period of several months. As for many other routing problems, the task is to construct a set of feasible routes serving each customer exactly once at minimum cost. Four different modes (car, moped, bicycle, and walking) are available, but not all customers are accessible by all modes. Thus, the problem is characterized by three interdependent decisions: the clustering of customers into districts, the choice of a mode for each district, and the routing of the postperson through its district. We present a t…
Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem
This paper presents the first full-fledged branch-and-price (bap) algorithm for the capacitated arc-routing problem (CARP). Prior exact solution techniques either rely on cutting planes or the transformation of the CARP into a node-routing problem. The drawbacks are either models with inherent symmetry, dense underlying networks, or a formulation where edge flows in a potential solution do not allow the reconstruction of unique CARP tours. The proposed algorithm circumvents all these drawbacks by taking the beneficial ingredients from existing CARP methods and combining them in a new way. The first step is the solution of the one-index formulation of the CARP in order to produce strong cut…
Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem
A dynamic time window relates to two operations that must be executed within a given time meaning that the difference between the points in time when the two operations are performed is bounded from above. The most prevalent context of dynamic time windows is when precedence is given for the two operations so that it is a priori specified that one operation must take place before the other. A prominent vehicle routing problem with dynamic time windows and precedence is the dial-a-ride problem (DARP), where user-specified transportation requests from origin to destination points must be serviced. The paper presents a new branch-and-cut-and-price solution approach for the DARP, the prototypi…
A branch-price-and-cut algorithm for the capacitated multiple vehicle traveling purchaser problem with unitary demand
Abstract The multiple vehicle traveling purchaser problem (MVTPP) consists of simultaneously selecting suppliers and routing a fleet of homogeneous vehicles to purchase different products at the selected suppliers so that all product demands are fulfilled and traveling and purchasing costs are minimized. We consider variants of the MVTPP in which the capacity of the vehicles can become binding and the demand for each product is one unit. Corresponding solution algorithms from the literature are either branch-and-cut or branch-and-price algorithms, where in the latter case the route-generation subproblem is solved on an expanded graph by applying standard dynamic-programming techniques. Our …
A branch-and-cut algorithm for the soft-clustered vehicle-routing problem
Abstract The soft-clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem (CVRP) in which customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. We introduce a novel symmetric formulation of the problem in which the clustering part is modeled with an asymmetric sub-model. We solve the new model with a branch-and-cut algorithm exploiting some known valid inequalities for the CVRP that can be adapted. In addition, we derive problem-specific cutting planes and new heuristic and exact separation procedures. For square grid instances in the Euclidean plane, we provide lower-bounding techniques …
Variable Fixing for Two-Arc Sequences in Branch-Price-and-Cut Algorithms on Path-Based Models
Variable fixing by reduced costs is a popular technique for accelerating the solution process of mixed-integer linear programs. For vehicle-routing problems solved by branch-price-and-cut algorithms, it is possible to fix to zero the variables associated with all routes containing at least one arc from a subset of arcs determined according to the dual solution of a linear relaxation. This is equivalent to removing these arcs from the network used to generate the routes. In this paper, we extend this technique to routes containing sequences of two arcs. Such sequences or their arcs cannot be removed directly from the network because routes traversing only one arc of a sequence might still b…