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

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

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