Local search for the undirected capacitated arc routing problem with profits |
| |
Authors: | E.E. Zachariadis C.T. Kiranoudis |
| |
Affiliation: | Department of Process Analysis and Plant Design, National Technical University of Athens, Athens, Greece |
| |
Abstract: | This paper deals with a recently introduced routing problem variant called the undirected capacitated arc routing problem with profits (UCARPP). The UCARPP model considered in the present study is primarily aimed at generating the route set which maximizes the profit collected from a set of potential customers, represented by edges of the examined transportation network. The secondary objective is to minimize the total route travel time. The generated routes are subject both to capacity and travel time constraints. To tackle the examined problem, we propose a local search metaheuristic development which explores two solution neighborhood structures. The conducted search is effectively diversified by means of the promises concept which is based on the aspiration criteria used in tabu search approaches. The proposed algorithm was tested on UCARPP benchmark instances taken from the literature. It efficiently produced high-quality results, improving several previously best known solutions. |
| |
Keywords: | Arc routing with profits Metaheuristics Local search Aspiration criteria |
本文献已被 ScienceDirect 等数据库收录! |