Development of Algorithm to Provide Dynamic Ride Sharing in Urban Area

Development of Algorithm to Provide Dynamic Ride Sharing in Urban Area

Mira Rameshbhai Patel (M.E. Trans- Pursuing)

Civil Engineering Department

1. College of Engineering Ahmedabad, Gujarat, India

   Prof. S. B. Khara

   Professor in Civil Engineering Government Polytechnic, Himmatnagar Sabarkantha, Gujarat, India

   Abstract Car pollution is one of the major causes of greenhouse emissions, and traffic congestion is rapidly becoming a social issue. Ride Sharing has the potential to mitigate this problem, but traditional ride sharing have some limitations and so, one of the solution of the above problems can be given by dynamic Ride-share systems, which aim to bring together travelers with similar itineraries and time schedules. Real-time ridesharing attempts to provide added flexibility to rideshare arrangements by allowing drivers and passengers to arrange occasional shared rides, ahead of time or on short notice. Effective and efficient optimization technology that automatically matches drivers and riders in real-time is one of the necessary components for a successful ride-share system. So in this paper, an algorithm is developed for GIS software ArcGIS, to match commuters information effectively so that best commuters with nearly same origin-destination and time schedule can be selected for a trip.

   KeywordsPollution; Ride Sharing; GIS; ArcGIS

   1. INTRODUCTION

      During the last decades, economic growth, globalization and modernization of our society have been severely increasing our demand for mobility. Solutions that meet increasing desire for freedom of the individual are longed for.

      Basically, widely used traditional modes of transportation are private vehicles and public transport system. Private car has remained the preferred mode of transport as it is perceived as a status symbol, allows for complex travel patterns, and provides privacy and flexibility, while mass transit system is widely used as it reduce the congestion and its ill effects. But private vehicles cause negative impact on environment and traffic condition; and mass transit system is not quite flexible and reliable and thus inadequate.

      So some innovative solution is necessary and one of the solutions is to provide ride sharing system. Conventional ride sharing involves an arrangement whereby drivers wishing to form carpools, pick up passengers waiting by the roadside. One likely reason for the success of casual ride sharing has been identified as the ease and speed with which a ride may be obtained. But it is relatively inflexible and requires long term arrangements.

      Thus, dynamic or real-time ride sharing system should be provided to reduce the ill effects. Real-time ridesharing enabled by automated matching is a service that dynamically arranges shared rides. Requests for rides are received over time, each consisting of two points, an origin and a destination.

      The Ride share agency matches the information with other participants registered in the Database and identifies potential Ride share partners. The goal is to schedule requests in real- time and minimize the users traveling times with service quality guarantee. Dynamic Ride sharing attempt to provide added flexibility to rideshare arrangements by allowing drivers and passengers to arrange occasional shared rides ahead of time or on short notice.

   2. ALGORITHM

      The whole system should be such that it automatically match potential passengers according to some criteria and thus provide a flexible and reliable ride sharing system which can arrange shared rides dynamically. This objective can be achieved by the use of Geographical Information System. A user friendly interface should be developed for this, which provides input to the users. The whole map with all necessary data should be created in GIS software ArcGIS. The input from users is first of all geocoded. Matching criteria like time as well as origin and destination is considered and users are matched according to pre described criteria. First the users are matched by their preferred time of travel. Users with approximately similar time of travel are selected and then checked for other criteria. Matching for origin and destination follows three conditions: users with exactly same origin as well as destination, users who can be picked up and dropped down on the original route of driver and driver have to travel some distance to pick the passenger up. The next condition is considered only if required users are not available from the previous condition. At last, table showing matched result is sent to user via interface.

      The basic algorithm for the development of methodology for ride sharing in urban area of Income tax to Kalupur corridor, which matches passengers in real time is developed as below:

      Create Map

      User Interface

      Geocode the data

      Match passengers by time

      Match passengers with similar origin as well as destination

      If four passengers are found

      No

      Match passengers on the route of driver

      Yes

      If total four passengers are found

      first set and destination in second set are directly considered as potential requests. If the result table shown by technique contains number of users that are required, mostly four in cab service, directly show result to the user through interface, otherwise go for next selection procedure.

      To select users on the route of the driver, first of all the first request is selected and the shortest path between origin and destination of same is developed. The whole path line is buffered for suitable distance and requests with origin in first half of total route length and destination in second half of route length, from the set generated, are selected as potential users. Again, if the result table contains number of users that are required, show result to the user through interface, otherwise go for next and last selection procedure.

      To select users for whom the driver have to deviate from his original route to pick them up, first of all the first request is selected and the shortest path between origin and destination of same is developed. The origin point, destination point as well as whole path line is buffered for suitable distance and three different result sets are generated accordingly. Requests with origin in first set or in second set (after deducting the overlapping portion of second and third set) as well as destination in third set are selected. The result is shown to user.

      The detailed algorithm along with ArcGIS software tools use is developed as under:

      Match passengers for whom driver have to deviate from his route to pick them up

      Table of result

      User Interface

      Figure 2: Basic Algorithm

      To provide flexibility to the user of ride sharing system, an user friendly interface should be made in which user can input his/her name, origin, destination, time of travel and other necessary information. This should than link to the ArcGIS software in which it will be analyzed to select potential users.

      In ArcGIS software, the map of the area should be made along with the road network of the area. Address of each location along with its longitude and latitude is saved in a table to form a dataset. The address requests given by users in the form of origin and destination are then geocoded. System should be developed so that it will ask user to correct or to input some other name of location until the result matches with the database.

      First of all, requests with approximately similar travel time are selected as potential users requests. Then to selet requests with exactly same origin and destination, the very first request is selected and buffered for zero linear distance. Two sets of result will be generated, out of which requests with origin in

      User Interface

      Enter Data of travel

      X-Y coordinates

      Geocode data according to database

   3. CONCLUSION

Create map

To reduce the ill effects and inadequacy of travel modes traditionally used, some innovative approach is necessary and so dynamic ride sharing with automatic matching and scheduling facility to provide flexibility and reliability in real- time is proposed. Formal definition of dynamic or real-time ride sharing is given and algorithm to provide an automatic matching system in ArcGIS software is developed along with a user friendly interface.

No

Yes

If matches with data

Yes

Selection according to similar time of travel

Create zero buffer around origin and destination of first request and users with origin in origin buffer zone and destination in destination zone

If total four users

No

Find the shortest path between origin and destination of first user

REFERENCES

1. Alan Erera et al, Sustainable Passenger Transportation: Dynamic Ride- Sharing, 2009.

2. Ali Haghani et al, Real-Time Rideshare Matching Problem,2009.

3. I.S. Jacobs and C.P. Bean, Fine particles, thin films and exchange anisotropy, in Magnetism, vol. III, G.T. Rado and H. Suhl, Eds. New York: Academic, 1963, pp. 271-350.

4. Niels Agatz et al, Optimization for dynamic ride-sharing: A review European Journal of Operational Research, 223, 295303,2012

5. Sasha dos Santos, A Geographical Information System for Dynamic Ride matching , Graduate School Theses and Dissertations, 2005.

Buffer around origin, destination and route line

Yes

If total four users

No

Find the shortest path between origin and destination of first user

Buffer around origin, destination and route line

Find requests with origin in buffer zone of origin or line by deducting the origins in overlapping portion of line with destination zone and destination in buffer zone of destination

Create result table of all potential request with trip ID, origin, destination and time

User Interface showing match

Figure 2: Detail Algorithm