VRPTW with
Multiple Service Workers

Route Construction Heuristics

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

VeRoLog, June 2012, Bologna

# Outline

1. Problem Background and Motivation
2. Route Construction Mechanisms
3. Numerical Results
4. Summary and Outlook

# Problem Background and Motivation

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

1. Time windows for delivery
2. High-density populated region
3. 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

# 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.
1. Reimplement solution construction mechanisms from Pureza et al. (2011) to compare their quality - independent from the used meta-heuristic
2. Perform computational experiments to determine their individual advantages
3. 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$
• 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)