Central European Journal of Operations Research manuscript No.
(will be inserted by the editor)

Combinatorially Simple Pickup and Delivery Paths
Marco E. Lübbecke
Technische Universität Berlin
Institut für Mathematik, Sekr. MA 6-1
Straße des 17. Juni 136, D-10623 Berlin, Germany
e-mail: M.Luebbecke@math.tu-berlin.de
September 9, 2003

Abstract Pickup and delivery problems discussed in the literature are often constrained to particularly simple solutions in terms of the sequence of visited locations. We study the very simplest pickup and delivery paths which are concatenations of short patterns visiting one or two requests. This restricted variant, still
N P -hard, is close to the traveling salesman problem with the additional choice ofwhat patterns to visit. We compare the number of restricted and unrestricted paths,
and evaluate their respective path lengths. We conclude with two polynomiallysolvable cases.
Key words Pickup and delivery problem; mini-cluster; traveling salesman problem; counting of paths
MSC (2000) 90B06, 90C27, 05A05

1 Motivation
Generically, when items are to be transported from origins to destinations by a capacitated vehicle we speak of the pickup and delivery problem (PDP). In particular,
variants with multiple vehicles and time window constraints have received considerable attention in the operations research literature [3,6,8–11,14,21,22]. Remarkably, many computational experiments are performed on problem instances
which allow only a restricted structure of solutions, that is, the feasible sequencesof pickups and deliveries are constrained. There are several reasons for such limitations: In dial-a-ride systems for the transportation for the handicapped and theelderly, temporal constraints strongly restrict the total vehicle load at any time [7];clustering approaches produce on average mini-clusters of small size [9,14]; theratio of the largest vehicle capacity and the smallest weight may be small [10,11,

2

Marco E. Lübbecke22]; in [17–19] simplicity of solutions is explicitly required in the problem definition. The aim of this paper is to demonstrate that well-defined restricted pickup
and delivery paths also have theoretical, possibly algorithmically useful benefits.
For a comprehensive review of the relevant approximative and exact solution
approaches to the PDP in its variants see [21,22]. A catalog of practical applications is provided in [6]. We consider a single vehicle only without time window
constraints. This setting arises as a subproblem for solution approaches to more
complex variants.
2 Pickup and Delivery Paths
Given a set R of n requests we represent the PDP by a directed graph G = (N, A).
The node set N comprises all pickup and delivery locations r + and r− , r ∈ R . For
each arc (i, j) ∈ A = N × N a weight ci j reflects the cost for traveling from i to
j. For each i ∈ N we are given the size `i of the load to be picked up (`i ≥ 0) or
delivered (`i ≤ 0), where `r+ = −`r− , r ∈ R . The vehicle capacity is denoted by L.
Definition 1 Let R = (i1 , i2 , . . . , iK ) with i p ∈ N, p = 1, . . . , K, represent a directed
simple path in G. R is called a pickup and delivery path (PD path) : ⇐⇒/ for all r ∈ R(i) Either {r+ , r− } ⊆ R or {r+ , r− } ∩ R = 0,(ii) If i p = r+ and iq = r− for an r ∈ R then p < q(iii) ∑kp=1 ` p ≤ L, for all k ≤ K

Conditions (i) through (iii) are called pairing, precedence, and capacity constraints,
in that order. Note that a PD path must not repeatedly visit the same request.
3 Combinatorially Simple Pickup and Delivery Paths
Define P1 = r∈R {(r+ , r− )}, P2 = r6=s∈R , {(r+ , s+ , s− , r− ), (r+ , s+ , r− , s− )}, and
P = P1 ∪ P2 . We use the simple node sequences P ∈ P , or patterns, as building
blocks for more complicated paths. Note that ∑ p∈P ` p = 0 for all P ∈ P .

Definition 2 A PD path R = (i1 , . . . , iK ) is called a P -concatenation : ⇐⇒ indices1 = p0 ≤ · · · ≤ pk = K exist such that(i p0 , . . . , i p1 ), (i p1 +1 , . . . , i p2 ), . . . , (i pk−1 +1 , . . . , i pk ) ∈ P .

In simple words, a pattern concatenation is a concatenation of patterns. In a sense,
we constrain each request’s context in admissible pickup and delivery paths. When
restricting ourselves to P1 only, we obtain a traveling salesman problem.
Lemma 1 Finding (a collection of) shortest P -concatenations which visit all requests is N P -hard in the strong sense.
Remark 1 The introduction of patterns allows for considering sequence dependent
travel cost. That is, we are able to account for the extent of work required at aparticular location which depends on the item picked up previously.

Combinatorially Simple Pickup and Delivery Paths

3

Applications Even though P -concatenations heavily constrain the general PDP,
we encouter applications which require solutions which are similarly simple instructure to ours. This includes the scheduling of switching locomotives [18,19],
ship scheduling [12], and the extraction of logs in forestry [20]. We discuss theseapplications in more detail in [17] and sketch here only one idealized example.
The HHLA CTA GmbH, Hamburg, Germany, plans an almost fully automatedcontainer terminal. Container vessels are loaded/unloaded, and containers are transported by automated guided vehicles (AGVs) to and from the intermediate stowage
areas. AGVs navigate via electronic marks in the ground, thus, the planning focus
is on assigning and scheduling the transports. An AGV may lift either one forty
feet container or two twenty feet container simultaneously. Therefore, each AGV
trip to the stowage area corresponds to serving either a P1 pattern or a P2 pattern.

4 Algorithmic Consequences
Ideas similar to pattern concatenation are well established in the operations research literature. Cluster-first route-second heuristics group requests into miniclusters and concatenate all of them into routes. In airline crew pairing [1,15] often
a subset of all possible pairings to work with is enumerated a priori. In contrast,
because of the small number of patterns which is O(n2 ), our intention is to select a
subset of P simultaneously to the construction of concatenations. Provided that P
is inherently given by the problem our approach is designed to be exact. We may
adapt e.g., existing labeling algorithms for resource constrained shortest paths [8],see [19] for a suggestion.
Note however, that although derived from the PDP, pattern concatenation is ofa different nature. The essential constraints of Def. 1 are explicitly controlled by
the definition of P . We may rather consider our problem as the simplest conceivable pickup and delivery flavored extension to the TSP. Additionally, we have toselect patterns that appropriately partition the node set N. On the one hand, thisstrongly suggests to focus algorithmic design on this selection. On the other hand,
it requires some care when adapting the above mentioned node oriented construction methods.
Due to the hardness of finding a shortest P -concatenation, we cannot expect todiscover an exact algorithm which is principally better than a complete enumeration of feasible solutions, either implicit or explicit. In order to get an impressionof the size of the solution space of such algorithms, an interesting question is how
many P -concatenations exist, especially in comparison to the general situation ofunrestricted pickup and delivery paths. We settle this issue in the next section.
Remark 2 Unlike two-stage strategies, in presence of time windows patterns do not
fix the temporal relation of nodes, i.e., travel times within a pattern. For instance,in [3] a vehicle is forced not to wait within a cluster, and the total cluster duration
is known in advance.

4

Marco E. Lübbecke

5 The Number of Concatenations
The aim of this section is to find an upper bound on the size of the solution space ofenumeration algorithms for P -concatenation. We would like to make the point that,when compared in a fair way, our restriction entails much fewer feasible solutions
but still guarantees an acceptable approximation guarantee.
For the sake of simplicity let us assume `r+ = 1, r ∈ R and L = 2, in particular
every pattern is feasible with respect to vehicle capacity. We denote by τ nP thenumber of P -concatenations which visit all n requests. The number of all PD paths
is τn = (2n)!/2n , which is simply the number of all directed Hamiltonian paths on
2n nodes, discarding those which do not respect the precedence constraints.
Lemma 2 The number of P -concatenations on 2n nodes isb 2n c i 2i−12

τP = n! · ∑ni=0 i!

· ∏ (n − j) .

(1)

j=i

Proof Each summand represents the number of different combinations of patterns
for a fixed number 0 ≤ i ≤ b 2n c of P2 patterns involved in the concatenation. We
assume that the empty product evaluates to one. For a fixed i there are (n − 2i)
P1 patterns, and therefore (n − 2i + 1) possibilities to position the first P2 pattern.
For the second P2 pattern there are (n − 2i + 2) possible positions, and finally(n − 2i + i) possibilities to place the last. This yields the stated product. Symmetry
in this counting is accounted for by dividing by the number i! of permutations of
the P2 patterns. Multiplication by 2i considers the fact that there are two different
P2 patterns for a given ordered pair of requests. Having thus calculated the numberof configurations of P1 and P2 patterns, multiplication by n! assigns requests toeach particular pattern. This gives (1). tuRemark 3 Usingnn!
k = (n−k)!·k! we may rewrite (1) as
b 2n cn−i.
τP = n! · ∑ 2 ·
i
i=0
n

i



(2)

An interpretation of (2) is that the binomial coefficient gives the number of possibilities to arrange n − 2i P1 and i P2 patterns (in their two forms): For i fixed
requests we only have to decide which of the remaining n − i requests are used tobuild P2 patterns.
Remark 4 Using another interpretation we obtain a recursive formula for τ nP , forwhich a different closed form can be given [16]. Similar to Fibonacci numbers,
define l1 = l2 = 1 and ln = ln−1 + 2 · ln−2 for 2 < n ∈ N.
Lemma 3 τnP = n! · ln+1 .

(3)Combinatorially Simple Pickup and Delivery Paths

5

Proof We use an inductive argument. Lemma 3 holds for n = 1, 2. Now suppose
the claim be valid for arbitrary but fixed n − 1, n ∈ N with n even. We omit theanalogue proof for odd n.
b n+1
2 c



 

b n+1
2 c
n+1−i
n−i
n−i
i
= (n + 1)! ∑ 2= (n + 1)! ∑ 2
+
i
i
i−1
i=0
i=0



b n−1
b 2n c 
2 c
(?)
i n−i
i n−1−i+ (n + 1)n(n − 1)! · 2 ∑ 2= (n + 1)n! ∑ 2
i
i
i=0
i=0

n+1 (2)

τP

i



(3)

= (n + 1) · n!ln+1 + 2 · (n + 1)n · (n − 1)!ln = (n + 1)!(ln+1 + 2 · ln) .

The last term equals (n + 1)! · ln+2. The index transformation (?) uses n even. tuAlthough τnP is exponential in n, its contribution to the total number of PD
paths is negligible.
Lemma 4 limn→∞ τnP /τn = 0 .
Proof
bnc

2
τnP
n!
n!
2n+i 2i−1=·∑·· n · 21.5n · n!
(n − j) ≤nτ(2n)! i=0 i! ∏
(2n)!
j=i

= n · 21.5n ·for n → ∞. tu

1 · 2 · ···· n
21.5nn< n · n = 0.5n −→ 0
(n + 1) · (n + 2) · · · ·· 2n22

Already for very small n the ratio is almost zero, but this was to be expected:
The comparison is not fair. More meaningfully, let us compare P -concatenations
against PD paths of an almost identically constrained vehicle, one with L = 2. This
− + −
+ − −
condition is weaker; it allows i+ , i+
1 , i1 , i2 , i2 , . . . , ik , ik , i with i, i1 , . . . , ik ∈ R ,n
k > 1 as a feasible path segment. Let τL=2 denote the number of PD paths which
are feasible in this situation.
Lemma 5 τnL=2 = 3n−1 n! .
Proof We prove this result by induction. For n = 1 we have τ1L=2 = 30 ·1! = 1 which
is clearly true. Now let τnL=2 = 3n−1n! hold for an arbitrary but fixed n ∈ N. We will
iteratively construct a path respecting L = 2. For each stage, given that i ∈ {0, 1, 2}
items are in the vehicle, and k requests are not yet completed, i.e., k destination
nodes are not yet visited, denote by τki the number of different possibilities ton+1
complement the current path from the current node. We seek τ L=2= τn+1
0 : In the
beginning no request is completed and the vehicle is empty.
When the vehicle is empty and k requests are not completed, we have k possibilities to immediately continue the path, i.e., τk0 = k · τk1 . When one item is in thevehicle, we can immediately deliver the item, reducing k by one and making the6

Marco E. Lübbecke

vehicle empty, or we can pick up another item, for which we have k − 1 possibilities. In the latter case, two items are in the vehicle, thus we must deliver precisely
one of them. Then, one item remains in the vehicle, and k is reduced by one, i.e.,τk2 = 2 · τk−1
for any k. More formally, we have1
τn+1
= (n + 1) · τn+1
= (n + 1) · (τn0 + n · τn+1
0
1
2 )=

τn
(n + 1) · (τn0 + 2n · τn1) = (n + 1) · (τn0 + 2n · 0 ) = 3 · (n + 1) · τn0 .
nnHence, by the induction hypothesis and τn0 = τnL=2 we have τn+1
L=2 = 3 (n + 1)! as
claimed. tuLemma 6 limn→∞ τnP /τnL=2 = 0 .

Proof Upper bounding τnP by eliminating the binomial coefficients via
b n2 c bnc 
n  
n 2
n
n
n
n
n
2
2
≤
2
≤
2
2
∑ i
∑ i
∑ i = 2 2 · 2n
i=0
i=0
i=0
√ n n
n
n
n−1
we obtain 2 2 · 2 /3
= 3 · 8 /3 → 0 as claimed. tub n2 c


n−i
≤
2
∑
i
i=0
i



i

When the vehicle capacity is two by definition of the problem situation, the restriction to P -concatenations is not that severe. Still, asymptotically, their fraction
among PD paths with L = 2 vanishes.
6 Error Analysis
What is the influence of our restrictions on the quality of solutions in terms of thepath length? One easily sees that a vehicle restricted to P -concatenations versus avehicle driving general PD paths performs arbitrarily bad. On the other hand, whenrestricting the latter vehicle to L = 2 the situation changes.
Lemma 7 Given the optimal length lL=2 of a PD path with L = 2, and the optimal
length lP of a P -concatenation in G, then lP ≤ 3 · lL=2 and this bound is tight.
Proof For a vehicle with L = 2, consider an optimal PD path R = (i1 , . . . , iK ) in Gof length lL=2 . We think of unit size items loaded into one of two storage holds inthe vehicle. Then, we construct an approximating P -concatenation as follows.
Given R, we know for each item whether it is loaded into storage hold 1 or 2.
Further, from R we have the sequence in which items are optimally served by thevehicle. In our P -concatenation we serve only one item at a time. Start in i 1 , andpickup and immediately deliver the first item which was loaded into storage hold1. Continue serving all items from hold 1 in the order given by R. Return to i 1 , andrepeat this procedure for all items which were loaded into storage hold 2.
In the worst case r + = i1 and r− = iK for some r ∈ R , and ci1 i2 = ciK−1 iK = 0.
Then, the length of this P -concatenation is exactly three times lL=2 . tuNote that we construct an approximating P1 -concatenation, so that, unfortunately, this gives no better approximation guarantee than a TSP approximation.

Combinatorially Simple Pickup and Delivery Paths

7

7 Polynomially Solvable Cases
A natural question in connection with hard optimization problems is to ask forpolynomially solvable special cases. We assume again that we have to visit all nrequests in a concatenation. In the context of the TSP, two research directions areclassical: Special attributes of the cost matrix, and restrictions to special (typicallysparse) graph structures. Balas [2] considers a third class similar in spirit to our approach, viz. constraining the combinatorial variability of a tour. We emphasize the
TSP polynomial time special cases—which are numerous—because they immediately give rise to an analogous statement for P1 -concatenation. Interestingly, when
we drop the TSP component of our problem, the remaining selection of patterns iseasy, and could be used in a heuristic cluster-first, route-second approach.
Proposition 1 A shortest P -concatenation can be found in polynomial time if thesequence of patterns is irrelevant, i.e., all arcs joining two patters have zero weight.
Proof Consider an undirected graph with vertex set V1 ∪V2 := {i | i ∈ R } ∪ {i0 | i ∈R } and edge set E1 ∪E2 ∪E3 := {(i, j) | i 6= j ∈ R }∪{(i0 , j0 ) | i 6= j ∈ R }∪{(i, i0 ) |i ∈ R }, i.e., for each request there exists a node in V1 and a copy in V2 joined byan edge in E3 , and (V1 , E1 ) and (V2 , E2 ) are complete, c.f. Fig. 1. Edges (i, j) ∈ E1
and (i0 , j0 ) ∈ E2 are weighted with the cost of a cheapest of the four patterns in P2
involving requests i and j. Similarly, twice the cost of the P1 pattern for request idefines the weight for (i, i0 ) ∈ E3 .
Let M be a perfect matching in this graph. The edge sets M1 = M ∩ (E1 ∪
E3 ) and M2 = M ∩ (E2 ∪ E3 ), respectively, each define a selection of patterns in
the obvious way. Furthermore, if M is a minimum weight perfect matching, theedge weight of M1 equals that of M2 . Otherwise, either M ∩ E1 or M ∩ E2 would
have greater weight, contradicting the optimality of M. Thus, the weight of M istwice the cost of an optimal selection of patterns. Serving these patterns in any
order gives an optimal solution to the P -concatenation problem. Polynomial timecomputability of M, see e.g., [4], completes the proof. t
u

i

V1

i0

V2

Fig. 1 Sketch of the undirected graph constructed in the proof of Proposition 1

We will now restrict the position of a request within a concatenation, adopting
an interesting idea for the TSP. We follow the lines of the original presentation [2].

8

Marco E. Lübbecke

For a given concatenation, we say that request i precedes request j if and only if
i− is visited before j − , i.e., i is completed not later than j is. Given an integer
1 ≤ k < n, and a linear ordering (1, . . . , n) of the set R of requests, a concatenationis required to fulfill the following condition:
For all i 6= j ∈ {1, . . . , n}, j ≥ i + k =⇒ i precedes j .

(4)

In other words, the position of request i within a concatenation is required to bein the interval [i − k + 1, i + k − 1]. Since for k = 1 the ordering (1, . . . , n) is already
optimal, (4) holds for a relatively small k only when the ordering is sufficiently
close to the optimal one. We state the main result of [2] in our terminology.
Theorem 1 Finding an optimal P1 -concatenation with (4) needs O(k2 2k−2 n) time.
An outline of the proof is as follows. The basic idea is to exploit the restricted
candidate set for a given position in the concatenation in the well known dynamic
programming approach to the TSP. This leads to the construction of a layered
graph G∗ = (N ∗ , A∗ ) with (in our case) n + 2 layers, the layers being the node sets∗Nl∗ , l = 0, . . . , n + 1, where N0∗ and Nn+1
only contain virtual start and end nodes∗of paths. Each node in Nl represents a P1 pattern in position l together with theknowledge about which requests were already visited. Two nodes are adjacent if
and only if the corresponding requests i and j can be served consecutively according to this knowledge and (4). The respective arc is weighted with c i− j+ + c j+ j− .
Balas [2] shows that |Nl∗ | ≤ (k + 1)2k−2 , l = 0, . . . , n + 1, and that the in-degree of
every node is bounded by k. This gives an upper bound on the number of arcs inG∗ . The claimed result then follows from the one-to-one correspondence between
shortest paths in G∗ and optimal P1 -concatenations in G, and the computabilityof such paths in a layered graph in O(|A∗ |). Repeating all the technicalities here
would be unduly. However, Balas’ idea allows for an immediate generalization.
Proposition 2 Construction of an optimal P -concatenation with (4) can be donein O(6 · k4 22k−4 n) time.
Proof Every path in G∗ represents a feasible sequence of requests to be completedwith respect to (4). Given i ∈ N ∗ , denote by req(i) the respective request. When all
patterns in P are allowed, for every two adjacent nodes i and j in G ∗ we have to decide according to which pattern the corresponding requests req(i) and req( j) are to
be served. Actually, given that req(i) precedes req( j), in addition to consecutively
serving two P1 patterns, there are two possible P2 -patterns.
∗∗ , p = 1, 2,
To represent this, we extend G∗ . We make four copies Nl,p,1
and Nl,p,2∗of the node sets Nl∗ , l = 2, . . . , n − 1, two copies N1,p,1, p = 1, 2, of N1∗ , and two∗∗∗copies Nn,p,2, p = 1, 2, of Nn∗ . The nodes in Nl,p,1
and Nl,p,2, will represent beginning and ending, respectively, a P2 pattern in one of its two forms p ∈ {1, 2} in the∗ , p = 1, 2, l = 1, . . . , n − 1, wel th position of a concatenation. In each node set Nl,p,1∗
make |δ(i)| copies from each i ∈ Nl , where δ(i) denotes the set of arcs leaving node
∗ , α ∈ δ(i), and i ∈ N ∗ , p = 1, 2, the respective copies
i. Denote by i1,α ∈ Nl,p,12l,p,2

Combinatorially Simple Pickup and Delivery Paths

9of i ∈ Nl∗ , l = 1, . . . , n. All arcs in A∗ remain intact. Additionally, we introduce thefollowing ten arc sets:A∗a,p =∗∗{(i1,α , j2 ) ∈ Nl,p,1
× Nl+1,p,2| (i, j) ∈ A∗ , α ∈ δ(i)},p = 1, 2∗∗{(i2 , j1,α ) ∈ Nl,p,2
× Nl+1,p,1| (i, j) ∈ A∗ , α ∈ δ(i)},p = 1, 2∗{(i, j1,α ) ∈ Nl∗ × Nl+1,p,1| (i, j) ∈ A∗ , α ∈ δ(i)},p = 1, 2l∈{1,...,n−1}A∗b,p =

l∈{2,...,n−2}A∗c,p =

l∈{0,...,n−2}A∗d,p =
l∈{2,...,n}∗∗{(i2 , j) ∈ Nl,p,1
× Nl+1| (i, j) ∈ A∗ },p = 1, 2

and
A∗e =

∗
∗
{(i2 , j1,α ) ∈ Nl,1,2
× Nl+1,2,1| (i, j) ∈ A∗ , α ∈ δ(i)}l∈{2,...,n−2}

A∗f =

∗
∗
{(i2 , j1,α ) ∈ Nl,2,2
× Nl+1,1,1| (i, j) ∈ A∗ , α ∈ δ(i)} .

l∈{2,...,n−2}

Let us denote by i+ and i− the origin and destination location, respectively, of therequest associated with node i ∈ N ∗ . We keep all arc weights wi j for (i, j) ∈ A∗
unchanged, i.e., wi j = ci− j+ + c j+ j− . We lose no generality in assuming thatp = 1 represents ( j + , i+ , i− , j− ), andp = 2 represents (i+ , j+ , i− , j− ).
∗ , α ∈ δ(i), l = 1, . . . , n − 1, has a unique successor
Observe, that each i1,α ∈ Nl,p,1∗
in Nl+1,p,2 . By analogy with the above, we denote by succ+ (i1,α ) the origin location of the request associated with this successor. This enables us to assign thefollowing weights to the additional arcs:(i1,α , j2 ) ∈ A∗a,1 : c j+ i+ + ci+ i− + ci− j−(i1,α , j2 ) ∈ A∗a,2 : ci+ j+ + c j+i− + ci− j−(i, j1,α ) ∈ A∗c,1 : ci− ,succ+ ( j1,α )(i, j1,α ) ∈ A∗c,2 : ci− j+(i2 , j1,α ) ∈ A∗b,1 : ci− ,succ+ ( j1,α )(i2 , j) ∈ A∗d,1 : ci− j+ + c j+ j−(i2 , j1,α ) ∈ A∗b,2 : ci− j+(i2 , j) ∈ A∗d,2 : ci− j+ + c j+ j−(i2 , j1,α ) ∈ A∗e : ci− j+(i2 , j1,α ) ∈ A∗f : ci− ,succ+ ( j1,α )Figure 2 gives an overall idea of our network construction. From the definition of
our node sets we obtain an upper bound of (k 2 2k−2 )2 (the square of Balas’ bound)∗
for the number of arcs entering any Nl,p,1, p = 1, 2, l = 1, . . . , n − 1. This dominates
the original upper bound on the number of arcs entering the other node sets. There∗ , viz. A∗ , A∗ , A∗ , A∗ , A∗ , A∗ , and theare six sets with arcs entering some Nl,p,1
e
c,1
c,2
f
b,1
b,2
claim follows from Thm. 1. tu

10Marco E. Lübbecke∗N1,1,1A∗a,1∗Nl,1,1A∗c,1∗
Nl,1,2

A∗e
N0∗

N1∗
∗
N1,2,1A∗

Nl∗∗
Nl,2,1∗
Nl,2,2

A∗c,2

A∗b,1

∗
Nl+1,1,1

A∗f
A∗d,1

∗
Nl+1,1,2∗
Nn,2,1

∗
Nl+1

Nn∗

∗
Nn+1

A∗d,2
A∗b,2
A∗a,2

∗
Nl+1,2,1∗
Nl+1,2,2∗
Nn,2,2

Fig. 2 Expansion of Balas’ network constructed in the proof of Thm. 2. Each line represents
the arcs connecting adjacent node sets. A thin line indicates that the corresponding arc set
has cardinality |A∗ |, whereas bold lines indicate arc sets with cardinality |A∗ |2 .

It is interesting to see that the ( j + , i+ , i− , j− ) patterns cause the costly expansion of the network. Without the expansion we would not have a unique successor∗ , α ∈ δ(i), l = 1, . . . , n − 1. Unfortunately, this successorof nodes in i1,α ∈ Nl,p,1
determines which location is to be visited in the pattern first. Thus, we would nothave been able to define arc weights e.g., for arcs in A∗b,1 . Note, however, that for(i+ , j+ , i− , j− ) patterns the first location to be visited is always known when it isgiven which request is to be completed first.
Corollary 1 An optimal concatenation of P1 and (i+ , j+ , i− , j− ) patterns with (4)can be found in time O(5 · k2 2k−2 n).

Proof Again, we construct an expanded network. We let α ≡ 1 and p ≡ 2 in theabove construction for the proof of Prop. 2. This leads to four arc sets, A ∗a,2 throughA∗d,2 , each of which has cardinality |A∗ |. We are able to uniquely define the respective arc weights precisely as above, and the claim follows from Thm. 1. tu
8 Conclusion
We investigate very simple pickup and delivery paths in an analytic way. We introduce small patterns serving exactly one or two requests and concatenate them into
paths. This concept is successfully applied in [19]. In this paper we demonstratethat our restriction drastically reduces the search space of an implicit enumeration
algorithm for finding an optimal PD path. In fact, all exact solution approaches to
the PDP, we are aware of, rely on some dynamic programming scheme. By bounding the prolongation of the path length by our restriction to a factor of three, wehave proven that P -concatenations give, in a sense, a good representation of all PD
paths where at most two requests are simultaneously served.
Acknowledgments This work was done while the author was with the Department of Mathematical Optimization, Braunschweig University of Technology. I wish to thank Thomas

Combinatorially Simple Pickup and Delivery Paths

11

Lindner, Tom Matsui, and Hannes Scheel for helpful discussions. I gratefully acknowledge
the careful reading and constructive suggestions of an anonymous referee of an earlier version of this paper [17].

References
1. R. Anbil, J.J. Forrest, and W.R. Pulleyblank. Column generation and the airline crew
pairing problem. In Proceedings of the International Congress of Mathematicians
Berlin, Extra Volume ICM 1998 of Doc. Math. J. DMV, pages III 677–686, August
1998.
2. E. Balas. New classes of efficiently solvable generalized traveling salesman problems.
Ann. Oper. Res., 86:529–558, 1999.
3. R. Borndörfer, M. Grötschel, F. Klostermeier, and C. Küttner. Telebus Berlin: Vehicle
scheduling in a dial-a-ride system. In N.H.M. Wilson, editor, Computer-Aided Transit
Scheduling, volume 471 of Lecture Notes in Economics and Mathematical Systems,
pages 391–422, Berlin, 1999. Springer.
4. W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and A. Schrijver. Combinatorial
Optimization. John Wiley & Sons, Chichester, 1998.
5. J.R. Daduna and A. Wren, editors. Computer-Aided Transit Scheduling, volume 308 of
Lecture Notes in Economics and Mathematical Systems. Springer, 1987.
6. G. Desaulniers, J. Desrosiers, A. Erdmann, M.M. Solomon, and F. Soumis. The VRP
with pickup and delivery. In P. Toth and D. Vigo, editors, The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, chapter 9. SIAM,
Philadelphia, 2001.
7. M. Desrochers, J.K. Lenstra, M.W.P. Savelsbergh, and F. Soumis. Vehicle routing withtime windows: Optimization and approximation. In Golden and Assad [13], pages 65–
84.
8. J. Desrosiers, Y. Dumas, M.M. Solomon, and F. Soumis. Time constrained routing andscheduling. In M.O. Ball, T.L. Magnanti, C.L. Monma, and G.L. Nemhauser, editors,
Network Routing, volume 8 of Handbooks in Operations Research and Management
Science, pages 35–139. North-Holland, Amsterdam, 1995.
9. J. Desrosiers, Y. Dumas, and F. Soumis. The multiple vehicle dial-a-ride problem. In
Daduna and Wren [5], pages 15–27.
10. J. Desrosiers, G. Laporte, M. Sauvé, F. Soumis, and S. Taillefer. Vehicle routing withfull loads. Comput. Oper. Res., 15(3):219–226, 1988.
11. Y. Dumas, J. Desrosiers, and F. Soumis. The pickup and delivery problem with time
windows. European J. Oper. Res., 54:7–22, 1991.
12. K. Fagerholt and M. Christiansen. A combined ship scheduling and allocation problem.
J. Opl. Res. Soc., 51(7):834–842, 2000.
13. B.L. Golden and A.A. Assad, editors. Vehicle Routing: Methods and Studies, volume 16of Studies in Management Science and Systems. North-Holland, 2nd edition, 1991.
14. I. Ioachim, J. Desrosiers, Y. Dumas, M.M. Solomon, and D. Villeneuve. A request
clustering algorithm for door-to-door handicapped transportation. Transportation Sci.,
29(1):63–78, 1995.
15. D. Klabjan, E.L. Johnson, G.L. Nemhauser, E. Gelman, and S. Ramaswamy. Solving
large airline crew scheduling problems: Random pairing generation and strong branching. Comput. Optim. Appl., 20(1):73–91, 2001.
16. D.E. Knuth. The Art of computer programming, Vol. 1: Fundamental Algorithms. Series
in Computer Science and Information Processing. Addison-Wesley, Reading, 1969.

12

Marco E. Lübbecke

17. M.E. Lübbecke. Engine Scheduling by Column Generation. PhD thesis, Braunschweig
University of Technology, Cuvillier Verlag, Göttingen, 2001.
18. M.E. Lübbecke and U.T. Zimmermann. Computer aided scheduling of switching engines. In W. Jäger and H.-J. Krebs, editors, Mathematics—Key Technology for the
Future: Joint Projects Between Universities and Industry, pages 690–702. SpringerVerlag, Berlin, 2003.
19. M.E. Lübbecke and U.T. Zimmermann. Engine routing and scheduling at industrial
in-plant railroads. Transportation Sci., 37(2):183–197, 2003.
20. M. Rönnqvist, A. Westerlund, and D. Carlsson. Extraction of logs in forestry using
operations research and geographical information systems. In Proceedings of the 32nd
Hawaii International Conference on System Sciences. IEEE, 1999.
21. M.W.P. Savelsbergh and M. Sol. The general pickup and delivery problem. Transportation Sci., 29(1):17–29, 1995.
22. M. Sol. Column Generation Techniques for Pickup and Delivery Problems. PhD thesis,
Eindhoven University of Technology, 1994.