Back to search

University of Thessaly (UTH)

On the online dial-a-ride-problem

Abstract

dc:description

This research is focused on Static and Online Algorithms for the DARP and OLDARP problems. The specific objectives are: 1. To study the "Online Dial-a-Ride" problem (ODARP), through an extensive literature study. New trends in research are considered, in order to get deep understanding of the practical application needs that guide the research on this field. Issues like the closeness of the proposed solutions to the optimal solutions are considered. 2. To identify the problem properties that can be useful in the overall understanding of the online problem. This is a challenging objective as we aim to identify specific problem properties concerning the problem solution space; this in turn will lead to understanding what the difficulties concerning the solution are. It will also indicate possible solution paths. 3. To construct the appropriate set of static algorithms. These can be used as sub-modules to the online algorithms. 4. To construct the appropriate set of online algorithms. With special emphasis on adapting optimization procedures that are continuously improved as the time progresses, taking advantage of the time that the system remains idle. 5. To evaluate these algorithms in terms of solution optimality, speed of execution and correctness of the results. This work contributed to the Dial-a-Ride Problem by offering six algorithms (offline and online) and in addition, an interesting contribution regards the profitability of a proposed but not yet existing DRT system. For these algorithms the complexity was studied offering useful information regarding the execution time. For the "VLSN" algorithm the size of the neighborhood was identified in comparison with the total solution space. For the online Regret algorithm (OR-DARP), we used regret techniques for optimization. The most important feature of the online regret algorithm is that optimization works continuously. There is no need for time horizons. The algorithm takes advantage of the small time periods that the system is in idle state and optimizes the solution. For the OR-DARP algorithm we also proposed a linear approach to describe the relationship between full static solutions and full online solution. Another important result is the existence of a critical limit where the regret optimization affects the solution quality negatively in terms of profitability. The Online Regret algorithm with probabilities (OP-DARP) was developed in order to anticipate the knowledge we have, for the selection of the trip assignments in a more intelligent way. The OP-DARP algorithm utilizes real historical trip data and gives more optimized solutions than the OR-DARP algorithm, in the majority of cases we have tested. For the handling of probabilistic demands the OP-DARP algorithm requires large amounts of processor power. If our processing system is powerful enough then the usage of OP-DARP is a necessity in order to optimize it as much as possible.

Degree

thesis:*
Grantor dc:publisher
University of Thessaly (UTH)
Year dc:date
2010

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Lois, Athanasios
  • Λόης, Αθανάσιος

Subjects

dc:subject × 22

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/21723

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Lois, Athanasios; Λόης, Αθανάσιος. On the online dial-a-ride-problem. University of Thessaly (UTH), 2010. http://hdl.handle.net/10442/hedi/21723