More Web Proxy on the site http://driver.im/

research-article

Open access

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

Authors:

Sreenivas Gollapudi,

Kostas Kollias,

Debmalya PanigrahiAuthors Info & Claims

SIGSPATIAL '22: Proceedings of the 30th International Conference on Advances in Geographic Information Systems

Article No.: 47, Pages 1 - 9

https://doi.org/10.1145/3557915.3560982

Published: 22 November 2022 Publication History

Abstract

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.

References

[1]

Vural Aksakalli, O. Furkan Sahin, and Ibrahim Ari. 2016. An AO^* Based Exact Algorithm for the Canadian Traveler Problem. INFORMS J. Comput. 28, 1 (2016), 96--111.

Digital Library

[2]

Saeed Alaei. 2014. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43, 2 (2014), 930--972.

[3]

N. Bansal, A. Blum, S. Chawla, and A. Meyerson. 2004. Approximation algorithms for deadline-TSP and vehicle routing with time-windows. In STOC. 166--174.

[4]

Amotz Bar-Noy and Baruch Schieber. 1991. The Canadian Traveller Problem. In Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms. 261--270.

Digital Library

[5]

A. Blum, S. Chawla, D. R. Karger, T. Lane, A. Meyerson, and M. Minkoff. 2007. Approximation algorithms for orienteering and discounted-reward TSP. SIAM J. Comput. 37, 2 (2007), 653--670.

Digital Library

[6]

M. Charikar, S. Khuller, and B. Raghavachari. 2001. Algorithms for capacitated vehicle routing. SIAM J. Comput. 31, 3 (2001), 665--682.

Digital Library

[7]

M. Charikar and B. Raghavachari. 1998. The finite capacity dial-a-ride problem. In FOCS. 458--467.

[8]

C. Chekuri, N. Korula, and M. Pál. 2012. Improved algorithms for orienteering and related problems. ACM Trans. Algorithms 8, 3 (2012), 23:1--23:27.

Digital Library

[9]

T. Chen, B. Zhang, H. Pourbabak, A. Kavousi-Fard, and W. Su. 2018. Optimal Routing and Charging of an Electric Vehicle Fleet for High-Efficiency Dynamic Transit Systems. IEEE Transactions on Smart Grid 9, 4 (2018), 3563--3572.

[10]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. 2009. Introduction to Algorithms (3. ed.). MIT Press.

[11]

DHL. [n.d.]. Self Driving Vehicles in Logistics. http://https://www.dhl.com/content/dam/downloads/g0/about_us/logistics_insights/dhl_self_driving_vehicles.pdf.

[12]

E. B. Dynkin. 1963. Optimal choice of the stopping moment of a Markov process. Dokl. Akad. Nauk SSSR 150 (1963), 238--240. Issue 2.

[13]

Patrick Eyerich, Thomas Keller, and Malte Helmert. 2010. High-Quality Policies for the Canadian Traveler's Problem. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11--15, 2010.

[14]

P. R. Freeman. 1983. The Secretary Problem and Its Extensions: A Review. International Statistical Review / Revue Internationale de Statistique 51, 2 (1983), 189--206.

[15]

B. L. Golden and A. A. Assad (Eds.). 1988. Vehicle Routing: Methods and Studies. Studies in Management Science and Systems, Vol. 16. North-Holland, Amsterdam.

[16]

I. L. Gørtz, V. Nagarajan, and R. Ravi. 2015. Minimum makespan multi-vehicle dial-a-ride. ACM Trans. Algorithms 11, 3 (2015), 23:1--23:29.

Digital Library

[17]

A. Gupta, M. T. Hajiaghayi, V. Nagarajan, and R. Ravi. 2010. Dial a ride from k-forest. ACM Trans. Algorithms 6, 2 (2010), 41:1--41:21.

Digital Library

[18]

M. Haimovich and A. H. G. Rinnooy Kan. 1985. Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10, 4 (1985), 527--542.

Digital Library

[19]

Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, and Tuomas Sandholm. 2007. Automated Online Mechanism Design and Prophet Inequalities. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence. 58--65.

[20]

DP Kennedy. 1987. Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their Applications 24, 1 (1987), 77--88.

[21]

Samir Khuller, Azarakhsh Malekian, and Julián Mestre. 2011. To fill or not to fill: The gas station problem. ACM Trans. Algorithms 7, 3 (2011), 36:1--36:16.

Digital Library

[22]

Robert Kleinberg. 2005. A multiple-choice secretary algorithm with applications to online auctions. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 630--631.

Digital Library

[23]

Ulrich Krengel and Louis Sucheston. 1977. Semiamarts and finite values. Bull. Amer. Math. Soc. 83, 4 (1977), 745--747.

[24]

Ulrich Krengel and Louis Sucheston. 1978. On semiamarts, amarts, and processes with finite value. Probability on Banach spaces 4 (1978), 197--266.

[25]

C-L. Li and D. Simchi-Levi. 1990. Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems. INFORMS Journal on Computing 2, 1 (1990), 64--73.

[26]

Jane Lin, Wei Zhou, and Ouri Wolfson. 2016. Electric vehicle routing problem. Transportation Research Procedia 12, Supplement C (2016), 508--521.

[27]

D. V. Lindley. 1961. Dynamic Programming and Decision Theory. Journal of the Royal Statistical Society. Series C (Applied Statistics) 10, 1 (1961), 39--51.

[28]

Evdokia Nikolova and David Karger. 2008. Route Planning under Uncertainty: The Canadian Traveller Problem. In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI. 969--974.

[29]

Christos Papadimitriou and Mihalis Yannakakis. 1991. Shortest paths without a map. Theoretical Computer Science 84 (1991), 127--150.

Digital Library

[30]

Martin Sachenbacher, Martin Leucker, Andreas Artmeier, and Julian Haselmayr. 2011. Efficient energy-optimal routing for electric vehicles. In Twenty-fifth AAAI conference on artificial intelligence.

Digital Library

[31]

Ester Samuel-Cahn. 1984. Comparison of Threshold Stop Rules and Maximum for Independent Nonnegative Random Variables. The Annals of Probability 12, 4 (1984), 1213--1216.

[32]

P. Toth and D. Vigo (Eds.). 2001. The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA.

[33]

H. Yang, Y. Deng, J. Qiu, M. Li, M. Lai, and Z. Y. Dong. 2017. Electric Vehicle Route Selection and Charging Navigation Strategy Based on Crowd Sensing. IEEE Transactions on Industrial Informatics 13, 5 (2017), 2214--2226.

Cited By

Jiang WZhou JZhu JSu GWang F(2025)FRI: a firefighter risk index using spatiotemporal modelling of wildfire spread and individual travelInternational Journal of Disaster Risk Reduction10.1016/j.ijdrr.2024.105151(105151)Online publication date: Jan-2025
https://doi.org/10.1016/j.ijdrr.2024.105151

Index Terms

The pit stop problem: how to plan your next road trip
1. Information systems
  1. Information systems applications
    1. Spatial-temporal systems
      1. Geographic information systems
2. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms

Recommendations

The Pit Stop Problem: How to Plan Your Next Road Trip
WSDM '22: Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining

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 ...
The Electric Vehicle Routing Problem with Capacitated Charging Stations
Electric vehicle routing problems (E-VRPs) deal with routing a fleet of electric vehicles (EVs) to serve a set of customers while minimizing an operational criterion, for example, cost or time. The feasibility of the routes is constrained by the autonomy ...
Network Flow Problems with Electric Vehicles
Integer Programming and Combinatorial Optimization
Abstract
Electric vehicle (EV) adoption in long-distance logistics faces challenges such as range anxiety and uneven distribution of charging stations. Two pivotal questions emerge: How can EVs be efficiently routed in a charging network considering range ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSPATIAL '22: Proceedings of the 30th International Conference on Advances in Geographic Information Systems

November 2022

806 pages

ISBN:9781450395298

DOI:10.1145/3557915

General Chairs:
Matthias Renz
Kiel University, Germany
,
Mohamed Sarwat
Wherobots Inc. / Arizona State University

Copyright © 2022 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGSPATIAL: ACM Special Interest Group on Spatial Information

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 November 2022

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF
ARO

Conference

SIGSPATIAL '22

Sponsor:

SIGSPATIAL

SIGSPATIAL '22: The 30th International Conference on Advances in Geographic Information Systems

November 1 - 4, 2022

Washington, Seattle

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
308
Total Downloads

Downloads (Last 12 months)155
Downloads (Last 6 weeks)20

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jiang WZhou JZhu JSu GWang F(2025)FRI: a firefighter risk index using spatiotemporal modelling of wildfire spread and individual travelInternational Journal of Disaster Risk Reduction10.1016/j.ijdrr.2024.105151(105151)Online publication date: Jan-2025
https://doi.org/10.1016/j.ijdrr.2024.105151

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents