University of Graz logo

Title Slide

2nd Doctoral Colloquium

Three essays on applied metaheuristics for logistical challenges in congested urban areas

Gerald Senarclens de Grancy <gerald@senarclens.eu>

Graz, 2014-01-08

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

Coke Truck in NY, NY

Solution

Single Route

Typical Benchmark Instance

Research Problem and Motivation

VRPTW with Multiple Service Workers (VRPTWMS)
  1. Systematic investigation of different metaheuristics and their components for the routing problem
    Goal
    Find a good combination delivering high quality results (i.e. low costs for trucks and workers) in a reasonable amount of time
    Question
    Does ACO outperform GRASP with respect to our goal
  2. Customer clustering and parking space allocation
  3. Caching strategy for relevant metaheuristics
Motivation
  • Additional applications
    • Delivering small (portable) packages (eg. mail)
    • Particularly interesting in (limited time) pedestrian areas
    • Mitigates effects of rush hours and congestion
  • Cost reduction and sustainability
    • Reduces cost on vehicles, fuel, inner city tolls, ...
    • Implicitly incorporates green objectives
  • Clustering is required
    • Cluster assignment problem and routing are not independent
    • Otherwise, outer routing algorithms essentially useless for practical purposes

Clustering Solution => Routing Input

Routing Solution

>20 kLOC

Aggregated Comparison

Runtime Analysis

Accomplishments and Future Research

Accomplishments
Possibilities for Future Research
  • Link cluster creation and outer routing
  • Combined learning strategies for metaheuristics

Questions and Feedback

gerald@senarclens.eu

Selected Bibliography

VRPTWMS

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

VRPTW

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)

Metaheuristics

M. Dorigo Ottimizzazione, apprendimento automatico, ed algoritmi basati su metafora naturale Ph.D.Thesis, Politecnico di Milano (1992)
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)

Scheduling

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)

Additional Material

Wilcoxon Signed Ranks Test