Using Ant Colony Optimization to solve Periodic Arc Routing Problem with Refill Points

Abstract

This research presents a solution process for Periodic Arc Routing Problem with Refill Points (PARPRP). The Periodic Arc Routing Problem is a natural extension of Arc Routing Problem (ARP) and is classified as an NP-hard problem. The street tree watering problem is used as the case study. The study tackles the ARP requiring a specified time horizon to fulfill it. A refill point in the problem is a node in the graph at which the vehicle capacity can be recovered as long as the vehicle makes a stop on it. The strategy of solving the problem is first to transform the problem into a Vehicle Routing Problem. Secondly, an Ant Colony Optimization algorithm is developed to solve the PARPRP because of its remarkable capability in the establishment of network routes. A local search method is incorporated to reach the local minimum for further improvement. Two sets of benchmarks are used to verify the solving process and the computational results are provided. The outputs indicate that proposed methods can yield promising solutions within reasonable execution time. A real case regarding the street tree watering of Kaohsiung city, Taiwan, is investigated. The results suggest that while α = 1 and β = 3 (i.e. parameters to control the influence of the pheromone value allocated on and the desirability of the arc, respectively), the algorithm can yield the best solution. The number of refill points is analyzed as well and output result suggests that a system with two refill points can obtain the least route length.

Keywords:

• Periodic Arc Routing Problem
• refill point
• Ant Colony Optimization
• street trees watering