The Hub Line Location Problem

Elisangela Martins de Sá (), Ivan Contreras (), Jean-François Cordeau (), Ricardo Saraiva de Camargo () and Gilberto de Miranda ()
Additional contact information
Elisangela Martins de Sá: Department of Industrial Engineering, Federal University of Minas Gerais, Pampulha, Belo Horizonte 31270-921, Brazil; and Interuniversity Research Centre on Enterprise Networks, Logistics, and Transportation (CIRRELT), Université de Montréal, Montréal, Québec H3C 3J7, Canada
Ivan Contreras: Concordia University, Montréal, Québec H3G 1M8, Canada; and Interuniversity Research Centre on Enterprise Networks, Logistics, and Transportation (CIRRELT), Université de Montréal, Montréal, Québec H3C 3J7, Canada
Jean-François Cordeau: HEC Montréal, Montréal, Quebec H3T 2A7, Canada; and Interuniversity Research Centre on Enterprise Networks, Logistics, and Transportation (CIRRELT), Université de Montréal, Montréal, Québec H3C 3J7, Canada
Ricardo Saraiva de Camargo: Department of Industrial Engineering, Federal University of Minas Gerais, Pampulha, Belo Horizonte 31270-921, Brazil
Gilberto de Miranda: Department of Industrial Engineering, Federal University of Minas Gerais, Pampulha, Belo Horizonte 31270-921, Brazil

Transportation Science, 2015, vol. 49, issue 3, 500-518

Abstract: This paper presents the hub line location problem in which the location of a set of hub facilities connected by means of a path (or line) is considered. Potential applications arise in the design of public transportation and rapid transit systems, where network design costs greatly dominate routing costs and thus full interconnection of hub facilities is unrealistic. Given that service time is the predominant objective in these applications, the problem considers the minimization of the total weighted travel time between origin/destination nodes while taking into account the time spent to access and exit the hub line. An exact algorithm based on a Benders decomposition of a strong path-based formulation is proposed. The standard decomposition method is enhanced through the incorporation of several features such as a multicut strategy, an efficient algorithm to solve the subproblem and to obtain stronger optimality cuts, and a Benders branch-and-cut scheme that requires the solution of only one master problem. Computational results obtained on benchmark instances with up to 100 nodes confirm the efficiency of the proposed algorithm, which is considerably faster and able to solve larger instances than a general purpose solver.

Keywords: hub location; line networks; Benders decomposition method (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (43)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2014.0576 (application/pdf)

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:inm:ortrsc:v:49:y:2015:i:3:p:500-518

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().