VRPTW with

Multiple Service Workers

Route construction heuristics

- Problem Background and Motivation
- Route Construction Mechanisms
- Metaheuristics
- Numerical Results
- Summary and Outlook

- Proposed by G. B. Dantzig and J. H. Ramser (1959)
- Service a number of customers with a fleet of vehicles
- Vehicles have limited carrying capacity
- Objective is to serve all customers
- Using a minimum number of trucks
- Traveling a minimum distance

- Solving is computationally complex
- Particularly for bigger instances
- Exact algorithms have "long" runtime
- Heuristic approach allows to quickly find near optimal solutions

- (C)VRP has been extensively dealt with
- G. B. Dantzig and J. H. Ramser (1959)
- G. Clarke and J. W. Wright (1962)
- M. Reimann, M. Stummer and K. Doerner
- ...

- Variation of the VRP
- Same objective function and constraints as VRP

- Additional constraints: delivery locations have time windows
- New constraints can facilitate finding solutions
- However in general, the computational complexity increases

- Solving is computationally complex
- Particularly for bigger instances
- Exact algorithms have "very long" runtime
- Heuristic approach is required to quickly find near optimal solutions
- Metaheuristics allow to improve the solution quality

- VRPTW has been extensively dealt with
- M. M. Solomon (1987)
- O. Bräysy and M. Gendreau (2005)
- O. Bräysy and M. Gendreau (2005a)
- ...

Delivery of soft drinks to small and medium sized retailers in Sao Paulo:

- High-density populated region
- Congested streets and scarcity of parking lots
- Time windows for delivery

- ⇒ variation of the VRPTW
- 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
- Time windows pose additional problems for clustering customers

- Service time can be reduced by assigning larger crews to the vehicles
- Particularly interesting if workers are cheap in relation to trucks

- Several new problems have to be dealt with
**VRPTW with the additional decision of assigning a number of service workers to each vehicle ⇒ VRPTWMS**- Customer clustering and parking space allocation need to be included in the algorithm
- Fexibility in the delivery dates for selected customers calls for a multi-period model
- Customer clustering and parking space allocation on the fly

- Lexicographic objective
- Fleet size
- Crew size
- Total distance

- Model assumptions
- Predefined nodes in our model correspond to the parking sites
- Parking sites are pre-assigned the actual customers to be visited
- ⇒ appropriate parking sites and allocation of actual customers to parking sites are given as inputs
- Service time in the nodes is a function of the local demand and the number of service workers assigned to the vehicle

- Problem complexity calls for a rapid metaheuristic
- Prior work only by Pureza et al. (2011)

The objective of our current research is to study the effect of different solution construction heuristics and their parameters on the overall solution quality in order to obtain better results after applying different meta-heuristics.

- Reimplement solution construction mechanisms from Pureza et al. (2011) to compare their quality - independent from the used meta-heuristic
- Perform computational experiments to determine their individual advantages
- Implement ACO and other metaheuristics in order to obtain better overall results

Heuristic

- Intended to gain computational performance potentially at the cost of accuracy
- Experience-based techniques for problem solving
- Interesting when lacking a fast (polynomial) algorithm
- And an exhaustive search is impractical
- Used to speed up the process of finding a satisfactory solution

Metaheuristic

- Optimization method that either trys to improve a candidate solution or learns from past solutions
- Few or no assumptions about the problem
- No guarantee a (near) optimal solution is ever found

- Probabilistic metaheuristic
- Uses swarm intelligence
- Initially proposed by M. Dorigo (1992)

- We're testing against the classical instances from M. M. Solomon (1987)
- These serve as benchmarks to compare the quality of different algorithms.

Solomon's I1 (adjusted)

- Importance of seed: furthest unassigned node
- Additional nodes are added one by one and selected by
minimal cost
cost = α * cost_dist + (1-α) * cost_time return cost - λ * c_m[depot, node]

- All vehicles are initialized with max. workers

Target size (1 worker)

- Given the best target fleet size
- Run I1 with 1 worker until given fleetsize is reached
- Add workers if unassigned clients are left
- For the remaining unassigned clients add additional trucks starting with one worker and adding workers as required

Parallel Solution Construction

- Main issue is seed selection
- Allows more freedom when adding nodes ⇒ works well with ACO's learning capability
- Requires additional local search

- Pheromone represents "proximity" between nodes in the solution
- Select a number of ants
- For a given time period
- Calculate a solution for each ant
- Determine the globally best solution
- Update the pheromone for the best solution

Instances r101 - r112

Without local search | |
---|---|

heuristic | # trucks |

Solomon I1 (earliest closing TW) | 183 |

Targetsize | 185 |

Solomon (furthest seed) | 166 |

With local search | |
---|---|

Solomon I1 | 166 |

Targetsize | 183 |

Comparison to Best Prior Results | |
---|---|

Pureza et al. (2011): ACO | 150 |

Pureza et al. (2011): TS | 148 |

New ACO w/out local search | 150 |

- Adapted version of Solomon's I1 heuristic works currently best
- With and without local search

Remains to be done

- Implement same local search as Pureza et al. (2011) for systematic comparison
- Implement tabus search and other metaheuristics (adaptive large neighbourhood search, ...?)
- Determine best tradeoff between more powerful local search operators and faster runtime when applying meta-heuristics

- Determine parking location and customer clustering
- Extend system to allow multiple periods
- Improve performance with (AA tree based) result hashing

Olli Bräysy and Michel Gendreau
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)

Olli Bräysy and Michel Gendreau
Vehicle Routing Problem with Time Windows, Part II: Metaheuristics
Transportation Science vol. 39, iss. 1, pp 119-139, INFORMS (2005)

G. Clarke and J. W. Wright
Scheduling of Vehicles from a Central Depot to a Number of Delivery Points
Operations Research, Vol. 12 Issue 4, pp. 568-581 (1962)

G. B. Dantzig and J. H. Ramser
The Truck Dispatching Problem
Management Science 6, pp. 80-91 (1959)

M. Dorigo
Ottimizzazione, apprendimento automatico, ed algoritmi basati su metafora naturale
Ph.D.Thesis, Politecnico di Milano (1992)

Asvin Goel and Volker Gruhn
Solving a dynamic real-life vehicle routing problem
Operations Research Proceedings 2005, pp 367–372, Springer (2006)

David Pisinger and Stefan Ropke
Large neighborhood search
Handbook of Metaheuristics, pp 399-419, Springer (2010)

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

Marc Reimann, Michael Stummer and Karl Doerner
A Savings Based Ant System For The Vehicle Routing Problem
Proceedings of the Genetic and Evolutionary Computation Conference, 31, pp. 1317-13261 (2002)

M. M. Solomon
Algorithms for the Vehicle Routing and Scheduling
Problems with Time Window Constraints
Operations Research, Vol. 35, No. 2, pp. 254-265 (1987)

Wikipedia
Ant colony optimization algorithms - Wikipedia, The Free Encyclopedia
Online; accessed 27-March-2012;
url
(2012)