Transportation infrastructure network design in the presence of modal competition: computational complexity classification and a genetic algorithm

• Federico Perea ^[1] ; Mozart B. C. Menezes ^[2] ; Juan A. Mesa ^[3] ; Fernando Rubio-Del-Rey ^[1]
  1. [1] Universidad Politécnica de Valencia

     Universidad Politécnica de Valencia

     Valencia, España

     
  2. [2] NEOMA Business School

     NEOMA Business School

     Arrondissement de Rouen, Francia

     
  3. [3] Universidad de Sevilla

     Universidad de Sevilla

     Sevilla, España

     

  Mostrar afiliaciones +
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 28, Nº. 2, 2020, págs. 442-474
• Idioma: inglés
• DOI: 10.1007/s11750-019-00537-x
• Enlaces
  • Texto completo
• Resumen

  • In this paper we analyze the computational complexity of transportation infrastructure network design problems, in the presence of a competing transportation mode. Some of these problems have previously been introduced in the literature. All problems studied have a common objective: the maximization of the number of travelers using the new network to be built. The differences between them are due to two factors. The first one is the constraints that the new network should satisfy: (1) budget constraint, (2) no-cycle constraint, (3) both constraints. The second factor is the topology of the network formed by the feasible links and stations: (1) a general network, (2) a forest. By combining these two factors, in total we analyze six problems, five of them are shown to be NP-hard, the sixth being trivial. Due to the NP-hardness of these problems, a genetic algorithm is proposed. Computational experiments show the applicability of this algorithm.