際際滷

際際滷Share a Scribd company logo

Presentation v2

Download as PPTX, PDF
Sanchit Khattry
Sanchit Khattry

This document describes a major technical project on vehicle sharing. It involves clustering cities using the K-means algorithm to assign user requests for transportation between sources and destinations to drivers. The project formalizes the routing and allocation problem and describes implementing an optimization module to solve it, with references provided for related work. Future work involves tailoring an algorithm to the specific project needs.

1 of 15
Download to read offline
Vehicle Sharing Major Technical Project Damini Singal (B10107) Sanchit Khattry (B10029) Final Year, Computer Science and Engineering
User ID Source Destination Date of Journey Time of Journey Max Detour Dist Preferences User ID :user1 Source :Chandigarh Destination :Delhi Date of Journey :14 November 2014 Time of Journey :21:00 Max Waiting Time:15 minutes Preferences :Age > 35, Male :user2 :Mandi :Roorkee :14 November 2014 :19:30 :6 km :None
Number of Clusters 3
City Name Coordinates Cluster id Cluster centroid Mandi 31.70817,76.93137 0 31.470200000000006,76.61453285714286 Hamirpur 31.6861,76.52131 0 31.470200000000006,76.61453285714286 Ner Chowk 31.60852,76.91533 0 31.470200000000006,76.61453285714286 Chandigarh 30.73331,76.77942 1 30.550172500000002,76.21847500000001 Shimla 31.10461,77.17342 0 31.470200000000006,76.61453285714286 Patiala 30.32062,76.39513 1 30.550172500000002,76.21847500000001 Dehradun 30.31649,78.03219 2 29.972666,77.836818 Muzaffarnagar 29.47268,77.70851 2 29.972666,77.836818 Rishikesh 30.08693,78.26761 2 29.972666,77.836818 Roorkee 29.85426,77.888 2 29.972666,77.836818 Ghumarwin 31.44192,76.71208 0 31.470200000000006,76.61453285714286 Hoshiarpur 31.52798,75.91375 0 31.470200000000006,76.61453285714286 Garhshankar 31.2141,76.13447 0 31.470200000000006,76.61453285714286 Ludhiana 30.90096,75.85728 1 30.550172500000002,76.21847500000001 Sangrur 30.2458,75.84207 1 30.550172500000002,76.21847500000001 Yamunanagar 30.13297,77.28778 2 29.972666,77.836818 Using K Means Algorithm To Cluster the Cities (K = 3)
Clustering Problem Clustering problem Classifying similar data items into clusters (high similarity among the points, dissimilar to points in other clusters) Input: Collection of nodes with the inputs User ID, Source, Destination, Time of journey, Tolerances (Time and distance) Output: User ID with the assigned Cluster ID Na誰ve ways to select features: Geographical location (Source) Chronological order (Time of Journey)
But the question that arises is how can we combine the features of both Time and Geographical Locations to create clusters for the given problem?
What if there is a passenger at Chandigarh or Shimla? Path taken by these Can pickup passengers at points without any change in Driver without route extra passengers
What problems arise? Say the driver picks up the passenger at Chandigarh following an alternate route Detour Tolerance of the Driver The system thus demands an Passenger Wait Time optimal routing algorithm which takes care of these and various Feasibility of the alternate other such factors involved route (traffic, road conditions etc.) Seat availability
But what about Hamirpur which is outside the tolerance limit by just 50 m? Problem! Say, Rupnagar, Chandigarh and Ambala Cantt are within the tolerance limit When will a passenger not get picked up? When lying outside the tolerance limit Set of requests close to the driver route When the driver denies Close here means within the detour tolerance of the driver.
Algorithm overview Start2 Start1 Laydown driver paths Destination1 Those lying within the routes are routed without any problem and the path is But what about these? Expand the width of the route as modified per the drivers detour tolerance Detour Tolerance2 Detour Tolerance1 Destination2 Fetch the set of requests Where is one request
Formalizing the problem Given sets of driver journey details: Di = {d_id, s, d, det, cap} Di = Driver i d_id = Driver ID s = Source Location d = Destination det = Detour Tolerance cap = Car capacity Given sets of passenger requests: Pi = {p_id, s, d, wt, num} Pi = Passenger i p_id = Passenger ID s = Source Location d = Destination wt = Wait Tolerance num = Number of Passengers
Formalizing the problem (contd.) The engine will give output sets as follows: Let D = {D1, D2, D3, , Di} P = {P1, P2, P3, , Pi} (J, RemP) = f(D, P) J = Sets of journeys {J1, J2, , Ji} Ji = {j_id, d_id, p_id} f = Routing and Allocation algorithm function j_id = Journey ID D = Driver P = Passenger RemP = Set of passengers who remain unallocated at the end of the current iteration
Routing and Allocation Implementation For routing and allocation in the first iteration we are using the implementation of round trip and A-Z trip over Google Maps API. A working module could be found at http://optimap.net/ The module implements the following algorithms: * Brute Force: Runtime O(n-1!) * Ant Colony along with local K2 optimization: Runtime O(numWaves * numAnts * n ^ 2) for ACO and O(numWaves * numAnts * n ^ 3) for rewiring Future Plan: Plugging in an algorithm to the module tailored to the project
Project Implementation
References 1. Manel, Sghaier, et al. "A distributed dijkstra's algorithm for the implementation of a Real Time Carpooling Service with an optimized aspect on siblings." the 14Th International IEEE Annual Conference on Intelligent Transportation Systems (ITSC 2011). 2011. 2. Chekuri, C., Korula, N., & P叩l, M. (2012). Improved algorithms for orienteering and related problems. ACM Transactions on Algorithms (TALG), 8(3), 23. 3. Agatz, N. A. H., Erera, A., Savelsbergh, M. W. P., & Wang, X. (2010).Sustainable passenger transportation: Dynamic ride-sharing (No. ERS-2010-010-LIS). Erasmus Research Institute of Management (ERIM). 4. Chao, I., Golden, B. L., & Wasil, E. A. (1996). A fast and effective heuristic for the orienteering problem. European Journal of Operational Research, 88(3), 475-489. 5. Chao, I., Golden, B. L., & Wasil, E. A. (1996). The team orienteering problem.European journal of operational research, 88(3), 464-474. 6. Lyft, Peer-to-peer ridesharing mobile application, http://www.lyft.com

More Related Content

Presentation v2

  • 1. Vehicle Sharing Major Technical Project Damini Singal (B10107) Sanchit Khattry (B10029) Final Year, Computer Science and Engineering
  • 2. User ID Source Destination Date of Journey Time of Journey Max Detour Dist Preferences User ID :user1 Source :Chandigarh Destination :Delhi Date of Journey :14 November 2014 Time of Journey :21:00 Max Waiting Time:15 minutes Preferences :Age > 35, Male :user2 :Mandi :Roorkee :14 November 2014 :19:30 :6 km :None
  • 4. City Name Coordinates Cluster id Cluster centroid Mandi 31.70817,76.93137 0 31.470200000000006,76.61453285714286 Hamirpur 31.6861,76.52131 0 31.470200000000006,76.61453285714286 Ner Chowk 31.60852,76.91533 0 31.470200000000006,76.61453285714286 Chandigarh 30.73331,76.77942 1 30.550172500000002,76.21847500000001 Shimla 31.10461,77.17342 0 31.470200000000006,76.61453285714286 Patiala 30.32062,76.39513 1 30.550172500000002,76.21847500000001 Dehradun 30.31649,78.03219 2 29.972666,77.836818 Muzaffarnagar 29.47268,77.70851 2 29.972666,77.836818 Rishikesh 30.08693,78.26761 2 29.972666,77.836818 Roorkee 29.85426,77.888 2 29.972666,77.836818 Ghumarwin 31.44192,76.71208 0 31.470200000000006,76.61453285714286 Hoshiarpur 31.52798,75.91375 0 31.470200000000006,76.61453285714286 Garhshankar 31.2141,76.13447 0 31.470200000000006,76.61453285714286 Ludhiana 30.90096,75.85728 1 30.550172500000002,76.21847500000001 Sangrur 30.2458,75.84207 1 30.550172500000002,76.21847500000001 Yamunanagar 30.13297,77.28778 2 29.972666,77.836818 Using K Means Algorithm To Cluster the Cities (K = 3)
  • 5. Clustering Problem Clustering problem Classifying similar data items into clusters (high similarity among the points, dissimilar to points in other clusters) Input: Collection of nodes with the inputs User ID, Source, Destination, Time of journey, Tolerances (Time and distance) Output: User ID with the assigned Cluster ID Na誰ve ways to select features: Geographical location (Source) Chronological order (Time of Journey)
  • 6. But the question that arises is how can we combine the features of both Time and Geographical Locations to create clusters for the given problem?
  • 7. What if there is a passenger at Chandigarh or Shimla? Path taken by these Can pickup passengers at points without any change in Driver without route extra passengers
  • 8. What problems arise? Say the driver picks up the passenger at Chandigarh following an alternate route Detour Tolerance of the Driver The system thus demands an Passenger Wait Time optimal routing algorithm which takes care of these and various Feasibility of the alternate other such factors involved route (traffic, road conditions etc.) Seat availability
  • 9. But what about Hamirpur which is outside the tolerance limit by just 50 m? Problem! Say, Rupnagar, Chandigarh and Ambala Cantt are within the tolerance limit When will a passenger not get picked up? When lying outside the tolerance limit Set of requests close to the driver route When the driver denies Close here means within the detour tolerance of the driver.
  • 10. Algorithm overview Start2 Start1 Laydown driver paths Destination1 Those lying within the routes are routed without any problem and the path is But what about these? Expand the width of the route as modified per the drivers detour tolerance Detour Tolerance2 Detour Tolerance1 Destination2 Fetch the set of requests Where is one request
  • 11. Formalizing the problem Given sets of driver journey details: Di = {d_id, s, d, det, cap} Di = Driver i d_id = Driver ID s = Source Location d = Destination det = Detour Tolerance cap = Car capacity Given sets of passenger requests: Pi = {p_id, s, d, wt, num} Pi = Passenger i p_id = Passenger ID s = Source Location d = Destination wt = Wait Tolerance num = Number of Passengers
  • 12. Formalizing the problem (contd.) The engine will give output sets as follows: Let D = {D1, D2, D3, , Di} P = {P1, P2, P3, , Pi} (J, RemP) = f(D, P) J = Sets of journeys {J1, J2, , Ji} Ji = {j_id, d_id, p_id} f = Routing and Allocation algorithm function j_id = Journey ID D = Driver P = Passenger RemP = Set of passengers who remain unallocated at the end of the current iteration
  • 13. Routing and Allocation Implementation For routing and allocation in the first iteration we are using the implementation of round trip and A-Z trip over Google Maps API. A working module could be found at http://optimap.net/ The module implements the following algorithms: * Brute Force: Runtime O(n-1!) * Ant Colony along with local K2 optimization: Runtime O(numWaves * numAnts * n ^ 2) for ACO and O(numWaves * numAnts * n ^ 3) for rewiring Future Plan: Plugging in an algorithm to the module tailored to the project
  • 15. References 1. Manel, Sghaier, et al. "A distributed dijkstra's algorithm for the implementation of a Real Time Carpooling Service with an optimized aspect on siblings." the 14Th International IEEE Annual Conference on Intelligent Transportation Systems (ITSC 2011). 2011. 2. Chekuri, C., Korula, N., & P叩l, M. (2012). Improved algorithms for orienteering and related problems. ACM Transactions on Algorithms (TALG), 8(3), 23. 3. Agatz, N. A. H., Erera, A., Savelsbergh, M. W. P., & Wang, X. (2010).Sustainable passenger transportation: Dynamic ride-sharing (No. ERS-2010-010-LIS). Erasmus Research Institute of Management (ERIM). 4. Chao, I., Golden, B. L., & Wasil, E. A. (1996). A fast and effective heuristic for the orienteering problem. European Journal of Operational Research, 88(3), 475-489. 5. Chao, I., Golden, B. L., & Wasil, E. A. (1996). The team orienteering problem.European journal of operational research, 88(3), 464-474. 6. Lyft, Peer-to-peer ridesharing mobile application, http://www.lyft.com