{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:12:34Z","timestamp":1760242354932,"version":"build-2065373602"},"reference-count":39,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2017,5,6]],"date-time":"2017-05-06T00:00:00Z","timestamp":1494028800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In transport planning, one should allow passengers to travel through the complicated transportation scheme with efficient use of different modes of transport. In this paper, we propose the use of a cockroach swarm optimization algorithm for determining paths with the shortest travel time. In our approach, this algorithm has been modified to work with the time-expanded model. Therefore, we present how the algorithm has to be adapted to this model, including correctly creating solutions and defining steps and movement in the search space. By introducing the proposed modifications, we are able to solve journey planning. The results have shown that the performance of our approach, in terms of converging to the best solutions, is satisfactory. Moreover, we have compared our results with Dijkstra\u2019s algorithm and a particle swarm optimization algorithm.<\/jats:p>","DOI":"10.3390\/e19050213","type":"journal-article","created":{"date-parts":[[2017,5,8]],"date-time":"2017-05-08T11:45:16Z","timestamp":1494243916000},"page":"213","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Cockroach Swarm Optimization Algorithm for Travel Planning"],"prefix":"10.3390","volume":"19","author":[{"given":"Joanna","family":"Kwiecie\u0144","sequence":"first","affiliation":[{"name":"Faculty of Electrical Engineering, Automatics, Computer Science and Biomedical Engineering, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Krak\u00f3w, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Pasieka","sequence":"additional","affiliation":[{"name":"Swisscom (Schweiz) AG, Waldeggstrasse 51, 3097 Liebefeld, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,5,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/351827.384254","article-title":"Dijkstra\u2019s algorithm on-line: An empirical case study from public railroad transport","volume":"5","author":"Schulz","year":"2000","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/3-540-45643-0_4","article-title":"Using multi-level graphs for timetable information in railway systems","volume":"Volume 2409","author":"Mount","year":"2002","journal-title":"Algorithm Engineering and Experiments"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1227161.1227166","article-title":"Efficient Models for Timetable Information in Public Transportation Systems","volume":"12","author":"Pyrga","year":"2008","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.entcs.2003.12.019","article-title":"Time dependent networks as models to achieve fast exact time-table queries","volume":"92","author":"Brodal","year":"2004","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Xing, B., and Gao, W. (2014). Innovative Computational Intelligence: A Rough Guide to 134 Clever Algorithms, Springer.","DOI":"10.1007\/978-3-319-03404-1"},{"key":"ref_6","unstructured":"Yang, X.-S. (2010). Nature-Inspired Metaheuristic Algorithms, Luniver Press. [2nd ed.]."},{"key":"ref_7","first-page":"4","article-title":"A modified cockroach swarm optimization","volume":"11","author":"Chen","year":"2011","journal-title":"Energy Proced."},{"key":"ref_8","first-page":"30","article-title":"Cockroach swarm optimization for vehicle routing problems","volume":"13","author":"Chen","year":"2011","journal-title":"Energy Procedia"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"226","DOI":"10.4028\/www.scientific.net\/AEF.1.226","article-title":"Cockroach swarm optimization algorithm for TSP","volume":"1","author":"Cheng","year":"2011","journal-title":"Adv. Eng. Forum"},{"key":"ref_10","first-page":"797","article-title":"Comparison of firefly and cockroach algorithms in selected discrete and combinatorial problems","volume":"62","author":"Filipowicz","year":"2014","journal-title":"Bull. Pol. Acad. Sci. Tech. Sci."},{"key":"ref_11","first-page":"484","article-title":"Use of different movement mechanisms in cockroach swarm optimization algorithm for traveling salesman problem","volume":"Volume 9693","author":"Rutkowski","year":"2016","journal-title":"Artificial Intelligence and Soft Computing"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Obagbuwa, I.C., and Abidoye, A.P. (2016). Binary cockroach swarm optimization for combinatorial optimization problem. Algorithms, 9.","DOI":"10.3390\/a9030059"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/978-3-319-49487-6_2","article-title":"Route Planning in Transportation Networks","volume":"Volume 9220","author":"Kliemann","year":"2016","journal-title":"Algorithm Engineering"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/978-3-540-74247-0_3","article-title":"Timetable information: Models and algorithms","volume":"Volume 4359","author":"Geraets","year":"2007","journal-title":"Algorithmic Methods for Railway Optimization"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1643","DOI":"10.1016\/j.asoc.2008.01.002","article-title":"Solving shortest path problem using particle swarm optimization","volume":"8","author":"Mohemmed","year":"2008","journal-title":"Appl. Soft Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1911","DOI":"10.1016\/j.eswa.2009.07.025","article-title":"Find multi-objective paths in stochastic networks via chaotic immune PSO","volume":"37","author":"Zhang","year":"2010","journal-title":"Expert Syst. Appl."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/j.amc.2006.11.171","article-title":"Nonlinear neural networks for solving the shortest path problem","volume":"189","author":"Effati","year":"2007","journal-title":"Appl. Math. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1016\/j.dsp.2011.02.004","article-title":"A novel algorithm for all pairs shortest path problem based on matrix multiplication and pulse coupled neural network","volume":"21","author":"Zhang","year":"2011","journal-title":"Digit. Signal Process."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"5056","DOI":"10.1016\/j.eswa.2015.02.046","article-title":"Multi-objective path finding in stochastic time-dependent road networks using non-dominated sorting genetic algorithm","volume":"42","author":"Babaei","year":"2015","journal-title":"Expert Syst. Appl."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1177\/0037549715623847","article-title":"Multi-objective path finding in stochastic networks using a biogeography-based optimization method","volume":"92","author":"Wang","year":"2016","journal-title":"Simulation"},{"key":"ref_21","unstructured":"Gen, M., Cheng, R., and Wang, D. (1997, January 13\u201316). Genetic algorithms for solving shortest path problems. Proceedings of the 1997 IEEE International Conference on Evolutionary Computing, Indianapolis, IN, USA."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/S0377-2217(01)00354-X","article-title":"Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks","volume":"144","author":"Davies","year":"2003","journal-title":"Eur. J. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0965-8564(99)00056-7","article-title":"Shortest viable path algorithm in multimodal networks","volume":"35","author":"Lozano","year":"2001","journal-title":"Transp. Res. Part A Policy Pract."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1016\/j.sbspro.2014.01.066","article-title":"An A\u2217 label-setting algorithm for multimodal resource constrained shortest path problem","volume":"111","author":"Ma","year":"2014","journal-title":"Procedia Soc. Behav. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1186\/s40467-015-0032-x","article-title":"A bi-objective model for uncertain multi-modal shortest path problems","volume":"3","author":"Zhang","year":"2015","journal-title":"J. Uncertain. Anal. Appl."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1016\/S0191-2615(02)00043-7","article-title":"An extended model and procedural framework for planning multi-modal passenger journeys","volume":"37","author":"Horn","year":"2003","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"2613","DOI":"10.1016\/j.apm.2013.10.059","article-title":"Exact algorithm for multi-criteria multi-modal shortest path with transfer delaying and arriving time-window in urban transit network","volume":"38","author":"Liu","year":"2014","journal-title":"Appl. Math. Model."},{"key":"ref_28","first-page":"193","article-title":"A multi-modal route planning approach with an improved genetic algorithm","volume":"38","author":"Yu","year":"2012","journal-title":"Adv. Geo-Spat. Inform. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"3324","DOI":"10.1016\/j.cor.2005.03.027","article-title":"Heuristic shortest path algorithms for transportation applications: State of the art","volume":"33","author":"Fu","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1016\/j.trpro.2015.09.028","article-title":"Memetic algorithm for computing shortest paths in multimodal transportation networks","volume":"10","author":"Dib","year":"2015","journal-title":"Transp. Res. Procedia"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/978-3-642-38527-8_6","article-title":"Intriguingly simple and fast transit routing","volume":"Volume 7933","author":"Bonifaci","year":"2013","journal-title":"Experimental Algorithms"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1287\/trsc.2014.0534","article-title":"Round-based public transit routing","volume":"49","author":"Delling","year":"2015","journal-title":"Transp. Sci."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/978-3-642-38527-8_24","article-title":"Computing Multimodal Journeys in Practice","volume":"Volume 7933","author":"Bonifaci","year":"2013","journal-title":"Experimental Algorithms"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Bast, H., and Storandt, S. (2014, January 4\u20137). Frequency-based search for public transit. Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Dallas, TX, USA.","DOI":"10.1145\/2666310.2666405"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/978-3-642-05465-5_7","article-title":"Engineering time-expanded graphs for faster timetable information","volume":"Volume 5868","author":"Ahuja","year":"2009","journal-title":"Robust and Online Large-Scale Optimization"},{"key":"ref_37","unstructured":"Geisberger, R. (2011). Advanced Route Planning in Transportation Networks. [Ph.D. Thesis, Karlsruhe Institute of Technology]."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s11721-007-0002-0","article-title":"Particle swarm optimization. An overview","volume":"1","author":"Poli","year":"2007","journal-title":"Swarm Intell."},{"key":"ref_39","first-page":"16","article-title":"Solving routing problem using particle swarm optimization","volume":"52","author":"Toofani","year":"2012","journal-title":"Int. J. Comput. Appl."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/19\/5\/213\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:34:54Z","timestamp":1760207694000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/19\/5\/213"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,6]]},"references-count":39,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2017,5]]}},"alternative-id":["e19050213"],"URL":"https:\/\/doi.org\/10.3390\/e19050213","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2017,5,6]]}}}