{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T23:25:51Z","timestamp":1672615551355},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T00:00:00Z","timestamp":1575331200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T00:00:00Z","timestamp":1575331200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Geoinformatica"],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s10707-019-00385-8","type":"journal-article","created":{"date-parts":[[2019,12,6]],"date-time":"2019-12-06T12:08:57Z","timestamp":1575634137000},"page":"513-531","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Constrained shortest path problems in bi-colored graphs: a label-setting approach"],"prefix":"10.1007","volume":"25","author":[{"given":"Amin","family":"AliAbdi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ali","family":"Mohades","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mansoor","family":"Davoodi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,3]]},"reference":[{"key":"385_CR1","doi-asserted-by":"crossref","unstructured":"LaValle SM (2006) Planning algorithms. Cambridge University Press, Cambridge","DOI":"10.1017\/CBO9780511546877"},{"key":"385_CR2","doi-asserted-by":"crossref","unstructured":"Turner L, Hamacher HW (2011) On Universal Shortest Paths. Springer Berlin Heidelberg, pp 313\u2013318","DOI":"10.1007\/978-3-642-20009-0_50"},{"key":"385_CR3","doi-asserted-by":"publisher","unstructured":"Gourv\u00e8s L, Lyra A, Martinhon C, Monnot J, Protti F (2009) On s-t paths and trails in edge-colored graphs. Electronic Notes in Discrete Mathematics 35:221\u2013226. https:\/\/doi.org\/10.1016\/j.endm.2009.11.037","DOI":"10.1016\/j.endm.2009.11.037"},{"key":"385_CR4","unstructured":"Garey MR, Johnson DS (1979) Computers and intracability: A guide to the theory of NP-completeness. W.H. Freeman, New York, NY, USA"},{"key":"385_CR5","unstructured":"Silva R, Craveirinha J (2004) An Overview of routing models for MPLS Networks. In: 1st Workshop Multicriteria Modelling in Telecommunication Network Planning and Design. Faculty of Economics of the University of Coimbra, Coimbra, Portugal, pp 17\u201324"},{"key":"385_CR6","doi-asserted-by":"crossref","unstructured":"Festa P (2015) Constrained shortest path problems: state-of-the-art and recent advances. In: 2015 17th International Conference on Transparent Optical Networks (ICTON). IEEE, pp 1\u201317","DOI":"10.1109\/ICTON.2015.7193456"},{"key":"385_CR7","doi-asserted-by":"publisher","unstructured":"Davoodi M (2017) Bi-objective path planning using deterministic algorithms. Robotics and Autonomous Systems 93:105\u2013115. https:\/\/doi.org\/10.1016\/j.robot.2017.03.021","DOI":"10.1016\/j.robot.2017.03.021"},{"key":"385_CR8","doi-asserted-by":"publisher","unstructured":"Davoodi M, Panahi F, Mohades A, Hashemi SN (2013) Multi-objective path planning in discrete space. Applied Soft Computing 13:709\u2013720. https:\/\/doi.org\/10.1016\/J.ASOC.2012.07.023","DOI":"10.1016\/J.ASOC.2012.07.023"},{"key":"385_CR9","doi-asserted-by":"publisher","unstructured":"Jaffe JM (1984) Algorithms for finding paths with multiple constraints. Networks 14:95\u2013116. https:\/\/doi.org\/10.1002\/net.3230140109","DOI":"10.1002\/net.3230140109"},{"key":"385_CR10","doi-asserted-by":"publisher","unstructured":"Lorenz DH, Raz D (2001) A simple efficient approximation scheme for the restricted shortest path problem. Operations Research Letters 28:213\u2013219. https:\/\/doi.org\/10.1016\/S0167-6377(01)00069-4","DOI":"10.1016\/S0167-6377(01)00069-4"},{"key":"385_CR11","doi-asserted-by":"publisher","unstructured":"Hassin R (1992) Approximation Schemes for the Restricted Shortest Path Problem. Math Oper Res 17:36\u201342. https:\/\/doi.org\/10.1287\/moor.17.1.36","DOI":"10.1287\/moor.17.1.36"},{"key":"385_CR12","doi-asserted-by":"publisher","unstructured":"Dumitrescu I, Boland N (2001) Algorithms for the Weight Constrained Shortest Path Problem. International Transactions in Operational Research 8:15\u201329. https:\/\/doi.org\/10.1111\/1475-3995.00003","DOI":"10.1111\/1475-3995.00003"},{"key":"385_CR13","doi-asserted-by":"publisher","unstructured":"Dumitrescu I, Boland N (2003) Improved Preprocessing, Labeling and Scaling Algorithms for the Weight-Constrained Shortest Path Problem. Networks 42:135\u2013153. https:\/\/doi.org\/10.1002\/net.10090","DOI":"10.1002\/net.10090"},{"key":"385_CR14","doi-asserted-by":"publisher","unstructured":"Chen S, Song M, Sahni S (2008) Two techniques for fast computation of constrained shortest paths. IEEE\/ACM Transactions on Networking 16:105\u2013115. https:\/\/doi.org\/10.1109\/TNET.2007.897965","DOI":"10.1109\/TNET.2007.897965"},{"key":"385_CR15","doi-asserted-by":"publisher","unstructured":"Santos L, Coutinho-Rodrigues J, Current JR (2007) An improved solution algorithm for the constrained shortest path problem. Transportation Research Part B: Methodological 41:756\u2013771. https:\/\/doi.org\/10.1016\/j.trb.2006.12.001","DOI":"10.1016\/j.trb.2006.12.001"},{"key":"385_CR16","doi-asserted-by":"publisher","unstructured":"Ergun F, Sinha R, Zhang L (2002) An improved FPTAS for Restricted Shortest Path. Information Processing Letters 83:287\u2013291. https:\/\/doi.org\/10.1016\/S0020-0190(02)00205-3","DOI":"10.1016\/S0020-0190(02)00205-3"},{"key":"385_CR17","doi-asserted-by":"publisher","unstructured":"Chen G, Xue G (2003) A PTAS for weight constrained Steiner trees in series\u2013parallel graphs. Theoretical Computer Science 304:237\u2013247. https:\/\/doi.org\/10.1016\/S0304-3975(03)00088-4","DOI":"10.1016\/S0304-3975(03)00088-4"},{"key":"385_CR18","doi-asserted-by":"crossref","unstructured":"Xin Yuan, Xingming Liu (2001) Heuristic algorithms for multi-constrained quality of service routing. In: Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213). IEEE, pp 844\u2013853","DOI":"10.1109\/INFCOM.2001.916275"},{"key":"385_CR19","doi-asserted-by":"publisher","unstructured":"Zheng Wang, Crowcroft J (1996) Quality-of-service routing for supporting multimedia applications. IEEE Journal on Selected Areas in Communications 14:1228\u20131234. https:\/\/doi.org\/10.1109\/49.536364","DOI":"10.1109\/49.536364"},{"key":"385_CR20","doi-asserted-by":"publisher","unstructured":"Tarapata Z (2007) Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms. International Journal of Applied Mathematics and Computer Science 17:269\u2013287. https:\/\/doi.org\/10.2478\/v10006-007-0023-2","DOI":"10.2478\/v10006-007-0023-2"},{"key":"385_CR21","doi-asserted-by":"publisher","unstructured":"Yen JY (1971) Finding the K shortest loopless paths in a network. Management Science 17:712\u2013716. https:\/\/doi.org\/10.1287\/mnsc.17.11.712","DOI":"10.1287\/mnsc.17.11.712"},{"key":"385_CR22","doi-asserted-by":"publisher","unstructured":"Eppstein D (1998) Finding the k Shortest Paths. SIAM Journal on Computing 28:652\u2013673. https:\/\/doi.org\/10.1137\/S0097539795290477","DOI":"10.1137\/S0097539795290477"},{"key":"385_CR23","doi-asserted-by":"crossref","unstructured":"Akiba T, Hayashi T, Nori N, Iwata Y, Yoshida Y (2015) Efficient Top-k Shortest-path Distance Queries on Large Networks by Pruned Landmark Labeling. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. AAAI Press, pp 2\u20138","DOI":"10.1609\/aaai.v29i1.9154"},{"key":"385_CR24","unstructured":"Burstein D, Metcalf L (2016) The K Shortest Paths Problem with Application to Routing. 1\u201337"},{"key":"385_CR25","unstructured":"Zhang S, Liu X (2013) A new algorithm for finding the k shortest transport paths in dynamic stochastic networks. Journal of Vibroengineering 15:726\u2013735"},{"key":"385_CR26","doi-asserted-by":"crossref","unstructured":"Scano G, Huguet MJ, Ngueveu SU (2016) Adaptations of k-shortest path algorithms for transportation networks. In: Proceedings of 2015 International Conference on Industrial Engineering and Systems Management, IEEE IESM 2015. pp 663\u2013669","DOI":"10.1109\/IESM.2015.7380229"},{"key":"385_CR27","doi-asserted-by":"publisher","unstructured":"Guo J, Jia L (2017) A new algorithm for finding the K shortest paths in a time-schedule network with constraints on arcs. Journal of Algorithms and Computational Technology 11:170\u2013177. https:\/\/doi.org\/10.1177\/1748301816680470","DOI":"10.1177\/1748301816680470"},{"key":"385_CR28","unstructured":"Chondrogiannis T, Bouros P, Gamper J, Leser U (2017) Exact and Approximate Algorithms for Finding k-Shortest Paths with Limited Overlap. In: 20th International Conference on Extending Database Technology\u202f: EDBT 2017. pp 414\u2013425"},{"key":"385_CR29","doi-asserted-by":"publisher","unstructured":"Wang S, Yang Y, Hu X, Li J, Xu B (2016) Solving the K -shortest paths problem in timetable-based public transportation systems. Journal of Intelligent Transportation Systems 20:413\u2013427. https:\/\/doi.org\/10.1080\/15472450.2015.1082911","DOI":"10.1080\/15472450.2015.1082911"},{"key":"385_CR30","doi-asserted-by":"crossref","unstructured":"Eppstein D (1994) Finding the k shortest paths. In: 35th Annual Symposium on Foundations of Computer Science. IEEE, pp 154\u2013165","DOI":"10.1109\/SFCS.1994.365697"},{"key":"385_CR31","doi-asserted-by":"crossref","unstructured":"Eppstein D, Gupta S (2017) Crossing Patterns in Nonplanar Road Networks. In: Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems - SIGSPATIAL\u201917. ACM Press, New York, New York, USA, pp 1\u20139","DOI":"10.1145\/3139958.3139999"},{"key":"385_CR32","doi-asserted-by":"publisher","unstructured":"Masucci AP, Smith D, Crooks A, Batty M (2009) Random planar graphs and the London street network. The European Physical Journal B 71:259\u2013271. https:\/\/doi.org\/10.1140\/epjb\/e2009-00290-4","DOI":"10.1140\/epjb\/e2009-00290-4"},{"key":"385_CR33","unstructured":"Schultes D (2008) Route Planning in Road Networks. VDM Verlag"},{"key":"385_CR34","doi-asserted-by":"publisher","unstructured":"Zhang Y, Liu J, Qian X, Qiu A, Zhang F (2017) An Automatic Road Network Construction Method Using Massive GPS Trajectory Data. ISPRS International Journal of Geo-Information 6:400. https:\/\/doi.org\/10.3390\/ijgi6120400","DOI":"10.3390\/ijgi6120400"},{"key":"385_CR35","doi-asserted-by":"publisher","unstructured":"Wang X, You S, Wang L (2017) Classifying road network patterns using multinomial logit model. Journal of Transport Geography 58:104\u2013112. https:\/\/doi.org\/10.1016\/j.jtrangeo.2016.11.013","DOI":"10.1016\/j.jtrangeo.2016.11.013"},{"key":"385_CR36","unstructured":"Gupta S (2018) Topological Algorithms for Geographic and Geometric Graphs. University Of California, Irvine Topological"},{"key":"385_CR37","doi-asserted-by":"publisher","unstructured":"Yang B, Guo C, Ma Y, Jensen CS (2015) Toward personalized, context-aware routing. The VLDB Journal 24:297\u2013318. https:\/\/doi.org\/10.1007\/s00778-015-0378-1","DOI":"10.1007\/s00778-015-0378-1"},{"key":"385_CR38","doi-asserted-by":"crossref","unstructured":"Ceikute V, Jensen CS (2013) Routing Service Quality -- Local Driver Behavior Versus Routing Services. In: 2013 IEEE 14th International Conference on Mobile Data Management. IEEE, pp 97\u2013106","DOI":"10.1109\/MDM.2013.20"},{"key":"385_CR39","doi-asserted-by":"crossref","unstructured":"Funke S, Storandt S (2015) Personalized route planning in road networks. In: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems - GIS \u201915. ACM Press, New York, New York, USA, pp 1\u201310","DOI":"10.1145\/2820783.2820830"},{"key":"385_CR40","doi-asserted-by":"crossref","unstructured":"Delling D, Wagner D (2009) Time-dependent route planning. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer, Berlin, Heidelberg, pp 207\u2013230","DOI":"10.1007\/978-3-642-05465-5_8"},{"key":"385_CR41","doi-asserted-by":"crossref","unstructured":"ter Mors AW, Witteveen C, Zutt J, Kuipers FA (2010) Context-Aware Route Planning. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer, Berlin, Heidelberg, pp 138\u2013149","DOI":"10.1007\/978-3-642-16178-0_14"},{"key":"385_CR42","doi-asserted-by":"publisher","unstructured":"Li PH, Yiu ML, Mouratidis K (2017) Discovering historic traffic-tolerant paths in road networks. GeoInformatica 21:1\u201332. https:\/\/doi.org\/10.1007\/s10707-016-0265-y","DOI":"10.1007\/s10707-016-0265-y"},{"key":"385_CR43","doi-asserted-by":"crossref","unstructured":"Geisberger R, Sanders P, Schultes D, Delling D (2008) Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Berlin Heidelberg, Berlin, Heidelberg, pp 319\u2013333","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"385_CR44","doi-asserted-by":"crossref","unstructured":"Bast H, Delling D, Goldberg A, M\u00fcller-Hannemann M, Pajor T, Sanders P, Wagner D, Werneck RF (2016) Route Planning in Transportation Networks. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). pp 19\u201380","DOI":"10.1007\/978-3-319-49487-6_2"},{"key":"385_CR45","doi-asserted-by":"crossref","unstructured":"Ahmadi MH, Haghighatdoost V (2017) General Time-Dependent Sequenced Route Queries in Road Networks. In: 2017 IEEE 15th Intl Conf on Dependable, Autonomic and Secure Computing, 15th Intl Conf on Pervasive Intelligence and Computing, 3rd Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress(DASC\/PiCom\/DataCom\/CyberSciTech). IEEE, New York, New York, USA, pp 949\u2013956","DOI":"10.1109\/DASC-PICom-DataCom-CyberSciTec.2017.158"},{"key":"385_CR46","doi-asserted-by":"crossref","unstructured":"Dibbelt J, Strasser B, Wagner D (2015) Fast exact shortest path and distance queries on road networks with parametrized costs. In: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems - GIS \u201915. ACM Press, New York, New York, USA, pp 1\u20134","DOI":"10.1145\/2820783.2820856"},{"key":"385_CR47","doi-asserted-by":"publisher","unstructured":"Delling D, Goldberg A V, Pajor T, Werneck RF (2017) Customizable Route Planning in Road Networks. Transportation Science 51:566\u2013591. https:\/\/doi.org\/10.1287\/trsc.2014.0579","DOI":"10.1287\/trsc.2014.0579"},{"key":"385_CR48","doi-asserted-by":"publisher","unstructured":"Yu J, Zhang Z, Sarwat M (2018) Spatial data management in apache spark: the GeoSpark perspective and beyond. GeoInformatica. https:\/\/doi.org\/10.1007\/s10707-018-0330-9","DOI":"10.1007\/s10707-018-0330-9"},{"key":"385_CR49","doi-asserted-by":"crossref","unstructured":"Eldawy A (2016) SpatialHadoop: A MapReduce Framework for Big Spatial Data","DOI":"10.1109\/ICDE.2015.7113382"}],"container-title":["GeoInformatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-019-00385-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10707-019-00385-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-019-00385-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,7]],"date-time":"2022-10-07T21:29:26Z","timestamp":1665178166000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10707-019-00385-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,3]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["385"],"URL":"https:\/\/doi.org\/10.1007\/s10707-019-00385-8","relation":{},"ISSN":["1384-6175","1573-7624"],"issn-type":[{"value":"1384-6175","type":"print"},{"value":"1573-7624","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,3]]},"assertion":[{"value":"30 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 June 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}