- -

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

RiuNet: Repositorio Institucional de la Universidad Politécnica de Valencia

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

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

Mostrar el registro sencillo del ítem

Ficheros en el ítem

Thumbnail
Nombre: Perea;Menezes;Mesa ...
Tamaño: 382.9Kb
Formato: PDF
Descripción: Versión del Autor.
Abrir
[Cerrado]
Nombre: Perea2020_Article ...
Tamaño: 2.112Mb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor
dc.contributor.author Perea Rojas Marcos, Federico es_ES
dc.contributor.author Menezes, Mozart B. C. es_ES
dc.contributor.author Mesa, Juan A. es_ES
dc.contributor.author Rubio-Del-Rey, Fernando es_ES
dc.date.accessioned 2021-05-21T03:31:30Z
dc.date.available 2021-05-21T03:31:30Z
dc.date.issued 2020-07 es_ES
dc.identifier.issn 1134-5764 es_ES
dc.identifier.uri http://hdl.handle.net/10251/166576
dc.description.abstract [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. es_ES
dc.description.sponsorship 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. es_ES
dc.language Inglés es_ES
dc.publisher Springer-Verlag es_ES
dc.relation.ispartof Top es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Networks es_ES
dc.subject Graphs es_ES
dc.subject Transportation es_ES
dc.subject Computational complexity es_ES
dc.subject Genetic algorithms es_ES
dc.subject.classification ESTADISTICA E INVESTIGACION OPERATIVA es_ES
dc.title Transportation infrastructure network design in the presence of modal competition: computational complexity classification and a genetic algorithm es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1007/s11750-019-00537-x es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MINECO//MTM2016-74983-C2-1-R/ES/Nuevos Desafíos Matemáticos en Problemas Logísticos y de Transporte Integrado sobre Redes Complejas: Diseño y Optimización/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MINECO//MTM2015-67706-P/ES/ANALISIS ESTRUCTURAL DE MODELOS MATEMATICOS DE OPTIMIZACION EN LOCALIZACION Y PLANIFICACION DEL TRANSPORTE/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/UPV//PAID-06-18/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/UPV//SP20180164/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/RTI2018-094940-B-I00/ES/OPTIMIZACION DE OPERACIONES EN TERMINALES PORTUARIAS/ es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Estadística e Investigación Operativa Aplicadas y Calidad - Departament d'Estadística i Investigació Operativa Aplicades i Qualitat es_ES
dc.description.bibliographicCitation Perea Rojas Marcos, F.; Menezes, MBC.; Mesa, JA.; Rubio-Del-Rey, F. (2020). Transportation infrastructure network design in the presence of modal competition: computational complexity classification and a genetic algorithm. Top. 28(2):442-474. https://doi.org/10.1007/s11750-019-00537-x es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1007/s11750-019-00537-x es_ES
dc.description.upvformatpinicio 442 es_ES
dc.description.upvformatpfin 474 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 28 es_ES
dc.description.issue 2 es_ES
dc.relation.pasarela S\400778 es_ES
dc.contributor.funder Agencia Estatal de Investigación es_ES
dc.contributor.funder European Regional Development Fund es_ES
dc.contributor.funder Universitat Politècnica de València es_ES
dc.contributor.funder Ministerio de Economía y Competitividad es_ES
dc.description.references Balakrishnan A, Magnanti TL, Mirchandani P (1997) Network design. Annotated bibliography in combinatorial optimization. Wiley, New York es_ES
dc.description.references Bussieck M, Winter T, Zimmermann U (1997) Discrete optimization in public rail transport. Math Prog 79(1–3):415–444 es_ES
dc.description.references Chakroborty P (2003) Genetic algorithms for optimal urban transit network design. Comput Aided Civ Infrastruct Eng 18:184–200 es_ES
dc.description.references Chakroborty P, Dwivedi T (2002) Optimal route network design for transit systems using genetic algorithms. Eng Optim 34(1):83–100 es_ES
dc.description.references Desaulniers G, Hickman MD (2007) Public transit. Transportation Handbooks in operations research and management science, vol 14. Elsevier, Amsterdam, pp 69–127 es_ES
dc.description.references García-Archilla B, Lozano AJ, Mesa JA, Perea F (2013) GRASP algorithms for the robust railway network design problem. J Heuristics 19(2):399–422 es_ES
dc.description.references Garey M, Johnson DS (1979) Computers and Intractability: a guide to the theory of NP-completeness. W.H Freeman and Company, US es_ES
dc.description.references Goel G, Karande C, Tripathi P, Wanga L (2010) Approximability of combinatorial problems with multi-agent submodular cost functions. ACM SIGecom Exch 9(1):1–4 es_ES
dc.description.references Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1:169–197 es_ES
dc.description.references Grötschel M, Lovász L, Schrijver A (1993) Geometric algorithms and combinatorial optimization, 2nd edn. Springer-Verlag, New York es_ES
dc.description.references Guihaire V, Hao JK (2008) Transit network design and scheduling: a global review. Transp Res Part A 42:1251–1273 es_ES
dc.description.references Jegelka SS (2012) Combinatorial problems with sub-modular coupling in machine learning and computer vision. Thesis ETH Zurich es_ES
dc.description.references Laporte G, Mesa JA, Ortega FA (1995) Assessing the efficiency of rapid transit configurations. Top 5:95–104 es_ES
dc.description.references Laporte G, Mesa JA, Perea F (2010) A game theoretic framework for the robust railway transit network design problem. Transp Res Part B 44:447–459 es_ES
dc.description.references Magnanti TL, Wong RT (1984) Network design and transportation planning: models and algorithms. Transp Sci 18:1–55 es_ES
dc.description.references Marín A, García-Ródenas R (2009) Location of infrastructure in urban railway networks. Comput Oper Res 36(5):1461–1477 es_ES
dc.description.references Mesa JA, Boffey BT (1996) A review of extensive facility location in networks. Eur J Oper Res 95:592–603 es_ES
dc.description.references Nayeem MA, Rahman MK, Rahman MS (2014) Transit network design by genetic algorithm with elitism. Transp Res Part C 46:30–45 es_ES
dc.description.references Nemhauser GL, Wolsey LA (1999) Integer and combinatorial optimization. Wiley, Amsterdam es_ES
dc.description.references Perea F, Mesa JA, Laporte G (2014) Adding a new station and a road link to a road-rail network in the presence of modal competition. Transp Res Part B 68:1–16 es_ES
dc.description.references Puerto J, Ricca F, Scozzari A (2018) Extensive facility location problems on networks: an updated review. TOP 26(2):187–226 es_ES
dc.description.references Schmidt M, Schöbel A (2014) Location of speed-up subnetworks. Ann Oper Res 223(1):379–401 es_ES
dc.description.references Schöbel A (2012) Line planning in public transportation: models and methods. OR Spectr 34(3):491–510 es_ES
dc.description.references Sourirajan K, Ozsen L, Uzsoy R (2009) A genetic algorithm for a single product network design model with lead time and safety stock considerations. Eur J Oper Res 197(2):599–608 es_ES
dc.description.references Székely L, Wang H (2005) On subtrees of trees. Adv Appl Math 34:138–155 es_ES
dc.description.references Ukkusuri SV, Mathew TV, Waller ST (2007) Robust transportation network design under demand uncertainty. Comput Aided Civ Infrast Eng 22:6–18 es_ES


Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem