University of Graz logo

VRPTW with
Multiple Service Workers

Route Construction Heuristics

Gerald Senarclens de Grancy (,
Marc Reimann (

EULOG, May 2012, Salzburg


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

Problem Background and Motivation

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

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

Typical Route

typical route

New Problems


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

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 issues are seed selection and remaining nodes
  • Allows more freedom when adding nodes
  • Requires repair function

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 other metaheuristics
  • Determine best tradeoff between more powerful local search operators and faster runtime when applying meta-heuristics
  • Improve performance with result hashing
  • Determine parking location and customer clustering
  • Extend system to allow multiple periods

Selected 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)
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)
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)