An Exact Algorithm for a Practical Pickup and Delivery Problem
Lucas Sippel, Michael A. Forbes, Joseph Menesch
School of Mathematics and Physics, The University of Queensland, Brisbane, Australia
uqlsippe@uq.edu.au, m.forbes@uq.edu.au, joseph.menesch@uqconnect.edu.au
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 4, 2022
Keywords: Vehicle routing, Fragments, Learning

1

Introduction

Fragment based methods have been used in Alyasiry et al. (2019) and Rist & Forbes (2021)
to solve the Pickup and Delivery Problem with Time Windows and the Dial-a-Ride Problem.
We propose a fragment based branch-and-cut algorithm for the Practical Pickup and Delivery
problem (PPDP) from Xu et al. (2003).
Xu et al. (2003) state that the PPDP “involves a set of practical complications that arecommonly seen in practice but have received little attention in the vehicle routing literature".
The most important of these are the existence of multiple time windows per request and theAmerican hours of service (HOS) constraints. These require a driver to have a 10 hour rest
minimum after at most 11 hours driving or 14 hours working. Also since Xu et al. (2003)’s study
was published, another HOS constraint requiring drivers to take a half hour break at most every
eight hours has been introduced, which we consider.
Xu et al. (2003) use a forward labelling dynamic program (DP) to construct negative reduced
cost vehicle routes in a price-and-branch heuristic. However, high dimensional labels are needed
to handle the HOS constraints. So the DP is slow for instances up to 200 requests, and intractable
for larger instances. Thus, the exact column generation DP is replaced by two heuristics for thepricing problems in larger instances. The set partitioning integer program is solved on a restrictedsubset of the routes once column generation terminates.
The proposed fragment based branch-and-cut algorithm has no need for column generation,
but instead uses a DP to schedule rests and breaks for routes retrospectively. The lifted feasibility
cuts of Rist & Forbes (2021) are used to eliminate routes when rests and breaks cannot be feasibly
scheduled. When they can, optimality cuts are used to incorporate the extra waiting cost into
the objective. Using a schedule DP and optimality cuts in a fragment based algorithm comprise
two novelties of this work. Combined, they enable the first exact algorithm for the PPDP. The
algorithm is also the first exact method for a vehicle routing problem with HOS constraints, thatconsiders multiple time windows per request, and a cost in the objective function for each hourvehicles are active. Computational results demonstrate the algorithm’s ability to solve instanceswith up to 700 requests. We also describe a supervised learning model used to restrict the set offragments, when fragment enumeration becomes intractable.
TRISTAN XI Symposium

Original abstract submittal

Lucas Sippel, Michael A. Forbes, and Joseph Menesch22

Methodology

A PPDP instance with n requests has locations V = {1, ..., 2n}, where i ≤ n is the pickup of
request i and i + n is the delivery. We denote the set of pickups by P . For all i, j ∈ V , dij is the
distance and tij is the travel time between i and j. Travel times are multiples of half an hoursuch that the time windows of each i ∈ V can be converted to a discrete set of time points T Pi .

2.1

Fragments

Generating all feasible routes for even moderately sized instances is intractable. In the same way
as Alyasiry et al. (2019), we circumvent this by generating fragments instead. Fragments aresequences of pickups and deliveries where the vehicle starts empty, ends empty, is never intermediately empty and time window, capacity, pairing, precedence and HOS constraints are satisfied.
We also create extended fragments by connecting each fragment to every feasible next pickup.
Since fragments are shorter than routes, there are typically far fewer of them, and any route can beconstructed by concatenating fragments. For example, a route such as (p1 , p2 , d2 , d1 , p3 , d3 , p4 , d4 )is constructed with extended fragments (p1 , p2 , d2 , d1 , p3 ) and (p3 , d3 , p4 ), and fragment (p4 , d4 ).

2.2

Timed Network

We build a timed network from the fragments. The timed network has timed nodes for eachpickup p ∈ P , (p, t), where t ∈ T Pp . We denote the set of timed nodes P̄ . Consecutive pairs oftimed nodes for the same pickup are connected by waiting arcs. We denote the set of waitingarcs A. Each a ∈ A starts at timed node a− = (pa , ea ) and ends at timed node a+ = (pa , fa ).
We then create timed fragments from each fragment. Each timed extended fragment ω connects
a timed node (i, t) to another timed node (j, t + ∆ω ), where ∆ω is the minimum duration of thetimed fragment sequence calculated by the schedule DP. Timed fragments with no extension do
not connect to a succeeding timed node since they represent the end of a route. We denote theset of timed fragments which include pickup p ∈ P by Ωp , and let Ω = ∪p∈P Ωp . Ωf is the set of
timed fragments originating from fragment f. Each ω ∈ Ω has corresponding fragment fω andstarts at timed node ω − . Timed extended fragments ω end at timed node ω + .
We then define the relaxed fragment mixed integer program, RF. RF has binary variables xω
for each ω ∈ Ω, ya for each a ∈ A, and zj for each j ∈ P̄ which are one if and only if a route
starts at j. Variables θp for each p ∈ P are used to implement the optimality cuts describedlater. RF is thus
X
X
X
X
min
F · zj +β · (fa − ea ) · ya +cω · xω +β · θp
(1)
a∈A

j∈P̄

ω∈Ω

p∈P

subject tozj +Xa∈A|a+ =j

ya +

X

xω −

ω∈Ω|ω + =j

X

Xa∈A|a− =jxω = 1ya −Xxω = 0∀j ∈ P̄ ,(2)∀p ∈ P,(3)∀ω ∈ Ω, a ∈ A, j ∈ P̄ ,(4)

∀p ∈ P,(5)ω∈Ω|ω − =jω∈Ωpxω , ya , zj ∈ {0, 1}
θp ≥ 0where F is the fixed route cost and β is the waiting cost per hour. For timed fragment ω withcorresponding fragment
is the sum of distance and waiting costs incurred by
P fω = (i1 , ..., il ), cωP
l−1
the vehicle, cω = α l−1
d
+
β(∆
−
ω
j=1 ij ij+1
j=1 tij ij+1 ) where α is the per mile driving cost. So
RF minimises the total fixed, distance and waiting costs, subject to flow conservation constraints(2), coverage constraints (3), binary constraints (4), and non-negativity constraints (5).
TRISTAN XI Symposium

Original abstract submittal

Lucas Sippel, Michael A. Forbes, and Joseph Menesch3

Routes are represented by chains of timed fragments at integer solutions to RF, however,chains may correspond to sequences for which rests and breaks cannot be scheduled. These are
eliminated with lifted lazy constraints as in Rist & Forbes (2021).

2.3

Optimality Cuts

Suppose a route in an integer solution to RF is represented by the chain of timed fragments,(ω1 , ..., ωl ). The route may require extra rests and breaks not included in the timed fragment
schedules, since these are calculated assuming timed fragments start with zero accumulated
working and driving hours. To handle this, variables θp for each pickup p ∈ P model the extra
waiting time of a route starting at p in the current integer solution. The extra waiting time, E,
is calculated via the schedule DP. If p is the route’s first pickup, we use the optimality cutθp ≥ E ·Xzj +j∈{p}×T Pp

l
X
X


xω − l ,(6)

i=1 ω∈Ωfω

i

to include the extra waiting cost in the objective.

3

The Schedule DP

We update Goel & Kok (2012)’s schedule DP to handle the additional HOS constraint mentioned
in the introduction. The schedule DP calculates the minimum completion time for some request
sequence (i1 , ..., il ) and start time t∗ , given rests and breaks must be scheduled according to
HOS constraints. It returns ∞ if the sequence cannot satisfy the HOS constraints. The DP isused to assess the feasibility of fragment sequences during their enumeration, and to calculate
the minimum completion time of each timed fragment given their start time. Also, it is used toassess the feasibility of routes and separate optimality cuts at integer solutions to RF.

4

Learning Model

In large instances with high request spatial density, enumerating time fragments becomes impossible due to the memory limit. We propose a simple supervised learning model which restricts
the set of fragments and hence |Ω|. A sequence of pickups and deliveries f′ = (i1 , ..., il ) is apartial fragment if there exists a fragment f = (i∗1 , ..., i∗m ) such that ij = i∗j for j = 1, ..., l. We
let Xf′ be the set of pickups p for which (i1 , .., il , p) is also a partial fragment. Enumerating
fragments involves repeatedly extending partial fragments f′ to all p ∈ Xf′ .
For each partial fragment f′ , instead of extending to all pickups in Xf′ , we can extend to somesubset Rκ (f′ ) ⊆ Xf′ where κ is a fixed integer and |Rκ (f′ )| = κ. To construct Rκ (f′ ) we requirefeature vector v(f′ , p) ∈ Rh for each p ∈ Xf′ which depends on the partial fragment f′ and thecandidate pickup extension p. Firstly, we obtain an ordering, p(1) , ..., p(|Xf′ |) , of the pickups in
Xf′ by arranging them in ascending order with respect to a linear combination of the features,u(f′ , p|a) = a⊤ v(f′ , p), where a ∈ Rh . Then we let Rκ (f′ ) = Rκ (f′ |a) = {p(1) , ..., p(κ) } ⊆ Xf′ .
Choosing weight vector a involves collating N partial fragment next pickup pairs, {(f′j , pj )}N
j=1 ,from optimal solutions to small, randomly generated instances. We use a loss function that counts
the number of times pj ∈/ Rκ (f′j |a),l(a|{(f′j , pj )}Nj=1 ) = N −N
X

I(pj ∈ Rκ (f′j |a)).

(7)

j=1

Hence, to find a we solve
min l(a|{(f′j , pj )}Nj=1 ).

a∈Rh

TRISTAN XI Symposium(8)
Original abstract submittal

Lucas Sippel, Michael A. Forbes, and Joseph Menesch54Computational Results

Table 1 gives summary results for the proposed algorithm on instances generated according to
Xu et al. (2003)’s procedure, except we restrict problems to one vehicle and carrier type with norequest incompatibilities. Column Size gives the side length of the square region which locations
are distributed in. Values given in each row are averages over 15 instances.
The Ω column gives the number of timed fragments enumerated. The T1 column gives timed
fragment enumeration duration in seconds. Column T2 gives solve times, which are limited to7200 seconds. Bold font indicates that all 15 instances are solved to optimality. The numbers
in superscript give the number of instances where timed fragments can be enumerated, and thenumber of instances solved to optimality respectively. Column Gap is calculated as U B−LB
LB
where U B is the best objective value found and LB is the largest lower bound found within thetime limit when solving exactly. The Ω̂ Prop. column gives the proportion of timed fragments
enumerated when the extension restriction model is used with h = 3 and κ = 3. Finally, column
ˆ is calculated in the same way as column Gap, except U B is replaced with UˆB which is theGapbest objective value found when using the extension restriction model.
Instances with up to 300 requests and high spatial density are solved to optimality. It is worth
noting that Xu et al. (2003) only give near optimal solutions for similarly sized instances withlower spatial density. Our algorithm can also solve larger instances with lower spatial density to
optimality. Finally, the extension restriction model achieves near optimal solutions with fewer
timed fragments, especially for problems with high spatial density. Hence, we infer that near
optimal solutions can be reliably obtained for instances with n ≥ 400 and a Size of 800.
Table 1 – Computational Results for Randomly Generated Instances
n

Size

Ω

T1

T2

Gap

Ω̂ Prop.

ˆ
Gap

50

800
1200
1600
800
1200
1600
800
1200
1600
800
1200
1600
800
1200
1600
1200
1600
1200
1600
1200
1600

5161.52434.11385.037807.7
9918.54934.3329574.5
52497.021907.1
1921789.9
184671.557035.65017686.6
432336.1
114166.9936553.5212178.4
1492127.7
346486.3
3062339.8
521197.7

0.9
0.7
0.6
5.5
2.6
2.1
48.2
12.1
9.0
295.9
37.0
21.4
814.7
90.7
41.9
183.5
71.4
307.6
117.6
647.5
178.1

1.3
0.5
0.3
21.8
2.1
1.1

0.00000.00000.00000.00000.00000.00000.00180.00000.00000.00610.00000.00000.02060.00020.00000.00100.00000.00190.00000.00460.0001

0.77
0.94
0.98
0.50
0.82
0.93
0.25
0.65
0.83
0.13
0.46
0.74
0.09
0.37
0.67
0.29
0.58
0.26
0.53
0.19
0.47

0.00150.00040.00030.00550.00310.00160.01210.00620.0041
0.02150.00970.00620.02990.01450.00980.01550.01250.01850.01330.02300.0154

100

200

300

400

500
600
700

2475.1(15,7)24.1
4.5
5684.4(15,2)
107.0
15.3
7261.5(5,0)
1398.4(15,12)38.0
3679.6(15,7)
124.2
5166.9(15,1)
565.9
6499.0(12,1)
1202.7(15,13)

References
Alyasiry, Ali Mehsin, Forbes, Michael, & Bulmer, Michael. 2019. An Exact Algorithm for the Pickup and
Delivery Problem with Time Windows and Last-in-First-out Loading. Transportation science, 53(6),1695–1705.
Goel, Asvin, & Kok, Leendert. 2012. Truck Driver Scheduling in the United States. Transportation
science, 46(3), 317–326.
Rist, Yannik, & Forbes, Michael A. 2021. A New Formulation for the Dial-a-Ride Problem. Transportation
science, 55(5), 1113–1135.
Xu, Hang, Chen, Zhi-Long, Rajagopal, Srinivas, & Arunapuram, Sundar. 2003. Solving a Practical
Pickup and Delivery Problem. Transportation science, 37(3), 347–364.

TRISTAN XI Symposium

Original abstract submittal