Outline

Problem Background and Motivation
Route Construction Mechanisms
Numerical Results
Summary and Outlook

Problem Background and Motivation

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

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

⇒ 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

Typical Route

New Problems

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

Several new problems have to be dealt with
1. VRPTW with the additional decision of assigning multiple of service workers to each vehicle ⇒ VRPTWMS
2. Customer clustering and parking space allocation need to be included in the algorithm
3. Fexibility in the delivery dates for selected customers calls for a multi-period model
4. Customer clustering and parking space allocation on the fly
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
- ⇒ appropriate parking sites and allocation of actual customers to parking sites are given as inputs
- Service time in the nodes is a function of the local demand and the number of service workers assigned to the vehicle
Problem complexity calls for a rapid metaheuristic
Prior work only by Pureza et al. (2011)

Goals

The objective of our current research is to study the effect of different solution construction heuristics and their parameters on the overall solution quality in order to obtain better results after applying different meta-heuristics.

Reimplement solution construction mechanisms from Pureza et al. (2011) to compare their quality - independent from the used meta-heuristic
Perform computational experiments to determine their individual advantages
Implement ACO and other metaheuristics in order to obtain better overall results

Route Construction Mechanisms

We're testing against the classical instances from M. M. Solomon (1987)
- r101 - r112 serve as benchmarks to compare the quality of different algorithms
- service time $$s_i = \min (2 d_i; T - \max (a_i;t_{0i})-t_{i0})$$ where
  
  $d_i$
  
  demand at node $i$
  
  $T$
  
  depot closing time
  
  $a_i$
  
  EST at node $i$
  
  $t_{0i}$, $t_{i0}$
  
  travel times between the depot and node $i$

Solomon's I1 (adjusted)

Importance of seed: furthest unassigned node

Additional nodes are added one by one and selected by minimal cost

cost = α * cost_dist + (1-α) * cost_time
return cost - λ * c_m[depot, node]

All vehicles are initialized with max. workers

Target size (1 worker)

Given the best target fleet size
Run I1 with 1 worker until given fleetsize is reached
Add workers if unassigned clients are left
For the remaining unassigned clients add additional trucks starting with one worker and adding workers as required

Parallel Solution Construction

Main issues are seed selection and remaining nodes
Allows more freedom when adding nodes
Requires repair function

Aggregated Numerical Results

Instances r101 - r112

Without local search
heuristic	# trucks
Solomon I1 (earliest closing TW)	183
Targetsize	185
Solomon (furthest seed)	166

With local search
Solomon I1	166
Targetsize	183

Comparison to Best Prior Results
Pureza et al. (2011): ACO	150
Pureza et al. (2011): TS	148
New ACO w/out local search	150

Summary and Outlook

Adapted version of Solomon's I1 heuristic works currently best

Remains to be done

Implement same local search as Pureza et al. (2011) for systematic comparison
Implement other metaheuristics
Determine best tradeoff between more powerful local search operators and faster runtime when applying meta-heuristics
Improve performance with result hashing

Determine parking location and customer clustering
Extend system to allow multiple periods

Selected 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)

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)

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)