An approximate ε-constraint method for the Multi-objective Undirected Capacitated Arc Routing Problem

The Undirected Capacitated Arc Routing Problem is a classical arc routing problem arising in practical situations (road maintenance, garbage collection, mail delivery, school bus routing, etc.) with the aim of minimizing the total transportation cost of a set of routes that service a set of required edges under capacity constraints. Most of logistic companies are interested in minimizing not only the total transportation cost, they also are focused in managing the deliveries on the edges, in such a way that the duration of the longest trip does not exceed an upper time limit, to take into account the working day duration of the drivers. Moreover, all the demands of the required edges are satisfied by considering a limited number of vehicles at the depot. In this paper, the Multi-objective Undirected Capacitated Arc Routing Problem where different and competitive objectives are taken into account simultaneously, is defined and studied. Three objectives are considered in order to: minimize the total transportation cost, the longest route (makespan) and the number of vehicle used to service all the required edges (i.e., the total number of routes). To find a set of solutions belonging to the optimal pareto front, an optimization-based heuristic procedure is proposed and its performance is evaluated on a set of benchmark instances.