A Heuristic Algorithm for the Undirected Capacitated General Routing Problem with Profits
Annarita De Maio  1, *@  , Demetrio Laganà  1@  , Francesca Vocaturo  2@  
1 : Department of Mechanical, Energy and Management Engineering, University of Calabria
Arcavacata di Rende (CS) -  Italy
2 : Department of Economics, Statistics and Finance “G. Anania”, University of Calabria
Arcavacata di Rende (CS) -  Italy
* : Corresponding author

We study the Undirected Capacitated General Routing Problem with Profits. The class of problems with profits has become very popular in the last decades due to their capability to model several real cases. Our problem is defined on an undirected graph where customers are represented by sets of vertices and edges. A non-negative demand and a given profit are associated to each of them. We consider a fleet of homogeneous capacitated vehicles located at the depot to service the customers. The aim is to maximize the difference between the total collected profit and the traveling cost. A feasible solution is represented by a subset of customers that are selected according to their net profit, that is the difference between the profit and the additional traveling cost to serve them. The problem is NP-hard. We propose a heuristic algorithm based on a local search technique. First, a set of feasible routes servicing a subset of customers is iteratively built by considering both the distance from the depot and the collected profit. Second, we use tailored moves embedded into a local search scheme to improve the initial solution. An in-depth analysis is conducted in order to investigate the effectiveness of each move. Preliminary computational results are presented. 

  • Poster
Online user: 1 RSS Feed