{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T23:32:29Z","timestamp":1725319949395},"reference-count":47,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2018,5,4]],"date-time":"2018-05-04T00:00:00Z","timestamp":1525392000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["41571379","41471319","41430635"],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"The process of searching for a dynamic constrained optimal path has received increasing attention in traffic planning, evacuation, and personalized or collaborative traffic service. As most existing multiple constrained optimal path (MCOP) methods cannot search for a path given various types of constraints that dynamically change during the search, few approaches for dynamic multiple constrained optimal path (DMCOP) with type II dynamics are available for practical use. In this study, we develop a method to solve the DMCOP problem with type II dynamics based on the unification of various types of constraints under a geometric algebra (GA) framework. In our method, the network topology and three different types of constraints are represented by using algebraic base coding. With a parameterized optimization of the MCOP algorithm based on a greedy search strategy under the generation-refinement paradigm, this algorithm is found to accurately support the discovery of optimal paths as the constraints of numerical values, nodes, and route structure types are dynamically added to the network. The algorithm was tested with simulated cases of optimal tourism route searches in China\u2019s road networks with various combinations of constraints. The case study indicates that our algorithm can not only solve the DMCOP with different types of constraints but also use constraints to speed up the route filtering.<\/jats:p>","DOI":"10.3390\/ijgi7050172","type":"journal-article","created":{"date-parts":[[2018,5,7]],"date-time":"2018-05-07T07:12:21Z","timestamp":1525677141000},"page":"172","source":"Crossref","is-referenced-by-count":7,"title":["Optimal Route Searching with Multiple Dynamical Constraints\u2014A Geometric Algebra Approach"],"prefix":"10.3390","volume":"7","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-0060-7852","authenticated-orcid":false,"given":"Dongshuang","family":"Li","sequence":"first","affiliation":[{"name":"Key Laboratory of Virtual Geographic Environment, Ministry of Education, Nanjing Normal University, Nanjing 210046, China"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-4225-9435","authenticated-orcid":false,"given":"Zhaoyuan","family":"Yu","sequence":"additional","affiliation":[{"name":"Key Laboratory of Virtual Geographic Environment, Ministry of Education, Nanjing Normal University, Nanjing 210046, China"},{"name":"State Key Laboratory Cultivation Base of Geographical Environment Evolution, Nanjing 210023, China"},{"name":"Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing 210023, China"}]},{"given":"Wen","family":"Luo","sequence":"additional","affiliation":[{"name":"Key Laboratory of Virtual Geographic Environment, Ministry of Education, Nanjing Normal University, Nanjing 210046, China"},{"name":"State Key Laboratory Cultivation Base of Geographical Environment Evolution, Nanjing 210023, China"}]},{"given":"Yong","family":"Hu","sequence":"additional","affiliation":[{"name":"Key Laboratory of Virtual Geographic Environment, Ministry of Education, Nanjing Normal University, Nanjing 210046, China"},{"name":"Institute of Computer Science and Technology, Nanjing Normal University, Nanjing 210023, China"}]},{"given":"Xiaoyu","family":"Che","sequence":"additional","affiliation":[{"name":"Key Laboratory of Virtual Geographic Environment, Ministry of Education, Nanjing Normal University, Nanjing 210046, China"}]},{"given":"Linwang","family":"Yuan","sequence":"additional","affiliation":[{"name":"Key Laboratory of Virtual Geographic Environment, Ministry of Education, Nanjing Normal University, Nanjing 210046, China"},{"name":"State Key Laboratory Cultivation Base of Geographical Environment Evolution, Nanjing 210023, China"},{"name":"Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing 210023, China"}]}],"member":"1968","published-online":{"date-parts":[[2018,5,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.trc.2014.01.003","article-title":"A dynamic evacuation model for pedestrian\u2013vehicle mixed-flow networks","volume":"40","author":"Zhang","year":"2014","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.proenv.2014.11.006","article-title":"Development of Planning Support System for Welfare Urban Design\u2014Optimal Route Finding for Wheelchair Users \u2606","volume":"22","author":"Inada","year":"2014","journal-title":"Procedia Environ. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/j.jtrangeo.2010.09.009","article-title":"A GIS-based toolkit for route choice analysis","volume":"19","author":"Papinski","year":"2011","journal-title":"J. Transp. Geogr."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1885","DOI":"10.1080\/13658816.2011.556119","article-title":"Constructing personalized transportation networks in multi-state supernetworks: A heuristic approach","volume":"25","author":"Liao","year":"2011","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1080\/03081060500053509","article-title":"Solving the Median Shortest Path Problem in the Planning and Design of Urban Transportation Networks Using a Vector Labeling Algorithm","volume":"28","author":"Nepal","year":"2005","journal-title":"Transp. Plan. Technol."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1126\/science.1137521","article-title":"Fast Routing in Road Networks with Transit Nodes","volume":"316","author":"Bast","year":"2007","journal-title":"Science"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1559\/152304007781002163","article-title":"Network Analysis in Geographic Information Science: Review, Assessment, and Projections","volume":"34","author":"Curtin","year":"2007","journal-title":"Cartogr. Geogr. Inf. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1016\/j.trb.2004.07.004","article-title":"Path enumeration by finding the constrained K-shortest paths","volume":"39","author":"Catalano","year":"2005","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1043","DOI":"10.1016\/j.trb.2012.03.005","article-title":"Parametric search and problem decomposition for approximating Pareto-optimal paths","volume":"46","author":"Xie","year":"2012","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1080\/13658810600607766","article-title":"An evolutionary algorithm for multicriteria path optimization problems","volume":"20","author":"Mooney","year":"2006","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1080\/13658810801949850","article-title":"Finding shortest paths on real road networks: The case for A*","volume":"23","author":"Zeng","year":"2009","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_12","first-page":"572","article-title":"Dynamic Activity-Travel Assignment in Multi-State Supernetworks\u2606","volume":"12","author":"Liu","year":"2015","journal-title":"Transportmetrica"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1002\/net.20247","article-title":"Lagrangian relaxation and enumeration for solving constrained shortest-path problems","volume":"52","author":"Carlyle","year":"2010","journal-title":"Networks"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/j.trb.2016.01.002","article-title":"Boundedly rational route choice behavior: A review of models and methodologies","volume":"85","author":"Di","year":"2016","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1016\/j.tourman.2011.01.006","article-title":"Web-based GIS in tourism information search: Perceptions, tasks, and trip attributes","volume":"32","author":"Chang","year":"2011","journal-title":"Tour. Manag."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.jtrangeo.2012.01.006","article-title":"Solving a location-routing problem with a multiobjective approach: The design of urban evacuation plans","volume":"22","year":"2012","journal-title":"J. Transp. Geogr."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1080\/13658816.2011.598133","article-title":"Reliable shortest path finding in stochastic networks with spatial correlated link travel times","volume":"26","author":"Chen","year":"2012","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.orl.2012.06.001","article-title":"Route planning with turn restrictions: A computational experiment","volume":"40","author":"Vanhove","year":"2012","journal-title":"Oper. Res. Lett."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1016\/j.jtrangeo.2014.01.009","article-title":"What about people in cycle network planning? Applying participative multicriteria GIS analysis in the case of the Athens metropolitan cycle network \u2606","volume":"35","author":"Milakis","year":"2014","journal-title":"J. Transp. Geogr."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1745","DOI":"10.1080\/13658810903514180","article-title":"Have a nice trip: An algorithm for identifying excess routes under satisfaction constraints","volume":"24","author":"Zachariasen","year":"2010","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_21","first-page":"25","article-title":"An Algorithm for Dynamic Optimal Path Selection with Constraint","volume":"5","author":"Qi","year":"2008","journal-title":"J. Comput. Inf. Syst."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Schott, R., and Staples, G.S. (2012). Operator Calculus on Graphs: Theory and Applications in Computer Science, World Scientific.","DOI":"10.1142\/9781848168770"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1428","DOI":"10.1002\/mma.2904","article-title":"Clifford algebra method for network expression, computation, and algorithm construction","volume":"37","author":"Yuan","year":"2014","journal-title":"Math. Methods Appl. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Yu, Z., Li, D., Zhu, S., Luo, W., Hu, Y., and Yuan, L. (2017). Multisource multisink optimal evacuation routing with dynamic network changes: A geometric algebra approach. Math. Methods Appl. Sci.","DOI":"10.1002\/mma.4465"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/j.compenvurbsys.2016.07.003","article-title":"A dynamic evacuation simulation framework based on geometric algebra","volume":"59","author":"Yu","year":"2016","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/j.trb.2013.05.008","article-title":"Bicriterion shortest path problem with a general nonadditive cost \u2606","volume":"57","author":"Chen","year":"2013","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Pouly, M., and Kohlas, J. (2011). Generic Inference: A Unifying Theory for Automated Reasoning, Wiley Publishing.","DOI":"10.1002\/9781118010877"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1007\/s00006-010-0228-6","article-title":"Dynamic Geometric Graph Processes: Adjacency Operator Approach","volume":"20","author":"Schott","year":"2010","journal-title":"Adv. Appl. Clifford Algebras"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1007\/s00006-008-0116-5","article-title":"A new adjacency matrix for finite graphs","volume":"18","author":"Staples","year":"2008","journal-title":"Adv. Appl. Clifford Algebras"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1111\/j.1467-9671.2010.01221.x","article-title":"CAUSTA: Clifford algebra-based unified spatio-temporal analysis","volume":"14","author":"Yuan","year":"2010","journal-title":"Trans. GIS"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"3081","DOI":"10.1016\/j.comnet.2010.05.017","article-title":"A survey on multi-constrained optimal path computation: Exact and approximate algorithms","volume":"54","author":"Garroppo","year":"2010","journal-title":"Comput. Netw."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1016\/j.asoc.2011.08.015","article-title":"An oriented spanning tree based genetic algorithm for multi-criteria shortest path problems","volume":"12","author":"Liu","year":"2012","journal-title":"Appl. Soft Comput. J."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Yu, Z., Yuan, L., Luo, W., Feng, L., and Lv, G. (2016). Spatio-Temporal Constrained Human Trajectory Generation from the PIR Motion Detector Sensor Network Data: A Geometric Algebra Approach. Sensors, 16.","DOI":"10.3390\/s16010043"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1016\/j.trb.2007.04.008","article-title":"The traffic equilibrium problem with nonadditive costs and its monotone mixed complementarity problem formulation","volume":"41","author":"Agdeppa","year":"2007","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"155205","DOI":"10.1088\/1751-8113\/41\/15\/155205","article-title":"Nilpotent adjacency matrices, random graphs and quantum random variables","volume":"41","author":"Schott","year":"2008","journal-title":"J. Phys. A Math. Theor."},{"key":"ref_36","unstructured":"Slimane, J.B., Ren\u00e9, S., Song, Y., Staples, G.S., and Tsiontsiou, E. (2015). Operator Calculus Algorithms for Multi-Constrained Paths, Southern Illinois University."},{"key":"ref_37","first-page":"321","article-title":"Semiring Frameworks and Algorithms for Shortest-Distance Problems","volume":"7","author":"Mohri","year":"2013","journal-title":"J. Autom. Lang. Comb."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1080\/03081060500247739","article-title":"Cycle Network Planning: Towards a Holistic Approach Using Temporal Topology","volume":"28","author":"Nash","year":"2005","journal-title":"Transp. Plan. Technol."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Lozano, L., and Medaglia, A.L. (2013). On an Exact Method for the Constrained Shortest Path Problem, Elsevier Science Ltd.","DOI":"10.1016\/j.cor.2012.07.008"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1111\/tgis.12057","article-title":"A Pattern-Based Approach for Matching Nodes in Heterogeneous Urban Road Networks","volume":"18","author":"Yang","year":"2015","journal-title":"Trans. GIS"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"3059","DOI":"10.1111\/tgis.12133","article-title":"A Hybrid Link-Node Approach for Finding Shortest Paths in Road Networks with Turn Restrictions","volume":"19","author":"Li","year":"2015","journal-title":"Trans. GIS"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1016\/j.trb.2015.08.002","article-title":"Transportation network design for maximizing space\u2013time accessibility","volume":"81","author":"Tong","year":"2015","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.trb.2015.10.008","article-title":"Modeling and optimization of multimodal urban networks with limited parking and dynamic pricing","volume":"83","author":"Zheng","year":"2016","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/j.trb.2015.06.014","article-title":"Da Efficient transit network design and frequencies setting multi-objective optimization by alternating objective genetic algorithm","volume":"81","author":"Arbex","year":"2015","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1063\/1.4756054","article-title":"Foundations of Geometric Algebra Computing","volume":"1479","author":"Hildenbrand","year":"2012","journal-title":"AIP Conf. Proc."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.trb.2017.09.011","article-title":"A decomposition approach to the static traffic assignment problem","volume":"105","author":"Jafari","year":"2017","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Sanders, P., and Schultes, D. (2005). Highway Hierarchies Hasten Exact Shortest Path Queries, Springer.","DOI":"10.1007\/11561071_51"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/7\/5\/172\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T19:45:14Z","timestamp":1718048714000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/7\/5\/172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,4]]},"references-count":47,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2018,5]]}},"alternative-id":["ijgi7050172"],"URL":"https:\/\/doi.org\/10.3390\/ijgi7050172","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,4]]}}}