IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v59y2012i5p325-339.html
   My bibliography  Save this article

Optimal path finding in direction, location, and time dependent environments

Author

Listed:
  • Irina S. Dolinskaya

Abstract

This article examines optimal path finding problems where cost function and constraints are direction, location, and time dependent. Recent advancements in sensor and data‐processing technology facilitate the collection of detailed real‐time information about the environment surrounding a ground vehicle, an airplane, or a naval vessel. We present a navigation model that makes use of such information. We relax a number of assumptions from existing literature on path‐finding problems and create an accurate, yet tractable, model suitable for implementation for a large class of problems. We present a dynamic programming model which integrates our earlier results for direction‐dependent, time and space homogeneous environment, and consequently, improves its accuracy, efficiency, and run‐time. The proposed path finding model also addresses limited information about the surrounding environment, control‐feasibility of the considered paths, such as sharpest feasible turns a vehicle can make, and computational demands of a time‐dependent environment. To demonstrate the applicability and performance of our path‐finding algorithm, computational experiments for a short‐range ship routing in dynamic wave‐field problem are presented. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012

Suggested Citation

  • Irina S. Dolinskaya, 2012. "Optimal path finding in direction, location, and time dependent environments," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(5), pages 325-339, August.
    • Handle: RePEc:wly:navres:v:59:y:2012:i:5:p:325-339
    DOI: 10.1002/nav.21492
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.21492
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.21492?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Stuart E. Dreyfus, 1969. "An Appraisal of Some Shortest-Path Algorithms," Operations Research, INFORMS, vol. 17(3), pages 395-412, June.
    2. Jeffrey M. Alden & Robert L. Smith, 1992. "Rolling Horizon Procedures in Nonhomogeneous Markov Decision Processes," Operations Research, INFORMS, vol. 40(3-supplem), pages 183-194, June.
    3. Anastassios N. Perakis & Nikiforos A. Papadakis, 1989. "Minimal Time Vessel Routing in a Time-Dependent Environment," Transportation Science, INFORMS, vol. 23(4), pages 266-276, November.
    4. Nikiforos A. Papadakis & Anastassios N. Perakis, 1990. "Deterministic Minimal Time Vessel Routing," Operations Research, INFORMS, vol. 38(3), pages 426-438, June.
    5. Philpott, A. B. & Sullivan, R. M. & Jackson, P. S., 1993. "Yacht velocity prediction using mathematical programming," European Journal of Operational Research, Elsevier, vol. 67(1), pages 13-24, May.
    6. Chung-Yee Lee & Eric V. Denardo, 1986. "Rolling Planning Horizons: Error Bounds for the Dynamic Lot Size Model," Mathematics of Operations Research, INFORMS, vol. 11(3), pages 423-432, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Irina S. Dolinskaya & Marina A. Epelman & Esra Şişikoğlu Sir & Robert L. Smith, 2016. "Parameter-Free Sampled Fictitious Play for Solving Deterministic Dynamic Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 169(2), pages 631-655, May.
    2. Shuaian Wang & Dan Zhuge & Lu Zhen & Chung-Yee Lee, 2021. "Liner Shipping Service Planning Under Sulfur Emission Regulations," Transportation Science, INFORMS, vol. 55(2), pages 491-509, March.
    3. Suresh Chand & Vernon Ning Hsu & Suresh Sethi, 2002. "Forecast, Solution, and Rolling Horizons in Operations Management Problems: A Classified Bibliography," Manufacturing & Service Operations Management, INFORMS, vol. 4(1), pages 25-43, September.
    4. Meng, Qiang & Du, Yuquan & Wang, Yadong, 2016. "Shipping log data based container ship fuel efficiency modeling," Transportation Research Part B: Methodological, Elsevier, vol. 83(C), pages 207-229.
    5. Ryan, Sarah M., 1998. "Forecast frequency in rolling horizon hedging heuristics for capacity expansion," European Journal of Operational Research, Elsevier, vol. 109(3), pages 550-558, September.
    6. Lo, Hong K. & McCord, Mark R., 1998. "Adaptive ship routing through stochastic ocean currents: general formulations and empirical results," Transportation Research Part A: Policy and Practice, Elsevier, vol. 32(7), pages 547-561, September.
    7. Lo, Hong K. & McCord, Mark R., 1995. "Routing through dynamic ocean currents: General heuristics and empirical results in the gulf stream region," Transportation Research Part B: Methodological, Elsevier, vol. 29(2), pages 109-124, April.
    8. Eugenio Vecchia & Silvia Marco & Alain Jean-Marie, 2012. "Illustrated review of convergence conditions of the value iteration algorithm and the rolling horizon procedure for average-cost MDPs," Annals of Operations Research, Springer, vol. 199(1), pages 193-214, October.
    9. Stanislaw Bylka, 1997. "Strong turnpike policies in the single‐item capacitated lot‐sizing problem with periodical dynamic parameter," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(8), pages 775-790, December.
    10. Pijls, Wim & Post, Henk, 2009. "A new bidirectional search algorithm with shortened postprocessing," European Journal of Operational Research, Elsevier, vol. 198(2), pages 363-369, October.
    11. Yang, Jinling & Chen, Zhiwei & Criado, Regino & Zhang, Shenggui, 2024. "A mathematical framework for shortest path length computation in multi-layer networks with inter-edge weighting and dynamic inter-edge weighting: The case of the Beijing bus network, China," Chaos, Solitons & Fractals, Elsevier, vol. 182(C).
    12. Dimitri P. Bertsekas, 2019. "Robust shortest path planning and semicontractive dynamic programming," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(1), pages 15-37, February.
    13. Yueyue Fan & Yu Nie, 2006. "Optimal Routing for Maximizing the Travel Time Reliability," Networks and Spatial Economics, Springer, vol. 6(3), pages 333-344, September.
    14. Sinitskaya, Ekaterina & Tesfatsion, Leigh, 2015. "Macroeconomies as constructively rational games," Journal of Economic Dynamics and Control, Elsevier, vol. 61(C), pages 152-182.
    15. A. B. Philpott & S. G. Henderson & D. Teirney, 2004. "A Simulation Model for Predicting Yacht Match Race Outcomes," Operations Research, INFORMS, vol. 52(1), pages 1-16, February.
    16. Azar Sadeghnejad-Barkousaraie & Rajan Batta & Moises Sudit, 2017. "Convoy movement problem: a civilian perspective," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 14-33, January.
    17. Huang, He & Gao, Song, 2012. "Optimal paths in dynamic networks with dependent random link travel times," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 579-598.
    18. Francesca Guerriero & Roberto Musmanno & Valerio Lacagnina & Antonio Pecorella, 2001. "A Class of Label-Correcting Methods for the K Shortest Paths Problem," Operations Research, INFORMS, vol. 49(3), pages 423-429, June.
    19. Michael Bastian, 1992. "A perfect lot‐tree procedure for the discounted dynamic lot‐size problem with speculation," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(5), pages 651-668, August.
    20. Ichoua, Soumia & Gendreau, Michel & Potvin, Jean-Yves, 2003. "Vehicle dispatching with time-dependent travel times," European Journal of Operational Research, Elsevier, vol. 144(2), pages 379-396, January.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:59:y:2012:i:5:p:325-339. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.