RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication
Artículo científico (JournalArticle)
Transportation infrastructure network design in the presence of modal competition: computational complexity classification and a genetic algorithm
[EN] 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., Mozart Menezes and Juan A. Mesa were partially supported by project MTM2015-
67706-P (MINECO/FEDER,UE). Federico Perea was partially supported by the Spanish Ministry of
Science, Innovation, and Universities, under projects "OPTEP-Port Terminal Operations Optimization" (No. RTI2018-094940-B-I00) and MTM2016-74983, fnanced with FEDER funds, and by the Universitat Politècnica de València under grant SP20180164 of the program Primeros Proyectos de Investigaciòn (PAID-06-18), Vicerrectorado de Investigaciòn, Innovaciòn y Transferencia. All this support is gratefully acknowledged.
Project:
Ministerio de Economía y Competitividad / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 MTM2016-74983-C2-1-R
,
Ministerio de Economía y Competitividad MTM2015-67706-P
,
Universitat Politècnica de València PAID-06-18
,
Universitat Politècnica de València SP20180164
,
Agencia Estatal de Investigación RTI2018-094940-B-I00