Including elastic demand in the hub line location problem

Resumen

The hub line location problem (HLLP) aims to locate p hubs connected by a path that is composed by p-1 hub arcs in such a way that the total travel time of the origin-destination pairs is minimized. If the direct travel time between an origin-destination is smaller than any path using the line, the demand is routed without using the hub line. HLLP assumes that demand between each origin and destination can be a priori estimated and that the resulting constructed hub line network does not have any effect on the demand. This problem was introduced in [1] and it has relevant applications in public transportation planning design (tram, subways, express bus lane, etc.) and road network design. In this work, we introduce the profit-oriented hub line location problem with elastic demand (ED-HLLP). This model is an extension of the HLLP that uses a gravity model to include the elasticity of demand. Gravity models have been previously used to model elastic demand in network design problems, see [2]. The aim of ED-HLLP is to maximize the revenue of the total time reduction provided by the hub line considering elastic demand. Thus, this new model takes into account the long-term impact on the demands that opening a hub line can have. We propose different non-linear formulations to address this problem. The main difference between them is the way in which the line structure is modeled. Due to the limitations that these formulations present, we introduce three main linear formulations. These linear formulations use the possible paths using the hub line as variables. Consequently, it is necessary to use a preprocessing phase that calculates the candidate paths for each origin destination. For this preprocessing phase, we provide efficient algorithms to create all possible candidate paths. Finally, we also present a computational experience that evaluates the strengths and limits of these formulations for ED-HLLP.