University of Graz logo

VRPTW with
Multiple Service Workers

A Designated Operator for Reducing Trucks

Gerald Senarclens de Grancy (,
Marc Reimann (

YAMS, December 2012, Graz

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 create a fast algorithm for creating high quality solutions for the VRPTWMS with predefined clusters.

Route Construction and Metaheuristic

New Truck Reduction Operator

The objective was to create a fast deterministic local search operator that improves the overall solution quality by explicitly focusing on reducing the number of trucks.

Sample Application

0_truck_reduction_operator 1_truck_reduction_operator 2_truck_reduction_operator 3_truck_reduction_operator 4_truck_reduction_operator 5_truck_reduction_operator

Aggregated Numerical Results

old (ts; aco) new
#trucks 148; 150 145
#workers 389; 377 368
#distance 15096; 15137 14976.83
iterations / s 152.53 158.53
Best known VRPTWMS solution values

Summary and Outlook

Remains to be done
  • Comparison to best known VRPTW solutions suggests that further improvement is possible
  • 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)