University of Graz logo

VRPTW with
Multiple Service Workers

Route construction heuristics

Gerald Senarclens de Grancy, gerald@senarclens.eu

Outline

  1. Problem Background and Motivation
  2. Route Construction Mechanisms
  3. Metaheuristics
  4. Numerical Results
  5. Summary and Outlook

Vehicle Routing Problem (VRP)

Sample VRP Instance

R101_25 R101_50 R101

VRP with Time Windows (VRPTW)

Sample VRPTW Instance

R101_25 R101_50

Problem Background and Motivation

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

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

Typical Route

typical route

New Problems

Goals

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.
  1. Reimplement solution construction mechanisms from Pureza et al. (2011) to compare their quality - independent from the used meta-heuristic
  2. Perform computational experiments to determine their individual advantages
  3. 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

Ant Colony Optimization (ACO)

aco

Route Construction Mechanisms

Route Construction Mechanisms

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
construction_0_1.svg construction_0_2.svg construction_0_1.svg construction_0_2.svg construction_0_1.svg construction_0_2.svg construction_0_1.svg construction_0_2.svg construction_0_1.svg construction_0_2.svg construction_0_1.svg construction_0_2.svg construction_0_2.svg construction_0_2.svg construction_0_1.svg construction_0_1.svg

Using ACO in the VRPTWMS

Aggregated Numerical Results

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

Summary and Outlook

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

Bibliography

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)