Vehicle Routing Problems with Time Windows and
Multiple Service Workers

Combined Learning for Clustering and Routing

EULOG, November 2014, Vienna

# 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 alternative mode of transportation
• foot (using hand trolley)
• cargo bike
• cargo scooter
• ...
• ⇒ 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
• Overcome lack of explicit objective function for clustering
• Allow learning from different routing problems

# Prior Work

• Prior work by Pureza et al. (2011)
• Hierarchical objective function $$\min C(t, s, d) = t \cdot c_t + s \cdot c_s + d \cdot c_d$$
1. Fleet size
2. Crew size
3. Total distance
$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
• 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
• 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 but lacks explicit objective function
• Cluster assignment problem and routing are not independent
• Otherwise, outer routing algorithms essentially useless for practical purposes

# 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 sequentially - one 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
• Routing algorithm gets the clusters as black boxes
Building Clusters
• For each client we decide whether
1. The client is added to the current 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 accumulated "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\\$$

# Clustering Ant Colony Optimization

• Problem is modeled as a graph of locations
• 15 minutes combined runtime
• Clusters are created one at a time using sequential heuristic with stochastic elements
• after num_ants iterations, a memory data structure is updated to allow learning from the best known solution
• Seed selection via weighted roulette wheel
• cluster.attractiveness() * trail(cluster.parking, cluster.client)
• Additional clients use a different trail
• cluster.evaluate_addition(client) * trail(cluster, client)
• Cluster can be kept as is or extended
• Trail is normalized to avoid bias for large clusters

# Routing Ant Colony Optimization

• Routing based on adapted Solomon I1 heuristic
• Additional matrices for the routing pheromone
• Since clusters change on every iteration, trails are location-based
• Pheromone requires $(m+1) * (n+1)$ lookups to represent each link
• Trail is normalized to avoid bias for large clusters
• Seed selection by depot distance and trail

# Results

• Aggregated total cost reduced by 10.74% (average) over prior BKS
• Trucks: -12.15% , workers: -4.68%, distance: -20.25%
                cost           clusters       trucks           workers          distance
average before: 41.24          89.46          32.80            81.06            3424.06
average after:  36.81          47.13          28.81            77.26            2730.73
average delta:   4.43 (-10.74%)                3.99 (-12.15%)   3.80 ( -4.68%)   693.33 (-20.25%)
best after:     34.98          46.74          27.33            73.83            2611.35
best delta:      6.26 (-15.19%)                5.47 (-16.67%)   7.23 (-8.91%)    812.71 (-23.74%)


• Apparently, it pays off to create larger clusters
• 89.46 (before) -> 47.13 (average)
• Also "improved" 3 out of 12 classical VRPTW results

# Summary and Outlook

Summary/ Accomplishments
• Designed feedback loop for learning from past results
• Created ACO using the feedback for both clustering and routing
• Implemented algorithms are published as open source
• Improved best known solutions for all benchmark instances
Remains to be done
• Allow changing the parking location as new customers are added to clusters
• 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)