Vehicle Routing Problems with Time Windows and
Multiple Service Workers

Customer Clustering

Gerald Senarclens de Grancy <gerald@senarclens.eu>,
Dagmar Tschabrun <dagmar.tschabrun@edu.uni-graz.at>,
Marc Reimann <marc.reimann@uni-graz.at>

YAMS, December 2013, Salzburg

Problem Origin and Background

Delivery of soft drinks to small and medium sized retailers in São Paulo:

1. Time windows for delivery ⇒ variation of the VRPTW
2. High-density populated region
3. Congested streets and scarcity of parking lots

Solution

• Driver parks vehicle close to some customer sites
• Goods are delivered to nearby customers by foot (using hand trolley)
• ⇒ long service times at each parking site
• Service time can be reduced by assigning larger crews to the vehicles
• Particularly interesting if workers are cheap in relation to trucks

New Problems

• Several new problems have to be dealt with
1. VRPTW with the additional decision of assigning multiple service workers to each vehicle ⇒ VRPTWMS
2. Customer clustering and parking space allocation
• Assigning customers to parkings (clustering) difficult because of time windows
• Related Problems include the multi-depot VRPTW, two-echelon VRPTW and Truck and trailer RPTW
3. Combined learning for clustering and routing to obtain better results

Prior Work

• Prior work by Pureza et al. (2011)
• Hierarchical objective function
1. Fleet size
2. Crew size
3. Total distance
• Modeled problem under strong assumptions
• Adjusted VRPTW instances from Solomon (1987)
• Nodes' coordinates correspond to cluster parking sites
• Parking sites are pre-assigned the actual customers to be visited
• Allocation of customers to parking sites are given as inputs
• Clusters' service time is a linear function of the demand and the number of service workers
• Designated parking spaces are not occupied
• "Outer routing" results by Pureza et al. (2011)
• Tested against adjusted R1 instances
• Tabu search: 148 vehicles, 389 service workers and 15105 distance units
• ACO: 150 vehicles, 377 service workers and 15137 distance units
• Our Results of the pre-clustered routing problem using ACO
• Outperformed results for 11 of the 12 R1 instances
• 145 (-2.02%/ -3.33%) vehicles
• 368 (-5.40%/ -2.39%) service workers
• 14976.83 (-0.85%/ -1.06%) distance units

Motivation

• Delivering small (portable) packages (eg. mail)
• Particularly interesting in (limited time) pedestrian areas
• Mitigates effects of rush hours and congestion
• Cost reduction and sustainability
• Reduces cost on vehicles, fuel, inner city tolls, ...
• Implicitly incorporates green objectives
• Clustering is required
• Cluster assignment problem and routing are not independent
• Otherwise, outer routing algorithms essentially useless for practical purposes
• Assumptions
• Deliveries are portable by a single worker
• Only direct delivery between parking and customers
• Cluster service time and time windows depend on inner schedule
• Customers are serviced by one worker
• Additional workers do not reduce service times at customers
• Additional workers allow servicing customers in parallel
• Designated parking spaces are not occupied
• Customer Scheduling
• Scheduling is also NP-hard
• Fast heuristic needed
• Ideally, the heuristic can be incorporated in a scheduling + outer routing learning process
• Objective function is $$\min C(t, s, d) = t \cdot c_t + s \cdot c_s + d \cdot c_d$$
• Different scheduling solutions can have the same (optimal) objective function value
• $t$
number of trucks
$s$
number of service workers
$d$
total distance driven by all trucks
$c_t$
fixed cost per truck
$c_s$
fixed cost per service worker
$c_d$
cost per distance unit

Goals

The objective of our current research is to identify good heuristics for creating customer clusters that can be efficiently serviced by as few trucks and workers as possible (minimize the objective function of the outer VRPTWMS).

The clustering consists of assigning customers to parking locations and determining a schedule for servicing the assigned customers.

1. Identification of required algorithmic components
2. Creation of realistic benchmark instances
3. Implementation and systematic evaluation of these heuristics

New Benchmark Instances

• Solomon instances do not reflect problem characteristics
• Some customers may have a parking
• Defined data interchange format using JSON schema
• Instances are easy to read in almost any programming language
• Single ASCII string
• Clients, parkings and the depot are denoted by their integer id
• Clusters are denoted by the id of their parking location, followed by a comma (','), followed by all clients in the cluster in the order they are processed (which might be in parallel) separated by commas
• Clusters are written in order they are visited on a route and separated by semicolons (';')
• Routes/ Trucks are encoded by the number of workers on the route followed by a semicolon followed by the starting depot; then all clusters are listed, separated by semicolons and followed by the closing depot
• Routes are separated by a single space
• Additional whitespace is forbidden in solution strings
• Example: '3;0;8,2,5,7;10,6;0 2;0;1,1,4;9,3;0'
• 54 representative instances
• Each instance has 200 clients
• 27 regionally clustered + 27 randomly distributed
• Instances with 50, 100 and 150 parking locations
• Tight, normal and wide time windows
• Low, normal and fast walking speed in relation to driving speed
• Example
• {
"name": "presentation 3",
"description": "This instance is for presentation/ demo purposes. It can also be used to test the efficiency of algorithms as it is designed with an optimal solution in mind. It can be solved with three trucks - one with one, the second with two and the third with three service workers. Parking at the customer sites is forbidden by an extremely high penalty.",
"truckCapacity": 100.0,
"costTruck": 1.0,
"costWorker": 0.1,
"costDistance": 0.0001,
"bestKnownTrucks": 3,
"bestKnownWorkers": 6,
"bestKnownDistance": 410.9302842022,
"bestKnownCost": 3.6410930284,
"bestKnownSolution": "3;0;1,6,10;2,5;3,8,12,11,14;4,9,13,7;0 2;0;15,21,27,23,30;18,28,25,24;16,20,26;19,22;17,29;0 1;0;31,47,43;35,40;32,45,49;36,41;31,48;33,46,42,44;0",
"optimumKnown": true,
"depot": { "id": 0, "x": 0.0, "y": 0.0, "est": 0.0, "lst": 480.0},
"parkings": [
{ "id":  1, "x": -29, "y": -31 },
...
{ "id": 39, "x":  -1, "y":  36 }
],
"clients": [
{ "id":  5, "x": -39, "y":  -9, "demand": 10, "est":   0, "lst": 240, "st": 5 },
...
{ "id": 49, "x":  53, "y":  -9, "demand": 10, "est":   0, "lst": 480, "st": 5 }
]
}


Clustering Customers

• Currently: cluster first, route second
• Clusters are built in parallel - one client at a time
• Each cluster keeps track of its service time and earliest and latest start
• A minimum amount of workers may be required
• Service time and earliest and latest start are calculated for each possible number of workers
• Outer routing algorithm gets the clusters as black boxes
Building Clusters
• For each client we decide whether
1. The client is added to an existing cluster or
2. a new cluster should be created using a dedicated parking
• The clustering currently uses an implicit objective function (attractivity) mainly minimizing the sum of the "makespan"
• When all clients are assigned, the outer routing is performed
• Created MIP model
• Parameters
$N$
set of customers ($n \in N$)
$P_0$
set of parking sites including the depot ($p \in P_0$)
$M$
set of customers and parking sites ($m \in M$), $M = N \bigcup P_0$
$C$
set of clusters ($c \in C$), $\vert C \vert$ = $\vert N \vert$
$L$
set of service workers in any cluster ($l \in L$)
$Q$
sufficiently large number to exclude certain combinations of customers, parking sites and service workers
$wt_{pn}$
walking time from parking site $p$ to customer $n$
$\alpha_{pn}$
earliest starting time of a customer minus $wt_{pn}$
$\beta_{pn}$
latest starting time of a customer minus $wt_{pn}$
$st_{np}$
service time of customer $n$ plus return time to parking site $p$
$d_n$
demand of customer $n$
$\text{cap}$
truck capacity
$\eta \in \{1,0\}$
parameter controlling emphasis on minimizing the number of clusters versus the makespan
• Decision Variables
• $x_{cp}=\begin{cases} 1, \text{if cluster }c\text{ uses parking site }p\\ 0, \text{otherwise} \end{cases}$
• $y_{cpn}=\begin{cases} 1, \text{if customer }n\text{ is in cluster }c\text{ with parking site } p\\ 0, \text{otherwise} \end{cases}$
• $v_{nn'}^{lc}=\begin{cases} 1, \text{if service worker }l\text{ walks from }n\text{ to }n'\text{ in cluster }c\\ 0, \text{otherwise} \end{cases}$
$\delta_n$
actual starting time at a customer $n$ which is a real number with a lower bound of zero
$\overline{\xi_c}$
actual finishing time of cluster $c$ (time when a truck leaves) which is a real number with a lower bound of zero
$\underline{\xi_c}$
actual starting time of cluster $c$ (time when truck arrives) which is a real number with a lower bound of zero
• $$\min z = \eta \sum_{c \in C} (\overline{\xi_c} - \underline{\xi_c}) + (1-\eta) \sum_{c \in C}\sum_{p \in P0}x_{cp}$$
s.t.
$$\overline{\xi_c} - \underline{\xi_c} \geq 0\\ \sum_{p \in P_0} x_{cp} \leq 1, \forall c \in C\\ \sum_{n \in N} y_{cpn} \cdot d_n \leq \text{cap} \cdot x_{cp}, \forall p \in P_0, \forall c \in C\\ \sum_{c \in C}\sum_{p \in P0} y_{cpn} = 1, \forall n \in N\\ y_{cpn} \leq x_{cp}, \forall n \in N, p \in P_0, \forall c \in C\\ x_{cp} \leq \sum_{n \in N} y_{cpn}, \forall p \in P0, \forall c \in C\\ \sum_{l \in L} \sum_{\substack{n' \in M \\ n' \neq n}} v_{nn'}^{lc} \leq \sum_{p \in P_0} y_{cpn}, \forall c \in C, \forall n \in N\\ \sum_{n'' \in M} v_{n''n}^{lc} = \sum_{n' \in M} v_{nn'}^{lc}, \forall n \in N, \forall c \in C, \forall l \in L\\ \sum_{c \in C}\sum_{l \in L}\sum_{\substack{n' \in M \\ n' \neq n}} v_{nn'}^{lc} = 1, \forall n \in N\\ \delta_n \geq \alpha_{pn} \cdot y_{cpn} - Q \cdot (1-y_{cpn}),\forall n \in N, \forall p \in P0, \forall c \in C\\ \delta_n \leq \beta_{pn} \cdot y_{cpn} + Q \cdot (1-y_{cpn}),\forall n \in N, \forall p \in P0, \forall c \in C\\ \delta_n \geq \delta_{n'} + wt_{pn'} + st_{pn'} -Q \cdot (1-v_{n'n}^{lc}) - Q \cdot (1-y_{cpn}), \forall n \in N, \forall p \in P0, \forall l \in L, \forall n' \in M, \forall c \in C\\ \underline{\xi_c} \leq \delta_n + Q \cdot (1-y_{cpn}), \forall n \in N, p \in P_0, \forall c \in C\\ \overline{\xi_c} \geq \delta_n + (wt_{pn} + st_{pn}) \cdot y_{cpn} - Q \cdot (1-y_{cpn}), \forall n \in N, p \in P_0, \forall c \in C\\$$

Summary and Outlook

Summary/ Accomplishments
• Currently best known solutions on outer routing
• Formulation and modeling of clustering problem
• Designed modular heuristics
• Implemented prototype
• Created specification (schema) for benchmark instances
• Generated designed and random benchmark instances
Remains to be done
• Allow changing the parking location as new customers are added to clusters
• Link cluster creation and outer routing
• Create local search operators to improve clusters

Selected Bibliography

VRPTWMS

Pureza, Vitoria; Morabito, Reinaldo and Reimann, Marc Vehicle Routing with Multiple Deliverymen: Modeling and Heuristic Approaches European Journal of Operational Research (2011)

VRPTW

Bräysy, Olli and Gendreau, Michel Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms Transportation Science vol. 39, iss. 1, pp 104-118, INFORMS (2005)
Bräysy, Olli and Gendreau, Michel Vehicle Routing Problem with Time Windows, Part II: Metaheuristics Transportation Science vol. 39, iss. 1, pp 119-139, INFORMS (2005)
Goel, Asvin and Gruhn, Volker Solving a dynamic real-life vehicle routing problem Operations Research Proceedings 2005, pp 367–372, Springer (2006)
Pisinger, David and Ropke, Stefan Large neighborhood search Handbook of Metaheuristics, pp 399-419, Springer (2010)
Solomon, M. M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints Operations Research, Vol. 35, No. 2, pp. 254-265 (1987)

Scheduling

Lenstra, J. K.; Shmoys, D. B. and Tardos, É. Approximation algorithms for scheduling unrelated parallel machines Mathematical Programming 46 (1990)
Pinedo, Michael L. Scheduling – Theory, Algorithms, and Systems Springer (2012)
Pinedo, Michael L. Planning and Scheduling in Manufacturing and Services Springer (2012)