On the selection of k efficient paths by clustering techniques

Massimiliano Caramia and Stefano Giordani

International Journal of Data Mining, Modelling and Management, 2009, vol. 1, issue 3, 237-260

Abstract: In the multi-objective shortest path problem usually there is not just one single path that simultaneously minimises r > 1 objective functions (costs); that is why the problem consists in finding the set of efficient paths of the given network. The number of such paths is often very large, while from an application point of view one is generally interested in selecting a given (small) number k > 1 of efficient paths that are representative of the whole efficient path set. In this paper, we propose a clustering-based approach for selecting k efficient paths maximising their representativeness with respect to the cost vectors of all the efficient paths or w.r.t. the dissimilarity among the k selected paths. Computational results are given on random networks; a comparison with a known approach in the literature is also presented.

Keywords: multi-objective shortest paths; fuzzy k-means algorithm; dissimilar paths; clustering. (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=27285 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijdmmm:v:1:y:2009:i:3:p:237-260

Access Statistics for this article

More articles in International Journal of Data Mining, Modelling and Management from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().