Analysis and Design of Public Transport Route Planner: Dijkstras Algorithm

Abstract

Nowadays, vehicle tracking is extremely useful for many things: personal vehicle security, public transportation management, fleet management, and mass transit management, among others. It is common for passengers to use public transport applications that propose the best route for them. Users may prefer a different route for public transportation depending on their preferences. Most users find the shortest route based on this criteria when choosing an ideal route. The shortest path is frequently determined using Dijkstra\'s Algorithm, according to our research. For this project, we designed a GIS application to improve public transportation using Geographic Information Systems (GIS). Based on the system\'s real-time location tracking, Dijkstra\'s algorithm provides taxis with the appropriate category for passengers. With this system, taxi drivers will not have to drive across town to pick up passengers, as confirmations will be sent directly to their phones. If you frequently have to wait for a taxi that has been booked, this will be helpful, especially if you are frequently left waiting.

Introduction

I. INTRODUCTION

Various factors have contributed to a recent increase in traffic congestion in the city. Public transportation and private vehicles are increasingly used in traffic as a result of population growth, and insufficient infrastructure cannot meet the demand. Globally, we are expecting a growth in the number of vehicles due to globalization and the rise of middle-class societies, including China and India. Although the number of vehicles has grown and middle- and upper-class residents have moved into the area, no tracking system (tracking) for vehicles has been developed.

The problem of traffic congestion has been addressed in an attempt to produce solutions. Optimizing the number of active vehicles on the road is much more expensive than improving  the road infrastructure. Based on observations and examinations, this study examined the running time and ease of use of existing apps. Review and assessment of the software consider aspects such as time taken to find a solution, accuracy of route returned as the solution, visual map support, search engine functionality, alternative paths, using GPS, printing route output, and foreign language options, as well as the ability to notify users of social events. They are used to create specific decision points. By comparing the ratings of applications according to these decision points, objective comparisons can be made. [1] An Analytic Hierarchy Process (AHP) is used to obtain the percent distribution of decision points and figure out the decision hierarchy. The nearest and farthest applications to ideal solutions are determined by TOPSIS (Technique for Order Preference by Similarity to Ideal Solution) [2] after weighing factors.

It has been shown in our study that route planning applications can be evaluated according to various criteria, including speed, ease of use, effectiveness, and economic impact. To provide instant and automatic service to passenger taxis, we are developing a system. In this system, the location and velocity of each taxi are monitored via a GIS (Geographic Information System) web-based application. Automatic taxi bookings will be handled by a system that employs Dijkstra's algorithm, which will determine which taxis are most suitable for passengers based on their parameters as well as the congestion around your premises, ensuring that passengers' orders are fulfilled.

II. RELATED WORK

In order to analyze the topology of transport networks, Space P modeling is preferred. A key component of this technique is that the same transit line stops at both stations of PTN if they are adjacent. A pair of stations is said to be adjacent if there is no station between them in the topology of real-life infrastructure.

In a bus transport network, Li and Zhu used Space P modeling for the first time in the literature. Based on the modeled network, they use Breadth-First Search to determine the route with the least number of stops. Also, Wang and Yang [12] used Space P to determine the optimal route based on the number of transfers in PTN. For each transfer, they multiply the adjacency matrix by itself. Due to this, more than one transfer may cause this method to take some time to run.

Space P is used to model PTN modes into complex networks in our approach. By adding edges in the complex network, stations within a specified walking distance are also connected. To determine the optimal route based on multi- factors, Dijkstra's Algorithm is applied to the modeled network. Dijkstra's Algorithm (DA) has also been modified or used directly in PTNs for route recommendation. According to Wang et al., [13] developed a public transportation data model (Matrix VL) and a query algorithm using Depth First Search and DA. A modified version of DA for route queries was developed by Xu et al. [14]. Bozyigit et. al. [15] DA was given penalties for reductions in the number of transfers.[16] Xiaoyong and Xueqin developed a heuristic algorithm to recommend routes based on transfers and distances. Ferreira et al. [17] propose a route advisor application that integrates data from various sources (government information, public transport, etc.) and uses DA to determine the quickest route. An optimized routing algorithm for hub transit networks was implemented by Goel et al. [18]. Using fuzzy factors and crisp values together, Biswas introduced a new algorithm for real-time Dijkstra's algorithms. Alternatively, Nasibov et al. An algorithm for maximizing preferred routes and minimizing stops were proposed by al. [20].

This study proposes a novel approach for route recommendation, combining Dijkstra's algorithm and Space P modeling technique for the first time. A simple and efficient method is used to determine the optimal route for each destination based on multiple factors (the number of transfers, the total distance, and the walking distance).

III. METHODS USED

A. Geographic Information System

Digital mapping and database creation are the two components of Geographic Information Systems (GIS). In the 1960s, CAD (Computer- Aided Design) became a standard tool in the design world, leading to the rapid development of digital cartography. GIS developments are also accelerated by the development of database management systems, involving DBMS especially, which provide a means of integrating spatial and nonspatial data. Various disciplines have been included in further developing GIS, such as remote sensing, photogrammetry, and surveying. GIS is now almost a part of everyday life. Almost any project or government program has benefited from geospatial technologies that work behind the scenes. Nowadays, almost every information system comes with a map feature. Something very difficult happened in Indonesia in terms of information services (services) and search needs during the 1980s.

B. Global Positioning System

With the help of satellites, the GPS system allows location on the earth's surface to be determined [10]. The GPS system calculates the location of the earth using satellite data. Despite their differences in appearance and software, GPS devices all work the same way. The number of satellites that can be simultaneously accessed by the GPS receiver is a very important difference between various GPS receivers. The device is capable of communicating with 12 satellites thanks to its 12-channel receiver. In contrast, GPS older models can only communicate with 8 or 5 satellites, but GPS receivers of the latest models can communicate with 14-20 satellites. The GPS calculates the error rate based on the number, position, and strength of satellite signals. An error rate of under 10 m (ideally below 5 m) from a GPS device can be used to determine the accuracy of GPS readings. There is generally no difference between GPS units when it comes to recording GPS data. When the movement occurs or the time elapses, GPS receivers record the data into their memory. It is generally termed as track points. It is possible to use GPS devices as complete navigation devices that provide driving directions and location details, but can also provide a tool that tells the user when and where it is going to move. A digital compass has been built into most receivers. A digital compass works with data from satellites. It is not a magnet compass and will only work  once a person starts moving.

C. Dijkstra Algorithm

Edsger Dijkstra invented Dijkstra's algorithm in 1959 to solve the shortest paths in a graph where node weight cannot be negative [7]. A node's weight and paths need to be exchanged with all the vertices in order to determine which node has the smallest weight. Dijkstra  is a simple and straightforward algorithm based on the greedy principle.

The Constituent elements greedy algorithm consists of the following components::

1. The set of candidates, C: A solution may be found in this set of elements. The shortest route on a graph is referred to as a candidate set.
2. The set of solutions, S: The solution set is independent of the candidate set as all of its elements come from the set of candidates, but not all of them
3. The selection function: Any candidate will be selected by this function, which allows the optimum solution to be produced for each step.
4. The feasibility function: If a candidate violates the constraint, his or her inclusion into the solution set will be denied.
5. The objective function: Taking the best solution from each of the options, the goal is to pick the own with the highest value.

The undirected graph shown in figure 3.10 contains five dots and seven tracks connecting them. Undirected graphs are analyzed using the Djikstra algorithm to compute the shortest distance between points.

Based on the calculation graph search algorithm Dijkstra appropriate procedural steps, completion of points 1 to 4 of the Dijkstra path algorithm has been completed. The first line of a set of 0 means a source point will be used as the source point for all routes, and another point will be stated as unknown since no trajectory has been known.

Point 1 is absolutely elected since it is the source track. As a result, it became a status set of 0. 1. Checkpoints 1, 2, 3, 4, and 5 will be directly adjacent. Then, Dijkstra chooses the most relevant point based on the weighting of each individual. The status of 0 is changed to 1, and so on, when point 2 is elected with a weight of 1, it is changed to 1. From points 1 to 4, the shortest path obtained from the Dijkstra-based search is via direct point 1 to point 4 with weight trajectory 5.

D. Automatic Vehicle Location

Computer-based vehicle tracking systems are used to locate vehicles [6]. All vehicles will be monitored for their current position and the data will be forwarded to the control center.

A vehicle's position information is stored on it for several seconds, in most cases. A control center can receive raw data about the vehicle's position or post-processed data after it has been collected by the vehicle's device.

AVL systems provide many benefits to an agent or transportation company. From an operational perspective, this system can improve scheduling, improve efficiency, integrate facilities systems, and reduce the number of supervisors (supervisors) on the ground. This new radio system reduces voice communications while improving emergency response times due to the use of mobile data terminals.

IV. SYSTEM DESIGN

GPS position information is displayed using a web-based service, based on Android-based GPS receivers installed in each vehicle (also called onboard units, or OBUs). In order for the system to operate, vehicles must be positioned in real time and traffic densities must be known. Using smartphones with Android operating systems as GPS receivers, the system uses location-based services. A smartphone's GPS feature will be linked up with Brace, which will send the data to a server. This application also reports the exact location of a smartphone in real-time to a server, as well as tracking its location. It is the server's database in which the GPS receiver transmits data. Based on data collected from the GPS receivers of the taxis, the application pages will display where each taxi is located upon a passenger's access to the application pages.

This system will use Dijkstra's algorithm to select the most appropriate vehicle. This system uses Dijkstra's algorithm to determine which vehicle is most appropriate for passengers. It takes the vehicle's position and the density of vehicles on city streets into account. A service-based push email will be sent to the taxi drivers when the system has located the taxi with the best categories.

Conclusion

Data is first processed by the GPS receiver and then sent to the server via a cellular communication network (GSM). Upon receiving latitude and longitude descriptors from the client, the server transmits them to Google Maps in order to compute taxi positions. The GPS receiver will provide latitude and longitude data so that a server can determine which taxi is closest to passengers. During a period that is adapted to traffic density, we will test this system in urban areas. There will be two conditions under which this system will be tested. During the first period, there is a high traffic density, which is between 7:30 AM and 3:00 PM. Secondly, at 5:00 PM to 9:00 PM when traffic conditions improve. A comparison between the designed system and the existing system services will take place as part of this test. Based on individual passenger waiting times, we can determine whether the service has improved. Based on a variety of criteria including the distance between a passenger and a taxi, the Dijkstra algorithm can be used to find the best taxi based on the shortest distance between the passenger and the taxi, as well as the amount of traffic in a given area. By having taxis near them, these apps provide both passengers with a way to call them, and taxi drivers with a means of saving time and fuel.

References

[1] Z. Huang, J. Li, and X. Liu, \"Information Needs of Urban Transit Travelers-The Case of Wuhan, China,\" in ICCTP 2009: Critical Issues in Transportation Systems Planning, Development, and Management, Harbin, China, 2009, pp. 1-7. [2] L. H. Chuin, Y. Lao, F. H. Meng, and L. H. Wai, \"A multi-criteria, multi-modal passenger route advisory system\", 1999. [3] Gilani, Komal; Bertin, Emmanuel; Hatin, Julien; Crespi, Noel (2020). [IEEE 2020 2nd Conference on Blockchain Research & Applications for Innovative Networks and Services (BRAINS) - Paris, France (2020.9.28-2020.9.30)] 2020 2nd Conference on Blockchain Research & Applications for Innovative Networks and Services (BRAINS)- A Survey on Blockchain-based Identity Management and Decentralized Privacy for Personal [4] Y. Z. Chen, N. Li, and D. R. He, \"A study on some urban bus transport networks,\" Physica A: Statistical Mechanics and its Applications, vol. [5] H. Wang, M. Hu, and W. Xiao, \"A new public transportation data model and shortest- path algorithms,\" in 2010 2nd International Asia Conference on Informatics in Control, Automation and Robotics (CAR 2010), 2010, vol. 1, pp. 456-459. [6] Johnson M.C., & Thomas, L.E. (2000), “Automatic Vehicle Location Successful Transit Applications”, U.S. Department of Transportations, Washington, DC. [7] Joyner D., Nguyen, V.H., Cohen, N. (2011), “Algorithmic Graph Theory”. [8] Odom W., (2007), “CCENT/CCNA ICND1 Official Exam Certification Guide”, Cisco Press, Indianapolis. [9] E. W. Dijkstra, \"A Note on Two Problems in Connexion with Graphs,\" Numer. Math., vol. 1, no. 1, pp. 269-271, Dec. 1959. [10] McWilliam N. (2005), “GIS, GPS, and Remote Sensing”, The Expedition Advisory Centre Royal Geographical Society 1 Kensington Gore, London. [11] L. S. C. Pun-Cheng and A. W. F. Chan, \"Optimal route computation for circular public transport routes with differential fare structure,\" Travel Behaviour and Society, vol. 3, pp. 71-77, Jan. 2016 [12] Sathiamoorthy M. (2009), “On GPS Tracking of Mobile Devices”, International Conference on Networking and Services”. [13] Yi Z., Ding W., Yanfei Y. (2009), “On Dynamic Scheduling of Vehicles Based on GPS / GIS / RFID”, Department of Computer Science & Technology, Harbin. [14] Yuan Gannan, Zhang Zhi, and Guan Shang Wei. (2008), “Research and Design of GIS in Vehicle Monitoring System”, Harbin Engineering University, Harbin. [15] A. Bozyi?it, G. Alanku?, and E. Nasibo?lu, \"Public transport route planning: Modified Dijkstra\'s algorithm,\" in 2017 International Conference on Computer Science and Engineering (UBMK), Antalya, 2017, pp. 502-505. [16] X. Yan and X. Niu, \"Study on a heuristic algorithm for public transport network multi- path selection,\" Urban Transport of China, vol. 3, 2005. [17] J. C. Ferreira, P. Filipe, and A. Silva, \"Multi-Modal Transportation Advisor system,\" in 2011 IEEE Forum on Integrated and Sustainable Transportation Systems, 2011, pp. 388-393. [18] N. Goel, N. R. Velaga, P. Vedagiri and T.V. Mathew, \"Optimal routing algorithm for large scale multi-modal transit networks,\" in World Conference on Transport Research, 2017. [19] S. S. Biswas, \"Fuzzy Real Time Dijkstra\'s Algorithm\", International Journal of Computational Intelligence Research, vol. 13, no. 4, pp. 631640, 2017. [20] E. Nasibov, A. C. Diker, and E. Nasibov, \"A multi-criteria route planning model based on fuzzy preference degrees of stops,\" Applied Soft Computing, vol. 49, pp. 13-26, Dec. 2016. [21] \"GMap.NET - Great Maps for Windows Forms Presentation\", CodePlex, 2017. [Online]. Available: [22] https://greatmaps.codeplex.com. [Accessed:12-Apr-2018]. [23] \"Eshot Genel Müdürlü?ü Resmi Web Sitesi\", Eshot.gov.tr, 2017. [Online] Available at: http://www.eshot.gov.tr [Accessed: 12- Apr-2018]. [24] \"Eshot Genel Müdürlü?ü Resmi Web Sitesi\", Eshot.gov.tr, 2017. [Online] Available at: http://www.eshot.gov.tr [Accessed: 12- Apr-2018]. [25] X. Xu, Y. Yin, and L. Liu, \"Improved Dijkstra\'s algorithm and its application in the intelligent transportation system,\" Journal of Residuals Science and Technology, vol. 13, no. 7, 2016. [26] X. Yan and X. Niu, \"Study on a heuristic algorithm for public transport network multi- path selection,\" Urban Transport of China, vol. 3, 2005.

Copyright

Copyright © 2022 Abhishek Ray, Himanshu Sharma, Divyanshu Sharma. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.