Bus Routing And Advisory Algorithms And Services
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Bus Routing And Advisory Algorithms And Services as PDF for free.
More details
- Words: 1,182
- Pages: 17
Bus Route Advisory Algorithms and Services
Akshaya Srivatsa Department of Telecommunication Engineering PESIT [email protected]
10/18/08
1
Agenda
Case Study-BMTC Problem Statement Solution Objectives System Architecture The Algorithm The Services Strengths And Limitations Next Steps Acknowledgement
10/18/08
2
Case Study-BMTC
Bangalore city has
Over 1700 bus routes Over 1100 bus stops 16 trunk routes and 14 more to be added Currently, highly disoriented bus routes
BMTC- Bangalore Metropolitan Transport Corporation
10/18/08
3
Problem Statement Current Scenario
Large number of bus stops and bus routes Difficulty in identifying good routes Public’s ignorance about the entire bus route system The bus stops are not equipped with dynamic display boards Long waiting time in bus stops due to lack of information on timing
10/18/08
4
Solution Objectives
To design a software, that
suggest routes between any two stops, after optimizing on time and distance
is accessible through
10/18/08
Internet – users can browse from their desktops Mobile phone - low priced Short Message Service [SMS], enables this service to be made available on mobile phones
5
Solution Objectives Continued Is highly user friendly and intuitive
The users need to provide, Starting bus stop name. Ending bus stop name.
Is capable of generating
10/18/08
Direct bus routes One interchange bus routes Grid bus routes -The future of bus services Trunk Routes Feeder Routes
6
System Architecture Commute rs
Internet
Tomcat,
2 Optimized bus routes
MySQL, Windows 2000
1 Get bus route
2 Optimized bus routes SMS
1 Get bus route SMS
NOW SMS/MMS gateway
10/18/08
7
A Prototype Implementation
A prototype software has been developed with both the internet and mobile phone access to get the bus route information
The software is developed using Java
A web application is based on Java server pages (JSP) and is deployed on Tomcat – J2EE servlet container
The backend database used for storing the bus route information is MySQL
An SMS implementation has also been developed using Now SMS/MMS gateway trial edition and Sony Ericsson mobile phone as the GSM modem
Metaphone and Soundex algorithms for spell check have been used.
10/18/08
8
The Algorithms Requirements
The following parameters are essential for the algorithm
Bus route length Total time of journey Timings of departure from the bus stations Stops the route visits Interchange points
In the case study of BMTC, we screen scraped some sample bus routes and built the database.
10/18/08
9
The Algorithms- Continued Direct Bus Routes • •
These routes are the simplest to find. Direct bus routes need not always provide time or money optimization. So routes which do not provide any of the optimizations need to be “Filtered” out.
Algorithm • •
Identify all routes that contain the starting bus stops name and ending bus stops name Ensure that the bus routes do not exceed a “Threshold” distance/time value
10/18/08
10
The AlgorithmsContinued One Interchange Routes S t a r in g S t o p
In terc h a n g e P o in t
•
Routes that need one change of bus.
•
Interchange points-These are typically stops where multiple routes intersect.
10/18/08
E n d in g S t o p
11
The Algorithms- Continued
S ta r t
I d e n ti f y A l l T h e I n te r c h a n g e P o in t s W i th i n T h e B o u n d in g R e c ta n g le C hoose A N ew I n te r c h a n g e P o in t
Algorithm
NO
A r e Th e re B u se s F r o m A t o I j?
YES
The bounding rectangle The interchange points The estimation metric Identifying routes with best metric Final constraints on the routes
NO
A r e T h er e B u se s F r o m Ij T o B ?
YES C a lc u la t e T h e M e t r ic F o r " A t o I j" a n d F o r " I j T o B " . A d d B o t h T h e M e tr ic s a n d N a m e I t A s " M e t r i c j" .
NO
H a ve A ll T he IjB e e n E x h au ste d ?
YES A rran g e T h e In te rch a n g e P o in ts I n D e cre a sin g O rd e r O f M etr ic
D is p l a y T h e T o p 3 R e s u ls
S to p
10/18/08
12
Strength of the solution
Solves route identification issues faced by people who use the metropolitan bus service. Very few cities offer this service across the world. Computationally simple The entire control lies in the estimation metric. Designed for Grid based services - The future of metropolitan bus services A generic algorithm – can be used with vehicles equipped with GPS systems, taxi routing etc
10/18/08
13
Limitations of the solution
Scalability – Cannot be scaled for ‘n’ interchange situations where n >= 2 Averaged out data – Not a good approach in solving a real world problem Soundex and Metaphone – Not the best spell check algorithms
10/18/08
14
Results
The algorithm is able to generate a fairly accurate bus routes. There is a good match between the routes suggested by the algorithm and routes actually taken by experienced bus commuters. Results obtained are better than the ones suggested by the BMTC site. Sometimes, the algorithm does not provide any “One interchange routes” if the existing bus system is not well designed. Sample Result ----Will add my programs output here---
10/18/08
15
Next Steps
Use of real time data, such as traffic congestion, time of arrival of the buses, in the algorithm Using the algorithm along with GPS services Redesigning and testing the algorithm for grid based services Making use of location services (Example-BMTC Yeliddiri service) Using maps for displaying results
10/18/08
16
Acknowledgement I would like to thank the following people who have guided me through this work
Dr.Bhanubhaskar and Dr. H N Shankar, Professors, PESIT
Mr. Bhosekar, Former Divisional Controller of BMTC Mr. Srivatsa Krishnaswamy, Director of technology and innovation, Perot Systems, Mr. Venkat Varadhan and Mrs. Lakshmi Kutty, senior architects, Hewlett Packard Mr.Anush Shetty, 8th semester Computer Science, PESIT
10/18/08
17
Akshaya Srivatsa Department of Telecommunication Engineering PESIT [email protected]
10/18/08
1
Agenda
Case Study-BMTC Problem Statement Solution Objectives System Architecture The Algorithm The Services Strengths And Limitations Next Steps Acknowledgement
10/18/08
2
Case Study-BMTC
Bangalore city has
Over 1700 bus routes Over 1100 bus stops 16 trunk routes and 14 more to be added Currently, highly disoriented bus routes
BMTC- Bangalore Metropolitan Transport Corporation
10/18/08
3
Problem Statement Current Scenario
Large number of bus stops and bus routes Difficulty in identifying good routes Public’s ignorance about the entire bus route system The bus stops are not equipped with dynamic display boards Long waiting time in bus stops due to lack of information on timing
10/18/08
4
Solution Objectives
To design a software, that
suggest routes between any two stops, after optimizing on time and distance
is accessible through
10/18/08
Internet – users can browse from their desktops Mobile phone - low priced Short Message Service [SMS], enables this service to be made available on mobile phones
5
Solution Objectives Continued Is highly user friendly and intuitive
The users need to provide, Starting bus stop name. Ending bus stop name.
Is capable of generating
10/18/08
Direct bus routes One interchange bus routes Grid bus routes -The future of bus services Trunk Routes Feeder Routes
6
System Architecture Commute rs
Internet
Tomcat,
2 Optimized bus routes
MySQL, Windows 2000
1 Get bus route
2 Optimized bus routes SMS
1 Get bus route SMS
NOW SMS/MMS gateway
10/18/08
7
A Prototype Implementation
A prototype software has been developed with both the internet and mobile phone access to get the bus route information
The software is developed using Java
A web application is based on Java server pages (JSP) and is deployed on Tomcat – J2EE servlet container
The backend database used for storing the bus route information is MySQL
An SMS implementation has also been developed using Now SMS/MMS gateway trial edition and Sony Ericsson mobile phone as the GSM modem
Metaphone and Soundex algorithms for spell check have been used.
10/18/08
8
The Algorithms Requirements
The following parameters are essential for the algorithm
Bus route length Total time of journey Timings of departure from the bus stations Stops the route visits Interchange points
In the case study of BMTC, we screen scraped some sample bus routes and built the database.
10/18/08
9
The Algorithms- Continued Direct Bus Routes • •
These routes are the simplest to find. Direct bus routes need not always provide time or money optimization. So routes which do not provide any of the optimizations need to be “Filtered” out.
Algorithm • •
Identify all routes that contain the starting bus stops name and ending bus stops name Ensure that the bus routes do not exceed a “Threshold” distance/time value
10/18/08
10
The AlgorithmsContinued One Interchange Routes S t a r in g S t o p
In terc h a n g e P o in t
•
Routes that need one change of bus.
•
Interchange points-These are typically stops where multiple routes intersect.
10/18/08
E n d in g S t o p
11
The Algorithms- Continued
S ta r t
I d e n ti f y A l l T h e I n te r c h a n g e P o in t s W i th i n T h e B o u n d in g R e c ta n g le C hoose A N ew I n te r c h a n g e P o in t
Algorithm
NO
A r e Th e re B u se s F r o m A t o I j?
YES
The bounding rectangle The interchange points The estimation metric Identifying routes with best metric Final constraints on the routes
NO
A r e T h er e B u se s F r o m Ij T o B ?
YES C a lc u la t e T h e M e t r ic F o r " A t o I j" a n d F o r " I j T o B " . A d d B o t h T h e M e tr ic s a n d N a m e I t A s " M e t r i c j" .
NO
H a ve A ll T he IjB e e n E x h au ste d ?
YES A rran g e T h e In te rch a n g e P o in ts I n D e cre a sin g O rd e r O f M etr ic
D is p l a y T h e T o p 3 R e s u ls
S to p
10/18/08
12
Strength of the solution
Solves route identification issues faced by people who use the metropolitan bus service. Very few cities offer this service across the world. Computationally simple The entire control lies in the estimation metric. Designed for Grid based services - The future of metropolitan bus services A generic algorithm – can be used with vehicles equipped with GPS systems, taxi routing etc
10/18/08
13
Limitations of the solution
Scalability – Cannot be scaled for ‘n’ interchange situations where n >= 2 Averaged out data – Not a good approach in solving a real world problem Soundex and Metaphone – Not the best spell check algorithms
10/18/08
14
Results
The algorithm is able to generate a fairly accurate bus routes. There is a good match between the routes suggested by the algorithm and routes actually taken by experienced bus commuters. Results obtained are better than the ones suggested by the BMTC site. Sometimes, the algorithm does not provide any “One interchange routes” if the existing bus system is not well designed. Sample Result ----Will add my programs output here---
10/18/08
15
Next Steps
Use of real time data, such as traffic congestion, time of arrival of the buses, in the algorithm Using the algorithm along with GPS services Redesigning and testing the algorithm for grid based services Making use of location services (Example-BMTC Yeliddiri service) Using maps for displaying results
10/18/08
16
Acknowledgement I would like to thank the following people who have guided me through this work
Dr.Bhanubhaskar and Dr. H N Shankar, Professors, PESIT
Mr. Bhosekar, Former Divisional Controller of BMTC Mr. Srivatsa Krishnaswamy, Director of technology and innovation, Perot Systems, Mr. Venkat Varadhan and Mrs. Lakshmi Kutty, senior architects, Hewlett Packard Mr.Anush Shetty, 8th semester Computer Science, PESIT
10/18/08
17
Related Documents
Bus Routing And Advisory Algorithms And Services
November 2019 3
Bus Route Identification Algorithms And Services
November 2019 2
Advisory Services
July 2020 7
