Heuristics for large-scale Capacitated Arc Routing Problems on mixed networks

Abstract

Residential waste collection is an expensive activity performed daily on large metropolitan areas throughout the year. Even a small improvement in waste collection and transfer operations can therefore lead to signi cant cost savings. A promising improvement area is to design better waste collection routes. In this thesis we show that the problem of designing optimal collection routes for waste collection vehicles can be modelled as the Mixed Capacitated Arc Routing Problem under Time Restrictions with Intermediate Facilities (MCARPTIF). The problem is a generalisation of the Capacitated Arc Routing Problem (CARP) and takes into consideration a mixed road network consisting of one- and two-way streets; a vehicle capacity that limits the amount of waste a vehicle can carry at any given time; Intermediate Facilities (IFs) where vehicles are allowed to unload their waste and resume their collection rounds; and a time restriction which prohibits the duration of a route from exceeding a time-limit. The objective of the MCARPTIF is to develop routes of minimum total cost while adhering to all the operational constraints and requirements of the problem. The MCARPTIF belongs to the class of NP-hard problems, making it impractical to solve large instances, such as those representing actual residential waste collection operations, through exact methods within reasonable computing times. Instead the most relied upon methods to address such problems are through heuristic and metaheuristic solution strategies. In this thesis we develop constructive and Local Search based improvement heuristics, as well as a Tabu Search metaheuristic for the MCARPTIF. A key component of the methods is the trade-o between the quality of the generated solutions and the speed (or time required) to generate and improve the solutions. In this thesis, short, medium and long execution time-limits are imposed, representing practical situations where solutions are sought within three-, thirty and sixty minutes. The performance of the methods is then critically evaluated under these time-limits through benchmark tests on new large MCARPTIF instances. For the short time-limits four constructive heuristics are developed and tested, and all proved capable of generating feasible solutions for large problem instances within three minutes. A vehicle reduction procedure is also implemented that allows the heuristics to better deal with cases where the eet size has to be minimised. The performance of the heuristics was inconsistent between di erent benchmark sets, particularly between waste collection instances and the smaller sets available in literature, thus con rming that the e ectiveness of heuristics on small instances does not guarantee that they will perform equally well in more realistic settings. Despite their inconsistent performance, the developed constructive heuristics play an important role in solving the MCARPTIF as they provide initial solutions for more advanced improvement heuristics, which can be applied when more execution time is available. For medium time-limits we develop advanced Local Search improvement heuristics that rely on two acceleration mechanisms to improve their e ciency. On the largest test instances the basic Local Search setups|that is, without the acceleration mechanisms| took between fteen minutes and three hours to improve a single solution to local optima. After embedding the accelerated mechanisms within the setups, Local Search took at most four minutes to reach local optima, thus allowing it to be used even when short execution time-limits are imposed. For long time-limits we extend the accelerated Local Search setup into a deterministic Tabu Search metaheuristic. The metaheuristic takes as input only two parameters, namely a tabu tenure and an execution time-limit. It then improves an initial solution beyond the local optima found using only Local Search. The metaheuristic is tested on large waste collection problem instances and outperforms both the constructive heuristics and accelerated Local Search setups under short, medium and long execution time-limits. The Tabu Search is then further tested as-is on Mixed Capacitated Arc Routing Problem (MCARP) instances and its performance is compared against an existing Memetic Algorithm for the problem. On large instances the Tabu Search is able to outperform the existing method in under three minutes, but on small and medium instances the existing method proved more e ective. On these sized instances Tabu Search requires in excess of fteen minutes and on some instances completely fails to outperform the Memetic Algorithm. Existing heuristic and metaheuristics are thus well capable of dealing with small to medium size instances. However, as our tests on the MCARP instances show, the performance of existing methods on large instances leaves much room for improvement. It is therefore recommended that more tests be performed on large instances such as those introduced in this thesis, which are similar in size to those encountered in practice. To test the limits of our solution methods a nal set of tests are performed on a huge waste collection instance with 6289 required arcs and edges; prior to this thesis the largest instance available from literature only had 803. Two constructive heuristics are capable of generating initial solutions for the instance within three minutes. Thereafter the accelerated Local Search heuristic is able to improve the initial solutions to local optima within thirty minutes. The Tabu Search is then able to marginally improve the solutions within one-hour. More signi cant improvements are obtained through the Tabu Search when it is allowed up-to 24 hours of execution time, which is expected given the size of the test instance. This nal test shows that the heuristics and metaheuristics developed in this thesis are capable of tackling, within reasonable computing times, very large MCARPTIF instances that are similar in size to those encountered in practice.