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

Delivery of soft drinks to small and medium sized retailers in São Paulo:

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

- 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
- Problematic in loading zones

- 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

- 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

- 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 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$$
- Fleet size
- Crew size
- 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

- 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

- Cluster seed selection
- Algorithm requires 4 matrices for long-term memory

- 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/ 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, ...)

Pureza, Vitoria; Morabito, Reinaldo and Reimann, Marc
Vehicle Routing with Multiple Deliverymen:
Modeling and Heuristic Approaches
European Journal of Operational Research (2011)

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)

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

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)