Skip to Main content Skip to Navigation
Conference papers

On the Generalized Elementary Shortest Path Problem: A heuristic approach

Abstract : We introduce the generalized elementary shortest path problem (GESPP) where in addition to the features of the shortest path problem, nodes belong to predefined non-disjoint clusters. Each cluster is associated to a profit to the cost function, obtained if at least one element in the cluster appears in the path. Several applications can be considered as school bus routing, pricing problems, or telecommunication network design. Thus, depending on the case, clusters could be interpreted as groups of nodes with linking features as, for example, being easily reachable from each other, or some kind of coverage guarantee. We compare the GESPP to similar problems in the literature and we propose a two-phase heuristic algorithm for graphs including negative cycles. Tests on random instances with up to 100 nodes show an average gap of 0.3% to the best known solutions computed in 2.8s in average.
Document type :
Conference papers
Complete list of metadatas
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Monday, July 6, 2020 - 9:05:05 AM
Last modification on : Wednesday, July 22, 2020 - 9:14:03 AM





William Guerrero, Nubia Velasco, Caroline Prodhon, Ciro Alberto Amaya. On the Generalized Elementary Shortest Path Problem: A heuristic approach. International Network Optimization Conference (INOC 2013), May 2013, Tenerife, Spain. pp.503-510, ⟨10.1016/j.endm.2013.05.131⟩. ⟨hal-02890008⟩



Record views