Abstract
dc:descriptionThis 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- Επιγραμμικό πρόβλημα dial-a-ride
- Πιθανολογική ζήτηση μεταφοράς
- Εντοπισμός σημείου κερδοφορίας συστήματος μεταφοράς
- Ευρετικός αλγόριθμος του προβλήματος dial-a-ride
- Απόλυτη επίλυση στο πρόβλημα dial-a-ride
- Αναζήτηση σε ευρεία γειτονιά λύσεων στο πρόβλημα dial-a-ride
- Dial-a-ride
- DARP
- Online DARP
- Online dial-a-ride
- Static regret algorithm
- Very large neighbourhood search
- DARP algorithm Stochastic Trip Demands handling
- DARP Algorithm Response Time
- DRT service quality parameters
- DRT Profitability
- Dial-a-Ride Solution Space
- Probabilistic Trip Demands
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Μηχανολόγου Μηχανικού
- Engineering and Technology
- Mechanical Engineering
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/21723