Vehicle Routing Problems with Time Windows and Multiple Service Workers

A Systematic Comparison between two Metaheuristics

Gerald Senarclens de Grancy (gerald@senarclens.eu),
Marc Reimann (marc.reimann@uni-graz.at)

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

Travelling salesman problem (TSP)
Capacitated Vehicle Routing Problem (VRP)
- Proposed by G. B. Dantzig and J. H. Ramser (1959)
- Service a number of customers with a fleet of vehicles with limited capacity
- Objective is to serve all customers requiring minimum costs
- Solving is computationally complex (prohibitive runtime)
- Heuristic approach allows to quickly find near optimal solutions
- (C)VRP has been extensively dealt with
  - 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)
- Variation of the VRP with additional constraints
- Solving is computationally complex (prohibitive runtime)
- Heuristic approach is required to quickly find good solutions
- Metaheuristics allow to improve the solution quality
- VRPTW has been extensively dealt with
  - M. M. Solomon (1987)
  - O. Bräysy and M. Gendreau (2005)
  - O. Bräysy and M. Gendreau (2005a)
  - ...
VRPTW does not attribute scarcity of parking lots

Solution Approach

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

Service time can be reduced by assigning larger crews to the vehicles
- Particularly interesting if workers are cheap in relation to trucks

New Problems

Any solution to this problem requires two steps

Clustering of customers around known parking locations
Efficient routing of trucks to each cluster

VRPTW with the additional decision of assigning multiple service workers to each vehicle ⇒ VRPTWMS
- Develop a good route construction heuristic
- Determine a reasonable set of local search operators
- Decide on a promising metaheuristic
- Prior work by Pureza et al. (2011)
- Lexicographic objective
  1. Fleet size
  2. Crew size
  3. Total distance
- Modeled problem under strong assumptions
  - Adjusted VRPTW instances from Solomon (1987)
  - Nodes' coordinates correspond to cluster parking sites
  - Parking sites are pre-assigned the actual customers to be visited
    - ⇒Allocation of customers to parking sites are given as inputs
  - Clusters' service time is a linear function of the demand and the number of service workers
  - Designated parking spaces are not occupied
Customer clustering and parking space allocation need to be included in the algorithm
Combined learning for clustering and routing to obtain better results

Motivation and Model

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

Goals

Identification of required algorithmic components
Implementation and systematic evaluation of these components

The objective of the presented paper was the systematic analysis of two metaheuristics to minimize the objective function of the VRPTWMS.

Greedy randomized adaptive search procedure (GRASP)

Based on greedy heuristic
Repeatedly constructs different solutions
Uses a restricted candidate list (RCL) to accommodate for myopic behavior
Using GRASP in the VRPTWMS
- Until stopping criterion is met
  1. Construct routes using the RCL
  2. [Improve the solution using a local search]
  3. Compare to globally best solution

Ant Colony Optimization (ACO)

Probabilistic metaheuristic
- Uses swarm intelligence
- Initially proposed by M. Dorigo (1992)
Using ACO in the VRPTWMS
- Pheromone represents "proximity" between nodes in the solution
- Select a number of ants
- Until stopping criterion is met
  1. For each ant construct routes using pheromone
  2. [For each ant improve the solution]
  3. Determine the globally best solution
  4. Update the pheromone for the best solution

Comparison to Prior Results

Results by Pureza et al. (2011)
- Tested against adjusted Solomon (1987) R1 instances
- Tabu search: 148 vehicles, 389 service workers and 15105 distance units
- ACO: 150 vehicles, 377 service workers and 15137 distance units

Our Results of the pre-clustered routing problem using ACO
- Outperformed results for 11 of the 12 R1 instances
- 145 (-2.02%/ -3.33%) vehicles
- 368 (-5.40%/ -2.39%) service workers
- 14976.83 (-0.85%/ -1.06%) distance units

Summary/ Accomplishments

Systematically compared algorithmic components
Currently best known solutions for all prior benchmark instances
Created specification (schema) for benchmark instances
Developed mini-language for serializing solutions
Generated designed and random benchmark instances
Implemented all algorithms and tools as open source software

Remains to be done

Incorporate clustering and routing algorithms

Link cluster creation and outer routing for combined learning

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)

Methodology

M. Dorigo Ottimizzazione, apprendimento automatico, ed algoritmi basati su metafora naturale Ph.D.Thesis, Politecnico di Milano (1992)

Marc Reimann and Marco Laumanns Savings based ant colony optimization for the capacitated minimum spanning tree problem Computers & OR, Vol. 33, pp. 1794–1822 (2006)