Metaheuristics to Solve the Multiobjective Transit Network Design Problem (TNDP) with Multiperiod Demand
In this paper we study the Tranport Network Design Problem (TNDP). It consists in finding the ideal combination of routes and frequencies that allow the decision maker to balance the interests of the users and the tran- sit operators, which are opposite. The TNDP uses as input a graph, with their tr...
- Autores:
-
Garzón, Natalia Andrea
González Neira, Eliana María
Pérez Vélez, Ignacio
- Tipo de recurso:
- Fecha de publicación:
- 2017
- Institución:
- Universidad EAFIT
- Repositorio:
- Repositorio EAFIT
- Idioma:
- spa
- OAI Identifier:
- oai:repository.eafit.edu.co:10784/13170
- Acceso en línea:
- http://publicaciones.eafit.edu.co/index.php/ingciencia/article/view/3681
http://hdl.handle.net/10784/13170
- Palabra clave:
- Network design problem
Public transportation
Variable neighborhood search
Multi-objective optimization
Diseño de redes de transporte
Transporte público
Búsqueda de vecindades variables
Optimización multiobjetivo
- Rights
- License
- Copyright (c) 2017 Natalia Andrea Garzon, Eliana María González Neira, Ignacio Pérez Vélez
| id |
REPOEAFIT2_c49de40df38001b375a6de61e018fa05 |
|---|---|
| oai_identifier_str |
oai:repository.eafit.edu.co:10784/13170 |
| network_acronym_str |
REPOEAFIT2 |
| network_name_str |
Repositorio EAFIT |
| repository_id_str |
|
| dc.title.eng.fl_str_mv |
Metaheuristics to Solve the Multiobjective Transit Network Design Problem (TNDP) with Multiperiod Demand |
| dc.title.spa.fl_str_mv |
Metaheurística para la solución del Transit Network Design Problem multiobjetivo con demanda multiperiodo |
| title |
Metaheuristics to Solve the Multiobjective Transit Network Design Problem (TNDP) with Multiperiod Demand |
| spellingShingle |
Metaheuristics to Solve the Multiobjective Transit Network Design Problem (TNDP) with Multiperiod Demand Network design problem Public transportation Variable neighborhood search Multi-objective optimization Diseño de redes de transporte Transporte público Búsqueda de vecindades variables Optimización multiobjetivo |
| title_short |
Metaheuristics to Solve the Multiobjective Transit Network Design Problem (TNDP) with Multiperiod Demand |
| title_full |
Metaheuristics to Solve the Multiobjective Transit Network Design Problem (TNDP) with Multiperiod Demand |
| title_fullStr |
Metaheuristics to Solve the Multiobjective Transit Network Design Problem (TNDP) with Multiperiod Demand |
| title_full_unstemmed |
Metaheuristics to Solve the Multiobjective Transit Network Design Problem (TNDP) with Multiperiod Demand |
| title_sort |
Metaheuristics to Solve the Multiobjective Transit Network Design Problem (TNDP) with Multiperiod Demand |
| dc.creator.fl_str_mv |
Garzón, Natalia Andrea González Neira, Eliana María Pérez Vélez, Ignacio |
| dc.contributor.author.none.fl_str_mv |
Garzón, Natalia Andrea González Neira, Eliana María Pérez Vélez, Ignacio |
| dc.contributor.affiliation.spa.fl_str_mv |
Escuela Colombiana de Ingeniería Julio Garavito Pontificia Universidad Javeriana |
| dc.subject.keyword.eng.fl_str_mv |
Network design problem Public transportation Variable neighborhood search Multi-objective optimization |
| topic |
Network design problem Public transportation Variable neighborhood search Multi-objective optimization Diseño de redes de transporte Transporte público Búsqueda de vecindades variables Optimización multiobjetivo |
| dc.subject.keyword.spa.fl_str_mv |
Diseño de redes de transporte Transporte público Búsqueda de vecindades variables Optimización multiobjetivo |
| description |
In this paper we study the Tranport Network Design Problem (TNDP). It consists in finding the ideal combination of routes and frequencies that allow the decision maker to balance the interests of the users and the tran- sit operators, which are opposite. The TNDP uses as input a graph, with their transportation costs (in this case time), and the demands associated to each pair of nodes. Our proposed approach to solve the TNDP is based on a Variable Neighborhood Search (VNS) metaheuristic. VNS has been used to solve different kinds of combinatorial optimization problems and it consists in searching competitive solutions by iterative changes of the neighborhood. The VNS is tested first for the case study designed by Mandl, which consists in 15 nodes and 21 arcs, and a symmetric demand matrix. Posteriorly the VNS was tested for other 11 instances of (15, 30 and 45 nodes). In the first place, the model was run for that original case to compare it with other authors who worked this problem in the past. Then, we tested the VNS approach for a changing demand model in 3 moments of the day (Morning, afternoon and night) to prove the positive results obtained in the first exercise and give a greater scope to the problem solution. |
| publishDate |
2017 |
| dc.date.issued.none.fl_str_mv |
2017-01-20 |
| dc.date.available.none.fl_str_mv |
2018-11-16T16:28:56Z |
| dc.date.accessioned.none.fl_str_mv |
2018-11-16T16:28:56Z |
| dc.date.none.fl_str_mv |
2017-01-20 |
| dc.type.eng.fl_str_mv |
info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion article publishedVersion |
| dc.type.coarversion.fl_str_mv |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| dc.type.coar.fl_str_mv |
http://purl.org/coar/resource_type/c_6501 http://purl.org/coar/resource_type/c_2df8fbb1 |
| dc.type.local.spa.fl_str_mv |
Artículo |
| status_str |
publishedVersion |
| dc.identifier.issn.none.fl_str_mv |
2256-4314 1794-9165 |
| dc.identifier.uri.none.fl_str_mv |
http://publicaciones.eafit.edu.co/index.php/ingciencia/article/view/3681 http://hdl.handle.net/10784/13170 |
| dc.identifier.doi.none.fl_str_mv |
10.17230/ingciencia.13.25.2 |
| identifier_str_mv |
2256-4314 1794-9165 10.17230/ingciencia.13.25.2 |
| url |
http://publicaciones.eafit.edu.co/index.php/ingciencia/article/view/3681 http://hdl.handle.net/10784/13170 |
| dc.language.iso.none.fl_str_mv |
spa |
| language |
spa |
| dc.relation.isversionof.none.fl_str_mv |
http://publicaciones.eafit.edu.co/index.php/ingciencia/article/view/3681 |
| dc.rights.eng.fl_str_mv |
Copyright (c) 2017 Natalia Andrea Garzon, Eliana María González Neira, Ignacio Pérez Vélez Attribution 4.0 International (CC BY 4.0) |
| dc.rights.coar.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| dc.rights.uri.none.fl_str_mv |
http://creativecommons.org/licenses/by/4.0 |
| dc.rights.local.spa.fl_str_mv |
Acceso abierto |
| rights_invalid_str_mv |
Copyright (c) 2017 Natalia Andrea Garzon, Eliana María González Neira, Ignacio Pérez Vélez Attribution 4.0 International (CC BY 4.0) http://creativecommons.org/licenses/by/4.0 Acceso abierto http://purl.org/coar/access_right/c_abf2 |
| dc.format.none.fl_str_mv |
application/pdf |
| dc.publisher.spa.fl_str_mv |
Universidad EAFIT |
| dc.source.none.fl_str_mv |
instname:Universidad EAFIT reponame:Repositorio Institucional Universidad EAFIT |
| dc.source.eng.fl_str_mv |
Ingeniería y Ciencia; Vol 13 No 25 (2017); 29-69 |
| dc.source.spa.fl_str_mv |
Ingeniería y Ciencia; Vol 13 No 25 (2017); 29-69 |
| instname_str |
Universidad EAFIT |
| institution |
Universidad EAFIT |
| reponame_str |
Repositorio Institucional Universidad EAFIT |
| collection |
Repositorio Institucional Universidad EAFIT |
| bitstream.url.fl_str_mv |
https://repository.eafit.edu.co/bitstreams/66bd48c8-c9d0-4a4a-a63a-52879493b506/download https://repository.eafit.edu.co/bitstreams/7e6361bc-c942-4703-8fea-7e1f974501a2/download https://repository.eafit.edu.co/bitstreams/fa0c368c-e8f3-4429-8ed6-eaad927ea801/download |
| bitstream.checksum.fl_str_mv |
969066d47b7f60904dbef40105c916e5 527ed3be7cc465e858825ca2eac14134 da9b21a5c7e00c7f1127cef8e97035e0 |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio Institucional Universidad EAFIT |
| repository.mail.fl_str_mv |
repositorio@eafit.edu.co |
| _version_ |
1818102402063007744 |
| spelling |
2017-01-202018-11-16T16:28:56Z2017-01-202018-11-16T16:28:56Z2256-43141794-9165http://publicaciones.eafit.edu.co/index.php/ingciencia/article/view/3681http://hdl.handle.net/10784/1317010.17230/ingciencia.13.25.2In this paper we study the Tranport Network Design Problem (TNDP). It consists in finding the ideal combination of routes and frequencies that allow the decision maker to balance the interests of the users and the tran- sit operators, which are opposite. The TNDP uses as input a graph, with their transportation costs (in this case time), and the demands associated to each pair of nodes. Our proposed approach to solve the TNDP is based on a Variable Neighborhood Search (VNS) metaheuristic. VNS has been used to solve different kinds of combinatorial optimization problems and it consists in searching competitive solutions by iterative changes of the neighborhood. The VNS is tested first for the case study designed by Mandl, which consists in 15 nodes and 21 arcs, and a symmetric demand matrix. Posteriorly the VNS was tested for other 11 instances of (15, 30 and 45 nodes). In the first place, the model was run for that original case to compare it with other authors who worked this problem in the past. Then, we tested the VNS approach for a changing demand model in 3 moments of the day (Morning, afternoon and night) to prove the positive results obtained in the first exercise and give a greater scope to the problem solution.En este artículo se estudia el problema de Red de Transporte, usualmente conocido como TNDP (Transit Network Design Problem) multiobjetivo. Este consiste en encontrar la combinación ideal de rutas y frecuencias, que permita realizar un balance entre los intereses de los usuarios y los opera- dores, que se contraponen. Utiliza como datos de entrada un grafo con sus respectivos costos de transporte (en este caso tiempos) y demandas aso- ciadas a cada par de nodos. Como método de solución a este problema de optimización combinatoria multiobjetivo, se propone el uso de la metaheu- rística Búsqueda en Vecindades Variables (VNS), que resuelve problemas de optimización buscando soluciones competitivas mediante el cambio de vecindario iterativamente. El método propuesto fue probado inicialmente en el caso de estudio diseñado por Mandl, que consiste en 15 nodos y 21 arcos, y una matriz de demandas simétrica; y posteriormente para otras 11 instancias con tres tamaños de grafo diferentes (15, 30, 45 nodos). El mode- lo primero se corrió con el caso original para compararlo con autores que en oportunidades pasadas han trabajado el mismo problema. Posteriormente el VNS propuesto se probó con un modelo de demanda cambiante en 3 momentos del día (Mañana, tarde y noche) para corroborar los resultados positivos obtenidos en el primer ejercicio y darle un alcance mayor a la solución del problema.application/pdfspaUniversidad EAFIThttp://publicaciones.eafit.edu.co/index.php/ingciencia/article/view/3681Copyright (c) 2017 Natalia Andrea Garzon, Eliana María González Neira, Ignacio Pérez VélezAttribution 4.0 International (CC BY 4.0)http://creativecommons.org/licenses/by/4.0Acceso abiertohttp://purl.org/coar/access_right/c_abf2instname:Universidad EAFITreponame:Repositorio Institucional Universidad EAFITIngeniería y Ciencia; Vol 13 No 25 (2017); 29-69Ingeniería y Ciencia; Vol 13 No 25 (2017); 29-69Metaheuristics to Solve the Multiobjective Transit Network Design Problem (TNDP) with Multiperiod DemandMetaheurística para la solución del Transit Network Design Problem multiobjetivo con demanda multiperiodoinfo:eu-repo/semantics/articleinfo:eu-repo/semantics/publishedVersionarticlepublishedVersionArtículohttp://purl.org/coar/version/c_970fb48d4fbd8a85http://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1Network design problemPublic transportationVariable neighborhood searchMulti-objective optimizationDiseño de redes de transporteTransporte públicoBúsqueda de vecindades variablesOptimización multiobjetivoGarzón, Natalia Andreab1c43538-7981-47ff-a4c9-d6b643e3646a-1González Neira, Eliana Maríacc4cd254-a5e1-46bb-bd30-71f7a36e5aae-1Pérez Vélez, Ignaciobd146bd7-865b-4416-9f33-c79039957ff0-1Escuela Colombiana de Ingeniería Julio GaravitoPontificia Universidad JaverianaIngeniería y Ciencia13252969ing.ciencORIGINAL2.pdf2.pdfTexto completo PDFapplication/pdf914796https://repository.eafit.edu.co/bitstreams/66bd48c8-c9d0-4a4a-a63a-52879493b506/download969066d47b7f60904dbef40105c916e5MD52articulo.htmlarticulo.htmlTexto completo HTMLtext/html374https://repository.eafit.edu.co/bitstreams/7e6361bc-c942-4703-8fea-7e1f974501a2/download527ed3be7cc465e858825ca2eac14134MD53THUMBNAILminaitura-ig_Mesa de trabajo 1.jpgminaitura-ig_Mesa de trabajo 1.jpgimage/jpeg265796https://repository.eafit.edu.co/bitstreams/fa0c368c-e8f3-4429-8ed6-eaad927ea801/downloadda9b21a5c7e00c7f1127cef8e97035e0MD5110784/13170oai:repository.eafit.edu.co:10784/131702024-12-04 11:48:25.433http://creativecommons.org/licenses/by/4.0Copyright (c) 2017 Natalia Andrea Garzon, Eliana María González Neira, Ignacio Pérez Vélezopen.accesshttps://repository.eafit.edu.coRepositorio Institucional Universidad EAFITrepositorio@eafit.edu.co |