License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2016.11
URN: urn:nbn:de:0030-drops-65358
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6535/
Veneti, Aphrodite ;
Konstantopoulos, Charalampos ;
Pantziou, Grammati
Time-Dependent Bi-Objective Itinerary Planning Algorithm: Application in Sea Transportation
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.
BibTeX - Entry
@InProceedings{veneti_et_al:OASIcs:2016:6535,
author = {Aphrodite Veneti and Charalampos Konstantopoulos and Grammati Pantziou},
title = {{Time-Dependent Bi-Objective Itinerary Planning Algorithm: Application in Sea Transportation}},
booktitle = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
pages = {11:1--11:14},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-95977-021-7},
ISSN = {2190-6807},
year = {2016},
volume = {54},
editor = {Marc Goerigk and Renato Werneck},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6535},
URN = {urn:nbn:de:0030-drops-65358},
doi = {10.4230/OASIcs.ATMOS.2016.11},
annote = {Keywords: Multi-criteria optimization, Label setting algorithm, Time dependent networks, Travel planning, Itinerary planning, Sea transportation}
}
|
Keywords: |
|
Multi-criteria optimization, Label setting algorithm, Time dependent networks, Travel planning, Itinerary planning, Sea transportation |
|
Collection: |
|
16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
24.08.2016 |
