On the Generalized Elementary Shortest Path Problem: A heuristic approach - Archive ouverte HAL Access content directly
Conference Papers Year : 2013

On the Generalized Elementary Shortest Path Problem: A heuristic approach

(1, 2) , (1, 2) , (2) , (1)
1
2

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.
Not file

Dates and versions

hal-02890008 , version 1 (06-07-2020)

Identifiers

Cite

William Javier 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⟩

Collections

CNRS UTT LOSI
16 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More