Inverse Combinatorial Optimization has become a relevant research subject over the past decades. In graph theory, the Inverse Shortest Path Length problem becomes relevant when people don't have access to the real cost of the arcs and want to infer their value so that the system has a specific outcome, such as one or more shortest paths between nodes. Several approaches have been proposed to tackle this problem, relying on different methods, and several applications have been suggested. This study explores an innovative evolutionary approach relying on a genetic algorithm. Two scenarios and corresponding representations are presented and experiments are conducted to test how they react to different graph characteristics and parameters. Their behaviour and differences are thoroughly discussed. The outcome supports that evolutionary algorithms may be a viable venue to tackle Inverse Shortest Path problems.<\/p>","DOI":"10.4018\/ijncr.2014100103","type":"journal-article","created":{"date-parts":[[2014,11,26]],"date-time":"2014-11-26T14:28:58Z","timestamp":1417012138000},"page":"36-54","source":"Crossref","is-referenced-by-count":2,"title":["A Genetic Algorithms Approach for Inverse Shortest Path Length Problems"],"prefix":"10.4018","volume":"4","author":[{"given":"Ant\u00f3nio","family":"Leit\u00e3o","sequence":"first","affiliation":[{"name":"CISUC, Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal"}]},{"given":"Adriano","family":"Vinhas","sequence":"additional","affiliation":[{"name":"CISUC, Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal"}]},{"given":"Penousal","family":"Machado","sequence":"additional","affiliation":[{"name":"CISUC, Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal"}]},{"given":"Francisco C\u00e2mara","family":"Pereira","sequence":"additional","affiliation":[{"name":"Department of Informatics Engineering, University of Coimbra & Singapore-MIT Alliance for Research and Technology, Singapore, Singapore"}]}],"member":"2432","reference":[{"key":"ijncr.2014100103-0","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0515-x"},{"key":"ijncr.2014100103-1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1052"},{"key":"ijncr.2014100103-2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.49.5.784.10601"},{"key":"ijncr.2014100103-3","doi-asserted-by":"publisher","DOI":"10.1287\/opre.49.5.771.10607"},{"key":"ijncr.2014100103-4","doi-asserted-by":"publisher","DOI":"10.1002\/net.10048"},{"key":"ijncr.2014100103-5","author":"R.Bellman","year":"1956","journal-title":"On a routing problem. Tech. rep"},{"key":"ijncr.2014100103-6","doi-asserted-by":"publisher","DOI":"10.1137\/0801026"},{"key":"ijncr.2014100103-7","first-page":"156","author":"D.Burton","year":"1997","journal-title":"The inverse shortest paths problem with upper bounds on shortest paths costs. Em Network Optimization"},{"key":"ijncr.2014100103-8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585693"},{"key":"ijncr.2014100103-9","unstructured":"Cai, M., & Yang, X. (1994). Inverse shortest path problems. Operations research and its applications. First International Symposium, ISORA, 95, pp. 19-22."},{"key":"ijncr.2014100103-10","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008360312607"},{"issue":"1","key":"ijncr.2014100103-11","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1002\/net.20344","article-title":"Complexity of some inverse shortest path lengths problems.","volume":"56","author":"T.Cui","year":"2010","journal-title":"Networks"},{"key":"ijncr.2014100103-12","doi-asserted-by":"crossref","unstructured":"Day, J. (2002). Management of railroad impedances for shortest path-based routing. Ph.D. thesis.","DOI":"10.1016\/S1571-0661(04)80529-2"},{"key":"ijncr.2014100103-13","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)80529-2"},{"key":"ijncr.2014100103-14","doi-asserted-by":"crossref","unstructured":"Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269-271.","DOI":"10.1007\/BF01386390"},{"key":"ijncr.2014100103-15","doi-asserted-by":"crossref","unstructured":"Fekete, S. P., Hochst{\\\u201da}ttler, W., Kromberg, S., & Moll, C. (1999). The complexity of an inverse shortest path problem. Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, 49, pp. 113-127.","DOI":"10.1090\/dimacs\/049\/06"},{"key":"ijncr.2014100103-16","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"ijncr.2014100103-17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591962"},{"key":"ijncr.2014100103-18","doi-asserted-by":"crossref","DOI":"10.1201\/9781420057140","author":"J. L.Gross","year":"2005","journal-title":"Graph theory and its applications"},{"key":"ijncr.2014100103-19","unstructured":"Hagberg, A., Swart, P., & Chult, S. D. (2008). Exploring network structure, dynamics, and function using NetworkX. Tech. rep., Los Alamos National Laboratory (LANL)."},{"key":"ijncr.2014100103-20","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038914.26975.9b"},{"key":"ijncr.2014100103-21","doi-asserted-by":"publisher","DOI":"10.1287\/opre.51.5.785.16756"},{"key":"ijncr.2014100103-22","unstructured":"Hung, C.-H., & Director-Sokol, J. (2003). On the inverse shortest path length problem."},{"key":"ijncr.2014100103-23","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321993"},{"key":"ijncr.2014100103-24","doi-asserted-by":"publisher","DOI":"10.1023\/A:1027305419461"},{"key":"ijncr.2014100103-25","unstructured":"Luke, S., Panait, L., Skolicki, Z., Bassett, J., Hubley, R., & Chircop, A. (2001). ECJ: a java-based evolutionary computation and genetic programming research system. Dispon{\\i}vel emhttp:\/\/www. cs. umd. edu\/projetc\/plus\/ec\/ecj\/, {\\'u}ltima visita em, 24."},{"key":"ijncr.2014100103-26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01193863"},{"key":"ijncr.2014100103-27","author":"E. F.Moore","year":"1959","journal-title":"The shortest path through a maze"},{"key":"ijncr.2014100103-28","doi-asserted-by":"publisher","DOI":"10.1287\/opre.47.2.291"},{"key":"ijncr.2014100103-29","doi-asserted-by":"crossref","unstructured":"Xu, S., & Zhang, J. (1995). An inverse problem of the weighted shortest path problem. Japan journal of industrial and applied mathematics, 12(1), 47-59.","DOI":"10.1007\/BF03167381"},{"key":"ijncr.2014100103-30","doi-asserted-by":"publisher","DOI":"10.1080\/02331939708844306"},{"key":"ijncr.2014100103-31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01193836"},{"issue":"3","key":"ijncr.2014100103-32","first-page":"347","article-title":"A column generation method for inverse shortest path problems. Zeitschrift f{\\\u201du}r","volume":"41","author":"J.Zhang","year":"1995","journal-title":"Operations Research"},{"key":"ijncr.2014100103-33","doi-asserted-by":"publisher","DOI":"10.1023\/B:COAP.0000013061.17529.79"},{"key":"ijncr.2014100103-34","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00876-7"},{"key":"ijncr.2014100103-35","doi-asserted-by":"crossref","unstructured":"Zhang, J., Yang, X., & Cai, M.-c. (1999). Reverse center location problem. Em Algorithms and Computation (pp. 279-294). Springer.","DOI":"10.1007\/3-540-46632-0_29"}],"container-title":["International Journal of Natural Computing Research"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=119692","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,5]],"date-time":"2024-06-05T10:13:13Z","timestamp":1717582393000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/ijncr.2014100103"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2014,10,1]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,10]]}},"URL":"https:\/\/doi.org\/10.4018\/ijncr.2014100103","relation":{},"ISSN":["1947-928X","1947-9298"],"issn-type":[{"value":"1947-928X","type":"print"},{"value":"1947-9298","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,1]]}}}