ReOpt: an Algorithm with a Quality Guaranty
for Solving the Static Relocation Problem
Sahar Bsaybes2? , Sven O. Krumke1 , Alain Quilliot2 , Annegret K. Wagler2 , and
Jan-Thierry Wegener2?

arXiv:1511.02751v1 [] 9 Nov 2015

1

University of Kaiserslautern (Department of Mathematics)
Kaiserslautern, Germany
krumke@mathematik.uni-kl.de
2
Université Blaise Pascal (Clermont-Ferrand II)
Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes
BP 10125, 63173 Aubière Cedex, France
{bsaybes,quilliot,wagler,wegener}@isima.fr

Abstract. In a carsharing system, a fleet of cars is distributed at stations in an urban area, customers can take and return cars at any time
and station. For operating such a system in a satisfactory way, the stations have to keep a good ratio between the numbers of free places and
cars in each station. This leads to the problem of relocating cars between
stations, which can be modeled within the framework of a metric task
system. In this paper, we focus on the Static Relocation Problem, where
the system has to be set into a certain state, outgoing from the current
state. We present a combinatorial approach and provide approximation
factors for several different situations.

1

Introduction

Carsharing is a modern way of car rental, attractive to customers who make only
occasional use of a car on demand. Carsharing contributes to sustainable transport as less car intensive means of urban transport, and an increasing number
of cities all over the world establish(ed) such services. Hereby, a fleet of cars is
distributed at specified stations in an urban area, customers can take a car at
any time and station and return it at any time and station, provided that there
is a car available at the start station and a free place at the final station. To
ensure the latter, the stations have to keep a good ratio between the number
of places and the number of cars in each station. This leads to the problem of
balancing the load of the stations, called Relocation Problem: an operator has to
monitor the load situations of the stations and to decide when and how to move
cars from “overfull” stations to “underfull” ones.
Balancing problems of this type occur for any car- or bikesharing system, but
the scale of the instances, the time delay for prebookings and the possibility to
?

This work was founded by the French National Research Agency, the European
Commission (Feder funds) and the Région Auvergne within the LabEx IMobS3.

move one or more vehicles in balancing steps differ. We consider an innovative
carsharing system, where the cars are partly autonomous, which allows to build
wireless convoys of cars leaded by a special vehicle, such that the whole convoy
is moved by only one driver (cf. [6]).
This setting is different from usual carsharing, but similar to bikesharing,
where trucks can simultaneously load and move several bikes during the relocation process [3,4,5]. The main goal is to guarantee a balanced system during
working hours (dynamic situation as in [5,8,9,11,10]) or to set up an appropriate
initial state for the morning (static situation as in [4,10]). Both, the dynamic and
the static versions are known to be N P-hard [1,2,4,12], and different heuristic
approaches have been developed, e.g., partitioning the problem into subproblems
by discrete particle swarm optimization [7], by reducing the search space [11],
using variable neighborhood search [13], or partitioning the problem into subproblems with clustering techniques [14].
In this paper, we address the static situation, where the system has to be set
into a certain state z T , outgoing from the current state z 0 , within a given time
horizon. [0, T ]
In Section 2, we model different variants of the Static Relocation Problem
within the framework of a (quasi) metric task system, where tasks consist in
moving cars out of “overfull” stations (with zv0 > zvT ) into “underfull” stations
(with zv0 < zvT ).
In the following, we present two approaches to solve the Static Relocation
Problem, an exact integer programming based method and a combinatorial approximation algorithm.
In Section 3, we present an exact approach to solve this problem using coupled
flows in time-expanded networks, where the flow of cars is dependent from the
flow of drivers since cars can only be moved in convoys. Due to the involved flow
coupling constraint, all variants of the problem require very long computation
times (see also Section 6) which motivated the study of a combinatorial algorithm
to solve the problem in reasonably short time.
In Section 4, we propse such an algorithm that firstly matches tasks to generate transport requests, subsequently solves a Pickup and Delivery Problem,
and iteratively augments the transport requests and resulting tours (Section 4).
This algorithm has an approximation factor based on the convoy size in several
different situations (Section 5). Parts of these results appeared without proofs
in [10].
We finally provide some computational results for both approaches (Section 6), and close with some remarks and future lines of research (Section 7).

2

Problem description and model

We model the Relocation Problem in the framework of a metric task system.
By [10], the studied carsharing system can be understood as a discrete eventbased system, where the system components are the stations v1 , . . . , vn , each
having an individual capacity cap(vi ), a system state z t ∈ Zn specifies for each
2

station vi the number of cars zit at a time point t ≤ T within a time horizon [0, T ]
and z t changes when customers or convoy drivers take or return cars at stations.
An operator monitors the evolution of system states over time and decides
when and how to move cars between the stations, in order to avoid infeasible
system states z t with zvt > cap(vi ) or zvt < 0 for some station v. More precisely,
a task is defined by τ = (v, x) where x ∈ Z \ {0} cars are to pickup (if x > 0) or
to deliver (if x < 0) at station v within the time-horizon [0, T ].
In the static situation, we consider a start state z 0 and a destination state z T .
Then the tasks are induced by the differences between these two states, i.e, for
every station v ∈ V with zv0 6= zvT we have a task (v, zv0 − zvT ). A station vo with
zv0o − zvTo > 0 is called an overfull station, a station vu with zv0u − zvTu > 0 is called
an underfull station, and a station vb with zv0o − zvTu = 0 is called an balanced
station.
Since our considered carsharing system is located in an urban area, due
to one-way streets, the distances between two stations v and v 0 may not be
symmetric, i.e., the distance from v to v 0 may differ from that from v 0 to v.
Furthermore, due to the traffic situation, the travel times also may vary. In order
to represent the one-way streets (or different travel times) it is suitable to encode
the urban area where the carsharing system is running as a (quasi) metric space 3
M = (V, d) induced by a directed weighted graph G = (V, A, cap, w), where the
nodes correspond to stations, arcs to their physical links in the urban area, node
weights to the station’s capacities, and the edge weights w : E → R+ determine
the distance d between two points v, v 0 ∈ V as length of a shortest directed path
from v to v 0 .
All drivers begin and end their work at the same location, a so-called depot. A
depot is represented in V by a distinguished origin vD ∈ V . In larger carsharing
systems, there are usually several depots VD distributed within the urban area.
Especially when a driver lives near a depot, he may prefer to start and end its
tour in the same depot. Furthermore, this ensures that always the same number
of trucks are located in the depots. However, in order to decrease the total
distances traveled by the drivers, it may be suitable for the operators of the
carsharing system that the drivers start and end their tours in different depots.
The number of drivers starting in depot vD ∈ VD is represented by a natural
number ZvDD ; the total number of available drivers is denoted by k = |Z D |.
This together yields a (quasi) metric task system, a pair (M, T ) where M =
(V, d) is the above metric space and T a set of tasks, as suitable framework to
embed the tours for the convoys. A driver able to lead a convoy plays the role
of a server. Each server has capacity L, corresponding to the maximum possible
number of cars per convoy; several servers are necessary to serve a task τ = (v, x)
if |x| > L holds.
3

A quasi metric space (M, d) contains a set M and a distance function d : M ×M → R
so that for all x, y, z ∈ M holds: (i) d(x, y) ≥ 0 (non-negativity), (ii) d(x, y) = 0 iff
x = y (identity of indiscernibles), (iii) d(x, z) ≤ d(x, y)+d(y, z) (triangle inequality).
Laxly said, a quasi metric is a “metric” where the symmetry condition is dropped.

3

More precisely, we define the following. An action for driver j is a 4-tuple
α = (j, v, t, x), where j ∈ {1, . . . , k} specifies the driver driv(α) performing the
action, v ∈ V specifies the station loc(α), t ∈ [0, T ] is the time t(a) when the
action is performed, and x ∈ Z the number of cars ∆x(α) to be loaded (if x > 0)
or unloaded (if x < 0). Hereby, the capacity of the convoy must not be exceeded,
i.e., we have |x| ≤ L. We say that an action is performed (by a driver) if he loads
(resp. unloads) |x| cars at v. An action is called pickup action if x > 0, drop
action if x < 0, and empty if x = 0.
A move from one station to another is m = (j, v, tv , v 0 , tv0 , xm ), where j ∈
{1, . . . , k} specifies the driver driv(m) that has to move from the origin station
orig(m) = v ∈ V starting at time dep(m) = tv to destination station dest(m) =
v 0 ∈ V arriving at time arr(m) = tv0 , and a load of `oad(m) = xm cars. Hereby,
we require that
(i) 0 ≤ `oad(m) ≤ L,
(ii) tv0 − tv = d(v, v 0 ), and
(iii) from orig(m) 6= dest(m) follows arr(m) = dep(m) + d(orig(m), dest(m)).
A move (j, v, tv , w, tw , xm ) with v = w is called waiting move.
A tour is an alternating sequence Γ = (m1 , α1 , m2 , α2 , . . . , αn−1 , mn ) of
moves and actions with
(i)
(ii)
(iii)
(iv)

driv(m1 ) = driv(α1 ) = · · · = driv(αn−1 ) = driv(mn ),
dest(mi ) = loc(αi ) = orig(mi+1 ),
arr(mi ) = t(αi ) = dep(mi+1 ), and
`oad(mi+1 ) = `oad(mi ) + ∆x(αi ).

By act(Γ ) we denote the sequence containing the actions of the tour Γ , i.e.,
act(Γ ) = (α1 , . . . , αn−1 ), and by mov(Γ ) we denote the sequence containing the
moves of the tour Γ , i.e., mov(Γ ) = (m1 , . . . , mn ).
The length of a tour corresponds to the distance traveled by the driver.
Several tours are composed to a transportation schedule. A collection of tours
{Γ1 , . . . , Γk } is a feasible transportation schedule S for (M, T ) if
(i) every driver has exactly one tour,
(ii) each task τ ∈ T is served (i.e., for every task τ = (v, x), the number of cars
picked up (resp. dropped) at station v sum up to x),
(iii) all system states z t are feasible during the whole time horizon [0, T ].
The total tour length of a transportation schedule is the sum of the lengths of its
tours. Condition (iii) requires that, besides the canonical precedences between a
move mi ∈ Γ and its successor move mi+1 in the same tour Γ , also dependencies
between tours are respected if preemption is used, i.e., if a car is transported in
one convoy from its origin to an intermediate station, and from there by another
convoy to its destination. This causes dependencies between tours, since some
moves cannot be performed before others are done without leading to infeasible
intermediate states (the reason why tours may contain waiting moves). More
precisely, an action α ∈ Γ induces a precedence, avoiding a system state z t with
zvt < 0 (resp. cap(v) < zvt ), if one of the following conditions is true:
4

• α drops cars at an overfull station,
• α picks up cars at an underfull station,
• α drops or picks up cars at a balanced station.
Note, it is possible that the action which is dependent on α may not be uniquely
determinable. Furthermore, an action with a dependency to α does not necessarily fulfill any of the three conditions.
We call a transportation schedule non-preemptive if there are no precedences
between moves of different tours, and preemptive otherwise. When every driver
starts and ends its tour in the same depot, we say it is a transportation schedule
with backhaul. Otherwise, we call it a transportation schedule without backhaul.
Our goal is to construct non-preemptive transportation schedules of minimal
total tour length for the Relocation Problem in the static situation.
Problem 1 (Static Relocation Problem (M, z 0 , z T , Z D , k, L)). Given a (quasi)
metric space M = (V, d) induced by a (directed) weighted graph G = (V, E, w, cap),
start state z 0 ∈ N|V | , destination state z T ∈ N|V | with |z 0 | = |z T | and time
horizon [0, T ], k servers of capacity L and ZvDd drivers start at depot vd ∈ VD ,
find a non-preemptive transportation schedule of minimal total tour length for
the metric task system (M, T ) where T consists of the tasks τ = (vi , zi0 − ziT )
for all vi with zi0 6= ziT .
Hereby, we further classify the Static Relocation Problem into the following
problems and their compositions:
• Symmetric Static Relocation Problem: if M is a metric space,
• Asymmetric Static Relocation Problem: if M is a quasi metric space,
• Static Relocation Problem with backhaul: if the solution is a transportation
schedule with backhaul, and
• Static Relocation Problem without backhaul: if the solution is a transportation schedule without backhaul.

3

Min-Cost Flows in Time-Expanded Network

In this section, we give an exact approach for the Static Relocation Problem
(M, z 0 , z T , Z D , k, L) without preemption by defining a time-expanded network
with coupled flows: car and driver flows. Hereby, we firstly describe the approach
for the Static Relocation Problem with backhaul (Sections 3.1–3.3). Afterwards,
in Section 3.4, we show how this approach can be modified in order to solve the
Static Relocation Problem without backhaul.
We consider a (quasi) metric space M = (V, d) induced by a (directed)
weighted graph G = (V ∪ VD , E, w, cap) representing the set of stations V , a
set of depots VD , the road (or logical) connections E between them, driving
times w : E → N, and the (quasi) metric d induced by the shortest path distances in G. In addition, there are per unit costs costc and costd for moving cars
and drivers within G. The task set T consists of the tasks τ = (v, zv0 − zvT ) for
all v with zv0 6= zvT . The output is a preemptive transportation schedule for the
metric task system (M, T ), the objective is to minimize its total tour length.
5

For that, we build a directed graph GT = (VT , AT ), with AT = AH ∪AL , as a
time-expanded version of the original network G. For each 1 ≤ j ≤ k, the drivers
and their convoys will form flows Fj and fj through GT which are coupled in
the sense that on those arcs a ∈ AL used for moves of convoys, we have the
condition fj (a) ≤ L · Fj (a) reflecting the dependencies between the two flows.
3.1

Time-expanded network GT

We build a time-expanded version GT = (VT , AT ) of the original network G.
The node set VT is constructed as follows: for each station and each depot v ∈
V and each time point t in the given time horizon [0, T ], there is a node (v, t) ∈ VT
which represents station/depot v at time t.
The arc set AT = AH ∪ AL of GT is composed of two subsets:
• AH contains, for each station v ∈ V of the original network and each t ∈
{0, 1, . . . , T − 1}, the holdover arc connecting (v, t) to (v, t + 1).
• AL contains, for each edge (v, v 0 ) of G and each point in time t ∈ {0, . . . , T }
such that t + d(v, v 0 ) ≤ T , the relocation arc from (v, t) to (v 0 , t + d(v, v 0 )).
Note, due to the identity of indiscernibles (i.e., d(v, v 0 ) = 0 iff v = v 0 ) it follows
that the time-expanded network GT is acyclic by construction. Furthermore, GT
is constructed the same way, regardless whether the original network is directed
or undirected.
3.2

Flows in GT

On the relocation arcs of GT , we define for each driver i a driver flow Fi as
well as a car flow fi which represents the convoy of this driver. On the holdover
arcs of GT , we define a driver flow Fi for each driver but only one car flow f .
We specify the capacities as well as the costs for each arc with respect to the
different flows.
A flow on a relocation arc corresponds to a (sub)move in a tour, i.e., some cars
are moved by drivers in a convoy from station v to another station v 0 . Hereby,
the stations can be used to pick up or to drop cars, or simply to transit a node
(when a driver/convoy passes the station(s) on its way to another station). A
relocation arc from (v, t) to (v 0 , t + d(v, v 0 )) has capacity 1 for each of the driver
flow Fi , 1 ≤ i ≤ k. In order to ensure that cars are moved only by drivers and
only in convoys of capacity L, we require that
fi (a) ≤ L · Fi (a) for all a ∈ AL .

(1)

Thus, the capacities for the car flows fi on the relocation arcs are not given by
constants but by a function. Note that due to these flow coupling constraints,
the constraint matrix of the network is not totally unimodular (as in the case
of uncoupled flows) and therefore solving such problems becomes hard. From
Equation (1) it directly follows that fi (a) ≤ L holds for all relocation arcs
a ∈ AL .
6

Since we consider transportation schedules without preemption, we must
ensure that cars are not exchanged between convoys. Furthermore, we have to
ensure that there is no “tour internal preemption”, i.e., a tour drops a car at one
station and later picks it up again. Inner preemption and preemption between
tours can be avoided by ensuring that cars are only picked up at overfull stations
and dropped at underfull stations. This means that there are more cars in a
convoy leaving an overfull station than entering the station. Analogously, there
are more cars in a convoy entering an underfull station than leaving the station,
and in balanced stations the number of cars entering the station is equal to the
number of cars leaving the station. Thus, one has to ensure that the following
constraints hold for every 1 ≤ i ≤ k
X

for all overfull stations vo ∈ VO

fi (a),

and all 0 < t < T ,

−
(vo ,t)
a∈δL

+
(vo ,t)
a∈δL

X

X

fi (a) ≥

+
a∈δL
(vu ,t)

X

X

fi (a) ≤

for all underfull stations vu ∈ VU

fi (a),

and all 0 < t < T ,

−
a∈δL
(vu ,t)

X

fi (a) =

+
(vb ,t)
a∈δL

for all balanced stations vb ∈ VB

fi (a),

and all 0 < t < T ,

−
(vb ,t)
a∈δL

(2)

(3)

(4)

+
−
where δL
(v, t) denotes the set of incoming relocation arcs of (v, t), and δL
(v, t)
denotes the set of outgoing relocation arcs of (v, t). Note, that the sums in these
equations are of a technical nature. In fact, in each of these equations there is
at most one summand positive while all other are zero. However, since we do
not know in advance which one is positive, we have to sum over all incoming
resp. outgoing relocation arcs of a node.
The costs for the driver flows on a relocation arc a correspond to the distance
traveled, i.e., if a corresponds to the edge (v, v 0 ) ∈ E the costs correspond to
w(a) := w(v, v 0 ).
A flow on a holdover arc corresponds to cars/drivers remaining at the station in the time interval [t, t + 1]. Since we do not allow precedences between
tours, a car is dropped only at underfull stations and only picked up from overfull stations; at balanced stations, cars are neither picked up nor dropped (see
constraints (2)–(4)). Therefore, we define only one car flow f on the holdover
arcs. Furthermore, it follows from (2)–(4) that at an overfull station the number
of cars is non-increasing over time, at an underfull station the number of cars is
non-decreasing over time, and at balanced stations the number of cars remains
equal all the time. Thus, it holds for every reachable system state z

zv0 ≥ zv ≥ zvT ,
zv0
zv0

≤ zv ≤
= zv =

zvT ,
zvT ,

if v is an overfull station,
if v is an underfull station,
if v is a balanced station.

Since z 0 and z T are feasible system states by definition, this implies that every
reachable system state z is feasible as well. Thus, capacities are not needed for
7

holdover arcs with respect to the car flow f . For each driver flow Fi , 1 ≤ i ≤ k,
we set a capacity of 1 on the holdover arcs. Moreover, the cost for all flows on
such arcs are zero.
With the help of Z D , we can assign a depot to each driver. For that, we set
= 1 if driver i starts (and ends) its tour in the depot vD ∈ VD , and Bvi D = 0
otherwise.
Bvi D

To correctly initialize the system, we use the nodes (v, 0) ∈ VT as sources
for both flows and set their balances accordingly to the initial numbers of cars
at station v and time 0 and locate the drivers at their depot vD ∈ VD , i.e., the
sum of the car flow values on all outgoing arcs of (v, 0) is set to zv0 , and for each
driver i, 1 ≤ i ≤ k, the sum of the driver flow values on all outgoing arcs of
(vD , 0) is set to Bvi D .
For all internal nodes (v, t) ∈ VT with 0 < t < T , we use flow conservation
constraints for the car flows f and fi , i.e.,

f ((v, t − 1), (v, t)) +

X
+
a∈δL
(v,t)

k
X

fi (a) = f ((v, t), (v, t + 1)) +

i=1

X
−
a∈δL
(v,t)

k
X

fi (a),

i=1

and the standard flow conservation constraints for each driver flows Fi , i.e.,
X

Fi (a) =

a∈δ − (v,t)

X

Fi (a),

a∈δ + (v,t)

for all 1 ≤ i ≤ k.
To ensure that the destination state is reached and each driver returns to its
depot, we use as sinks the nodes (v, T ), v ∈ V , for the car flow and the nodes
(vD , T ), vD ∈ VD , for the driver flow, and set their balances accordingly to z T
resp. to Bvi D for each driver flow Fi . Since there are k drivers, the sum of all
outgoing (resp. incoming) driver flows of all depots vD ∈ VD sums up to k.
Figure 1 illustrates a time-expanded network with capacities on the arcs as
well as the balances for the nodes (v, 0) and (v, T ). Furthermore, optimal flows
f, fi and Fi based on the network from Figure 2 are shown in this figure.

3.3

Integer linear program for Min-Cost-Flow in GT

To solve the Static Relocation Problem exactly, we aim at determining convoy
tours with a minimal total tour length. For that, we summarize the previous
sections by presenting an integer linear programming formulation for a min-cost
8

(a, 0)
(b, 0)

(a, 1)
2

(a, 2)
2

(b, 1)

2

(b, 2)

(a, 3)

1

(a, 4)

(b, 3)

2

(b, 4)

1

(a, 5)

1

(b, 5)

1

(a, 6)

1

(a, 7)

(b, 6)

(b, 7)

(c, 6)

(c, 7)

(a, 8)

1

(a, 9)

(c, 1)

(c, 2)

(c, 3)

(c, 4)

(c, 5)

(d, 1)

(e, 0)

(d, 2)

(e, 1)

(d, 3)

(e, 2)

1

(b, 10)

(a, 11)

(b, 9)

(b, 11)

(c, 8)

(c, 9)

1

(c, 10)

1

(c, 11)

(d, 9)

1

(d, 10)

1

(d, 11)

(e, 9)

1

(e, 10)

1

(e, 11)

1

1

(d, 0)

(a, 10)

(b, 8)

2

(c, 0)

1

(e, 3)

(d, 4)
1

(d, 5)
1

(e, 4)

(e, 5)

1

(d, 6)

1

(e, 6)

1

(d, 7)

1

(e, 7)

1

(d, 8)

1

(e, 8)

1

1

(f, 0)
(vD , 0)

2

2

(f, 1)
(vD , 1)

(f, 2)

(f, 3)

(f, 4)

(f, 5)

(f, 6)

(f, 7)

(f, 8)

(f, 9)

(vD , 2)

(vD , 3)

(vD , 4)

(vD , 5)

(vD , 6)

(vD , 7)

(vD , 8)

(vD , 9)

(f, 10)

(f, 11)

(vD , 10) (vD , 11)

Fig. 1. This figure shows the time-expanded network GT for the graph G from Figure 2.
The time horizon is set to T = 11. Every node of the form (v, t) represents a station v
(or the depot) at time t. In this car sharing system, there are two drivers. The driver
flow F1 is indicated by dash dotted arcs, the driver flow F2 by dotted arcs, and the
car flow f by solid arcs. The car flows f1 and f2 are not shown in the image, however,
their flow values are at the corresponding driver flows (if the value is positive). The
flow values of f on the holdover arcs are the numbers at the holdover arcs. The total
tour length is 17.

flow problem in the time-expanded network GT = (VT , AT ):
min

X

w(a)

k
X

Fi (a)

(5a)

i=1

a∈AL

f ((v, 0), (v, 1)) +

k
X

X

fi (a) = zv0 ,

∀(v, 0) ∈ VT

(5b)

∀(v, T ) ∈ VT

(5c)

∀1 ≤ i ≤ k

(5d)

∀1 ≤ i ≤ k

(5e)

∀v ∈ V, 0 < t < T

(5f)

−
a∈δL
(v,0) i=1

X

k
X

a∈δ + (v,T )

i=1

f ((v, T − 1), (v, T )) +
X

fi (a) = zvT ,

Fi (a) = Bvi ,

a∈δ − (v,0)

X
a∈δ + (v

Fi (a) = Bvi ,

D ,T )

X

f ((v, t − 1), (v, t)) +

k
X

fi (a)

+
a∈δL
(v,t) i=1

= f ((v, t), (v, t + 1)) +

k
X

X

fi (a),

−
a∈δL
(v,t) i=1

X
a∈δ + (v,t)

Fi (a) =

X

Fi (a),

∀v ∈ V, 0 < t < T, ∀1 ≤ i ≤ k (5g)

a∈δ − (v,t)

9

X

fi (a) ≤

+
a∈δL
(vo ,t)

X

fi (a),

∀vo ∈ VO , ∀0 < t < T, ∀1 ≤ i ≤ k (5h)

fi (a),

∀vu ∈ VU , ∀0 < t < T, ∀1 ≤ i ≤ k (5i)

fi (a),

∀vb ∈ VB , ∀0 < t < T, ∀1 ≤ i ≤ k (5j)

−
a∈δL
(vo ,t)

fi (a) ≥

+
a∈δL
(vu ,t)

X

X

X
−
a∈δL
(vu ,t)

fi (a) =

+
a∈δL
(vb ,t)

X
−
a∈δL
(vb ,t)

fi (a) ≤ L · Fi (a),

∀a ∈ AL , ∀1 ≤ i ≤ k

f, fi integer, Fi binary,

(5k)
(5l)

−
where δ − (v, t) denotes the set of outgoing arcs of (v, t) (and δL
(v, t) denotes
+
the set of outgoing relocation arcs of (v, t)), and δ (v, t) denotes the set of
+
incoming arcs of (v, t) (and δL
(v, t) denotes the set of incoming relocation arcs
of (v, t)). The objective function (5a) measures and minimizes the total tour
length of the transportation schedule. The equalities (5b) and (5d) give the
initial number of cars (resp. drivers) for each station (resp. for the depots).
Conditions (5f) and (5g) are the flow conservation constraints for the flows Fi and
f, fi , respectively. The conditions (5c) and (5e) ensure to reach the destination
state and that every driver returns to its depot at the end of the time horizon.
The conditions (5h), (5i) and (5j) ensure that cars are only picked up at overfull
stations, and dropped at underfull stations. Finally, the constraints (5k) couple
the flows fi and Fi so that cars on relocation arcs cannot move without their
driver. Furthermore, these constraints give the capacities for fi on relocation
arcs.
Finally, the flows in the time-expanded network have to be interpreted as
a transportation schedule. Hereby, car and driver flows on relocation arcs correspond to a move, differences in the car flow to actions. Note, one can easily
compute a transportation schedule from the resulting flows. For that, positive
flow Fj on a relocation arc a = ((v, tv ), (v 0 , tv0 )) corresponds to a move m =
(j, v, tv , v 0 , tv0 , fj (a)). Actions are implied by differences of flow values between
incoming and outgoing relocation arcs, i.e., if we have Fj (a) = Fj (a0 ) = 1 with
a0 = ((v 0 , tv0 ), (v 00 , tv00 )), and fj (a) 6= fj (a0 ) then the action α = (j, v 0 , tv0 , fj (a)−
fj (a0 )) is implied. This implies:

Theorem 1. The optimal solution of system (5) corresponds to a non-preemptive
transportation schedule with minimal total tour length for the Static Relocation
Problem with backhaul (G, z 0 , z T , Z D , k, L) (Symmetric and Asymmetric).
3.4

Static Relocation Problem without backhaul

In this section, we consider the Static Relocation Problem without backhaul,
and highlight the differences between the exact approach for solving the Static
Relocation Problem with and without backhaul.
In the integer linear program stated in the previous section, the equations (5e)
ensure that every driver returns to its depot. Thus, it is sufficient to conveniently
modify these equations.
10

For that, we replace the equations (5e) by the following two constraints
X
Fi (a) ≤ 1,
∀1 ≤ i ≤ k, ∀vD ∈ VD ,
(6)
a∈δ + (vD ,T )

X

Fi (a) = 0,

∀1 ≤ i ≤ k, ∀v ∈ V \ VD .

(7)

a∈δ + (v,T )

Hereby, (6) ensures that every driver can return to any depot and (7) ensures
that the drivers do not end their tours in a station but only in a depot. Thus,
we can compute non-preemptive transportation schedules with a minimal total
tour length for the Symmetric (resp. Asymmetric) Static Relocation Problem
without backhaul.

4

The combinatorial algorithm ReOpt

The computation times for computing an exact solution by solving the integer linear program (5b)–(5l) are extremely high even for small instances (see
Table 1). This motivates the study of a combinatorial algorithm to solve the
problem in reasonably short time. Therefore, we describe in detail the strategy
ReOpt proposed in [10] to solve a Static Relocation Problem. The input of ReOpt is the Static Relocation Problem (M, z 0 , z T , Z D , k, L). Hereby, we consider
a complete weighted graph G = (VO ∪ VU ∪ VD , E, d) induced by a (quasi) metric
space M = (V, d), containing only the overfull stations VO ⊆ V (with zi0 > ziT ),
the underfull stations VU ⊆ V (with zi0 < ziT ), and a set of depots VD , as well
as all connections E between them and driving times d : E → N. The task set T
again consists of the tasks τ = (v, zv0 − zvT ) for all v ∈ VO ∪ VU . The output of
ReOpt is a non-preemptive transportation schedule for the (quasi) metric task
system (M, T ), the objective is to minimize its total tour length.
The ReOpt approach performs three steps. Firstly, we construct a weighted
complete bipartite graph and find a matching between overfull and underfull
stations with minimal edge weight. Each edge in this matching corresponds to
a transport request between two stations. Secondly, tours for all convoys are
constructed (using a heuristic insertion technique) serving each transport request. Since the transport requests stemming from the minimum matching do
not necessarily lead to optimal convoy tours, the final step is to iteratively augment the tours by “rematching” certain origin/destination pairs, i.e., to reinsert
accordingly adapted moves in such a way that the total tour length decreases.
4.1

First step: Compute transport requests

In the first step, we compute transport requests of the form (vo , vu , x), where vo
is an overfull station, vu an underfull station and x is the number of cars to be
transported from vo to vu . For that, we construct a weighted complete bipartite
graph B = (VO ∪ VU , A, w, p) and consider a restricted vector w ∈ R|A| of edge
weights (reflecting the distance between the two adjacent stations) and a vector
11

p ∈ N|VO ∪VU | of node weights reflecting the number pv = |zv0 − zvT | of cars which
have to be moved in or out the corresponding station v.
Define a perfect p-matching in B to be a multiset x : A → N of the edges
such that for each node v ∈ VO ∪ VU , exactly pv incident edges are selected,
|VO ∪VU |
counted with multiplicities xa . Note that by construction
, the
P of p ∈ N P
existence of such a perfect p-matching is ensured by vo ∈VO po = vu ∈VU pu
P
P
0
T
since
v∈V zv =
v∈V
P zv . The goal is to find a perfect p-matching x with
minimal edge weight a∈A wa xa , including multiplicities. The problem can be
formulated by the following integer linear program
X
min
w a xa ,
(8a)
a∈A

X
a∈δ + (v

xa = pvo ,

∀vo ∈ VO (8b)

xa = pvu ,

∀vu ∈ VU (8c)

o)

X
a∈δ + (vu )

xa integer.

(8d)

Note that the constraint matrix is totally unimodular, and thus, problem can be
solved efficiently [].
Each selected matching edge a = vo vu , with vo ∈ VO and vu ∈ VU , corresponds to a transport request for xa cars from station vo to station vu . The set
TR of all such transport requests provides the input for a Pickup and Delivery
Problem (PDP) which has to be solved subsequently in order to construct tours
for all convoys serving each transport request.
4.2

Second step: Serving the transport requests

In this section, we give an algorithm Pdp-Insert which solves the PDP using heuristic insertion techniques. The input for Pdp-Insert is the complete
weighted graph G = (VO ∪ VU ∪ VD , E, w), the total number k of drivers, the
convoy capacity L, and the set of transport requests TR. The output of PdpInsert is a non-preemptive transportation schedule for the drivers, which serves
all transport requests in TR within the time horizon [0, T ].
For that, we define some further notions. Let Γj be a tour for a driver j and
let tr = (vo , vu , x) be a transport request. We say that tr is served by Γj if there
exists a pickup action αo = (·, vo , y) and a drop action αu = (·, vu , −y) in Γj ,
so that t(αo ) < t(αu ). Hereby, tr is fully served if y = x and partially served
if y < x. By y tr (Γj ) := y we denote the number of cars served from tr by Γj .
A transport request tr = (vo , vu , x) can be (partially) inserted into a tour Γj ,
serving y cars, as follows:
• select a move m = (j, v, tv , w, tw , xm ) where vo shall be inserted,
• remove m from Γj ,
• add move (j, v, tv , vo , tv + d(v, vo ), xm ), action (j, vo , y), move (j, vo , tv +
d(v, vo ), w, tv + d(v, vo ) + d(vo , w), xm + y) to the tour,
12

• update departure and arrival times of all successive moves and actions,
• do analogous steps for u.
This yields a new tour Γj0 which (partially) serves tr. By applying the opposite
steps, tr can be removed from Γj0 , which yields Γj .
Now let tr be (fully or partially) served by Γ , and Γjw be the tour derived from
Γj without serving tr. We denote the marginal costs per load unit CM (tr, Γj )
by
len(Γj ) − len(Γjw )
CM (tr, Γj ) =
.
y tr (Γj )
Now the algorithm Pdp-Insert can be described as follows:
(i) For each driver j initialize the tour so that it starts and ends in the drivers
depot vD ∈ VD , i.e., initialize the tour with the move (j, vD , 0, vD , 0, 0).
(ii) Choose a transport request tr that has an origin or a destination already in
a tour, else randomly select one.
(iii) Calculate the marginal cost per load unit of inserting this transport request
to each possible tour. Hereby, take the number of cars to be transported into
account (i.e., respect the convoy capacity) as well as the time. Select the
tour with the minimum marginal cost per load unit and insert the transport
request into this tour.
(iv) If the transport request tr is fully served, remove it from TR. Otherwise, it
is partially served by a tour Γ . Then subtract the number of cars inserted
from the load of the transport request, i.e., remove tr from TR and add a
new transport request tr0 = (vo , vu , x − y tr (Γ )) to TR.
(v) Repeat these steps until all the transport requests are fully served.

-1
3
-1

2

d

c

3

2

vD

-1
3
-1

2

2

d

b

2

b

2

2

vD

2

2

2

1

4

2

2

2

2

c

3

1
1

-1

a

2

f

4

1

-1

a

1

2

f

1

-1

-1

e

e

Fig. 2. In each figure (left and right side), a carsharing system with 6 stations (a to
f ) and one depot (vD ) is illustrated as a graph G. There are two tours (dashed and
dotted), one for each of the two drivers (server capacity L = 2), giving a non-preemptive
transportation schedule. The numbers at the stations show the amount of cars to be
moved from (> 0) or to the station (< 0). On the left side, the transportation schedule
before the reoptimization step is shown (total tour length = 22), on the right side, the
transportation schedule after this step (total tour length = 19).

The algorithm Pdp-Insert computes a non-preemptive transportation schedule. However, the transportation schedule created from the transport requests
13

stemming from the minimal perfect p-matching does not necessarily lead to optimal tours. Therefore, the final step is to iteratively augment the tours by “rematching” certain origin/destination pairs, i.e., to reinsert accordingly adapted
moves in such a way that the total tour length decreases.
4.3

Third step: Reoptimization

The algorithm defined here involves the two previous steps: computation of transport requests and the algorithm Pdp-Insert. The input for the reoptimization
step is a transportation schedule S serving all transport requests in TR and two
natural numbers ∆, N ∈ N. The output is a transportation schedule having a
total tour length less or equal to the total tour length of S. The algorithmic
scheme of the reoptimization step is as follows:
(i) From S we withdraw the N transport requests with highest marginal cost
per load: TR0 = {(vo1 , vu1 , x1 ), . . . , (voN , vuN , xN )}.
(ii) From the withdrawn transport requests we compute sets of over- and underfull stations, i.e., the set VO∗ = {vo ∈ VO | (vo , ·, ·) ∈ TR0 }, the set
VU ∗ = {vu ∈ VU | (·, vu , ·) ∈PTR0 } and the vector xP∈ N|VO∗ |·|VU ∗ | by
xou = min{po , pu }, where po = (vo ,·,x)∈TR0 x and pu = (·,vu ,x)∈TR0 x.
(iii) For every pair (vo , vu ) ∈ VO∗ × VU ∗ and every tour Γ we compute the additional marginal cost CM + (Γ, (vo , vu )), where CM + (Γ, (vo , vu )) = Γ (vo ,vu ) −
Γ and Γ (vo ,vu ) is the tour after inserting a transport request (vo , vu , 1). Let
wou = minΓ ∈S CM + (Γ, (vo , vu )) be the minimal additional marginal cost.
(iv) Next we generate a weighted complete bipartite graph B = (VO∗ ∪VU ∗ , A, w, p)
and compute a minimal perfect p-matching (as in Step 1). From the minimal
perfect p-matching, transport requests are generated, which serve as input
for the algorithm Pdp-Insert (as in Step 2).
(v) Redo these steps ∆ times.
(vi) Finally, we return the best found transportation schedule, i.e., the one with
the smallest total tour length.
Figure 2 shows an example for the reoptimization step improving a transportation schedule stemming from the minimal perfect p-matching of Step 1.
The algorithm ReOpt is summarized in Algorithm 1.
Finally, we give some comments about the complexity of the algorithm ReOpt. The minimal perfect p-matching of Step 1 of the algorithm ReOpt (Section 4.1), can be computed in polynomial time. Since constructing an optimal
transportation schedule from the minimal perfect p-matching (Section 4.2) results in a dial-a-ride problem, this step is at least N P-hard. Thus, the second
step cannot be solved in polynomial time unless P = N P holds. Therefore, the
total complexity of ReOpt is at least in N P.

5

Approximation factors

In this section, we consider several different situations and show that in most of
these cases, the algorithm ReOpt achieves a finite approximation factor based
14

Algorithm 1 ReOpt
Input: a Static Relocation Problem (M, z 0 , z T , Z D , k, L), integers N , ∆
Output: a non-preemptive transportation schedule
1: Find a minimal perfect p-matching (Step 1)
2: while counter < ∆ do
3:
update counter
4:
construct k tours by Pdp-Insert serving all transport requests (Step 2)
5:
rematch after withdrawing the N requests that have highest additional marginal
costs in their tours (Step 3)
6: return transportation schedule of smallest found total tour length

on the capacity of the convoys. We consider the symmetric and asymmetric situations, when there is only one depot on the system and when there are multiple
depots. In the case of multiple depots, we distinguish between tours with and
without “backhaul”, i.e., whether each driver has to return to its starting depot
(with backhaul) or to any depot in the system (without backhaul). Obviously,
in the case of only a single depot in the system, the Static Relocation Problem
with backhaul and without backhaul coincide.
Firstly, we consider the case when there is only one depot in the system (Section 5.1). Hereby, we show that the approximation factor is equal in both cases,
the symmetric and the asymmetric one. Secondly, we consider multiple depots in
the system (Section 5.2). In this case, the symmetric and asymmetric situations
become different, depending whether the transportation schedule contains only
tours with or without backhaul.
Throughout this section, we assume that the time horizon is always large
enough.
5.1

Single depot

In this section, we show that in the case when there is only one depot in the
system, ReOpt achieves a finite approximation factor based on the capacity of
the convoys.
Theorem 2. For the Static Relocation Problem (M, z 0 , z T , Z D , k, L) with one
depot, the algorithm ReOpt achieves an approximation factor of L + 1.
That ReOpt computes a non-preemptive transportation schedule for the
Static Relocation Problem has already been observed in the previous section. In
order to prove the approximation factor, we first introduce some definitions, as
well as state and prove some lemmas.
Firstly, from a given tour, we construct a new tour where each action picks
up (resp. drops) exactly one car. Considering such tours only simplifies several technical issues, like estimating the number of consecutive pickup actions.
Secondly, we construct a new transportation schedule from an optimal transportation schedule and a minimal perfect p-matching. Finally, we compare the
15

lengths of an optimal transportation schedule S ∗ , a transportation schedule S p
derived from a minimal perfect p-matching, and the constructed transportation
schedule S t and show that
`(S p ) ≤ `(S t ) ≤ (L + 1)`(S ∗ )
holds, which proves the stated approximation factor. Hereby, we construct the
transportation schedule S p by taking moves and actions of the optimal transportation schedule S ∗ and by constructing moves from the transport requests of
the minimal perfect p-matching. Then, the approximation factor (L+1) emerges
from the maximal number of moves corresponding to moves through the system
in order to pickup cars and from moves which are serving a transport requests.
We start by showing how to construct a tour Γ from a given tour Γ =
(m1 , α1 , . . . , αn−1 , mn ), where in each action exactly one car is picked up or
dropped.
For every i ∈ {1, . . . , n} do
• add move mi to Γ ,
• for every action αi = (j, v, x) where more than one car is picked up from a
station v at time tv , we “replace” the action by actions each picking one car
and waiting moves (with 0 waiting time) between these actions, i.e., if x > 1
then add the following x actions and x − 1 moves ((j, v, 1), (j, v, tv , v, tv , xi +
1), . . . , (j, v, tv , v, tv , xi + x − 1), (j, v, 1)) are added to Γ ,
• for every action αi = (j, v, x) where more than one car is dropped at a station w at time tw , we “replace” the action by actions each picking one car
and waiting moves (with 0 waiting time) between these actions, i.e., if x < −1
then add the following x actions and x−1 moves ((j, w, −1), (j, w, tw , w, tw , xi −
1), . . . , (j, w, tw , w, tw , xi − x + 1), (j, w, −1)) are added to Γ ,
• every action αi = (j, v, x) with −1 ≤ x ≤ 1 is added unchanged to Γ .
The tour Γ is called a uniform tour corresponding to Γ . A transportation schedule containing only uniform tours is called uniform transportation schedule.
Note that a uniform tour is indeed a tour. Furthermore, note that there
exists exactly one uniform tour corresponding to a tour (if no unnecessary empty
actions and waiting moves are added), but from a uniform tour, one can generally
derive several non-uniform tours.
In this section, we consider non-preemptive transportation schedules, i.e.,
there does not exist a tour depending on another tour. Therefore, empty actions
can be safely removed from any tour in a transportation schedule (some moves
may need to be adjusted accordingly). For the rest of this section, we assume
that no action is empty.

16

Example 1. Let us consider the graph and the dashed tour for driver 1 from the
right side of Figure 2. The tour is then given by
Γ ={
(1, vD , 0, b, 4, 0),
(1, b, 2),
(1, b, 4, d, 6, 2),
(1, d, −1),
(1, d, 6, a, 8, 1),
(1, a, −1),
(1, a, 8, vD , 11, 0)
},
and the corresponding uniform tour is then
Γ ={
(1, vD , 0, b, 4, 0),
(1, b, 1),
(1, b, 4, b, 4, 1),
(1, b, 1),
(1, b, 4, d, 6, 2),
(1, d, −1),
(1, d, 6, a, 8, 1),
(1, a, −1),
(1, a, 8, vD , 11, 0)
}.
The “replaced” action is highlighted with bold fonts, all other actions a ∈ act(Γ )
have already the form ∆x(a) = ±1.
4
The following lemma is a direct conclusion from the construction of an uniform tour.
Lemma 1. Let Γ = (m1 , α1 , . . . , mn−1 , αn−1 , mn ) be a uniform tour for driver j.
Then there are at most L consecutive pickup (resp. drop) actions in the sequence
act(Γ ).
Next, we construct a graph G from a given tour, where the set of nodes
corresponds to the actions, and the set of arcs to the moves of the tour. Afterwards, we combine this graph with transport requests (leading to a graph Gt ),
which then helps us to construct another tour (from this tour we finally gain
the transportation schedule S t ). This constructed tour has some nice properties
with respect to the number of traverses of each arc of Gt , which finally helps us
to prove our main result (Theorem 2).
17

From a given tour Γ = (m1 , α1 , m2 , . . . , αn−1 , mn ), we construct a directed
weighted graph G = (V + ∪ V − ∪ V = , A, w), where
(i) the set of nodes V = V + ∪ V − ∪ V = corresponds to the actions in Γ , V +
corresponds to the set of pickup actions, V − to the set of drop actions, and
V = to an empty action at the depot vD , i.e., V = = {(·, vD , 0)};
(ii) there is an arc from v ∈ V to v 0 ∈ V if v = αj and v 0 = αj+1 for a 1 ≤ j ≤ n,
furthermore there is an arc from (·, vD , 0) to α1 and from αn−1 to (·, vD , 0);
(iii) the weight function w corresponds to the distances between the origin and
destination stations of the corresponding moves, i.e., we set w(αj , αj+1 ) =
d(orig(mj+1 ), dest(mj+1 )).
We call such a graph a tour graph for Γ , the set A is called the set of tour arcs.
Note that one can assign to every arc a ∈ A of a tour graph a move m ∈ Γ .
Then m is called the corresponding move to a.
Example 2. The tour graph for the tour Γ from Example 1 is illustrated in
Figure 3.
4
vD
−

d

b+

2

0

4

b+

3

2

a−

Fig. 3. This figure shows the tour graph for the uniform tour Γ from Example 1.
The weights of the arcs correspond to the shortest distance between the connected two
stations. In the tour graph, a pickup action at station v ∈ V is denoted by v + and a
drop action at v by v − .

Analogously, to a uniform tour we now define a set of uniform transport
requests. A transport request (vi , wi , xi ) is called uniform if xi = 1. Obviously,
every set of transport requests can be transformed into a set of uniform transport
requests by splitting every transport request (vi , wi , xi ) into xi uniform transport
requests. A set of transport requests TR is called set of uniform transport requests
if every transport request r ∈ TR is uniform.
To each uniform transport request (v, w, 1) ∈ TR, we can now assign two
actions for a driver j, one pickup (j, v, 1) and one drop action (j, w, −1). Hereby,
every action is assigned to exactly one transport request.
Let G = (V, A, w) be a tour graph and let TR be a set of transport requests.
Then we construct a directed weighted graph Gt = (V, A ∪ At , w), where At is
the set of transport arcs, which consist of arcs corresponding to the transport
requests in TR, i.e., for a transport request r ∈ TR there is an arc between
v, v 0 ∈ V if v is the assigned pickup action of r and v 0 the assigned drop action
of r. The weight of a transport arc is equal to the distance between the locations
18

of the two assigned actions. The graph Gt is called a transport graph (see Figure 4
for an illustration).
vD
−

d

b+
2

2

0

4

b+
1
3

2

a−

Fig. 4. This figure shows a transport graph for the uniform tour Γ from Example 1
and the set of transport requests TR = {(b, d, 1), (b, a, 1)}. The weights of the arcs
correspond to the shortest distance between the connected two stations. In the tour
graph, a pickup action at station v ∈ V is of the form v + and a drop action is of the
form v − . The dash-dotted arcs correspond to transport arcs.

Remark 1. Let G = (V, A, w) be a tour graph for a tour Γ for driver j and let
TR be a set of transport requests. From a transport graph Gt = (V, A ∪ At , w)
t
for G and TR, one can construct a new tour Γ that serves all transport requests
in TR, as follows:
• Start in the depot vD (resp. the node corresponding to the depot).
• Consider the next tour arc a ∈ A or non-traversed transport arc at ∈ At .
t
• If a tour arc a = (v, w) is selected, we add a corresponding move m to Γ
from loc(v) to loc(w) with xm (m) = 0.
• If necessary, add empty actions (or merge the moves).
• If a transport arc at = (v, w) is selected, we add the pickup action v, a move
t
(j, loc(v), ·, loc(w), ·, 1) and a drop action w to Γ .
• When all transport requests are served, return to depot the by following tour
arcs until the depot is reached.
The departure and arrival times of a move mj are directly induces by the departure and arrival times of the moves preceding m1 , . . . , mj−1 .
Note that following this construction, we always construct a tour. However,
without further restrictions this easy construction does not ensure an upper
bound on the number of traverses of an arc (later in Algorithm 2 we give a
refined construction which ensures an upper bound on the number of traverses
of an arc).
♦
When we speak about a constructed tour (from a transport graph Gt and a
set of transport requests T R), we mean a tour Γ which is constructed using only
the arcs from Gt and which serves all transport requests from TR.
Example 3. Let us consider the transport graph from Figure 4. A possible new
tour serving all transport requests TR constructed from the transport graph, is
19

then given by (see Figure 5 for an illustration)
t

Γ ={
(1, vD , 0, b1 , 4, 0),
(1, b1 , 0),
(1, b1 , 0, b2 , 4, 0),
(1, b2 , 1),
(1, b2 , 4, d, 6, 1),
(1, d, −1),
(1, d, 6, a, 8, 0),
(1, a, 0),
(1, a, 8, vD , 11, 0),
(1, vD , 0),
(1, vD , 11, b1 , 15, 0),
(1, b1 , 1),
(1, b1 , 15, a, 17, 1),
(1, a, −1),
(1, a, 17, vD , 19, 0),
}.
Hereby, the stations b1 and b2 both correspond to the station b. However, for
the sake of readability, we use b1 and b2 instead of b.
4
0
0

−

d

1

0

b+
2

0

b+
1

vD

0
0

1

a−

Fig. 5. This figure shows a possible tour constructed from the transport graph of
Figure 4 serving the transport requests TR = {(b, d, 1), (b, a, 1)}.

Our goal is to construct a new tour from a transport graph, constructed from
an optimal tour, and from a set of transport requests, which is generated from
a minimal perfect p-matching. Then, we show that the approximation factors
from Theorem 2 hold for this constructed new tour. For that we define a function
which returns for each arc of a transport graph the number of traverses of the
arc during the construction of the tour.
Let Γ be a uniform tour, TR be a set of transport requests and Gt = (V, A ∪
t
A , w) be a transport graph for Γ and TR. Furthermore, let Γ t be a constructed
20

tour from Gt and TR. Then, we consider a so-called traverse counter function,
which is a function f a : A → N which reflects how often a tour arc a ∈ A is
traversed during the construction of Γ t .
With the function f a , we counts the traverses of the tour arcs only, while we
the request arcs are handled later.
Example 4. Let us consider the transport graph from Figure 4 and the tour Γ
from Example 3. The traverse counter function f a is then

t

f a (vD , b+
1 ) = 2,
+
f a (b+
1 , b2 ) = 1,
−
f a (b+
2 , d ) = 0,

f a (d− , a− ) = 1,
f a (a− , vD ) = 2.
Note that there are two arcs in the transport graph from Figure 4 between b+
2
t
and d− , one tour arc and one request arc. Hereby, the tour Γ is constructed not
−
by traversing the tour arc (b+
2 , d ) but instead by traversing the transport arc
−
−
from b+
to
d
is
traversed.
Thus,
we have f a (b+
4
2
2 , d ) = 0.
Lemma 2. Let Γ be a uniform tour starting and ending in depot vD , TR a set
of transport requests, and Gt = (V + ∪ V − ∪ V = , A ∪ At , w) a transport graph for
Γ and TR. Furthermore, let Γ be the constructed tour from Algorithm 2 and let
f a be a traverse counter function for Γ . Then f a (a) ≤ L + 1 holds for all tour
arcs a ∈ A. More specifically, we have
(i) f a (a) ≤ L + 1 holds for all tour arcs a = (v, w) ∈ A with v ∈ V − ,
(ii) f a (a0 ) ≤ L holds for all tour arcs a0 = (v 0 , w0 ) ∈ A with v 0 ∈ V + .
Proof. In the Example 4, we can already make an important observation, namely,
nodes corresponding to a pickup action increase the number of traverses, nodes
corresponding to a drop action decrease the number of traverses. Next, we show
that this observation is always true.
Claim 2.1. Let a1 , a2 ∈ A be two tour arcs with a1 = (v, w) and a2 = (w, u)
(i.e., a2 is the successive tour arc of a1 ). Then |f a (a1 ) − f a (a2 )| = 1 holds. More
specifically, it holds
(i) f a (a1 ) − f a (a2 ) = 1 if w ∈ V + ,
(ii) f a (a1 ) − f a (a2 ) = −1 if w ∈ V − .
t
Proof. The movement of a driver can bePmodeled by a flow
P f : A∪A →
N. Then the flow conservation constraint a∈δ+ (v) f (a) = a∈δ− (v) f (a) must
hold. Hereby, the transport arcs must be taken into consideration as well. It
is easy to see that there always exists a flow f with f (a) = f a (a) for all tour
arcs a ∈ A. Since every node corresponding to a pickup action has exactly one
outgoing transport arc and every drop action has exactly one incoming transport
arc, and due to the flow conservation constraint it follows that

21

(i) f a (a1 ) − f a (a2 ) = 1 if w ∈ V + ,
(ii) f a (a1 ) − f a (a2 ) = −1 if w ∈ V −
holds and, thus, proves the statement.

♦

There are several consequences from this lemma. Firstly, we show in the
next corollary that the difference of the number of traverses of two different
tour arcs can be bounded from above. Secondly, we show a relation between the
number of traverses of an arc and the number of cars that are transfered in the
corresponding move within the constructed tour.
Claim 2.2. Let a1 , . . . , aτ ∈ A be successive tour arcs (i.e, a1 = (v1 , v2 ), a2 =
(v2 , v3 ), . . . , aτ = (vτ , vτ +1 )), and let t : A → N be a function that returns the
number of cars transfered in the corresponding moves in Γ . Then
(i) |f a (a1 ) − f a (aτ )| ≤ L, and
(ii) f a (a) + t(a) = const holds for all tour arcs a ∈ A. Especially it holds
f a (a) + t(a) = f a (a0 ) + t(a0 ) for every pair of tour arcs a, a0 ∈ A.
Proof. “(i)” Lemma 1 shows that in every tour there are maximal L consecutive pickup actions and maximal L consecutive drop actions. Furthermore, the
number of cars in a convoy must not exceed the capacity L. Since |f a (aj ) −
f a (aj+1 )| = 1 holds, the difference cannot be greater than L.
“(ii)” Let a ∈ A be a tour arc and let a0 ∈ A be the successive tour arc. We
proof the statement with two cases, when the end node of a is a node in V + and
when it is a node in V − .
Case i (the end node of a is a node in V + ): From Claim 2.1 (i) it follows that
f a (a) − f a (a0 ) = 1. Since the end node of a corresponds to a pickup action, the
number of cars transported in Γ is increased by 1, i.e., we have t(a)−t(a0 ) = −1.
Thus, it follows f a (a) − f a (a0 ) + t(a) − t(a0 ) = 0 and, therefore, f a (a) + t(a) =
f a (a0 ) + t(a0 ).
Case ii (the end node of a is a node in V − ): From Claim 2.1 (ii) it follows that
f a (a) − f a (a0 ) = −1. Since the end node of a corresponds to a drop action, the
number of cars transported in Γ is decreased by 1, i.e., we have t(a) − t(a0 ) = 1.
Thus, it follows f a (a) − f a (a0 ) + t(a) − t(a0 ) = 0 and, therefore, f a (a) + t(a) =
f a (a0 ) + t(a0 ).
We have shown, that the statement holds for two successive arcs. The statement for arbitrary pairs now follows by iteratively applying the two cases.
♦
Next, we show that the maximum of a traverse counting function is always
on the incoming and outgoing tour arcs of the depot.
=
Claim 2.3. Let V = = {vD
}. Then
=
=
(i) f a ((vD
, ·)) = f a ((·, vD
)) ≥ f a (a0 ) for all tour arcs a0 ∈ A,
a
=
a
=
(ii) f ((vD , ·)) = f ((·, vD )) > f a (a0 ) for all tour arcs a00 = (v, w) ∈ A, with
v ∈ V +.

22

Proof. Let t : A → N be a function that returns the number of cars transfered in
the corresponding moves in Γ . From Lemma 2 (ii) we know that f a (a) + t(a) =
f a (a0 )+t(a0 ) for a, a0 ∈ A. At the beginning and end of a tour, the number of cars
=
=
in a convoy is always 0 and, thus, we have f a ((vD
, ·)) = f a ((·, vD
)) = f a (a)+t(a)
0
for all a ∈ A. The statements now follows since t(a ) ≥ 0 for all a0 ∈ A and
t(a00 ) ≥ 1 for all a00 = (v, w) ∈ A, with v ∈ V + .
♦
In Algorithm 2 we describe a specific construction for new tours from a given
tour and a given set of transport requests. For this new tour f a (a) ≤ L + 1 holds
for all a ∈ A. This can be seen as follows.
Algorithm 2 Construct new tour
Input: a uniform tour Γ = (m1 , α1 , . . . , αν−1 , mν ) with backhaul for driver j, the
depot vD , a set of transport requests TR
Output: a tour Γ serving all transport requests of TR
1: construct transport graph Gt = (V + ∪ V − ∪ V = , A ∪ At , w)
2: initialize Γ ← ∅
=
3: initialize currN ode ← vD
4: while not every node in V + has been visited do
5:
if currN ode ∈ V + and has not been visited then
6:
mark currN ode as visited
7:
follow transport arc and add corresponding moves and actions to Γ
8:
else
9:
follow tour arc and add corresponding move to Γ
10:
update currN ode
11: follow tour Γ until arriving in depot node
12: if necessary insert empty actions between two successive moves in Γ
13: return Γ

It is fairly easy to see that Algorithm 2 follows basically the same steps as
in Remark 1. Furthermore, one can easily see that really a tour is constructed,
serving all transport requests. In contrast to the construction in Remark 1,
Algorithm 2 “follows” the given tour only until it arrives at a non-visited node
corresponding to a pickup action and directly serve the transport request.
Since the constructed tour in Algorithm 2 “follows” the moves from Γ until
the next non-visited pickup action, it is ensured, that the number of traverses
of an arc is not artificially increased. Thus, the result follows with the help of
Lemma 1, Claim 2.1, Claim 2.2 and Claim 2.3.
t
u
Remark 2. Although Algorithm 2 starts the construction of the tour from the
depot, any arbitrary node could be used as a starting node. That could be done
by removing line 3 and giving currN ode as a parameter. When the construction
is started with another node, Lemma 2 still holds, and so does Lemma 4.
♦
Let Γ be a uniform tour, and let TR be a set of uniform transport requests
so that Γ serves all transport requests in TR. Furthermore, let Gt = (V + ∪ V − ∪
23

V = , A ∪ At ) be a transport graph for Γ and TR. Since every transport request
r = (v, v 0 , 1) ∈ TR is served by Γ , there exists a path of tour arcs in Gt from the
action α1 corresponding to v to the action αl corresponding to v 0 . Let this path
of tour arcs be p(α1 , αl ) = (α1 , α2 ), (α2 , α3 ), . . . , (αl−1 , αl ). Due to the triangle
inequality we can estimate the length w(α1 , αl ) of the transport arc by
w(α1 , αl ) ≤ w(α1 , α2 ) + · · · + w(αl−1 , αl ).
Therefore, the length of all transport arcs can be estimated by applying above
formula iteratively on all transport arcs,
X
X
X
w(a) ≤
w(α, α0 ),
(9)
a∈At

a∈At (α,α0 )∈p(a)

where p(a) is the minimal path of tour arcs in Gt between the corresponding
actions. Now we can consider a function f TR : A → N, called transport estimate
function, where f TR (a) shows how often the tour arc a is used in the right hand
side of Equation (9). With F TR can reformulate Equation (9) as
X
X
X
X
w(a) ≤
w(α, α0 ) =
f TR (a)w(a).
(10)
a∈At

a∈At (α,α0 )∈p(a)

a∈A

It is easy to see, that the values of a transport estimate function depends
on the choice of the set of transport requests TR. In order to prove the main
theorem, we consider a specific set of transport requests. For that let Γ be a
uniform tour for a driver starting and ending in depot vD . A set of uniform
transport requests TR so that
(i) Γ serves all transport requests in TR,
(ii) for every transport request r ∈ TR there are at most L actions between two
corresponding actions for r, and
(iii) there does not exist a transport request (loc(v), loc(w), 1) ∈ TR so that
the minimal path from loc(v) to loc(w) of tour arcs traverses the tour arcs
connecting the depot,
holds is called a set of close distance uniform transport requests for Γ .
In the next lemma, we show that for every uniform tour there exists a set
of close distance uniform transport requests. Hereby, also the motivation for the
choice of the name becomes clear as well.
Lemma 3. Let Γ be a uniform tour for a driver starting and ending in depot vD .
Then there exists a set of close distance uniform transport requests for Γ .
Proof. Let Γ = (m1 , α1 , . . . , mn−1 , αn−1 , mn ). Since a tour starts and ends in
the depot and there must be no car in the depot it follows that
X
x=0
(11)
α=(j,v,x)∈Γ

24

holds for every tour Γ = (m1 , α1 , . . . , mn−1 , αn−1 , mn ). Furthermore, if Γ contains actions, it follows that the first action is a pickup action and the last action
a drop action. Otherwise, there exists a move m = (j, ·, ·, ·, ·, x) with x < 0 or
x > L or the driver transfers vehicles into the depot, contradicting the definition
of a tour.
We construct a set of transportation requests TR by assigning the station
of the first pickup action in Γ to the station of the first drop action in Γ , the
station of the second pickup action in Γ to the station of the second drop action
in Γ , and so forth until all actions are assigned. Since the number of cars picked
up or dropped in an action in Γ is exactly one and due to Equation (11), there
exists a pickup action for a drop action. Thus, it also follows that the number
of actions is even in Γ .
Let r ∈ TR be a transportation request and let α be the corresponding
pickup and α0 the corresponding drop action for r. Using this construction, we
show that there are at most L actions between α and α0 .
We prove the statement by induction over the number of actions n in Γ . For
n = 0 and n = 2 there are 0 < L actions between α and α0 proving the base
case.
Let us assume that the induction hypothesis holds, i.e., there are at most L
actions between α and α0 for all tours with n actions.
Next, we prove the inductive step. For that, let Γ have n + 2 actions.
We construct a sequence of n actions and n + 1 moves from Γ by removing
the first pickup and the first drop action from Γ . Afterwards, we show that this
sequence is a tour. Then the statement follows from the induction hypothesis.
Since every action is non-empty, α1 is the first pickup action. Let α` be the
first drop action. Furthermore, let m1 = (j, v1 , tv1 , w1 , tw1 , x1 ), m2 = (j, v2 , tv2 , w2 , tw2 , x2 )
and m` = (j, v` , tv` , w` , tw` , x` ), m`+1 = (j, v`+1 , tv`+1 , w`+1 , tw`+1 , x`+1 ).
First, let us consider the following new moves m̂1,2 = (j, v1 , tv1 , w2 , tw2 , x1 )
and m̂`,`+1 = (j, v` , tv` , w`+1 , tw`+1 , x`+1 ) and let m̂i = (j, vi , tvi , wi , twi , xi − 1),
for all 3 ≤ i ≤ `−1, be a move constructed from the move mi = (j, vi , tvi , wi , twi , xi ).
Finally, let m̂ι = mι for all ` + 2 ≤ ι ≤ n + 2.
Then Γ 0 = (m̂1,2 , α2 , m̂3 , . . . , α`−1 , m̂`,`+1 , α`+1 , m̂`+2 , . . . , αn−1 , m̂n ) is an
alternative sequence of n + 1 moves and n actions. We show that Γ 0 is indeed
a tour. It is sufficient to show for every move m̂i = (j, ·, ·, ·, ·, xi ) in Γ 0 that
0 ≤ xi ≤ L holds.
For that, we consider the number n+ of consecutive pickup actions before the move m`,`+1 and number n− of consecutive drop actions directly after m`,`+1 in Γ , as well as the number n̂+ of consecutive pickup actions before
the move m̂`,`+1 and number n̂− of consecutive drop actions directly after m̂`,`+1
in Γ̂ . Since Γ is a tour, it follows from Lemma 1 that 0 ≤ n+ − n− ≤ L holds.
From the construction of Γ 0 it follows
n+ − n− = (n̂+ + 1) − (n̂− + 1) = n̂+ − n̂−
and, thus, we have 0 ≤ n̂+ − n̂− ≤ L. Furthermore, it follows that the number
of cars in the convoy of driver j are equal in both sequences in and after the
25

move m`+1 and m̂`,`+1 , respectively, i.e., for every ` + 2 ≤ i ≤ n + 2 we have
0 ≤ xi ≤ L, where xi is the number of cars in the move m̂i .
Then, it follows for every move m̂i = (j, ·, ·, ·, ·, xi ) in Γ 0 that 0 ≤ xi ≤ L
holds, and, thus, that Γ 0 is a tour with n actions. Therefore, the induction
hypothesis can be applied to Γ 0 and it follows that there are at most L actions
between the corresponding pickup and drop actions of a transportation request.
Since there are at most L consecutive pickup actions at the start of a tour
(Lemma 1), it follows that there are at most L actions between the first pickup
action and the first drop action. This proves the inductive step and the statement
follows.
Since we assign a transport request to every pickup and drop action, the tour
serves all transport requests in TR.
Finally, it follows by construction that there does not exist a transport request
(loc(v), loc(w), 1 so that the minimal path from loc(v) to loc(w) of tour arcs
traverses the tour arcs connecting the depot.
t
u
Lemma 4. Let Γ = (m1 , α1 , . . . , mn−1 , αn−1 , mn ) be a uniform tour starting
and ending in depot vD , and let G = (V, A, w) be a tour graph for Γ . Furthermore, let t : A → N be a function that returns the number of cars transfered
in the corresponding moves in Γ , and let TR be a set of close distance uniform
transport requests for Γ . Then for a transport estimate function f TR for TR it
holds
(i) f TR (a) = t(a) for all a ∈ A, and
(ii) f a (a) + f TR (a) = f a (a0 ) + f TR (a0 ) for all a, a0 ∈ A.
Proof. Firstly, we show that for a transport graph Gt = (V + ∪V − ∪V = , A∪At , w)
for Γ and TR and a transport estimate function f TR for Gt
(a) f TR (a) − f TR (a0 ) = 1 for all a = (v, w) ∈ A, a0 = (w, u) ∈ A with w ∈ V − ,
and
(b) f TR (a) − f TR (a0 ) = −1 for all a = (v, w) ∈ A, a0 = (w, u) ∈ A with w ∈ V + ,
holds. Within the proof, we also show that (i) holds. Secondly, the Statement (ii)
follows from Claim 2.2 (ii).
To prove the third statement, we show that f TR (a) = xa , where ma =
(j, ·, ·, ·, ·, xa ) is the move corresponding to the tour arc a = (v, w) ∈ A. This
can be seen as follows. Since TR is a set of close distance transport requests,
there does not exist a transport request (loc(v), loc(w), 1) so that the minimal
path of tour arcs traverses the tour arcs connecting the depot. Thus, we have
f TR (a) = f TR (a0 ) = 0 where a = (vD , v1 ) ∈ A and a0 = (·, vD ) ∈ A. Since
Γ is a tour, the node v ∈ V corresponds to a pickup action. Thus, for the
move ma1 = (j, ·, ·, ·, ·, xa1 ) corresponding to the tour arc a1 = (v1 , v2 ), we have
xa1 = 1. Furthermore, the tour arc a1 appears once on the right hand side of
Equation (9), i.e., f TR (a1 ) = 1 = xa1 .
If v2 ∈ V + corresponds to a pickup action then the number of cars transfered
from v2 to the next station is increased by one. Since the destination of the
26

transport request that started in v1 does not correspond to v2 , the corresponding
tour arc a2 appears twice on the right hand side of Equation (9): once due to
the transport request (v1 , ·, 1) and once due to (v2 , ·, 1).
Analogously, if v2 ∈ V − corresponds to a drop action, the number of cars
transfered from v2 to the next station is decreased by one. Since the transport arc
corresponding to the transport request (v1 , v2 , 1) ends in v2 , the number of appearances of the tour arc a2 = (v2 , ·) ∈ A on the right hand side of Equation (9)
is decreased as well.
In the first case we have f TR (a1 ) − f TR (a2 ) = −1 and in the second case
TR
f (a1 ) − f TR (a2 ) = 1.
The above arguments can be applied iteratively to all nodes in V + ∪ V − ,
showing that (a) and (b) hold.
Since the values of the transport estimate function f TR corresponds to the
number of cars transfered in the corresponding move, the stament follows directly
from Claim 2.2 (ii).
t
u
Finally, we prove the main theorem of this section.
Theorem 3. For the Static Relocation Problem (G, z 0 , z T , Z D , k, L) with one
depot, the algorithm ReOpt achieves an approximation factor of L + 1 for all
L ∈ N. This approximation factor holds in the symmetric and in the asymmetric
case.
Proof. We start by proving a special case when there is only one driver in the
system. Afterwards, we generalize this special case to the general situation when
there are k drivers in the system.
Let Γ ∗ be an optimal tour for (G, z 0 , z T , Z D , 1, L). Let TRp be a set of
transportation requests induced by a minimal perfect p-matching, and let Γ p an
optimal tour serving all transport requests in TRp , i.e., a tour with a minimal
total tour length serving all transport requests in TRp . Finally, let Γ be the
constructed tour from Algorithm 2. Then we have
`(Γ ∗ ) ≤ `(Γ p ) ≤ `(Γ )
where `(Γ ) is the total tour length of the tour Γ . Thus, we only need to show
that
`(Γ ) ≤ (L + 1)`(Γ ∗ )
(12)
holds.
Let TR be a set of close distance uniform transport requests. Since TRp is
induced by a minimal perfect p-matching, it holds
X
X
d(v, w) ≤
d(v, w)
(v,w,1)∈TRp

(v,w,1)∈TR

Let f a be a traverse counter function for Γ ∗ and let f TR be a transport
estimate function. Let t : A → N be a function that returns the number of cars
transfered in the corresponding moves in Γ ∗ . By definition, a convoy is empty at
27

the beginning of a tour, and therefore, t(a0 ) = 0 for a0 = (vD , ·) ∈ A. Since we
have t(a) = f TR (a) for all a ∈ A (Lemma 4 (i)), it follows f a (a0 ) + f TR (a0 ) =
f a (a0 ). From Lemma 2 we know that f a (a) ≤ L + 1 for all a ∈ A, and thus, it
follows from Lemma 4 (ii) that f a (a) + f TR (a) ≤ L + 1 holds for all a ∈ A.
With above and Equation (10) we can estimate the total tour length `(Γ ) by
X
X
w(at )
`(Γ ) =
f a (a)w(a) +
a∈A

≤

X

f a (a)w(a) +

a∈A

=

X

at ∈At

X

f TR (a)w(a)

a∈A
a

f (a) + f

TR


(a) w(a)

a∈A

≤ (L + 1)

X

w(a)

a∈A

= (L + 1) · `(Γ ∗ )
proving the statement of the theorem if there is only one driver in the system.
Next we consider the general case, i.e., there are k ∈ N drivers. Since there
is only one depot, and every tour starts and ends in the depot, all tours can be
“merged” to one tour. For that let S = (Γ 1 , . . . , Γ k ) be a transportation schedule
with k tours and with Γ j = (mj1 , α1j , . . . , αλj j −1 , mjλj ). Since by assumption T is
large enough, we can construct a new tour Γ = Γ 1 Γ 2 . . . Γ k , where (except for
the first and last tour) the moves to and from the depot are replaced by one
move between the succeeding and preceding station, respectively (see Figure 6
for an illustration). Thus, all k tours are performed by only one driver. Due to
the triangle inequality it follows that the length of the tour Γ is at most the
total tour length of the transportation schedule S. Therefore, we can generalize
the statement when there are k drivers in the system.
-1

c

-1

d

vD

-1

c

vD

-1
2

d

b

-1

2

a

2

b

-1

2

a

f

-1

f

-1

e

e

Fig. 6. This figure illustrates how one driver can perform k tours if there is only one
depot. On the left side, the figure illustrates a transportation schedule with 2 drivers,
On the right side, a combined transportation schedule with only one driver.

Finally, note that we constructed a new tour by following either the tour
arcs (induced by an optimal tour) or the transport request arcs (induced by
28

the minimal perfect p-matching). Especially, no back arc is traversed. Thus, it
follows that this approximation factor is also valid for the asymmetric case when
there is only one depot.
t
u
5.2

Multiple depots

In the case that there is only one depot, the algorithm ReOpt has an approximation factor of L + 1, independently from the number of drivers, or whether
we have the symmetric or asymmetric case. In this section, we consider the case
when there are multiple depots. Hereby, we can further distinguish between two
situations: every tour must start and end in the same depot (Static Relocation
Problem with multiple depots and with backhaul), and every tour can start and
end in a different depot (Static Relocation Problem with multiple depots and
without backhaul).
Firstly, we consider the situation where every tour can start and end in a
different depot (i.e., tours without backhaul). We show that in the asymmetric
case, the algorithm ReOpt generally does not have an approximation factor.
However, we give for a special case an approximation factor of L + 1, namely
when in the optimal tour every driver returns to the depot from where its tour
started. Note that this special case makes an assumption to the properties of
an optimal tour, while the case when we have backhaul forces the tours to have
certain properties in order to be a feasible solution for the Static Relocation
Problem. In the symmetric case without backhaul, the approximation factor is
2 · (L + 1). We gain the factor 2 since the algorithm ReOpt ensures that all
drivers return to their starting depot.
Secondly, we consider the situation when every tour must end in its starting depot (i.e., tours with backhaul). In this situation, we can show that the
algorithm ReOpt has an approximation factor of L + 1 in the symmetric and
asymmetric situation. We show this approximation factor, by applying nearly
the same steps as we do in previous section, where we prove the approximation
factor for the case when there is only a single depot. In fact, we mainly modify
the construction of the transport graph (Definition 1) and Algorithm 2, so that
they are able to handle not only one tour but multiple tours (Algorithm 3).
In order to show, that there does not exist an approximation factor for the
algorithm ReOpt in the asymmetric case, even when there is only one driver,
we consider the following example.
1
2
Example 5. We consider the asymmetric situation with two depots vD
and vD
and four stations V = {a, b, c, d}. There is only one driver in the system, the
convoy capacity is 1. In the stations a and c, one car has to be picked up, and
at b and d one car has to be dropped. We consider the following distances
1
2
1
2
d(vD
, a) = d(b, c) = d(d, vD
) = d(vD
, vD
)=1

d(a, b) = d(c, d) = 2
d(c, b) = d(a, d) = 1
29

and for all other pairs of stations v and w we set
d(v, w) = x,
with x  2 arbitrary. An optimal tour Γ ∗ serving all requests is induced by the
1
2
path (vD
, a, b, c, d, vD
). The total tour length `(Γ ∗ ) = 5.

b−

1

2

a+

c+
2

1

1

d−
1

1
vD

2
vD

Fig. 7. This figure shows a schedule graph for an optimal tour Γ ∗ and the set of minimal transport requests TR = {(c, b, 1), (d, a, 1)}. The arcs, with their numbers below,
correspond to the distance between the connected stations. For all other distances,
i.e., for the distances of the non-visible arcs, the distances are x  1. In the schedule
graph, a pickup action at station v ∈ V is denoted by v + and a drop action by v − .
The dash-dotted arcs correspond to transport arcs.

A set of transport requests induced by a minimal perfect p-matching is given
by TR = {(c, b, 1), (d, a, 1)}. The total tour length `(Γ ) for every tour, serving
the transport requests in TR, is at least x + 4. Since x was arbitrarily selected,
there cannot exist a constant c ∈ R so that
x + 4 ≤ `(Γ ) ≤ c · `(Γ ∗ ) = c · 5
holds.

4

The reason why we cannot give an approximation factor in the previous
example is that we have to traverse at least once an arc that is not traversed by
an optimal tour. Note that this example holds for all algorithms which compute
tours using all arcs from a minimal perfect p-matching. An open question is
whether there exists a deterministic algorithm for the Static Relocation Problem
with multiple depots without backhaul with a constant approximation factor.
However, in order to prove an approximation factor for the a special case of
the Asymmetric Static Relocation Problem with multiple depots without backhaul, where in the optimal transportation schedule every driver returns to its
starting depot, and in order to prove the approximation factor for the Symmetric
Static Relocation Problem with multiple depots without backhaul, we have to
give some definitions and further results.
30

First, we define a graph similar to a transport graph, but in this case it is
constructed from a transportation schedule instead of a tour. As in the transport
graph, the nodes correspond to the actions, and the arcs correspond to moves.
Definition 1. From a given transportation schedule S = (Γ 1 , . . . , Γ k ), where
Γ j = (mj1 , α1j , . . . , αnj j −1 , mjnj ) we can construct a weighted graph G = (V + ∪
1

k

1

k

V − ∪ V = , A, w), with V + = V + ∪ · · · ∪ V + , V − ∪ · · · ∪ V − , V = = V = 1 ∪
· · · ∪ V = k and A = A1 ∪ · · · ∪ Ak , where
j

j

(i) the sets of nodes V j = V + ∪ V − correspond to the actions in Γ j ; the
j
set of pickup nodes V + corresponds to the set of pickup actions, the set
−j
of drop nodes V
to the set of drop actions, the set of depot nodes V = j
j
to the set containing empty actions at the depots, i.e., V = j = {(j, vD
, 0) |
j
j
Γ starts in vD };
j
(ii) there is an arc from v ∈ V j to v 0 ∈ V j if v = αij and v 0 = αi+1
for a
j
j
j
j
1 ≤ i ≤ n , furthermore there is an arc from (j, vD , 0) to α1 and from αn−1
j
to (j, vD
, 0);
(iii) the weight function w corresponds to the distances between the origin and
j
destination stations of the corresponding moves, i.e., we set w(αij , αi+1
)=
d(orig(mji+1 ), dest(mji+1 )).
We call such a graph a schedule graph for S, the set A is called the set of
schedule tour arcs.
Let TR be a set of transport requests. Then a graph Gtm = (V + ∪ V − ∪
=
V , A ∪ At , w) is called transport schedule graph if (V + ∪ V − ∪ V = , A, w) is
a schedule graph and the set At corresponds to the transport requests, i.e., to
every transport request r = (loc(α), loc(α0 ), 1) ∈ TR there is an arc (α, α0 ) ∈ At
assigned to r.
Let S = (Γ 1 , . . . , Γ k ) be a transportation schedule, let TR be a set of transport requests, and let Gtm = (V + ∪ V − ∪ V = , A ∪ At , w) be the corresponding
transport schedule graph. Then we can construct a directed graph from a transport schedule graph, which has as nodes the tours and as arcs the transport
requests between the tours. Laxly said, this graph “highlights” the transport requests which are between two different tours. This simplified version of a transport schedule graph enables us to prove some properties which we need in order
to gain an approximation factor for ReOpt which is independent from the number of depots in the system. Formally, we define a directed graph Gs = (V s , As ),
with
• each node v s ∈ V s corresponds to a tour Γ ∈ S, and
• every arc corresponds to a transport request (loc(α), loc(α0 ), 1) ∈ TR, where
i
i
j
j
α and α0 are in different tours, i.e., α ∈ V + ∪ V − , α0 ∈ V + ∪ V − , with
i 6= j.
We call the graph Gs a tour connection graph for Gtm (see Figure 8 for an
illustration). Note, that a tour connection graph is loop free, but there can be
multiple arcs between two nodes.
31

1
vD
−

d

b+
2

2
vD

c−

b+
1
f1+

a−

f2+
e−

Fig. 8. This figure shows a tour connection graph constructed from the two tours
shown in Figure 2 and from the transport requests induced by an optimal solution
(see Figure 1). Solid arcs correspond to the schedule tour arcs, and the dashed arcs
correspond to the transport requests. In the graph, a pickup action at station v ∈ V
+
is denoted by v + and a drop action by v − . The nodes b+
1 and b2 correspond both to
+
+
a pickup action at station b (and analog for the nodes f1 and f2 ). Furthermore, note
that both tours start in the same depot, but in a tour connection graph, there is a
depot for each tour.

Lemma 5. Let S = (Γ 1 , . . . , Γ k ) be a transportation schedule, let TR be a set of
transport requests, and let Gtm = (V + ∪ V − ∪ V = , A ∪ At , w) be a corresponding
transport schedule graph. Furthermore, let Gs be a tour connection graph for
Gtm . Then it is true
(i) every connected component in Gs is also strongly connected,
(ii) if every tour in S is a tour with backhaul, then every connected component
in Gtm is also strongly connected.
Proof. “(i)”: we prove that for every node v s ∈ V s and for every outgoing arc
as ∈ As of v s there exists an incoming arc as ∈ As of v s . Every transport arc
at = (v, w) ∈ At connects exactly two actions. Whenever v corresponds to an
action in one tour Γ and w corresponds to an action in another tour Γ 0 , there is
an arc as ∈ As . Since every action in S is uniform, it follows that the number of
non-empty actions in every tour is even. Therefore, there must exist a transport
arc (v 0 , w0 ) ∈ At , with w0 ∈ Γ and v 0 ∈ Γ 00 6= Γ , i.e., there is an incoming arc in
As . Thus, we have |δ + (v s )| = |δ − (v s )| for all v s ∈ V s .
From Euler’s Theorem it now follows that in every connected component
of Gs there exists an Eulerian walk. Especially, it follows that every connected
component of Gs is also strongly connected.
“(ii)”: since S is a transportation schedule with backhaul, every tour of S is
represented by a cycle of tour arcs in G and, thus, a strongly connected component. From the two statements above it follows that every connected component
in Gtm is also strongly connected.
t
u
Note, in the asymmetric case without backhaul, connected components in Gtm
are generally not strongly connected (e.g., see Example 5). Furthermore, whenever we modify this graph so that every connected component becomes strongly
connected, at least one arc cannot be estimated in general. Later we see that in
32

the symmetric case, we can modify Gs so that every connected component in Gs
is also strongly connected and every added arc can be estimated. This is achieved
by connecting some actions with the “original” depot. In the symmetric case, an
approximation factor can then still be computed since the distance from v to w
is equal to the distance from w to v.
Algorithm 3 Construct new transportation schedule (asymmetric case with
multiple depots and without backhaul)
Input: a uniform transportation schedule S with backhaul, a set of depots VD , a set
of uniform transport requests TR
Output: a uniform transportation schedule S with backhaul
1
k
1: construct transport schedule graph G = (V + ∪ · · · ∪ V + ∪ V − ∪ V = , A ∪ At , w)
j
2: initialize Γ ← ∅ for all j ∈ {1, . . . , k}
3: for j ∈ {1, . . . , k} do
. loop through every tour
j
j
4:
initialize currN ode ← vD
. tour Γ j starts in depot vD
5:
initialize currT our ← j
. the currently considered tour
currT our
6:
while not every node in V +
has been visited do
currT our
7:
if currN ode ∈ V +
and has not been visited then
8:
mark currN ode as visited
9:
follow transport arc and add corresponding moves and actions to Γ
10:
update currT our if tour is changed
11:
else
12:
follow tour arc and add corresponding move to Γ
13:
update currN ode
14:
follow current tour until arriving in depot
15: insert empty actions between two successive moves if necessary
16: return S = (Γ 1 , . . . , Γ k )

Algorithm 3 constructs a new transportation schedule with backhaul from a
given uniform transportation schedule with backhaul, a set of depots and a set
of uniform transport requests. Hereby, the algorithm always prioritizes following
transport request arcs over following tour arcs. Similarly to the constructed tour
from the previous section, we state and prove some properties of this transportation schedule.
It is easy to see that Algorithm 3 constructs a new transportation schedule.
However, it is not obvious that in this transportation schedule all drivers return
to their original depot, which we show in the next lemma.
Lemma 6. Let S be a uniform transportation schedule with backhaul, let VD be a
set of depots and let TR be a set of uniform transport requests. Then Algorithm 3
constructs a new transportation schedule with backhaul.
Proof. In Algorithm 3 we “follow” the tour arcs of a tour until we come to a
pickup node that has not been visited before (lines 7 and 12). If in the algorithm
the current node is a non-visited pickup node, then the algorithm “follows” the
33

transport (lines 8–10). From Lemma 5 we know that every connected component in G is also strongly connected. Furthermore, the number of incoming and
outgoing arcs for every node in Gs are equal and, thus, there exists an Eulerian
walk in Gs . Therefore, it follows that the transportation schedule constructed in
Algorithm 3 is a transportation schedule with backhaul.
t
u
Next, we show that the approximation factor L + 1 holds even in the case of
multiple depots.
Theorem 4. For the Static Relocation Problem (G, VD , z 0 , z T , Z D , k, L) with
multiple depots and with backhaul, and a complete graph G, the algorithm ReOpt computes a non-preemptive transportation schedule and achieves an approximation factor of L + 1. This approximation factor holds for the symmetric
and asymmetric situation.
Proof. In order to prove this statement, we show how the results of the previous
section can be applied to the case when there are multiple depots. For that we
concentrate on an arbitrary tour from the optimal transportation schedule and
show that we can apply the results from the previous section on this tour. Since
the tour is arbitrarily selected, the statement then follows.
Let Gtm be a transport schedule graph for an optimal transportation schedule
S and let TRp be a set of transport requests computed from a minimal perfect
p-matching. Let Γ ` ∈ S be an arbitrary tour. We say that there is a transport
request between tours, if there exists a transport request arc (v, w) in Gtm so
i
j
that v ∈ V + and w ∈ V − with i 6= j. In other words, if v corresponds to a
pickup action in a tour Γ i and w corresponds to a drop action in tour Γ j with
i 6= j.
As we did before, we construct tours Γ from the optimal transportation
schedule and the set of transport requests.
We consider two different cases for this tour, when there are no transport
requests in TR between this tour and another tour, and when there are transport
requests in TR between this tour and another tour.
Case 1 (there are no transport requests in TR between this tour and another
tour): in this case, we can directly apply Theorem 2 on Γ ` , showing the statement
for this case.
Case 2 (there are transport requests in TR between this tour and another
tour): in this case, we cannot directly apply Theorem 2 as we did in the previous
case. However, due to Remark 2, it is not necessary to start the construction
of a new tour within the depot but it can be used any arbitrary node within
a transport graph. Furthermore, all results from Section 5.1 hold, when the
construction has not been started in the depot.
From Lemma 5 it follows that whenever Algorithm 3 “leaves” a tour at
`
`
node v ∈ V + , it will eventually “return” to a node w ∈ V − . Hereby, w is the
first “entered” node after the tour has been changed.
From the point of view of the tour Γ ` , the path from v to w in Gtm is like
a transport request from v to w. Thus, we replace this path by an artificial
34

transport request arc (v, w). By repeating this procedure for all nodes which
are start or end nodes of a transport request between Γ ` and another tour, we
receive a transport graph G` . On the constructed tour from G` and the transport
requests we apply Theorem 2. Since the tour was arbitrarily selected, this proves
the statement.
t
u
Finally, we consider the Symmetric Static Relocation Problem with multiple
depots and without backhaul. For a first result, we show that the algorithm
ReOpt achieves an approximation factor of at most 2 · (L + 1). In order to prove
this approximation factor, we construct in an intermediate step a transportation
schedule with backhaul S from the optimal transportation schedule S ∗ . For
every tour Γ ∗ ∈ S ∗ we construct a new tour Γ by adding an arc from the
last action of Γ ∗ back to the “starting” depot (if they differ in the original
tour). Since we consider the symmetric situation, this arc can be estimated by
the total tour length of Γ ∗ . Thus, the total tour length of this constructed
transportation schedule is at most twice as large as the total tour length of the
optimal transportation schedule. Applying Theorem 4 on S then yields:
Theorem 5. For the Symmetric Static Relocation Problem (G, VD , z 0 , z T , Z D , k, L)
with multiple depots and without backhaul, and a complete graph G, the algorithm
ReOpt computes a non-preemptive transportation schedule and achieves an approximation factor of 2 · (L + 1).

6

Computational Results

Both, the exact approach and the heuristic approach ReOpt, have been tested
on randomly generated instances (with 20–80 over-/underfull stations, 50–100
stations in total, convoy capacities 5 and 10, and 10–30 drivers). The stations are
randomly distributed on a plane and the distances between two closest stations
(w.r.t. the Euclidean metric) are kept as rounded integers in the graph. Hereby,
we ensure that the graph is connected. The time horizons are set to 100 in all
test runs. Note that the size of these instances corresponds to small car- or
bikesharing systems or to clusters of larger systems, as in [14].
The algorithm ReOPT has been implemented in C++, and CPLEX v12.4
is used for solving ILPs. The operating system is Linux (CentOS with kernel
version 2.6.32). The tests have been run on an Intel Xeon X5687 clocked at
3.60GHz, with 64 GB RAM.
For solving the integer linear program of the exact approach, we use Gurobi
5.6. The test have been run on a Linux server (CentOS with kernel version 2.6.32)
with 160 Intel Xeon CPUs E7-8870 clocked at 2.40GHz, with 1 TB RAM. For
the tests, we limited the number of threads to 32. Since we could not find any
feasible solution for the first instance after 40 hours, we rerun the solver on
this instance with an increased time-limit of 160 hours. After about 50 hours,
a feasible solution has been found by Gurobi. However, even after 160 hours,
the optimal solution could not be found. Due to the enormous runtime and the
little to no gain, we did not rerun the solver with an increased time-limit on the
35

remaining instances. The solution found by the ILP solver has a total tour length
of 337 units and the lower bound found by Gurobi is 109 (thus, the duality gap is
approximately 67.7%). Due to the enormous runtime of finding a solution with
the exact approach, we did not continue with the other instances. Furthermore,
one can see, that the improvements of the solution of the ILP solver are very
little compared to the extra computational time spend.
In order to compute a preemptive transportation schedule, it is not necessary to distinguish between each of the drivers. Therefore, there are less variables
within the integer linear program which models the preemptive situation than
within the integer linear program which models a non-preemptive situation for
the same instances. Since the total tour lengths of transportation schedules with
preemption give lower bounds for the total tour lengths of non-preemptive transportation schedules, we state the lower bounds computed from non-preemptive
transportation schedules. The lower bounds from Table 1 are taken from feasible
preemptive transportation schedules, and the duality gaps are computed from
these lower bounds.
ReOPT computes solutions within a reasonable time (in average less than 1.5
minutes for the smaller instances with at most 40 imbalanced stations, less than
8 minutes for the middle sized instances with 60 imbalanced stations, and about
17 minutes for the bigger instances with 80 imbalanced stations, see Table 1).
Table 1. This table shows the average computational results for several test sets of
instances of the algorithm ReOPT in comparison to the found optimal value by solving
the ILP (the time limit was set to 2h and 4h). The considered time horizon is 100 for all
test instances. The algorithm ReOPT was run several times with different parameters
for N and ∆. In this table, the following parameters and results are shown: the total
amount of stations (1st column) and the number of overfull and underfull stations (2nd
column). Hereby, the numbers in brackets are the number of overfull resp. underfull
stations. Furthermore, it shows the number of drivers k, the server capacity L, the
average runtime in seconds of ReOPT, the total tour length found by ReOPT and by
the ILP solver, and the average optimality gap ((ttlReOP T − ttlILP )/ttlReOP T ).
stations
50
50
100
100

7

±stations
20 (10/10)
40 (20/20)
60 (30/30)
80 (40/40)

k
10
20
30
30

L runtime (s) ttl (ReOPT) ttl (ILP 2h) ttl (ILP 4h) gap (%)
5/10
2.5
354.25
330
330
7.35
5/10
72.33
469
435.75
432.5
7.74
5/10
451.5
665.67
526
521
16.73
5/10 981.92
658.33
–
–
–

Conclusion

In this paper, we considered the Static Relocation Problem (M, z 0 , z T , Z D , k, L),
where tours for k drivers have to be computed in a (quasi) metric space M , where
the maximal length of the tours must be smaller or equal to a given time horizon
T . Hereby, the drivers transfer cars between the stations by forming convoys of
36

at most L cars. In order to have an exact solution we construct a time-expanded
network GT from the original network G and compute coupled flows (a car and
a driver flow) on this network with an ILP. Due to the coupling constraints, the
constraint matrix of the network is not totally unimodular (as in the case of
uncoupled flows), reflecting that the problem is at least N P-hard.
Thus, we presented a heuristic approach to solve the Static Relocation Problem: the algorithm ReOpt. The construction of the tours by ReOpt is as follows: firstly, transport requests between “overfull” and “underfull” stations are
generated by a perfect p-matching. These transport requests serve as input for
a Pickup and Delivery Problem, which is solved in the second step. Finally,
the tours are iteratively augmented by “rematching” certain origin/destination
pairs, i.e., to reinsert accordingly adapted moves in such a way that the total
tour length decreases.
The algorithm ReOpt has an approximation factor based on the given convoy sizes for the Symmetric Static Relocation Problem with and without backhaul (Theorem 2 and Theorem 3). In the asymmetric situation, the approach
ReOpt can ensure a finite upper bound for the ratio of its solution to the optimal
solution only for the Asymmetric Static Relocation Problem with backhaul (Example 5 and Theorem 5). The approximation factors for ReOpt in the different
situations are summarized in Table 2.
Table 2. This table summarizes the approximation factors of ReOpt. All different
situations which we consider in this paper are shown. In the case that there is only one
depot, the tours with and without backhaul coincide (the reason why we marked two
entries with a hyphon ‘-’).
with backhaul
without backhaul
symmetric asymmetric symmetric asymmetric
single
L+1
L+1
multiple L + 1
L+1
2(L + 1)
∞

Both approaches have been tested on randomly generated instances (with
20–80 over-/underfull stations, 50 and 100 stations in total, convoy capacities 5
and 10, and 10–30 drivers). The time horizon was set to 100 in all test runs. Note
that the size of these instances corresponds to small car- or bikesharing systems
or to clusters of larger systems, as in [14]. While the optimal solution could not
be found even after 160 hours, the algorithm ReOPT computes solutions within
a reasonable time (in average less than 1.5 minutes for the smaller instances with
at most 40 imbalanced stations, less than 8 minutes for the middle sized instances
with 60 imbalanced stations, and about 17 minutes for the bigger instances with
80 imbalanced stations), and a reasonable gap to the solution computed by the
ILP (see Table 1). In order to be able to give at least a meaningful duality gap,
we compared the solution with some lower bounds for preemptive transportation
schedules, which can be computed in a shorter time.
37

There are several practical and theoretical open questions according to the
Static Relocation Problem. Improving the runtime and solutions of ReOPT is
one goal. Usually, every driver used gives additional costs. Thus, it is desirable
to know the minimal number of drivers needed in order to solve the Static
Relocation Problem within the given time horizon. To the best of our knowledge
this is still an open question. Due to the time horizon, it is possible that there
does not exist a feasible solution for a given instance at all. Having feasibility
conditions is useful in two directions: to save unnecessary computation time for
an algorithm and to generate test instances which can give feasible solutions.
Thus, finding feasibility conditions as well as lower bounds for the time horizon
is another goal for the future.

References
1. Michael O. Ball, Thomas L. Magnanti, Clyde L. Monma, and George L.
Nemhauser, editors. Network Models, volume 7 of Handbooks in Operations Research and Management Science. Elsevier Science B.V., Amsterdam, 1995.
2. Michael O. Ball, Thomas L. Magnanti, Clyde L. Monma, and George L.
Nemhauser, editors. Network Routing, volume 8 of Handbooks in Operations Research and Management Science. Elsevier Science B.V., Amsterdam, 1995.
3. Mike Benchimol, Pascal Benchimol, Benoı̂t Chappert, Arnaud de la Taille, Fabien
Laroche, Frédéric Meunier, and Ludovic Robinet. Balancing the stations of a self
service ”bike hire” system. RAIRO - Operations Research, 45:37–61, 0 2011.
4. Daniel Chemla, Frédéric Meunier, and Roberto Wolfler Calvo. Bike sharing systems: Solving the static rebalancing problem. pages 120–146, 2013.
5. Claudio Contardo, Catherine Morency, and Louis-Martin Rousseau. Balancing a
dynamic public bike-sharing system. Technical Report 9, CIRRELT, 2012. https:
//www.cirrelt.ca/DocumentsTravail/CIRRELT-2012-09.pdf.
6. Madeleine EL-Zaher, Baudouin Dafflon, Franck Gechter, and Jean-Michel Contet.
Vehicle platoon control with multi-configuration ability. Proc. Computer Science,
9(0):1503–1512, 2012.
7. Fatma Pinar Goksal, Ismail Karaoglan, and Fulya Altiparmak. A hybrid discrete
particle swarm optimization for vehicle routing problem with simultaneous pickup
and delivery. Computers and Industrial Engineering, 65(1):39–53, May 2013.
8. Pascal Halffmann, Sven O. Krumke, Alain Quilliot, Annegret K. Wagler, and JanThierry Wegener. On the online max-accept relocation problem. Procedings of
6th International Workshop on Freight Transportation and Logistics (ODYSSEUS
2015), 2015. (to appear).
9. Pascal Halffmann, Sven O. Krumke, Alain Quilliot, Annegret K. Wagler, and JanThierry Wegener. On the online min-wait relocation problem. Procedings of LAGOS2015, 2015. (to appear).
10. Sven O. Krumke, Alain Quilliot, Annegret K. Wagler, and Jan-Thierry Wegener.
Models and algorithms for carsharing systems and related problems. Electronic
Notes in Discrete Mathematics, 44(0):201 – 206, 2013.
11. Sven O. Krumke, Alain Quilliot, Annegret K. Wagler, and Jan-Thierry Wegener.
Relocation in carsharing systems using flows in time-expanded networks. In
Joachim Gudmundsson and Jyrki Katajainen, editors, Experimental Algorithms,
volume 8504 of LNCS, pages 87–98. Springer, 2014.

38

12. George L. Nemhauser, Alexander H. G. Rinnooy Kan, and Michael J. Todd, editors.
Optimization, volume 1 of Handbooks in Operations Research and Management
Science. Elsevier Science B.V., Amsterdam, 1989.
13. Marian Rainer-Harbach, Petrina Papazek, Bin Hu, and Günther R. Raidl. Balancing bicycle sharing systems: A variable neighborhood search approach. In EvoCOP,
pages 121–132, 2013.
14. Jasper Schuijbroek, Robert Hampshire, and Willem-Jan van Hoeve. Inventory
rebalancing and vehicle routing in bike sharing systems. 2013. working paper.

39

