Keywords

1 Introduction

Branch-and-price-and-cut algorithms are powerful approaches for solving combinatorial optimization problems such as routing problems to optimality [1]. These algorithms comprise the techniques branch-and-bound, column generation, and addition of valid inequalities, which are interdependent. The branch-and-bound method ensures feasible integer solutions through a systematic and usefully restricted enumeration. Column generation is applied to formulations with a huge number of variables to find and add improving columns dynamically. In routing problems, the problem of finding improving columns is usually an elementary shortest path problem with resource constraints (ESPPRC) [4]. Valid inequalities (cuts) can be identified and added to a formulation to strengthen its linear relaxation. The details of all three parts depend on the problem that is tackled.

Routing refers to the task of selecting paths through a network. A very famous routing problem is the vehicle routing problem (VRP) where a fleet of vehicles has to perform a set of tasks with minimal costs [10]. There are numerous variants of the vehicle routing problem. In the cumulative dissertation of the author, which is summarized in the following, applications of and improvements on branch-and-price-and-cut algorithms for routing problems will be discussed.

2 Dynamic Half-Way Points in Bidirectional Labeling

As mentioned above, the subproblem of routing problems within column generation is usually an ESPPRC. Here, the task is to find the best path (with respect to the reduced costs) from a given source to a given sink that fulfills a set of constraints defined over a set of resources. Although the ESPPRC is known to be NP-hard, it can be solved effectively with a dynamic-programming based labeling algorithm. The labeling can usually be performed through a forward or a backward labeling approach, but monodirectional labelings typically suffer from an explosion of labels.

Bounded bidirectional labeling was introduced in order to mitigate the explosion of labels [5]. Both forward partial paths and backward partial paths are created, but processed only up to a so-called half-way point of a monotone resource in the middle of its feasible domain. When labeling terminates, suitable forward and backward labels have to be merged to complete paths.

However, within asymmetric instances or in applications in which forward and backward labeling differs significantly, a predefined half-way point in the middle may be unfavorable.

In Fig. 1, an example of an ESPPRC instance with unbalanced forward and backward labeling is depicted. The functions show, for any value T of the monotone resource, the number of processed forward labels with value ≤ T, the number of processed backward labels with value ≥ T, and the sum of both values.

Fig. 1
figure 1

Example of an SPPRC instance with unbalanced forward and backward labeling; static half-way point H St = 6180 in the middle of the time horizon and dynamic half-way point H Dy = 4158

Full size image

Obviously, the static half-way point H St produces much more labels than necessary. In our paper [9], we present a strategy to determine the half-way point H Dy dynamically by always continuing the labeling in the direction with the smaller number of unprocessed labels. As in the example in the figure, this dynamic half-way point leads to a reduced number of processed labels, which normally corresponds to a faster computation time. Much more computational results on different types of vehicle routing problems can be found in our paper [9].

3 Bidirectional Labeling for Pickup-and-Delivery

The pickup-and-delivery problem (PDP) deals with requests of transporting goods or passengers from specific pickup locations to corresponding delivery locations. Thus, compared to the classic vehicle routing problem (VRP), there are additional pairing and precedence constraints on the locations that need to be visited. We present the first bidirectional labeling approach for column-generation subproblems of PDPs in [3]. A strong dominance relation can only be achieved when it is never beneficial in terms of reduced costs to visit the second location of a request (the delivery point in forward direction and the pickup point in backward direction). However, the dual costs can not be distributed on the arcs such that this condition is true in both directions. For that reason, bidirectional search seemed to be unattractive for ESPPRCs with a pickup and delivery structure. We show that it is possible to use different cost matrices for the two directions when the merge procedure is adapted accordingly. Thus, the strong dominance relation can be used in both directions making the bidirectional search attractive again.

The performance profiles in Fig. 2 compare six labeling strategies on 220 PDPTW benchmark instances: Fw for forward, Bw for backward, Bi for bidirectional, Dy for dynamic half-way points, St for static half-way points, S for strong dominance and W for weak dominance. The performance profile ρ A(τ) of an algorithm A of a set of algorithms \(\mathcal {A}\) is the fraction of instances that algorithm A can solve within a factor τ of the fastest algorithm of \(\mathcal {A}\). The figure shows that the branch-and-price-and-cut with labeling strategy Bi-Dy-SS clearly dominates all other algorithms. Indeed, it is at most 1.5 times slower than the fastest algorithm for more than 90% of the instances solved by at least one algorithm.

Fig. 2
figure 2

Performance profiles of branch-and-price-and-cut algorithms using six different labeling strategies

Full size image

4 Truck-and-Trailer Routing Problem

The truck-and-trailer routing problem (TTRP) describes situations where trucks and attached trailers are used to visit customers with the restriction that some customers are not reachable by trailers. Hence, trailers can be parked at some locations and have to be recoupled later. Our algorithm described in [8] combines several state-of-the-art techniques for VRPs and tackles two new extensions. The first problem extension is the enlargement of the planning horizon from 1 to 2 days. Thereby, a symmetry arises, which is tackled by a tailored column-generation stabilization method. The second problem extension is the consideration of quantity-dependent transfer times for the load transfers from the truck to the trailer. We propose an adapted labeling algorithm that can handle the emerging tradeoff between the consumed time and the free space in the truck through additional resources. The resulting trade-off curves along a simple example route of a truck-and-trailer combination are shown in Fig. 3. The vehicle starts at the depot, parks the trailer at d(p), visits a lorry customer 1, drives back to the parking station for transfer τ(p), visits another lorry customer 2, picks up the trailer at c(p) and finally returns to the depot.

Fig. 3
figure 3

Example for tradeoff propagation with quantity-dependent transfer times. EAT = earliest arrival time, loadL = load in the lorry, q i supply and [e i, l i] time window of customer i

Full size image

The computational results demonstrate that our algorithm outperforms existing approaches on TTRP benchmark instances. We attribute this success mainly to the use of subset-row cuts and the new bidirectional labeling. The results regarding the extensions demonstrated their influences on the overall routing costs and showed that the solvability does not change excessively despite the more complicated problems.

5 Periodic Vehicle Routing Problem

In the periodic VRP (PVRP), the planning horizon is extended to multiple periods and customers need to be visited several times according to one of their offered visiting patterns. In the standard variant, the customers need to be visited regularly with a preset visit frequency. An exact method dealing with some more flexible visiting patterns is presented in [2].

In [6], we present a branch-and-price-and-cut algorithm for the classical PVRP with time windows and an extension to even more different visiting patterns. Whereas the classical PVRP expects visiting patterns with regular intervals between the visits and a fixed visit frequency for every customer during the planning horizon, this paper enables all kinds of visiting patterns. Therefor, we introduce two new types of underlying pricing networks, on which a state-of-the-art labeling algorithm can find new columns. The more effective network type is illustrated for a small example with two customers offering different schedules in a planning horizon of 4 days in Fig. 4.

Fig. 4
figure 4

Task networks for 4 days of an example with customer A offering schedules {0, 2} & {1, 3}, and customer B offering schedules {0, 2} & {0, 3} & {0, 2, 3}

Full size image

Moreover, for instances that fulfill a special symmetry, we show that constraint aggregation significantly improves the solution process. Different PVRP-specific settings are evaluated by computational tests and the optimality of two PVRPTW benchmark instances can be proven for the first time.

6 Service Network Design and Hub Location Problem

The service network design and hub location problem (SNDHLP) tackled in [7] does not belong to VRPs, but it also includes routing decisions. Its task is to select locations and connections between them to establish a network for the routing of a given set of transport requests.

Requests have to be transported via road and rail through a network whose hub nodes and connections between them have to be selected. In contrast to most other related works, the decision on a connection is not only about its existence but about the corresponding frequency of services. A simple example with an optimal solution is depicted in Fig. 5.

Fig. 5
figure 5

Example SNDHLP instance with solution

Full size image

Furthermore, several other real-world conditions such as restricted number of transshipments, transport time limits and splittable requests are considered in this combination for the first time. The branch-and-price-and-cut algorithm is adapted to the problem by a specific layered pricing network, an hierarchical branching scheme, the incorporation of three types of valid inequalities, and further acceleration techniques. Computational tests on real world instances of the major German rail company prove the practical applicability of the algorithm.

7 Conclusions

All summarized papers deal with branch-and-price-and-cut algorithms to find optimal solutions for different routing problems. Thereby, existing procedures were improved and new problem variants became solvable. The bidirectional labeling for the solution of ESPPRCs was accelerated through the introduced dynamic half-way point. By using different cost matrices in forward and backward labeling, bidirectional labeling became applicable for all pickup and delivery problems. Truck-and-trailer routing problems were extended to a 2 days planning horizon and quantity-dependent transfer times. For periodic vehicle routing problems, an exact algorithm which can tackle all kinds of visiting patterns was presented for the first time. Finally, a real-world problem combining service network design and hub location in the context of combined transport was solved.