PhD Dissertation Proposal

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

Gerald Senarclens de Grancy, gerald@senarclens.eu

Outline

Problem Background and Motivation
Current State of Research
Methods & Approach

Problem Background and Motivation

Delivery of soft drinks from central depot to small and medium sized retailers in Sao Paulo:

High-density populated region
Congested streets and scarcity of parking lots
Time windows for delivery (⇒ variation of the VRPTW)

Driver parks vehicle close to some customer sites
Goods are delivered to nearby customers by foot (using hand trolley)
⇒ long service times at each parking site
Time windows pose additional problems for clustering customers
Details
- Lexicographic objective
  1. Fleet size
  2. Crew size
  3. Total distance
- Model assumptions
  - Predefined nodes in our model correspond to the parking sites
  - Parking sites are pre-assigned the actual customers to be visited
  - Service time in the nodes is a function of the local demand and the number of service workers assigned to the vehicle

Problem Background and Motivation

Problem Background and Motivation

Service time can be reduced by assigning larger crews to the vehicles
- Particularly interesting if workers are cheap in relation to trucks
New problem: VRPTW with Multiple Service Workers (VRPTWMS)
Several new research problems have to be dealt with

Research Problem

Systematically investigate the performance of different metaheuristics and route construction heuristics for the VRPTWMS
Include customer clustering and parking space allocation in the algorithm
Allow for fexibility in the delivery dates for selected customers

Current State of Research

Vehicle Routing Problem (VRP)
- G. B. Dantzig and J. H. Ramser (1959)
- G. Clarke and J. W. Wright (1962)
- M. Reimann, M. Stummer and K. Doerner (2002)
VRP with Time Windows (VRPTW)
- M. M. Solomon (1987)
- O. Bräysy and M. Gendreau (2005)
- O. Bräysy and M. Gendreau (2005a)
VRPTW with multiple service workers (VRPTWMS)
- Pureza et al. (2011)
Metaheuristics
- M. Dorigo (1992)
- A. Goel and V. Gruhn (2006)
- D. Pisinger and S. Ropke (2010)

Methods & Approach

Dissertation project will be laid out in three related, but separate parts
Methodology can be summarized as computational experiments (⇒ empirical analysis)
Problem complexity calls for a rapid metaheuristic (ACO, TS, ALNS, ...)
Result will be innovative approaches for solving the new problem

Each sub-problem will be started by a written specification
Discussion of different solution approaches to related problems in the literature
Algorithmic decisions
Implement algorithm in a statically typed, compiled programming language
- C or C++
- GNU toolchain
- Linux operating system
Analysis of the results

Submit at least three articles
Allow fellow scientists the use study improve share approach - publish implementation using the GNU GPLv3

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)

G. Clarke and J. W. Wright Scheduling of Vehicles from a Central Depot to a Number of Delivery Points Operations Research, Vol. 12 Issue 4, pp. 568-581 (1962)

G. B. Dantzig and J. H. Ramser The Truck Dispatching Problem Management Science 6, pp. 80-91 (1959)

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)

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

Marc Reimann, Michael Stummer and Karl Doerner A Savings Based Ant System For The Vehicle Routing Problem Proceedings of the Genetic and Evolutionary Computation Conference, 31, pp. 1317-13261 (2002)

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)