Abstract
The rise of innovative transportation services and the recent breakthrough in the development of autonomous vehicles have stimulated the research on collective travel planning problems such as ride-sharing, carpooling, and on-demand vehicle routing in recent years. In this paper, we introduce several optimization problems to recommend a suitable route and stops of a vehicle, in a road network, for a group of users intending to travel collectively. The goal of each problem is to minimize the aggregate cost of the individual travelers’ paths and the shared route under various constraints. First, we introduce the optimal end-stops (OES) query that finds a pair of pick-up-and-drop-off locations such that the sum of the distance between these locations and the total distance traveled by the travelers from their start locations to the pick-up location and from the drop-off location to their end locations is minimized. We propose a polynomial-time fast algorithm for the OES query by utilizing the path-coherence property of road networks. Second, we formulate the optimal route and intermediate stops (ORIS) query to find a set of intermediate stops for the vehicle such that the sum of the total distance traveled by the vehicle and the total distance traveled by the travelers from their start locations to one of the stops and to their end locations from one of the stops is minimized. We propose a novel near-optimal polynomial-time-and-space heuristic algorithm for the ORIS query that performs reasonably well in practice. We also analyze several variants of this problem. Finally, we perform extensive experiments to demonstrate the efficiency and efficacy of our algorithms.
| Original language | English |
|---|---|
| Title of host publication | 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSSPATIAL GIS 2017) |
| Editors | Erik Hoel, Shawn Newsam, Siva Ravada, Roberto Tamassia, Goce Trajcevski |
| Place of Publication | New York NY USA |
| Publisher | Association for Computing Machinery (ACM) |
| Pages | 1-10 |
| Number of pages | 10 |
| ISBN (Print) | 9781450345897 |
| DOIs | |
| Publication status | Published - 7 Nov 2017 |
| Event | ACM International Conference on Advances in Geographic Information Systems 2017 - Redondo Beach, United States of America Duration: 7 Nov 2017 → 10 Nov 2017 Conference number: 25th https://sigspatial2017.sigspatial.org/ |
Conference
| Conference | ACM International Conference on Advances in Geographic Information Systems 2017 |
|---|---|
| Abbreviated title | SIGSPATIAL 2017 |
| Country | United States of America |
| City | Redondo Beach |
| Period | 7/11/17 → 10/11/17 |
| Internet address |
Keywords
- Collective travel planning
- Optimal route
- Ride sharing
- Stops
Cite this
}
The optimal route and stops for a group of users in a road network. / Reza, Radi Muhammad; Ali, Mohammed Eunus; Cheema, Muhammad Aamir.
25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSSPATIAL GIS 2017). ed. / Erik Hoel; Shawn Newsam; Siva Ravada; Roberto Tamassia; Goce Trajcevski. New York NY USA : Association for Computing Machinery (ACM), 2017. p. 1-10 4.Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review
TY - GEN
T1 - The optimal route and stops for a group of users in a road network
AU - Reza, Radi Muhammad
AU - Ali, Mohammed Eunus
AU - Cheema, Muhammad Aamir
PY - 2017/11/7
Y1 - 2017/11/7
N2 - The rise of innovative transportation services and the recent breakthrough in the development of autonomous vehicles have stimulated the research on collective travel planning problems such as ride-sharing, carpooling, and on-demand vehicle routing in recent years. In this paper, we introduce several optimization problems to recommend a suitable route and stops of a vehicle, in a road network, for a group of users intending to travel collectively. The goal of each problem is to minimize the aggregate cost of the individual travelers’ paths and the shared route under various constraints. First, we introduce the optimal end-stops (OES) query that finds a pair of pick-up-and-drop-off locations such that the sum of the distance between these locations and the total distance traveled by the travelers from their start locations to the pick-up location and from the drop-off location to their end locations is minimized. We propose a polynomial-time fast algorithm for the OES query by utilizing the path-coherence property of road networks. Second, we formulate the optimal route and intermediate stops (ORIS) query to find a set of intermediate stops for the vehicle such that the sum of the total distance traveled by the vehicle and the total distance traveled by the travelers from their start locations to one of the stops and to their end locations from one of the stops is minimized. We propose a novel near-optimal polynomial-time-and-space heuristic algorithm for the ORIS query that performs reasonably well in practice. We also analyze several variants of this problem. Finally, we perform extensive experiments to demonstrate the efficiency and efficacy of our algorithms.
AB - The rise of innovative transportation services and the recent breakthrough in the development of autonomous vehicles have stimulated the research on collective travel planning problems such as ride-sharing, carpooling, and on-demand vehicle routing in recent years. In this paper, we introduce several optimization problems to recommend a suitable route and stops of a vehicle, in a road network, for a group of users intending to travel collectively. The goal of each problem is to minimize the aggregate cost of the individual travelers’ paths and the shared route under various constraints. First, we introduce the optimal end-stops (OES) query that finds a pair of pick-up-and-drop-off locations such that the sum of the distance between these locations and the total distance traveled by the travelers from their start locations to the pick-up location and from the drop-off location to their end locations is minimized. We propose a polynomial-time fast algorithm for the OES query by utilizing the path-coherence property of road networks. Second, we formulate the optimal route and intermediate stops (ORIS) query to find a set of intermediate stops for the vehicle such that the sum of the total distance traveled by the vehicle and the total distance traveled by the travelers from their start locations to one of the stops and to their end locations from one of the stops is minimized. We propose a novel near-optimal polynomial-time-and-space heuristic algorithm for the ORIS query that performs reasonably well in practice. We also analyze several variants of this problem. Finally, we perform extensive experiments to demonstrate the efficiency and efficacy of our algorithms.
KW - Collective travel planning
KW - Optimal route
KW - Ride sharing
KW - Stops
UR - http://www.scopus.com/inward/record.url?scp=85040968038&partnerID=8YFLogxK
U2 - 10.1145/3139958.3140061
DO - 10.1145/3139958.3140061
M3 - Conference Paper
SN - 9781450345897
SP - 1
EP - 10
BT - 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSSPATIAL GIS 2017)
A2 - Hoel, Erik
A2 - Newsam, Shawn
A2 - Ravada, Siva
A2 - Tamassia, Roberto
A2 - Trajcevski, Goce
PB - Association for Computing Machinery (ACM)
CY - New York NY USA
ER -