In this paper, we extend our previous work on greedy constructive heuristics for the Mixed Capacitated Arc Routing Problem under Time Restrictions with Intermediate Facilities (MCARPTIF) by developing efficient local search improvement heuristics for the problem. Five commonly used arc routing move operators were adapted for the problem, and basic local search implementations were tested on waste collection benchmark sets. Tests showed that despite the application of commonly used speed-up techniques, the local search implementations are very slow on large test instances with more than one-thousand required arcs and edges. In response, more advanced local search acceleration mechanisms from literature were adapted and combined for the MCARPTIF and tested on the same instances. On the large instances, the basic local search setups took between 15 min and 3 h to improve a single solution to local optima, whereas the accelerated implementations took at most 4 min while producing similar quality local optima. The best performing implementation made use of two existing acceleration mechanisms, namely Static-Move-Descriptors and Greedy-Compound-Independent-Moves. A third mechanism, Nearest-Neighbour-Lists was also tested and although it reduced execution times it resulted in local search terminating at worse quality local optima. Given the importance of local search within metaheuristics, the developed local search heuristics provide a significant contribution to arc routing. First, the implementations can be extended to and incorporated into metaheuristics for the MCARPTIF. Second, the acceleration mechanisms can be applied to existing local search metaheuristics for Capacitated Arc Routing Problems, thereby improving the efficiency of the metaheuristics and allowing them to better deal with large instances.
Supplementary Data S1. Supplementary Raw Research Data. This is open data under the CC BY license http://creativecommons.org/licenses/by/4.0/.
Supplementary Data S2. Supplementary Raw Research Data. This is open data under the CC BY license http://creativecommons.org/licenses/by/4.0/.
Du Plessis, L.M.(African Consortium of Public Administration, 2016)
Any organisation’s functioning is dependent on the people involved in it and
their ability to optimally work towards the organisation’s mandate. In a highly
competitive world, career success and accompanying rewards play ...
Fourie, D.J. (David Johannes); Schoeman, Linda(South African Association for Public Administration and Management, 2010-06)
Restitution has to be made in a highly political environment, making the planning and design of restitution programmes in rural, peri-urban and urban areas extremely complex. The development of governance structures for ...
Brandi, Wesley Antonio(University of Pretoria, 2011-08-11)
Search engines have become integral to the way in which we use the Web of today. Not only are they an important real time source of links to relevant information, but they also serve as a starting point to the Web. A ...