Document Open Access Logo

Time-Dependent Bi-Objective Itinerary Planning Algorithm: Application in Sea Transportation

Authors Aphrodite Veneti, Charalampos Konstantopoulos, Grammati Pantziou

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2016.11.pdf
  • Filesize: 432 kB
  • 14 pages

Document Identifiers

Author Details

Aphrodite Veneti
Charalampos Konstantopoulos
Grammati Pantziou

Cite As Get BibTex

Aphrodite Veneti, Charalampos Konstantopoulos, and Grammati Pantziou. Time-Dependent Bi-Objective Itinerary Planning Algorithm: Application in Sea Transportation. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/OASIcs.ATMOS.2016.11

Abstract

A special case of the Time-Dependent Shortest Path Problem (TDSPP) is the itinerary planning problem where the objective is to find the shortest path between a source and a destination node which passes through a fixed sequence of intermediate nodes. In this paper, we deviate from the common approach for solving this problem, that is, finding first the shortest paths between successive nodes in the above sequence and then synthesizing the final solution from the solutions of these sub-problems. We propose a more direct approach and solve the problem by a label-setting approach which is able to early prune a lot of partial paths that cannot be part of the optimal solution. In addition, we study a different version of the main problem where it is only required that the solution path should pass through a set of specific nodes irrespectively of the particular order in which these nodes are included in the path. As a case study, we have applied the proposed techniques for solving the itinerary planning of a ship with respect to two conflicting criteria, in the area of the Aegean Sea, Greece. Moreover, the algorithm handles the case that the ship speed is not constant throughout the whole voyage. Specifically, it can be set at a different level each time the ship departs from an intermediate port in order to obtain low cost solutions for the itinerary planning. The experimental results confirm the high performance of the proposed algorithms.

Subject Classification

Keywords
  • Multi-criteria optimization
  • Label setting algorithm
  • Time dependent networks
  • Travel planning
  • Itinerary planning
  • Sea transportation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Konstantinos N Androutsopoulos and Konstantinos G Zografos. Solving the multi-criteria time-dependent routing and scheduling problem in a multimodal fixed scheduled network. European Journal of Operational Research, 192(1):18-28, 2009. Google Scholar
  2. Kyriakos Avgouleas. Optimal ship routing. PhD thesis, Massachusetts Institute of Technology, 2008. Google Scholar
  3. Jean-François Bérubé, Jean-Yves Potvin, and Jean Vaucher. Time-dependent shortest paths through a fixed sequence of nodes: application to a travel planning problem. Computers &operations research, 33(6):1838-1856, 2006. Google Scholar
  4. Ismail Chabini. Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time. Transportation Research Record: Journal of the Transportation Research Board, 1645(1):170-175, 1998. Google Scholar
  5. Camila F Costa, Mario A Nascimento, José AF Macêdo, Yannis Theodoridis, Nikos Pelekis, and Javam Machado. Optimal time-dependent sequenced route queries in road networks. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, page 56. ACM, 2015. Google Scholar
  6. Rafael Castro de Andrade. New formulations for the elementary shortest-path problem visiting a given set of nodes. European Journal of Operational Research, 254(3):755-768, 2016. Google Scholar
  7. Theodoros Giannakopoulos, Ioannis A Vetsikas, Ioanna Koromila, Vangelis Karkaletsis, and Stavros Perantonis. Aminess: a platform for environmentally safe shipping. In Proceedings of the 7th International Conference on PErvasive Technologies Related to Assistive Environments, page 45. ACM, 2014. Google Scholar
  8. Konstantinos G Gkonis and Harilaos N Psaraftis. Some key variables affecting liner shipping costs. Laboratory for Maritime Transport, National Technical University of Athens, 2010. Google Scholar
  9. Jörn Hinnenthal and Günther Clauss. Robust pareto-optimum routing of ships utilising deterministic and ensemble weather forecasts. Ships and Offshore Structures, 5(2):105-114, 2010. Google Scholar
  10. Lars Magnus Hvattum, Inge Norstad, Kjetil Fagerholt, and Gilbert Laporte. Analysis of an exact algorithm for the vessel speed optimization problem. Networks, 62(2):132-135, 2013. Google Scholar
  11. MSC IMO. 1/circ. 1228. Revised guidance to the master for avoiding dangerous situations in adverse weather and sea conditions, adopted 11th January, 2007. Google Scholar
  12. David E Kaufman and Robert L Smith. Fastest paths in time-dependent networks for intelligent vehicle-highway systems application. Journal of Intelligent Transportation Systems, 1(1):1-11, 1993. Google Scholar
  13. Ioanna Koromila, Zoe Nivolianitou, and Theodoros Giannakopoulos. Bayesian network to predict environmental risk of a possible ship accident. In Proceedings of the 7th International Conference on PErvasive Technologies Related to Assistive Environments, page 44. ACM, 2014. Google Scholar
  14. Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, and Shang-Hua Teng. On trip planning queries in spatial databases. In Advances in Spatial and Temporal Databases, pages 273-290. Springer, 2005. Google Scholar
  15. John J Liu. Supply chain management and transport logistics. Routledge, 2011. Google Scholar
  16. G Mannarini, G Coppini, P Oddo, and N Pinardi. A prototype of ship routing decision support system for an operational oceanographic service. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation, 7(1):53-59, 2013. Google Scholar
  17. Stéphane Marie, Eric Courteille, et al. Multi-objective optimization of motor vessel route. In Proceedings of the Int. Symp. TransNav, volume 9, pages 411-418, 2009. Google Scholar
  18. Ariel Orda and Raphael Rom. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. Journal of the ACM (JACM), 37(3):607-625, 1990. Google Scholar
  19. Ariel Orda and Raphael Rom. Minimum weight paths in time-dependent networks. Networks, 21(3):295-319, 1991. Google Scholar
  20. David Ronen. The effect of oil price on the optimal speed of ships. Journal of the Operational Research Society, 33(11):1035-1040, 1982. Google Scholar
  21. Mehdi Sharifzadeh, Mohammad Kolahdouzan, and Cyrus Shahabi. The optimal sequenced route query. The VLDB journal, 17(4):765-787, 2008. Google Scholar
  22. J Szlapczynska and R Smierzchalski. Multicriteria optimisation in weather routing. In Proceedings of the Int. Symp. TransNav, volume 9, pages 423-429, 2009. Google Scholar
  23. K Takashima, B Mezaoui, and R Shoji. On the fuel saving operation for coastal merchant ships using weather routing. In Proceedings of Int. Symp. TransNav, volume 9, pages 431-436, 2009. Google Scholar
  24. Aphrodite Veneti, Charalampos Konstantopoulos, and Grammati Pantziou. Continuous and discrete time label setting algorithms for the time dependent bi-criteria shortest path problem. In Operations Research and Computing: Algorithms and Software for Analytics, pages 62-73, Virginia, January 11-13 2015. 14th INFORMS Computing Society Conference Richmond. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact