Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem

Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem

0.00 Avg rating0 Votes
Article ID: iaor2006961
Country: United Kingdom
Volume: 32
Issue: 9
Start Page Number: 2383
End Page Number: 2405
Publication Date: Sep 2005
Journal: Computers and Operations Research
Authors: , ,
Keywords: transportation: road, graphs, heuristics
Abstract:

Monitoring flows on networks is a research area for which a number of applications are waiting for models and algorithms to face new problems emerging with a very high pace. In this paper we analyze a particular optimization problem, namely the Dominating Paths Problem (DPP), that has application in this field especially for urban transportation networks. Given an undirected G = (V,E) and a subset BV of bound vertices, we look for a set of vertices M of minimum size such that each element of M is the origin of one or more paths, and the set of all these paths dominates B. For this NP-hard problem, we present an approximation algorithm and new heuristic procedures extensively evaluated on a set of test instances. We defined two different sets of benchmarks: grid graphs and random graphs. Moreover, we included two test cases taken from real life traffic networks. Computational results, discussed in the paper, give insights both on the problem and on the algorithm's performance.

Reviews

Required fields are marked *. Your email address will not be published.