Skip to main content

The pit stop problem: how to plan your next road trip

Publication ,  Conference
Gollapudi, S; Kollias, K; Panigrahi, D
Published in: GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
November 1, 2022

Many online trip planning and navigation software need to routinely solve the problem of deciding where to take stops during a journey for various services such as refueling (or EV charging), rest stops, food, etc. The goal is to minimize the overhead of these stops while ensuring that the traveller is not starved of any essential resource (such as fuel, rest, or food) during the journey. In this paper, we formally model this problem and call it the pit stop problem. We design algorithms for this problem under various settings: single vs multiple types of stops, and offline vs online optimization (i.e., in advance of or during the trip). Our algorithms achieve provable guarantees in terms of approximating the optimal solution. We then extensively evaluate our algorithms on real world data and demonstrate that they significantly outperform baseline solutions.

Duke Scholars

Published In

GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems

DOI

Publication Date

November 1, 2022
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Gollapudi, S., Kollias, K., & Panigrahi, D. (2022). The pit stop problem: how to plan your next road trip. In GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems. https://doi.org/10.1145/3557915.3560982
Gollapudi, S., K. Kollias, and D. Panigrahi. “The pit stop problem: how to plan your next road trip.” In GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 2022. https://doi.org/10.1145/3557915.3560982.
Gollapudi S, Kollias K, Panigrahi D. The pit stop problem: how to plan your next road trip. In: GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems. 2022.
Gollapudi, S., et al. “The pit stop problem: how to plan your next road trip.” GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 2022. Scopus, doi:10.1145/3557915.3560982.
Gollapudi S, Kollias K, Panigrahi D. The pit stop problem: how to plan your next road trip. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems. 2022.

Published In

GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems

DOI

Publication Date

November 1, 2022