University of Graz logo

Three Essays on

Applied Metaheuristics for Logistical Challenges in Congested Urban Areas

Gerald Senarclens de Grancy <>
advisor: Marc Reimann <>

Defensio Dissertationis, March 2015, Graz

Problem Origin and Background

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

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


New Problems

1st paper (with Marc Reimann)
VRPTW with the additional decision of assigning multiple service workers to each vehicle ⇒ VRPTWMS
2nd paper (with Marc Reimann)
Customer clustering and parking space allocation
3rd paper
Combined learning for clustering and routing
  • Overcome lack of explicit objective function for clustering
  • Allow learning from different routing problems


Prior Work

Learning from Prior Results

Feedback Loop


Summary and Outlook

Summary/ Accomplishments
Still, a lot more can be done
  • Add time windows to parking locations
  • Allow changing the parking location as new customers are added to clusters
  • Create local search operators to improve clusters
  • Alternative models should be investigated (drop off and pick up, routing in clusters, ...)


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)
El-Sherbeny, Nasser A. Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods Journal of King Saud University (Science) (2010")
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)

Related problems

Bektaş, Tolga and Gouveia, Luis Requiem for the Miller–Tucker–Zemlin subtour elimination constraints? European Journal of Operational Research 236 (2013) 820-832


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)