University of Graz logo

Vehicle Routing Problems with Time Windows and
Multiple Service Workers

Customer Clustering

Gerald Senarclens de Grancy <>,
Dagmar Tschabrun <>,
Marc Reimann <>

YAMS, December 2013, Salzburg

Problem Origin and Background

Delivery of soft drinks to small and medium sized retailers in São Paulo:

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


New Problems

  1. VRPTW with the additional decision of assigning multiple service workers to each vehicle ⇒ VRPTWMS
  2. Customer clustering and parking space allocation
    • Assigning customers to parkings (clustering) difficult because of time windows
    • Related Problems include the multi-depot VRPTW, two-echelon VRPTW and Truck and trailer RPTW
  3. Combined learning for clustering and routing to obtain better results

Prior Work



The objective of our current research is to identify good heuristics for creating customer clusters that can be efficiently serviced by as few trucks and workers as possible (minimize the objective function of the outer VRPTWMS).

The clustering consists of assigning customers to parking locations and determining a schedule for servicing the assigned customers.

  1. Identification of required algorithmic components
  2. Creation of realistic benchmark instances
  3. Implementation and systematic evaluation of these heuristics

Clustering Customers

New Benchmark Instances

Clustering Customers

Building Clusters
  • For each client we decide whether
    1. The client is added to an existing 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 sum of the "makespan"
  • When all clients are assigned, the outer routing is performed

Summary and Outlook

Summary/ Accomplishments
Remains to be done
  • Allow changing the parking location as new customers are added to clusters
  • Link cluster creation and outer routing
  • Create local search operators to improve clusters

Questions and Feedback

Selected Bibliography


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


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)


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)