Three Essays on

Applied Metaheuristics for Logistical Challenges in Congested Urban Areas

Gerald Senarclens de Grancy <gerald@senarclens.eu>
advisor: Marc Reimann <marc.reimann@uni-graz.at>

Defensio Dissertationis, March 2015, Graz

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

Solution

• Driver parks vehicle close to some customer sites
• Goods are delivered to nearby customers by alternative mode of transportation
• foot (using hand trolley)
• cargo bike
• cargo scooter
• ...
• ⇒ 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

• Several new problems have to be dealt with
1st paper (with Marc Reimann)
VRPTW with the additional decision of assigning multiple service workers to each vehicle ⇒ VRPTWMS
2nd paper (with Marc Reimann)
Customer clustering and parking space allocation
3rd paper
Combined learning for clustering and routing
• Overcome lack of explicit objective function for clustering
• Allow learning from different routing problems

Motivation

• Many potential applications
• Delivering small (portable) packages
• Particularly interesting in (limited time) pedestrian areas
• Mitigates effects of rush hours and congestion
• Designated loading zones gain in attractiveness
• Cost reduction and sustainability
• Reduces cost on vehicles, fuel, inner city tolls, ...
• Implicitly incorporates green objectives
• Scientific relevance
• Problem has not been studied in-depth
• Complete lack of algorithm for two-stage model
• Achieving a good tradeoff between the cost of additional workers and more efficient routing is a non trivial and very interesting research question

Prior Work

• Prior work by Pureza et al. (2011)
• Hierarchical objective function $$\min C(t, s, d) = t \cdot c_t + s \cdot c_s + d \cdot c_d$$
1. Fleet size
2. Crew size
3. Total distance
$t$
number of trucks
$s$
number of service workers
$d$
total distance driven by all trucks
$c_t$
fixed cost per truck
$c_s$
fixed cost per service worker
$c_d$
cost per distance unit
• 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

Feedback Loop

• Based on the ant colony optimization metaheuristic
• Learning algorithm

problem.initialize_pheromone()
while problem.proceed():
for ant in problem.ants:
solution = problem.solve()  # use pheromone
if solution.value < problem.best_solution.value:
problem.best_solution = solution
problem.update_pheromone()  # use best available solution

• Decisions based on weighted roulette wheel
• Cluster seed selection

cluster.attractiveness() * trail(cluster.parking, cluster.seed)

• Extending clusters

cluster.evaluate_addition(client) * trail(cluster, client)

• Clusters change on every iteration $\Rightarrow$ routing trails are location-based
• Trails are normalized to avoid bias for large clusters
• Algorithm requires 4 matrices for long-term memory

Results

• 1st paper - routing predefined clusters
• Outperformed best results for 11 of 12 modified R1 instances
• 145 (-2.02%/ -3.33%) vehicles
• 368 (-5.40%/ -2.39%) service workers
• 14976.83 (-0.85%/ -1.06%) distance units
• 2nd paper - clustering heuristics
• Introduced two deterministic clustering heuristics
• Objective function value vastly improved over serving customers separately for every benchmark instance
• Average cost saving 32.25% (parallel heuristic)
• 3rd paper - combined learning
• Aggregated total cost reduced by 10.74% (average) over prior BKS
• New BKS permit 45.30% saving over separate service
• Also "improved" 3 out of 12 classical VRPTW results
• ACO Memory footprint is $O(l^2)$
• No overhead in asymptotic runtime for single iteration
• It pays off to create larger clusters
• 89.46 (before) -> 47.13 (average)

Summary and Outlook

Summary/ Accomplishments
• Improved results for pre-clustered instances
• Created 54 representative benchmark instances
• Each instance has 200 clients
• 27 regionally clustered + 27 randomly distributed
• Instances with 50, 100 and 150 parking locations
• Tight, normal and wide time windows
• Low, normal and fast walking speed in relation to driving speed
• Designed heuristics for clustering customers with time windows
• Proposed feedback loop for linking clustering and routing
• Created ACO using this feedback
• Source code for all algorithms is published as open source (782 commits)
• Three accepted articles in peer-reviewed scientific journals, 17 talks at relevant conferences, ...
• Demonstrated that cost and environmental impact can be reduced by thinking bi-modal
• Currently engaging in a joint project with the Austrian Economic Chambers to find optimal locations for new loading zones in Vienna
Still, a lot more can be done
• Add time windows to parking locations
• Allow changing the parking location as new customers are added to clusters
• Create local search operators to improve clusters
• Alternative models should be investigated (drop off and pick up, routing in clusters, ...)

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)
El-Sherbeny, Nasser A. Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods Journal of King Saud University (Science) (2010")
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)

Related problems

Bektaş, Tolga and Gouveia, Luis Requiem for the Miller–Tucker–Zemlin subtour elimination constraints? European Journal of Operational Research 236 (2013) 820-832

Scheduling

Lenstra, J. K.; Shmoys, D. B. and Tardos, É. Approximation algorithms for scheduling unrelated parallel machines Mathematical Programming 46 (1990)
Pinedo, Michael L. Scheduling – Theory, Algorithms, and Systems Springer (2012)
Pinedo, Michael L. Planning and Scheduling in Manufacturing and Services Springer (2012)