Bus Route Identification Algorithms And Services

Bus Route Advisory Algorithms and Services Akshaya Srivatsa, Student, 6 Semester Telecommunication Engineering, Vishweswaraya Technological University, PESIT, Bangalore th

Abstract Public transport system plays an important role in any city as thousands of people depend on it for their transportation in the city. Over the past few decades, cities have been growing at a tremendous pace in every aspect, including the public transport services. This paper is restricted to the discussion of the most popular type of public transport system namely the metropolitan bus service. More buses are being added every year and more routes are being designed to cater to the needs of the growing cities, especially in emerging countries like India. As a result, bus routes are getting complicated with time and identifying the best route to reach your destination has become quite a tedious process. When we say best route, we must strive to optimize on time and distance and hence money. The case study detailed in this paper is about Bangalore Metropolitan Transport Corporation [BMTC-01], a government body offering passenger transport services to Bangalore city. However this solution can be extended to any other passenger bus service in another city. From a passenger point of view, identifying routes is very complicated simply because of the enormous size of public transport systems (For bus services, a count of number of bus stops or bus routes can be of the order of few thousands). One of the many solutions is to employ grid based bus services[Grid02], which can reduce the number of bus routes. This is exactly what BMTC is implementing. But the fact remains that, no matter how simple the bus routes become, it is always tough to find the best route between two stops. This paper talks about designing a software solution, which can suggest routes between any two stops in the city, after optimizing on time and distance. The user need not know any information about the bus routes in the system prior to the using

of the software. The software will provide all the necessary information-like bus stops, intermediate bus interchange stops, buses to board, timings, and frequency - required for the user to move between any two stops in the city. With spell check algorithms like Metaphone[10] and Soundex[09], the user need not know the accurate spelling of stop names too. A rough estimate of the spelling is sufficient to find out the routes that the user is interested in. The software implements a novel implementation of Dijkstra’s algorithms[15] to wotk in linear time. Today Short Message Service [SMS-03] is highly inexpensive (from 1 paise to about 50 paise per message). With the growing usage of mobile phones and low priced SMS, we ultimately plan to enable the above mentioned services on mobile phones.

Introduction Before defining the problem statement, I would like to bring out the problems faced by the passengers in the current bus systems. Based on the case study of BMTC, the following points give us a good picture of the problems faced in any bus service in general. •

•

•

BMTC has over 1700 bus routes in the city and the public is not aware of the existence of many of these routes. Each traveler tries to remember only a few routes numbers. Travelers and tourists visiting the city find it tough to identify the best route to their destination, as they are not aware of the bus routes, bus numbering schemes etc. Even the residents of the city make the mistake of boarding the same bus and over crowding it, when in fact there are sufficient buses and bus routes in any given direction. This is because of the fact that many are unaware of the existence of other bus routes

•

•

and frequencies, as mentioned in point number 1. In a city like Bangalore, there are around 1200 bus stops (including the main bus stations). ‘Picture 1’ gives us an idea of the “Density of stops in a city”. The red dots represent the bus stops. ‘Picture 2’ shows that it is not possible to pack the entire bus route information on a single board due to its small dimensions (unless an electronic board is used, which is quite expensive). As a result, identifying the right bus route between two points in the city just by looking at the bus number or by trying to read the bus route map is quite a complicated and a tedious process.

Identifying the optimum route is not an “Impossible” task, but it is a complex task for human beings because it requires lot of storage, computation and calculations, which is beyond the intended functions of the human brain. But in today’s world, computers are used in every possible field. One field in which computers beat human beings hands down isComputation . With current technologies, calculations or computation can now be performed at phenomenal speeds, taking only a fraction of a second which otherwise would have taken hours or even days for any human being. In short, using a computer to find out the best route is one of the many solutions to the above specified problems and it is this solution we now describe.

Problem Statement “To design a software, which can suggest routes between any two stops in the city, after optimizing on time and distance. The software must be highly user friendly so that the user need not have knowledge about the bus system, prior to using the software. With the growing usage of mobile phones and low priced SMS, ultimately this service must be made available on mobile phones via Short Message Service[SMS].” Picture1: A portion of the BMTC bus stops map (Red dots represent the bus stops) Courtesy: BMTC and Integra Systems and Services

Solution The solution to the problem, as given in the problem statement, starts with designing an algorithm to identifying the routes.

The Algorithm Requirements

Picture 2: A picture of a bus route information board of the bus Courtesy: http://www.primarystuff.co.uk/photos/albums/pics/More_Maths/ normal_bus_number.jpg

I. The parameters passed by the user to the program as follows: 1. The Starting Point Bus Stop-Mandatory 2. The Ending Point Bus Stop-Mandatory 3. Time at which the user intends to start his journey-Optional Irrespective of whether the third parameter is present or not, there is no route defined without the first two parameters.

Note that the entire city map is partitioned into grids. More information on this will follow.

II. This paper will focus on only 3 types of bus routes. 1. Direct bus routes 2. Bus routes with one interchange point 3. Grid bus routes

Interchange Points

III. All the bus routes and bus stop information must be present in a database having the following tables Bus routes This table has complete information on the different bus routes in the city. The schema is given as follows. Assume that A is the starting point for a bus. 1. Bus Number or the Route Number, say B 2. Total time of journey between Bus Stand A and Bus Stand B. 3. Total distance of the journey between Bus Stand A and Bus Stand B. 4. Average time between the buses leaving the bus stand A (avg_to). 5. Average time between the buses leaving the bus stand B(avg_fro). 6. All the time-ordered stops the bus B visits as it plies between bus stand A and bus stand B all day. Example: For route number ‘10’, “K R Market” is Bus stand A and “JP Nagar 6Th Phase” is Bus stand B and all the stops it visits are stored as shown below :K R MARKET:MAHILA SAMAJ/OKKALIGARA SANGHA:TAXI STAND:SOUTH END CIRCLE:JAYANAGAR 5TH BLOCK:JP NAGAR 24TH MAIN 9TH CROSS:JP NAGAR 6TH PHASE:

This is a table that contains a subset of all the stops in the city. This table has those stops in the city where many different bus routes intersect and these stops are ideal places to change buses. The schema is as follows 1. Bus stop or Interchange point name. 2. Grid location of the stop. The Routes table (Table III) is based on the fact that a given bus in many cities in India (like Bangalore city) keeps shuttling between the same two bus stands all day (Bus Stand A and Bus Stand B) and visits all the stops in its route in its journey. Every bus stop is best understood when viewed as a point in a 2-dimensional space, where the space is the city itself. We can either associate a co-ordinate with every stop or employ a “Grid Square map”[04]. To identify the routes and stops visited between a starting point and an ending point, it is better to employ the latter system. A simple definition of Grid Square map is given below. “A Grid is a set of numbered rows and lettered columns (or vice versa) superimposed on a map to identify a given small area on the map or the features of the map”[05] . ‘Picture 3’ is an example of a grid square map for Bangalore city. Bounding Rectangle

Note that the bus stops are separated by colon ‘:’ characters. The other tables in the database are STOP A Bus Stops

STOP B

This table contains all the stops in the city. The schema is as follows 1. Bus stops name 2. Grid location of the stop. This gives us the grid square in which the stop is located in.

Picture 3: Grid map of Bangalore city Courtesy: http://www.indianholiday.com

Now consider two stops, ‘Stop A’ located in the square C5 and ‘Stop B’ located in the square B3 as shown in the ‘Picture 3’. Any bus route between these two stops that we are interested in has to lie within that rectangle on the grid-map, which contains both the stops within itself. Such a rectangle is called as “Bounding Rectangle”[06]. The red rectangle in ‘Picture 3’ represents a bounding rectangle for A & B. The above statement is made under the assumption that any route lying outside the bounding rectangle has to be longer than the routes inside the rectangle. This is a fair assumption as this assumption will hold true for a majority of the routes if not for all. Now within the bounding rectangle, the set of all routes to move from a given origin stop to destination stop is quite large, in which most of the routes are either too long or too time consuming or both. So we are interested in finding that subset of routes which are both time and distance optimized. To find this, its important to design a metric[07]. “Metrics” as given by Wikipedia[08], is defined as follows. “Metrics are a system of parameters or ways of quantitative and periodic assessment of a process that is to be measured, along with the procedures to carry out such measurement and the procedures for the interpretation of the assessment in the light of previous or comparable assessments.”. In simpler terms, metric is a way to measure a quantity in any process. In our process, we need a metric to distinguish between ‘Advantageous routes’ and ‘Routes that do not give us time and distance advantage’. A simple metric that I have employed is given below Metric for routes = (K x froute no)/Da,b, where froute no = frequency of bus route which is (avg_to)-1 or (avg_fro)-1 depending upon the direction of the route. Da,b = distance between stop a and stop b. K = A scaling factor The lager the metric is, the more advantageous it is. Direct bus routes:

For direct routes we need to look for those bus routes where both the starting and ending stops are present in the ‘route’. There may be many direct bus routes and some direct bus routes may not be advantageous. So we use the metric to filter out all those routes in which we are not interested. This is done by choosing those routes whose metric gives us a value greater than a “Threshold value”. Bus routes with one interchange point: This means that to reach the destination, the passenger needs to change buses at a particular interchange points. This approach is necessary as there may not be direct buses between the given two stops in the city. Here we plan to use an adaptation of Dijkstra’s algorithm. The original Dijkstra’s algorithms is general for N hops graphs and computationally longer. Since our problem is restricted to a maximum of two hops, we can reduce the time complexity of the Dijkstra’s algorithm by eliminating the steps involved in identifying tentative & permanent nodes. Staring Stop

Interc hange Point

Flow Chart: Direct Bus Route

Ending Stop

So the steps involved in finding the route are as follows 1. After identifying the bounding rectangle, we need to identify all the interchange points within the bounding rectangle from the table ‘Interchange points’ from the database. 2. Choose a new interchange point, Ij 3. Are there buses from starting point (A) to intermediate point (Ij) and from Ij to ending point (B)? If yes, go to step 4 else go to step 2. This step is used to identify only those interchange points through which a route between A and B exits. 4. Calculate the metric for each bus routes between A and Ij and the bus route between Ij and B. 5. Add all the metrics to form a new metric associated with the interchange point called as ‘METRICj’. 6. If all the interchange points have been exhausted, go to step 7 else go to step 2. 7. Larger the value of METRICj is, the better is the rote through that interchange point. Arrange all the interchange points in the decreasing order of their value, so that the best routes appear first and the worst appear at the end of the list. 8. Sometimes a certain route may give a very good value of metric and yet will give a route that may be extremely long. Hence, in terms of priorities, the length of the route must be placed higher than the metric. So select only those routes whose route lengths are less than a threshold value– say 1.3 times the average route length between the two stops. So this step is essentially used to “Filter” out the routes from the best available routes. 9. Display all the results. Now each metric associated with the interchange point tells us how advantageous it is to travel by via interchange point. Larger the metric, better is the interchange point and more advantageous it is. ‘Flow Chart 2’ represents the flowchart for this algorithm.

Flow Chart: Bus Route With One Interchange

Grid Bus Routes: This system is most likely going to replace all the previously mentioned system in many cities, if not all. This system makes the understanding of the bus system simpler than with arbitrary routes running all over the city. Grid bus routes consist of • TR, Trunk Routes, which are routes that run across the city. They cover major stops and stations of the entire city but do not cover the smaller stops located within areas. In other words, they help you move from one area in the city to another area. Typically these routes run in north-south and east-west directions. • FDR, Feeder Routes, which are routes that cover the smaller stops local to an area. They typically keep moving in a circular fashion and are confined to smaller regions of the city like residential area, cross roads of the locality etc. To move from starting point A to end point B, we need a combination of Trunk routes and Feeder routes. The passenger has to move from his stop to the closest trunk route stop by using one of the Feeder buses. He must then travel by trunk routes to reach that stop which is closest to his destination. He must then use the feeder service local to that area to move to his final destination. Let the starting point be STA and end point be END. An overview of the Algorithm (not the exact algorithm) 1. Identify the locations of the two stops (STA and END) in terms of the grid location as we discussed earlier. 2. Find the closest trunk stops for starting and ending points. Let the trunk stop closest to STA be TR-STA and that closest to END be TR-END. 3. Find the Trunk Routes (TR’s) that connect the TR-STR and TR-END. 4. Find the feeders that help the passenger to move from STR to TR-STR. 5. Find the feeders that help the passenger move from TR-END to END 6. Display the results.

The advantages with grid bus routes system are: 1. Trunk Routes are typically on high traffic roads while feeders are local to the area. Hence we can see that there is a well defined “Logic” in the entire system unlike the current system which has random ways of designing routes. This is analogous ‘bus based hardware design’ vis-à-vis random connections. It can also be compared with the way ‘internet’ or ‘telephone network’ are designed. 2. The entire city can be covered with very few Trunk Routes and hence the number of trunk routes that is needed will be much less than the current system. In the case of Bangalore, BMTC is yet to implement Grid Based services on full swing. But they say that they have identified 15 Trunk Routes for the entire city, which is much better than current 1700 randomly oriented bus route system in the city. 3. One of the problems with the current system is that there is no proper distribution of the load across different bus routes. These two are totally eliminated in Grid Routes as trunk routes are uniformly distributed over the city and frequency of buses is kept quite uniform in the entire city. 4. An immediate consequence of point 3 is that the algorithm to find out the best routes from STA to END is simpler than the current system because the metric can be made independent of frequency. 5. Routes are also easier to understand for an average user. Locations once expressed in grid coordinates will allow users to figure out a way to use a combination of routes. As of now, this concept is yet to be tested as there is no city/town in the country that uses gird based service. BMTC would be the first to implement this concept and hence we can test only after we get a database on grid based services.

Search Tool A city will have thousands of stops in itself. In the case of Bangalore city, it has close to 1200 stops. Etymologically, the stop names have local language

origin. Hence spelling the names in English may not be unique. But the database contains a unique name for each stop. So it becomes necessary to develop a dictionary of the stop names as given in the database, so that even when the user enters a spelling of a stop different from that present in the database, an algorithm can be used to find the closest matching stop name as given in the dictionary. Hence this closest match can now be used to find the routes. The algorithms we have used are Soundex [09] and Metaphone[10]. These are phonetic algorithms that assign different numerical values to different syllables and alphabets and hence return an alphanumeric representation of the word. The algorithms many not be the best one but they are quite immune to spelling errors and return the actual spelling that the user was referring to. Using a dictionary consisting of stop names given in the database (after lot of cleaning of raw data in the original DB), we have successfully been able to implement the search tool.

Implementation The entire software has been developed on Java Platform. Using Java Swing GUI Toolkit[11], there is a stand alone version of the software. A web based implementation is based on Java Server Pages (JSP)[12] using Apache TomCat JSP server[13]. The user can either search the stops name based on the starting letter of the stop name or by entering the stop name. This will give him a subset of all the stops starting with the given letter. Also, the user can enter the name of the stop itself. The software will give you the closest matching stop names. Most important requirement of the software is the database. I have used MySQL Database Management Software[14] for this purpose. The discussion of populating our database is beyond the scope of this paper and hence would like to give you the gist of the database. Using “Screen scraping” techniques[12], I was able to extract 1700 bus routes’ information present in from the BMTC website[01]. Different methods and algorithms were

written for “Duplicate Entry Elimination” and ”Fault elimination”. In the end I have developed an error free database of the current bus system in Bangalore. For the SMS implementation, there are numerous SMS Gateway products. Currently for testing purposes, I have used NowSMS SMS/MMS gateway[13] Trial Edition software. The GSM modem used for testing purposes was Sony Ericsson K700i [15]GSM Mobile Phone. Any mobile phone can be used as a GSM modem. There are also PC Card based GSM modems manufactured by Nokia, Sony Ericsson and Panasonic etc

Results The algorithm has been successful in generating direct bus routes and one stop interchange routes, which have both distance and time optimization. Spell check algorithms can find the exact spelling of the route even if the user to makes 3-4 mistakes in spelling the bus stop. The implementation of the algorithm in the form of a web tool (JSP), stand alone desktop tool (JFC SWING) and SMS service has worked as expected without any errors. The sample results obtained from the above mentioned tools are given below. Spell Check • KAVERI NAGAR is the actual spelling of a particular stop in the city. The following misspelled names when entered still gave KAVERI NAGAR as the result. KAVERI ANGAR, KAVERUNAGAR, KAVER NAGAR, KAVERNGAR etc • Similar test was performed on A NARAYANPURA and the results were the same for following spellings entered ANARAYANPURA, A NARYANPURA, A NARAYANAAPURA etc Bus Routes Bangalore city has 1200 stops as mentioned before. Mapping all the 1200 stops into the DB needs a lot of man power and effort and hence only about 120 stops from 6 grid locations ( D4, D5, D6, E4, E5 and E6) were mapped as shown in Picture 4 for testing. Some routes were tested and the program was able to successfully come out with well optimized routes.

The following results were obtained from the JSP version of this tool.

The Buses From "BINNY LAYOUT" To "KEMPEGOWD BUS STATION" are as follows >>> 87A , 87B , 87C , P87 ,

1. Routes from BANASHANKARI BUS STAND TO KEMPEGOWDA BUS STAND

The Buses From "KEMPEGOWD BUS STATION" To "YESHWANTHAPURA BUS STATION" are as follows >>> 250D , 250E , 251 , 251A , 251B , 252D , 252G , 252T , 253A , 253K , 254 , 254A , 254D , 255 , 255A , 255B , 255E , 255F , 256B , 256D , 257A , 257D , 258A , 258E , 258F , 258G , 258H , 258L , 258M , 263A , 263B , 263C , 263D , 263E , 369K , 52E , 82C , 83C , 90E , 98A , 98E , P16 ,

The Direct Buses From "BANASHANAKARI BUS STATION" To "KEMPEGOWD BUS STATION" are as follows 12 , 211J , 22.9 , 12E , 14A , 210CA , 210E , 211B , 211L , 213N , 215G , 215J , 215N , 215O , 215R , J14 , P21 , The routes where you have to change once are as follows. ROUTE 1

ROUTE 2 The Buses From "BINNY LAYOUT" To "SWASTHIK" are as follows >>> 63A , The Buses From "SWASTHIK" To "YESHWANTHAPURA BUS STATION" are as follows >>> 1 , 173 , 1A , 23 , 42 , 47 , 79A , 98E ,

The Buses From "BANASHANAKARI BUS STATION" To "SWASTHIK" Are As Follows >>> 14 ,

ROUTE 3

The Buses From "SWASTHIK" To "KEMPEGOWD BUS STATION" are as follows >>> 104 , 105A , 276N , 98E , TR6 ,

The Buses From "BINNY LAYOUT" To "NAYANDA HALLI" are as follows >>> 87B ,

ROUTE 2

The Buses From "NAYANDA HALLI" To "YESHWANTHAPURA BUS STATION" are as follows >>> 401R ,

The Buses From "BANASHANAKARI BUS STATION" To "LEPROSARIUM" are as follows >>> 214F , The Buses From "LEPROSARIUM" To "KEMPEGOWD BUS STATION" are as follows >>> 196 , 243F , 61D , 61G , 61H , 87C , ROUTE 3 The Buses From "BANASHANAKARI BUS STATION" To "MM INDUSTRIES" are as follows >>> PK21 , 14A , 23A , P21 , The Buses From "MM INDUSTRIES" To "KEMPEGOWD BUS STATION" are as follows >>> 12C , 14A , 15C , 15E , 15G , 15H , 15L , 210A , 210R , 210U , JPV15H , JPV210A , P21 , PK210A ,

3. Routes From VIVEKANANDA NAGAR To NAVARANG TALKIES The Are No Direct Buses From "VIVEKANANDA NAGAR" To "NAVARANG TALKIES" ROUTE 1 The Buses From "VIVEKANANDA NAGAR" To "KEMPEGOWD BUS STATION" are as follows >>> 146A , 276N , 43A , The Buses From "KEMPEGOWD BUS STATION" To "NAVARANG TALKIES" Are As Follow >>> 89C , JPV80A , P11 , P80 , P80A , ROUTE 2

2. Routes From BINNY LAYOUT To YESHWANTHPUR BUS STAND

The Are No Direct Buses From "BINNY LAYOUT" To "YESHWANTHAPURA BUS STATION" The routes where you have to change once are as follows.

ROUTE 1

The Buses From "VIVEKANANDA NAGAR" To "SIRSI CIRCLE" are as follows >>> 192 , The Buses From "SIRSI CIRCLE" To "NAVARANG TALKIES" are as follows >>> J91D , P91D ,

SMS In every SMS Gateway, like in NowSMS, there is an option for executing certain shell commands when

the server receives an SMS. The format for the SMS chosen is “STARTING POINT <space> ENDINGPOINT”. When the server receives an SMS in the above mentioned format, it passes the Sender’s number, STARTINGPOINT and ENDINGPOINT to a Java program which processes the bus routes and sends an SMS back to the sender using redirecting URL’s provided by the SMS gateway. The spell check algorithms used here are more accurate than in web tool implementation or the stand alone implementation and hence help us find the exact stop more precisely. The discussion of the spell check algorithms used here is beyond the scope of this paper.

Conclusion India is a country of a billion people. This is one of the biggest economies in the world. As a matter of fact, the number of commuters by bus or any other public transport system in India exceeds the numbers of other developed and developing countries. This country needs solutions for mass transport systems. For bus transport systems, we have created prototype server software for providing bus route information to travel from point A to point B using Bus Services within the city. The solution becomes highly useful when integrated with SMS services, because SMS has taken over the mobile market by a storm and the future of many services lies in mobile integration. The solution can be extended in many ways with additional features and can be applied to similar problems such as car sharing, pooling, GPS tracking etc. The next logical step would be build a robust, high performance system that can serve the hapless commuters of any large city making their daily experience more acceptable.

Acknowledgement I would like to thank my friend Anush Shetty, (CS 8th Semester PESIT), for introducing me to the problem. I would also like to thank Mr Bhosekar, (Former Division Controller Of BMTC), for giving me insight into the grid system and BMTC for providing me with the bus route information of Bangalore city. I would also like to thank Mr.R Vekat Varadhan (Senior Architect, Hewlett Packard) for helping me with coding techniques and tips. Lastly and most importantly, I would like to thank late.Bhanu Bhaskar ( Professor, PESIT) and Dr.

Shekar Borgaonkar (Director Of HP Laboratories, India) for their support and guidance.

Abbreviations BMTC Bangalore Metropolitan Transport Corporation. SMS Short Message Service TR Trunk Routes FDR Feeder Routes JSP Java Server Pages MMS Multimedia Messaging Service GSM Global System for Mobile Communications DBMS Database Management System DB Database

SQL

Structured Query Language

References [01] Bangalore Metropolitan Transport Corporation Official Website. http://www.bmtcinfo.com/ [02] Grid Plan Wikipedia, the free encyclopedia http://en.wikipedia.org/wiki/Grid_plan [03] Short Message Service, Wikipedia the free encyclopedia http://en.wikipedia.org/wiki/Short_message_service [04] Grid Square Map Definitionthefreedictionary.com http://www.thefreedictionary.com/grid+coordinate+s ystem [05] Grid Square Map Definition http://en.mimi.hu/gis/grid.html [06] Minimum Bounding Rectangle- CLIM http://www.mikemac.com/mikemac/clim/bboxes.ht ml [07] Metric- Wikipeida the free encyclopedia http://en.wikipedia.org/wiki/Metrics [08] Wikipedia, free encyclopedia http://en.wikipedia.org [09] Soundex Algorithm Wikipedia http://en.wikipedia.org/wiki/soundex [10] Metaphone Spelling Algorithm Wikipedia http://en.wikipedia.org/wiki/Metaphone [11] Creating GUI with JFC Swing http://java.sun.com/docs/books/tutorial/uiswing/ [12] Screem Scraping Wikipedia http://en.wikipedia.org/wiki/Screen_scraping [13] NowSMS SMS/MMS Gateway www.nowsms.com/ [14] MySQL OpenSource DBMS www.mysql.com/ [15] Dijkstra’s Algorithm

Picture 4 – BMTC’s Route Map Of Bangalore Courtesy: BMTC and Integra Systems (Black Mark Over A Stop means that there is no Information about the Stop in the database’)

Screen Shots Using Swing Interface

Screen Shot 1- Login Screen

Screen Shot 2 – Bus Stop Information

Screen Shot 3 – Selecting the Start and End Bus Stops

Screen Shot 4 – Resulting Routes Information