University of Graz logo

Vehicle Routing Problems with Time Windows and
Multiple Service Workers

Combined Learning for Clustering and Routing

Gerald Senarclens de Grancy <>,

Euro, July 2015, Glasgow

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
    • Overcome lack of explicit objective function for clustering
    • Allow learning from different routing problems

Prior Work


New Benchmark Instances

Clustering Customers

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

Learning from Prior Results

Clustering Ant Colony Optimization

Routing Ant Colony Optimization


Summary and Outlook

Summary/ Accomplishments
Remains to be done
  • Allow changing the parking location as new customers are added to clusters
  • 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)