VRPTW with
Multiple Service Workers

A Designated Operator for Reducing Trucks

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

YAMS, December 2012, Graz

# 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
• $\Rightarrow$ variation of the VRPTW
• Driver parks vehicle close to some customer sites
• Goods are delivered to nearby customers by foot (using hand trolley)
• $\Rightarrow$ 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 $\Rightarrow$ 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
• 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
• $\Rightarrow$ appropriate parking sites and allocation of actual customers to parking sites are given as inputs
• Service time is a linear function of the accumulated demand and the number of service workers
• Problem complexity calls for a rapid metaheuristic
• Prior work only by Pureza et al. (2011)

# Route Construction and Metaheuristic

• We're testing against the classical instances from M. M. Solomon (1987)
• r101 - r112 serve as benchmarks to compare the quality of different algorithms
• $s_i$: service time for a single worker at cluster $i$ $$s_i = \min (2 * demand_i, depot\_closing\_time - \max(est_i, travel\_time_{0i}) - travel\_time_{i0})$$ to ensure that $$\max(est_i, travel\_time_{0i}) + s_i + travel\_time_{i0} \leq depot\_closing\_time$$
• Stochastic Solomon I1 worked best as route construction heuristic
• Seed: furthest unassigned node
• Additional nodes are added one by one and selected by minimal cost
$cost = \alpha \times cost\_dist + (1 - \alpha) \times cost\_time$
$return$ $cost - \lambda \times distance\_matrix[depot, node]$
• All vehicles are initialized with max. workers
• Deterministic local search
• Considers hierarchic objective function
• Solution* improve_solution(Solution *sol) {
sol = reduce_trucks(sol);
reduce_workers(sol);
return sol;
}

• Operators: move2, move1, swap1 and the new truck reduction operator
• Solution* reduce_trucks(Solution *sol) {
int improved = 0;
do {
improved = 0;
improved |= move_all(sol, REDUCE_TRUCKS);
improved |= swap_all(sol);
improved |= new_operator(&sol);
} while (improved);
return sol;
}

• Currently, the ACO metaheuristic gives the best results
• Probabilistic metaheuristic
• Uses swarm intelligence
• Initially proposed by M. Dorigo (1992)
• Application in the VRPTWMS
• Pheromone represents "proximity" between nodes in the solution
• Select a number of ants
• For a given time period
1. Construct a solution for each ant
2. Pheromone guides the route construction
3. Determine the globally best solution
4. Extract pheromone for the best solution

# New Truck Reduction Operator

The objective was to create a fast deterministic local search operator that improves the overall solution quality by explicitly focusing on reducing the number of trucks.
• Systematically tries to remove single routes
• Allows temporary degradation of the solution quality
• A clone of the current solution is used
• Feasibility is preserved
• One route at a time, the operator tries to move all nodes to their best position on any other route
• def new_operator(sol):
reduced, improved = True, False
while (reduced):
for route in sol.routes:
reduced = empty_route(sol, route)
if (reduced):
remove_route(sol, route)
improved = 1
break
return improved;
}

• Emptying a route is aborted as soon as a node cannot be moved

# Aggregated Numerical Results

• Instances r101 - r112
• 900s runtime
old (ts; aco) new
#trucks 148; 150 145
#workers 389; 377 368
#distance 15096; 15137 14976.83
iterations / s 152.53 158.53
Best known VRPTWMS solution values

# Summary and Outlook

• Designated truck reduction is fast and improves solution quality
Remains to be done
• Comparison to best known VRPTW solutions suggests that further improvement is possible
• 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)