On the online dial-a-ride-problem

Abstract

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.

Αυτή η έρευνα επικεντρώθηκε στα online προβλήματα dial a ride. Οι βασικοί στόχοι αυτής της διατριβής ήταν: 1. Η μελέτη του προβλήματος Online Dial-a-Ride μέσα από μια εκτενή ανασκόπηση της σχετικής βιβλιογραφίας. Η μελέτη αφορούσε τις σύγχρονες τεχνικές επίλυσης αυτών των προβλημάτων καθώς και θέματα εγγύτητας ως προς την βέλτιστη λύση. 2. Ο καθορισμός των ιδιοτήτων του προβλήματος έτσι ώστε να επιτευχθεί μια σφαιρική αντίληψη του προβλήματος αλλά και των online χαρακτηριστικών του. 3. Η κατασκευή του κατάλληλου συνόλου στατικών αλγορίθμων, οι οποίοι θα μπορούν να χρησιμοποιηθούν ως υποενότητες στους online αλγορίθμους. 4. Η κατασκευή του κατάλληλου συνόλου των online αλγορίθμων. Ιδιαίτερη έμφαση δόθηκε στις διαδικασίες βελτιστοποίησης έτσι ώστε η λύση να βελτιώνεται συνεχώς καθώς ο χρόνος προχωρεί, αξιοποιώντας κατά κύριο λόγο το χρόνο εκείνο όπου το σύστημα παραμένει σε αδράνεια. 5. Την αξιολόγηση αυτών των αλγορίθμων όσον αφορά την βέλτιστη λύση, την ταχύτητα εκτέλεσης και την ορθότητα των αποτελεσμάτων. Η διατριβή αυτή συνέβαλε στο Dial-a-Ride πρόβλημα προσφέροντας έξι αλγορίθμους (offline και online) και επιπλέον μια ενδιαφέρουσα μεθοδολογία ως προς την αποδοτικότητα ενός μελλοντικού αλλά μη υπαρκτού συστήματος μεταφοράς κατ' απαίτηση (Demand Responsive). Για αυτούς τους αλγορίθμους μελετήθηκε η πολυπλοκότητα τους, προσφέροντας χρήσιμες πληροφορίες σχετικά με το χρόνο εκτέλεσης. Για τον αλγόριθμο DP Exact υπολογίσθηκε ο συνολικός αριθμός πιθανών συνδυασμών κατανομής των αιτήσεων μεταφοράς, δηλαδή ο συνολικός χώρος των λύσεων. Για τον VLSN αλγόριθμο υπολογίσθηκε το μέγεθος της γειτονιάς λύσεων που αναζητεί σε σύγκριση με το συνολικό χώρο λύσεων. Για τον online αλγόριθμο OR-DARP, χρησιμοποιήθηκαν τεχνικές regret για την διαδικασία βελτιστοποίησης. Το πιο σημαντικό χαρακτηριστικό του OR-DARP αλγορίθμου είναι ότι η βελτιστοποίηση λειτουργεί συνεχώς και ότι δεν υπάρχει καμία ανάγκη για προκαθορισμένους χρονικούς ορίζοντες βελτιστοποίησης. Ο αλγόριθμος εκμεταλλεύεται τις μικρές χρονικές περιόδους που το σύστημα βρίσκεται σε κατάσταση αναμονής και βελτιστοποιεί τη λύση. Για τον αλγόριθμο ORDARP προτάθηκε επίσης μια γραμμική προσέγγιση για να περιγράψει τον λόγο ανταγωνισμού μεταξύ της πλήρους στατικής λύσης και μιας πλήρους online λύσης. Ένα άλλο σημαντικό αποτέλεσμα είναι η ύπαρξη και η εύρεση ενός κρίσιμου ορίου, όπου η βελτιστοποίηση επηρεάζει την ποιότητα της λύσης αρνητικά. Ο αλγόριθμος OP-DARP - ως μετεξέλιξη του αλγορίθμου OR-DARP αναπτύχθηκε με σκοπό να κάνει χρήση την πρότερη και ιστορική γνώση που έχουμε, έτσι ώστε η επιλογή των αναθέσεων για κάθε ζήτηση μεταφοράς να γίνεται με ένα πιο έξυπνο τρόπο μέσω της χρήσης στοχαστικών ζητήσεων μεταφοράς. Ο αλγόριθμος OP-DARP χρησιμοποιεί πραγματικά ιστορικά δεδομένα μεταφορών και προσφέρει περισσότερο βελτιστοποιημένες λύσεις από τον αλγόριθμο OR-DARP, στην πλειονότητα των περιπτώσεων που έχει δοκιμαστεί. Για το χειρισμό των στοχαστικών ζητήσεων ο αλγόριθμος OP-DARP απαιτεί μεγάλα ποσά υπολογιστικής ισχύος. Εάν το υπολογιστικό μας σύστημα είναι αρκετά ισχυρό τότε, η χρήση του αλγορίθμου OP-DARP προσφέρει αναμφισβήτητα επιπλέον βελτιστοποίηση σε σχέση με τον αλγόριθμο OR-DARP.