The optimal route and stops for a group of users in a road network

Radi Muhammad Reza, Mohammed Eunus Ali, Muhammad Aamir Cheema

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    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 languageEnglish
    Title of host publication25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSSPATIAL GIS 2017)
    EditorsErik Hoel, Shawn Newsam, Siva Ravada, Roberto Tamassia, Goce Trajcevski
    Place of PublicationNew York NY USA
    PublisherAssociation for Computing Machinery (ACM)
    Pages1-10
    Number of pages10
    ISBN (Print)9781450345897
    DOIs
    Publication statusPublished - 7 Nov 2017
    EventACM International Conference on Advances in Geographic Information Systems 2017 - Redondo Beach, United States of America
    Duration: 7 Nov 201710 Nov 2017
    Conference number: 25th
    https://sigspatial2017.sigspatial.org/

    Conference

    ConferenceACM International Conference on Advances in Geographic Information Systems 2017
    Abbreviated titleSIGSPATIAL 2017
    CountryUnited States of America
    CityRedondo Beach
    Period7/11/1710/11/17
    Internet address

    Keywords

    • Collective travel planning
    • Optimal route
    • Ride sharing
    • Stops

    Cite this

    Reza, R. M., Ali, M. E., & Cheema, M. A. (2017). The optimal route and stops for a group of users in a road network. In E. Hoel, S. Newsam, S. Ravada, R. Tamassia, & G. Trajcevski (Eds.), 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSSPATIAL GIS 2017) (pp. 1-10). [4] New York NY USA: Association for Computing Machinery (ACM). https://doi.org/10.1145/3139958.3140061
    Reza, Radi Muhammad ; Ali, Mohammed Eunus ; Cheema, Muhammad Aamir. / The optimal route and stops for a group of users in a road network. 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSSPATIAL GIS 2017). editor / Erik Hoel ; Shawn Newsam ; Siva Ravada ; Roberto Tamassia ; Goce Trajcevski. New York NY USA : Association for Computing Machinery (ACM), 2017. pp. 1-10
    @inproceedings{d4ed74c4ce624cd08ade3e4ed4a3ce8a,
    title = "The optimal route and stops for a group of users in a road network",
    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.",
    keywords = "Collective travel planning, Optimal route, Ride sharing, Stops",
    author = "Reza, {Radi Muhammad} and Ali, {Mohammed Eunus} and Cheema, {Muhammad Aamir}",
    year = "2017",
    month = "11",
    day = "7",
    doi = "10.1145/3139958.3140061",
    language = "English",
    isbn = "9781450345897",
    pages = "1--10",
    editor = "Erik Hoel and Shawn Newsam and Siva Ravada and Roberto Tamassia and Goce Trajcevski",
    booktitle = "25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSSPATIAL GIS 2017)",
    publisher = "Association for Computing Machinery (ACM)",
    address = "United States of America",

    }

    Reza, RM, Ali, ME & Cheema, MA 2017, The optimal route and stops for a group of users in a road network. in E Hoel, S Newsam, S Ravada, R Tamassia & G Trajcevski (eds), 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSSPATIAL GIS 2017)., 4, Association for Computing Machinery (ACM), New York NY USA, pp. 1-10, ACM International Conference on Advances in Geographic Information Systems 2017, Redondo Beach, United States of America, 7/11/17. https://doi.org/10.1145/3139958.3140061

    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 proceedingConference PaperResearchpeer-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 -

    Reza RM, Ali ME, Cheema MA. The optimal route and stops for a group of users in a road network. In Hoel E, Newsam S, Ravada S, Tamassia R, Trajcevski G, editors, 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSSPATIAL GIS 2017). New York NY USA: Association for Computing Machinery (ACM). 2017. p. 1-10. 4 https://doi.org/10.1145/3139958.3140061