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

Additional applications
- 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
- Human readable
- Instances are easy to read in almost any programming language
Added additional meta-data like the serialized best known solution
- 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\\ $$

Learning from Prior Results

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

Questions and Feedback

gerald@senarclens.eu

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)

Problem Origin and Background

Solution

New Problems

Prior Work

Motivation

New Benchmark Instances

Clustering Customers

Learning from Prior Results

Clustering Ant Colony Optimization

Routing Ant Colony Optimization

Results

Summary and Outlook

Questions and Feedback

gerald@senarclens.eu

Selected Bibliography

VRPTWMS

VRPTW

Scheduling

Problem Origin and Background

Solution

New Problems

Prior Work

Motivation

New Benchmark Instances

Clustering Customers

Learning from Prior Results

Clustering Ant Colony Optimization

Routing Ant Colony Optimization

Results

Summary and Outlook

Questions and Feedback gerald@senarclens.eu

Selected Bibliography

VRPTWMS

VRPTW

Scheduling

Questions and Feedback

gerald@senarclens.eu