Cited By
View all- Lin FHsieh H(2022)Multicriteria Route Planning for In-Operation Mass Transit under Urban DataApplied Sciences10.3390/app1206312712:6(3127)Online publication date: 18-Mar-2022
Conntrans: A Two-Stage Concentric Annealing Approach for Multi-Criteria Distributed Competitive Stationary Resource Searching
Pages 163 - 174
Abstract
Transportation between satellite cities or inside the city center has always been a crucial factor in contributing to a better quality of life. This paper focuses on a multi-criteria distributed competitive route planning for parking slot cruising in regions where neither real-time nor historical availability of parking slots is accessible. An inference-than-planning framework is proposed for solving the parking slot searching using a zero-information distributed model with an availability inference for parking slots in areas with no sensor coverage. Meanwhile, a proposed Conntrans algorithm is suggested as a two-stage structure with three relaxing policies: adjacent cruising, on-orbital annealing, and orbital transitioning. The evaluation is conducted based on the simulation in a publicly accessible real-world parking data from SFPark in San Francisco; the area is divided into 3 separated regions with different urban characteristics. Overall results show that the proposed availability inference model can retrieve decent performance. Furthermore, Conntrans is able to outperform baselines and state-of-the-arts in overall score by at most 77% with a success rate at around 97% and maintains the quality of solutions under various circumstances.
References
[1]
Mohamed Abdallah, Mohamad Adghim, Munjed Maraqa, and Elkhalifa Aldahab. 2019. Simulation and optimization of dynamic waste collection routes. Waste Management & Research: The Journal for a Sustainable Circular Economy.
[2]
Md Golam Rabiul Alam, Mohammad Mehedi Hassan, Md Zia Uddin, Ahmad Almogren, and Giancarlo Fortino. 2019. Autonomic computation offloading in mobile edge for IoT applications. Future Generation Computer Systems 90: 149--157.
[3]
Dou An, Qingyu Yang, Donghe Li, Wei Yu, Wei Zhao, and Chao-Bo Yan. 2020. Where Am I Parking: Incentive Online Parking-Space Sharing Mechanism With Privacy Protection. IEEE Transactions on Automation Science and Engineering.
[4]
Daniel Ayala, Ouri Wolfson, Bhaskar Dasgupta, Jie Lin, and Bo Xu. 2018. Spatio-Temporal Matching for Urban Transportation Applications. ACM Transactions on Spatial Algorithms and Systems 3(4): 1--39.
[5]
Daniel Ayala, Ouri Wolfson, Bo Xu, Bhaskar Dasgupta, and Jie Lin. 2011. Parking slot assignment games. In ACM SIGSPATIAL.
[6]
Daniel Ayala, Ouri Wolfson, Bo Xu, Bhaskar DasGupta, and Jie Lin. 2012. Pricing of parking for congestion reduction. In ACM SIGSPATIAL 43--51.
[7]
Daniel Ayala, Ouri Wolfson, Bo Xu, Bhaskar DasGupta, and Jie Lin. 2012. Parking in Competitive Settings: A Gravitational Approach. In IEEE MDM
[8]
Claudio Badii, Paolo Nesi, and Irene Paoli. 2018. Predicting Available Parking Slots on Critical and Regular Services by Exploiting a Range of Open Data. IEEE Access.
[9]
Hannah Bast. 2009. Car or public transport - two worlds. Efficient Algorithms 5760: 355--367.
[10]
Hannah Bast, Erik Carlsson, Arno Eigenwillig, Robert Geisberger, Chris Harrelson, Veselin Raychev, and Fabien Viger. 2010. Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns. In Proceedings of the 18th Annual European Symposium on Algorithms 290--301.
[11]
Hannah Bast, Stefan Funke, Domagoj Matijević, Camil Demetrescu, Andrew Goldberg, and David Johnson. 2006. TRANSIT: Ultrafast Shortest-Path Queries with Linear-Time Preprocessing. In 9th DIMACS Implementation Challenge --- Shortest Path, DIMACS.
[12]
Mohamed Baza, Mohamed Mahmoud, Gautam Srivastava, Waleed Alasmary, and Mohamed Younis. 2020. A light blockchain-powered privacy-preserving organization scheme for ride sharing services. In IEEE Vehicular Technology Conference (VTC).
[13]
Asma Belhadi, Youcef Djenouri, Gautam Srivastava, Djamel Djenouri, Alberto Cano, and Jerry Chun-Wei Lin. 2020. A Two-Phase Anomaly Detection Model for Secure Intelligent Transportation Ride-Hailing Trajectories. IEEE Transactions on Intelligent Transportation Systems (ITS).
[14]
Philip Blythe, Yanjie Ji, Amy Guo, Wei Wang, and Dounan Tang. 2014. Short-term forecasting of available parking space using wavelet neural network model. IET Intelligent Transport Systems. 9(2): 202--209.
[15]
Fabian Bock and Sergio Di Martino. 2018. On-street parking data in San Francisco - SFpark sensor data and simulated crowd-sensing data. Harvard Dataverse.
[16]
Felix Borutta, Sebastian Schmoll, and Sabrina Friedl. 2019. Optimizing the Spatio-Temporal Resource Search Problem with Reinforcement Learning. In ACM SIGSPATIAL 628--631.
[17]
Valentin Buchhold, Peter Sanders, and Dorothea Wagner. 2019. Real-time Traffic Assignment Using Engineered Customizable Contraction Hierarchies. Journal of Experimental Algorithmics 24: 1--28.
[18]
Kevin Buchin, Irina Kostitsyna, Bram Custers, and Martijn Struijs. 2019. A Sampling-based Strategy for Distributing Taxis in a Road Network for Occupancy Maximization. In ACM SIGSPATIAL 616--619.
[19]
Tianqi Chen and Carlos Guestrin. 2016. XGBoost: A Scalable Tree Boosting System. In ACM SIGKDD 785--794.
[20]
Jingwei Chen, Robert C. Holte, Sandra Zilles, and Nathan R. Sturtevant. 2017. Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions. In IJCAI 489--495.
[21]
Shuo-Yan Chou, Shih-Wei Lin, and Chien-Chang Li. 2008. Dynamic parking negotiation and guidance using an agent-based platform. Expert Systems with Applications 35(3): 805--817.
[22]
Thomas M. Cover and Joy A. Thomas. 1991. Entropy, relative entropy and mutual information. Elements of Information Theory, ch. 2, sec. 1, pp. 12--13.
[23]
Bhaskar DasGupta, João P. Hespanha, James Riehl, and Eduardo Sontag. 2006. Honey-pot constrained searching with local sensory information. Nonlinear Analysis: Theory, Methods & Applications 65(9): 1773--1793.
[24]
Daniel Delling, Julian Dibbelt, and Thomas Pajor. 2019. Fast and Exact Public Transit Routing with Restricted Pareto Sets. In SIAM ALENEX 54--65.
[25]
Daniel Delling, Thomas Pajor, and Renato F. Werneck. 2015. Round-Based Public Transit Routing. Transportation Science 49(3): 591--604.
[26]
Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner. 2009. Engineering route planning algorithms. Algorithmics of Large and Complex Networks 5515: 117--139.
[27]
Mauro Dell'Orco and Dušan Teodorović. 2007. Multi Agent Systems Approach to Parking Facilities Management. Applied Research in Uncertainty Modeling and Analysis, pp. 321--339.
[28]
Alexandros Efentakis, Dieter Pfoser, and Agnès Voisard. 2011. Efficient data management in support of shortest-path computation. In ACM SIGSPATIAL 28--33.
[29]
Matthias Ehrgott and Kathrin Klamroth. 1997. Connectedness of efficient solutions in multiple criteria combinatorial optimization. European Journal of Operational Research 97(1): 159--166.
[30]
Jie-Yue Fang, Fandel Lin, and Hsun-Ping Hsieh. 2020. A Multi-criteria System for Recommending Taxi Routes with an Advance Reservation. In ECML-PKDD 308-322, Ghent, Belgium.
[31]
Luca M. Gambardella and Marco Dorigo. 1995. Ant-Q: A Reinforcement Learning approach to the traveling salesman problem. In ICML 252--260.
[32]
M.R. Garey and D.S. Johnson. 1979. Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company.
[33]
Michael R. Garey, David S. Johnson, and Larry J. Stockmeyer. 1976. Some simplified NP-complete graph problems. Theoretical Computer Science 1(3): 237--267.
[34]
Cyril Gavoille, David Peleg Stéphane Pérennes, and Ran Raz. 2001. Distance labeling in graphs. In ACM-SIAM SODA 210--219.
[35]
Liya Guo, Shan Huang, Jun Zhuang and Adel W. Sadek. 2013. Modeling Parking Behavior Under Uncertainty: A Static Game Theoretic versus a Sequential Neo-additive Capacity Modeling Approach. Networks and Spatial Economics 13: 327--350.
[36]
Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics (4)2: 100--107.
[37]
Xinxin Huang, Yingguo Gao, and Xiaohui Duan. 2020. An Autonomous Parking Space Planning System Based on Pattern Searching Algorithm. In IEEE International Conference on Smart City and Informatization (iSCI).
[38]
Cheng Jin, Lei Wang, Lei Shu, Yuyao Feng, and Xueqing Xu. 2012. A fairness-aware smart parking scheme aided by parking lots. In IEEE International Conference on Communications (ICC) 2119--2123.
[39]
Gregor Jossé, Matthias Schubert, and Hans-Peter Kriegel. 2013. Probabilistic parking queries using aging functions. In ACM SIGSPATIAL 452--455.
[40]
Merkourios Karaliopoulos, Konstantinos Katsikopoulos, and Lambros Lambrinos. 2014. Bounded rationality can increase parking search efficiency. In ACM MobiHoc 195--204.
[41]
Joon-Seok Kim, Dieter Pfoser, and Andreas Züfle. 2019. Distance-Aware Competitive Spatiotemporal Searching Using Spatiotemporal Resource Matrix Factorization. In ACM SIGSPATIAL 624--627.
[42]
Oanh Tran Thi Kim, Nguyen H. Tran, Chuan Pham, Tuan LeAnh, My T. Thai, and Choong Seon Hong. 2020. Parking Assignment: Minimizing Parking Expenses and Balancing Parking Demand Among Multiple Parking Lots. IEEE Transactions on Automation Science and Engineering 17(3): 1320--1331.
[43]
Yuichi Kobayashi, Noboru Kiyama, Hirokazu Aoshima, and Masamori Kashiyama. 2011. A route search method for electric vehicles in consideration of range and locations of charging stations. In IEEE Intelligent Vehicles Symposium (IV).
[44]
Amir O. Kotb, Yao-Chun Shen, Xu Zhu, and Yi Huang. 2016. iParker---A New Smart Car-Parking System Based on Dynamic Resource Allocation and Pricing. IEEE Transactions on Intelligent Transportation Systems 17(9): 2637--2647.
[45]
Nadav Levy and Itzhak Benenson. 2015. GIS-based method for assessing city parking patterns. Journal of Transport Geography 46: 220--231.
[46]
Xiangdong Li, Yuefeng Cen, Gang Cen, and Zengwei Xu. 2019. Prediction of short-term available parking space using LSTM model. In International Conference on Computer Science & Education (ICCSE) 631--635.
[47]
Peng Li, Demin Li, and Xiaolu Zhang. 2013. CGPS: A Collaborative Game in Parking-Lot Search. In International Conference on Soft Computing Techniques and Engineering Application 105--113.
[48]
Y.H. Li, H.J. Mao, and Y.M. Qin. 2019. Vehicle Routing Problem with Multiple Time Windows and Batch Splitting Based on Inferior First Bidirectional Search Algorithm. In ICEMCE. 1314(1): 012116.
[49]
Fan Li and Yu Wang. 2007. Routing in vehicular ad hoc networks: A survey. IEEE Vehicular Technology Magazine 2(2): 12--22.
[50]
Andy Liaw and Matthew Wiener. 2002. Classification and regression by randomForest. R news 2(3): 18--22.
[51]
Fandel Lin and Hsun-Ping Hsieh. 2021. A Joint Passenger Flow Inference and Path Recommender System for Deploying New Routes and Stations of Mass Transit Transportation, 2021. ACM Transactions on Knowledge Discovery from Data (TKDD). 16(1): 1--36.
[52]
Fandel Lin and Hsun-Ping Hsieh. 2020. A Goal-Prioritized Algorithm for Additional Route Deployment on Existing Mass Transportation Sys-tem. In IEEE ICDM 1130-1135, Sorrento, Italy.
[53]
Fandel Lin, Hsun-Ping Hsieh, and Jie-Yu Fang. 2020. A Route-Affecting Region Based Approach for Feature Extraction in Transportation Route Planning. In ECML-PKDD 275-290, Ghent, Belgium.
[54]
Jacek Malczewski. 2006. GIS-based multicriteria decision analysis: a survey of the literature, International Journal of Geographical Information Science 20(7): 703--726.
[55]
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. 2020. Reinforcement Learning for Combinatorial Optimization: A Survey. arXiv:2003.03600v3.
[56]
Naourez Mejri, Mouna Ayari, Rami Langar, and Leila Saidane. 2016. Reservation-based multi-objective smart parking approach for smart cities. In IEEE International Smart Cities Conference (ISC2).
[57]
Lingfeng Ming, Qi Hu, Ming Dong and Bolong Zheng. 2020. An Effective Fleet Management Strategy for Collaborative Spatio-Temporal Searching. In ACM SIGSPATIAL, Seattle, WA, USA.
[58]
Giuseppe Musolino, Antonio Polimeni, Corrado Rindone, and Antonino Vitetta. 2013. Travel Time Forecasting and Dynamic Routes Design for Emergency Vehicles. Procedia - Social and Behavioral Sciences.
[59]
John F. Nash Jr. 1950. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences 36: 48--49.
[60]
Yiwen Nie, Wei Yang, Zhi Chen, Nanxue Lu, Liusheng Huang, and Huan Huang. 2021. Public Curb Parking Demand Estimation With POI Distribution. IEEE Transactions on Intelligent Transportation Systems (ITS).
[61]
Karl Pearson. 1905. The Problem of the Random Walk. Nature 72: 294.
[62]
Michael N. Rice and Vassilis Tsotras. 2012. Bidirectional A Search with Additive Approximation Bounds. In SoCS.
[63]
Wayne A. Sarasua, Prashant Malisetty, and Mashrur Chowdhury. 2011. Using GIS-based, Hitchcock Algorithm to Optimize Parking Allocations for Special Events. Applied GIS 7(2): 1--13.
[64]
Sebastian Schmoll and Matthias Schubert. 2020. Semi-Markov Reinforcement Learning for Stochastic Resource Collection. In IJCAI 3349--3355.
[65]
Michael Schneider, Andreas Stenger, and Dominik Goeke. 2014. The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations. PLoS ONE Transportation Science 48(4): 500--520.
[66]
Eshed Shaham, Ariel Felner, Nathan R. Sturtevant, and Jeffrey S. Rosenschein. 2018. Minimizing Node Expansions in Bidirectional Search with Consistent Heuristics. In SoCS 81--98.
[67]
Wei Shao, Flora D. Salim, Tao Gu, Ngoc-Thanh Dinh, and Jeffrey Chan. 2017. Traveling Officer Problem: Managing Car Parking Violations Efficiently Using Sensor Data. IEEE Internet of Things Journal 5(2): 802--810.
[68]
Dani Simons. 2012. SFpark San Francisco Knows How to Park It. Sustainable Transportation 23: 26--27.
[69]
Qing Song, Meng Li, and Xiaolei Li. 2018. Accurate and fast path computation on large urban road networks: A general approach. PLoS ONE 13(2): e0192274.
[70]
Linda Steg and Robert Gifford. 2005. Sustainable transportation and quality of life. Journal of Transport Geography 13(1): 59--69.
[71]
Dušan Teodorović and Panta Lučić. 2006. Intelligent parking systems. European Journal of Operational Research 175(3): 1666--1681.
[72]
Barrett W. Thomas, Tobia Calogiuri, and Mike Hewitt. 2018. An exact bidirectional A approach for solving resource-constrained shortest path problems. Networks 73(2): 187--205.
[73]
Vasilis Verroios, Vasilis Efstathiou, and Alex Delis. 2011. Reaching Available Public Parking Spaces in Urban Environments Using Ad Hoc Networking. In IEEE MDM.
[74]
Dorothea Wagner, Thomas Willhalm, and Christos Zaroliagis. 2005. Geometric containers for efficient shortest-path computation. Journal of Experimental Algorithmics 10: 1--30.
[75]
Mingkang Wu, Haobin Jiang, and Chin-AnTan. 2021. Automated Parking Space Allocation during Transition with both Human-Operated and Autonomous Vehicles. Applied Science 11(2): 855.
[76]
Shuguan Yang, Wei Ma, Xidong Pi, and SeanQian. 2019. A deep learning approach to real-time parking occupancy prediction in transportation networks incorporating multiple spatio-temporal data sources. Transportation Research Part C: Emerging Technologies 107: 248--265.
[77]
Dingqi Yang, Daqing Zhang, Vincent W. Zheng, Zhiyong Yu. 2015. Modeling User Activity Preference by Leveraging User Spatial Temporal Characteristics in LBSNs. IEEE Transaction on Systems, Man, and Cybernetics: Systems, (TSMC) 45(1): 129--142.
[78]
Ruonan Zhang, Santosh N. Kabadi, and Abraham P. Punnen. 2011. The minimum spanning tree problem with conflict constraints and its variations. Discrete Optimization 8: 191--205.
[79]
Weijia Zhang, Hao Liu, Yanchi Liu, Jingbo Zhou, Tong Xu, and Hui Xiong. 2020. Semi-Supervised City-Wide Parking Availability Prediction via Hierarchical Recurrent Graph Neural Network. IEEE Transactions on Knowledge and Data Engineering (TKDE).
[80]
Jiandong Zhao, Yujie Guo, and Xiaohong Duan. 2017. Dynamic Path Planning of Emergency Vehicles Based on Travel Time Prediction. Journal of Advanced Transportation.
[81]
Bolong Zheng, Qi Hu, Lingfeng Ming, Jilin Hu, Lu Chen, Kai Zheng, and Christian S. Jensen. 2020. SOUP: Spatial-Temporal Demand Forecasting and Competitive Supply. arXiv:2009.12157.
[82]
Brain D. Ziebart, Anind K. Dey, and James Andrew Bagnell. 2008. Fast Planning for Dynamic Preferences. In ICAPS.
[83]
Onno Zoeter, Christopher Dance, Stéphane Clinchant, and Jean-Marc Andreoli. 2014. New algorithms for parking demand management and a city-scale deployment. In ACM SIGKDD 1819--1828.
Index Terms
- Conntrans: A Two-Stage Concentric Annealing Approach for Multi-Criteria Distributed Competitive Stationary Resource Searching
Recommendations
Exploiting Network Structure in Multi-criteria Distributed and Competitive Stationary-resource Searching
Transportation between satellite cities or inside the city center has always been a crucial factor in contributing to a better quality of life. This article focuses on multi-criteria distributed and competitive route planning for stationary resources in ...
A Decision Framework to Recommend Cruising Locations for Taxi Drivers under the Constraint of Booking Information
As the demand for taxi reservation services has increased, increasing the income of taxi drivers with advanced services has attracted attention. In this article, we propose a path decision framework that considers real-time spatial-temporal predictions ...
Traveling Transporter Problem: Arranging a New Circular Route in a Public Transportation System Based on Heterogeneous Non-Monotonic Urban Data
Hybrid computational intelligent systems that synergize learning-based inference models and route planning strategies have thrived in recent years. In this article, we focus on the non-monotonicity originated from heterogeneous urban data, as well as ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2021
700 pages
ISBN:9781450386647
DOI:10.1145/3474717
Copyright © 2021 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 November 2021
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
Conference
SIGSPATIAL '21
Sponsor:
SIGSPATIAL '21: 29th International Conference on Advances in Geographic Information Systems
November 2 - 5, 2021
Beijing, China
Acceptance Rates
Overall Acceptance Rate 257 of 1,238 submissions, 21%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 101Total Downloads
- Downloads (Last 12 months)11
- Downloads (Last 6 weeks)1
Reflects downloads up to 26 Nov 2024
Other Metrics
Citations
Cited By
View all- Lin FHsieh H(2022)Multicriteria Route Planning for In-Operation Mass Transit under Urban DataApplied Sciences10.3390/app1206312712:6(3127)Online publication date: 18-Mar-2022
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in