Publication:
Metaheurística para la solución del Transit Network Design Problem multiobjetivo con demanda multiperiodo

Thumbnail Image
Files

Files

Metaheurística para la solución del Transit Network Design Problem multiobjetivo con demanda multiperiodo.pdf (884.72 KB)
View Statistics
Reference Managers
Mendeley
Indexers
Google Scholar CORE
QR Code
QR Code
Authors

Authors

Garzón, Natalia Andrea
González Neira, Eliana María
Pérez Vélez, Ignacio
Abstract (Spanish)
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 metaheurí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 11instancias con tres tamaños de grafo diferentes (15, 30, 45 nodos). El modelo 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 3momentos 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.
Abstract (English)
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 transit 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.
Extent
41 páginas
URI: https://repositorio.escuelaing.edu.co/handle/001/1621
Collections

Collections

AI - Centro de Investigación en Manufactura y Servicios – CIMSER
References

O. Figueroa, “Políticas de desarrollo y políticas de transporte urbano.coherencias y contradicciones. in: Carrión, f. (ed.). la ciudad construida.urbanismo en américa latina.” Quito. FLACSO – Junta de Andalucía, Tech.Rep., 2001. [Online]. Available: http://www.flacso.org.ec/docs/sfccfigueroa.pdf 31

Norambuena, “Diseño Óptimo de sistemas de trans-porte público urbano,”Master’s thesis, Pontificia uni-versidadcatolicadechile,2002. [Online].Available:http://www.academia.edu/9176445/DISE%C3%91O_%C3%93PTIMO_DE_SISTEMAS_DE_TRANSPORTE_P%C3%9ABLICO_URBANO 31

O. Figueroa, “Transporte urbano y globalización. políticas y efectosen américa latina,”Revista EURE - Revista De Estudios UrbanoRegionales, vol. 34, no. 94, pp. 41–53, 2005. [Online]. Available:http://www.eure.cl/index.php/eure/article/view/1337 31

A. Gutiérrez, “Transporte público y exclusión social. reflexiones paradiscusión en latinoamérica tras la década del 90,” inXIII CongresoLatinoamericano de Transporte público y urbano., 2005. [Online]. Available: http://www.filo.uba.ar/contenidos/investigacion/institutos/geo/ptt/GutierrezClatpu05.pdf 31

C. A. Coello, C. Dhaenens, and L. Jourdan, “Multi-objective combinatorialoptimization: Problematic and context,” inAdvances in multi-objective na-ture inspired computing. Springer, 2010, pp. 1–21. 31

C. Blum and A. Roli, “Metaheuristics in combinatorial optimization: Over-view and conceptual comparison,”ACM Computing Surveys (CSUR), vol. 35,no. 3, pp. 268–308, 2003. 31

C. A. Martínez, “Metaheurísticas híbridas aplicadas al problema de ruteode arcos capacitados,” Ph.D. dissertation, Universidad de Buenos Aires,2011. [Online]. Available: http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_4979_Martinez 31

P. Hansen, N. Mladenović, and J. A. M. Pérez, “Variable neighbourhoodsearch: methods and applications,”Annals of Operations Research, vol. 175,no. 1, pp. 367–407, 2010. 31

K. K. M. Karlaftis, “Transit route network design problem: Review,”Journalof Transportation Engineering, vol. 135, no. 8, pp. 491–505, 2009. 32

W. Fan and R. B. Machemehl,A Tabu Search Based Heuristic Methodfor the Transit Route Network Design Problem. Berlin, Heidelberg:Springer Berlin Heidelberg, 2008, pp. 387–408. [Online]. Available:http://dx.doi.org/10.1007/978-3-540-73312-6_20 32

E. Cipriani, S. Gori, and M. Petrelli, “Transit network design: A procedureand an application to a large urban area,”Transportation Research Part C:Emerging Technologies, vol. 20, no. 1, pp. 3 – 14, 2012, special issue onOptimization in Public Transport+ISTT2011Special issue on Optimizationin Public Transport+International Symposium on Transportation and TrafficTheory (ISTTT), Berkeley, California, July 18-20, 2011. [Online]. Available:http://www.sciencedirect.com/science/article/pii/S0968090X10001397 32,33

M. H. Baaj and H. S. Mahmassani, “An ai-based approach fortransit route system planning and design,”Journal of AdvancedTransportation, vol. 25, no. 2, pp. 187–209, 1991. [Online]. Available:http://dx.doi.org/10.1002/atr.5670250205 32, 42

A. Mauttone, H. Cancela, and M. Urquhart, “Diseño y optimizacion de rutasy frecuencias en el transporte colectivo urbano, modelos y algoritmos,” 2002.32

V. Tom and S. Mohan, “Transit route network design using frequency codedgenetic algorithm,”Journal of transportation engineering, vol. 129, no. 2, pp.186–195, 2003. 32

F. Zhao and X. Zeng, “Simulated annealing–genetic algorithm for transitnetwork optimization,”Journal of Computing in Civil Engineering, vol. 20,no. 1, pp. 57–68, 2006. 32, 33

W. Szeto and Y. Wu, “A simultaneous bus route design and frequency settingproblem for tin shui wai, hong kong,”European Journal of OperationalResearch, vol. 209, no. 2, pp. 141 – 155, 2011. [Online]. Available:http://www.sciencedirect.com/science/article/pii/S0377221710005576 32

A. Ceder and Y. Israeli, “User and operator perspectives in transit networkdesign,”Transportation Research Record, vol. 1623, pp. 3–7, 1998. 32

A. Mauttone and M. E. Urquhart, “A route set construction algorithm for thetransit network design problem,”Computers & Operations Research, vol. 36,no. 8, pp. 2440 – 2449, 2009, constraint Programming. [Online]. Available:http://www.sciencedirect.com/science/article/pii/S0305054808001780 32

L. Fan and C. L. Mumford, “A metaheuristic approach to the urban transitrouting problem,”Journal of Heuristics, vol. 16, no. 3, pp. 353–372, 2010. 32

M. Nikolić and D. Teodorović, “Transit network design by bee colony opti-mization,”Expert Systems with Applications, vol. 40, no. 15, pp. 5945–5955,2013. 32, 33, 40

A. B. Hosapujari and A. Verma, “Development of a hub and spokemodel for bus transit route network design,”Procedia - Social andBehavioral Sciences, vol. 104, pp. 835 – 844, 2013. [Online]. Available:http://www.sciencedirect.com/science/article/pii/S1877042813045692 32,33

M. A. Nayeem, M. K. Rahman, and M. S. Rahman, “Transit network designby genetic algorithm with elitism,”Transportation Research Part C: Emer-ging Technologies, vol. 46, pp. 30–45, 2014. 32, 33

V. Guihaire and J.-K. Hao, “Transit network design and scheduling: A globalreview,”Transportation Research Part A: Policy and Practice, vol. 42, no. 10,pp. 1251–1273, 2008. 32

T. L. Magnanti and R. T. Wong, “Network design and transportation plan-ning: Models and algorithms,”Transportation science, vol. 18, no. 1, pp.1–55, 1984. 33

Z. Gao, H. Sun, and L. L. Shan, “A continuous equilibrium network designmodel and algorithm for transit systems,”Transportation Research Part B:Methodological, vol. 38, no. 3, pp. 235–250, 2004. 33

R. Borndörfer, M. Grötschel, and M. Pfetsch, “A column-generation approachto line planning in public transport,”Transportation Science, vol. 41, no. 1,pp. 123–132, 2007. 33

J. Guan, H. Yang, and S. Wirasinghe, “Simultaneous optimization oftransit line configuration and passenger line assignment,”TransportationResearch Part B: Methodological, vol. 40, no. 10, pp. 885 – 902,2006. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0191261506000154 33

M. Ehrgott and X. Gandibleux, “Approximative solution methods for mul-tiobjective combinatorial optimization,”Top, vol. 12, no. 1, pp. 1–63, 2004.33

D. E. Goldberg and J. H. Holland, “Genetic algorithms and machine lear-ning,”Machine learning, vol. 3, no. 2, pp. 95–99, 1988. 33

S. Pattnaik, S. Mohan, and V. Tom, “Urban bus transit route network de-sign using genetic algorithm,”Journal of transportation engineering, vol. 124,no. 4, pp. 368–375, 1998

J. Agrawal and T. V. Mathew, “Transit route network design using parallelgenetic algorithm,”Journal of Computing in Civil Engineering, vol. 18, no. 3,pp. 248–256, 2004. 33

M. Bielli, M. Caramia, and P. Carotenuto, “Genetic algorithms inbus network optimization,”Transportation Research Part C: EmergingTechnologies, vol. 10, no. 1, pp. 19 – 34, 2002. [Online]. Available:http://www.sciencedirect.com/science/article/pii/S0968090X00000486 33

P. Chakroborty, “Genetic algorithms for optimal urban transit network de-sign,”Computer-Aided Civil and Infrastructure Engineering, vol. 18, no. 3,pp. 184–200, 2003. 33

K. Deb, “Multi-objective optimization using evolutionary algorithms,” 2001.33

J. Pacheco, A. Alvarez, S. Casado, and J. L. González-Velarde, “A tabu searchapproach to an urban transport problem in northern spain,”Computers &Operations Research, vol. 36, no. 3, pp. 967–979, 2009. 33

A. Mauttone and M. E. Urquhart, “A multi-objective metaheuristicapproach for the transit network design problem,”Public Transport, vol. 1,no. 4, pp. 253–273, 2009. [Online]. Available: http://dx.doi.org/10.1007/s12469-010-0016-7 33

K. Fleszar and K. S. Hindi, “An effective vns for the capacitated p-medianproblem,”European Journal of Operational Research, vol. 191, no. 3, pp.612–622, 2008. 33

J. Yang, J. Zhang, M. E. Aydin, and J. Y. Wu, “A novel programming modeland optimisation algorithms for wcdma networks,” inVehicular TechnologyConference, 2007. VTC2007-Spring. IEEE 65th. IEEE, 2007, pp. 1182–1187. 33

M. P. Pérez, F. A. Rodríguez, and J. M. Moreno-Vega, “A hybrid vns–pathrelinking for the p-hub median problem,”IMA Journal of Management Mat-hematics, 2007. 33

J. Puchinger, G. R. Raidl, and U. Pferschy, “The core concept for the mul-tidimensional knapsack problem,” inEuropean Conference on EvolutionaryComputation in Combinatorial Optimization. Springer, 2006, pp. 195–208.33

J. D. Beltrán, J. E. Calderón, R. J. Cabrera, J. A. M. Pérez, and J. M.Moreno-vega, “Grasp/vns hybrid for the strip packing problem,” inIn 1stInternational Workshop on Hybrid Metaheuristics, 2004, pp. 79–90 33

F. Parreño, R. Alvarez-Valdes, J. F. Oliveira, and J. M. Tamarit,“Neighborhood structures for the container loading problem: a vnsimplementation,”Journal of Heuristics, vol. 16, no. 1, pp. 1–22, 2010. [Online]. Available: http://dx.doi.org/10.1007/s10732-008-9081-3 33

S. Bock and K. Hoberg, “Detailed layout planning for irregularly-shapedmachines with transportation path design,”European Journal of OperationalResearch, vol. 177, no. 2, pp. 693–718, 2007. 33

Z. Sevkli and F. Sevilgen, “Variable neighborhood search for the orientee-ring problem,”Computer and Information Sciences–ISCIS 2006, pp. 134–143, 2006. 33

C. Archetti, A. Hertz, and M. G. Speranza, “Metaheuristics for the teamorienteering problem,”Journal of Heuristics, vol. 13, no. 1, pp. 49–76, 2007.33

X. Wang and L. Tang, “A population-based variable neighborhood search forthe single machine total weighted tardiness problem,”Computers & Opera-tions Research, vol. 36, no. 6, pp. 2105–2110, 2009. 33

M. R. De Paula, M. G. Ravetti, G. R. Mateus, and P. M. Pardalos, “Sol-ving parallel machines scheduling problems with sequence-dependent setuptimes using variable neighbourhood search,”IMA Journal of ManagementMathematics, vol. 18, no. 2, pp. 101–115, 2007. 33

C. Gagné, M. Gravel, and W. L. Price, “Using metaheuristic compromiseprogramming for the solution of multiple-objective scheduling problems,”The Journal of the Operational Research Society, vol. 56, no. 6, pp. 687–698,2005. [Online]. Available: http://www.jstor.org/stable/4102041 33

M. Sevkli and M. E. Aydin, “A variable neighbourhood search algorithmfor job shop scheduling problems,” inEuropean Conference on EvolutionaryComputation in Combinatorial Optimization. Springer, 2006, pp. 261–271.33

W. Pan Q, W. Wang, and Y. Zhu, “Somemeta-heuristics for no-wait flowshopproblem,”Computer Integrated Manufacturing System, vol. 13, no. 5, pp.967–970, 2007

R. Kolisch and S. Hartmann, “Experimental investigation of heuristics forresource-constrained project scheduling: An update,”European journal ofoperational research, vol. 174, no. 1, pp. 23–37, 2006.

B. Hu and G. R. Raidl, “Effective neighborhood structures for the genera-lized traveling salesman problem,” inEuropean Conference on EvolutionaryComputation in Combinatorial Optimization. Springer, 2008, pp. 36–47.

F. Carrabs, J.-F. Cordeau, and G. Laporte, “Variable neighbourhood searchfor the pickup and delivery traveling salesman problem with lifo loading,”Informs Journal Computation, vol. 19, no. 4, pp. 618–632, 2007.

L.-M. Rousseau, M. Gendreau, and G. Pesant, “Using constraint-basedoperators to solve the vehicle routing problem with time windows,”Journal of Heuristics, vol. 8, no. 1, pp. 43–58, 2002. [Online]. Available:http://dx.doi.org/10.1023/A:1013661617536

M. Polacek, R. F. Hartl, K. Doerner, and M. Reimann, “A variableneighborhood search for the multi depot vehicle routing problem with timewindows,”Journal of Heuristics, vol. 10, no. 6, pp. 613–627, 2004. [Online].Available: http://dx.doi.org/10.1007/s10732-005-5432-5

P. Hansen, N. Mladenovic, and J. Moreno, “Variable neighborhood search,”Revista Iberoamericana de Inteligncia Artificial, vol. 7, no. 19, pp. 1–16, 2003.

C. E. Mandl, “Evaluation and optimization of urban public transportationnetworks,”European Journal of Operational Research, vol. 5, no. 6, pp. 396–404, 1980