Optimal routing in infinite-capacity dial-a-ride problems: a topological analysis of linear and star metrics

Abstract

The Dial-a-Ride Problem (DARP) is a model within combinatorial optimization, representing an essential component of modern logistics for the movement of goods and people. Unlike standard delivery tasks, the DARP requires a vehicle to visit pickup locations before their corresponding destinations. While much of the literature focuses on multi-vehicle systems with numerous real-world constraints, this thesis investigates the foundational mechanics of the problem. We specifically analyze the single-vehicle, non-preemptive, infinite-capacity DARP, seeking to establish exact algorithmic solutions across a set of fundamental metric topologies. To ground this research, the thesis includes a literature review from the theoretical perspective. This review surveys existing exact polynomial-time algorithms, complexity results, and approximation frameworks. Furthermore, it explores dynamic routing through online competitive analysis and examines the emerging paradigm of learning-augmented algorithms. The core of the thesis focuses on three metric spaces: the semi-line, the line, and the star graph. These topologies are selected because they serve as structural building blocks for more complex networks. By examining these spaces, we isolate the fundamental spatial and temporal complexities generated by the interplay between network structure and the requirement to service paired transportation requests. The contribution of this research consists of the design and proof of exact algorithms for the selected topologies. For both the semi-line and the line, we develop methodologies that identify optimal routing trajectories within polynomial time complexity. In the case of the star graph, we establish a structural bound that categorizes the problem within the XP complexity class. This study establishes a methodology for optimal routing by transitioning from simple geometries to more complex structures. These findings provide a theoretical foundation for future efforts to solve the DARP on generalized trees and arbitrary metric spaces. The thesis concludes with a summary of these results and a discussion on potential avenues for future research.Η παρούσα διατριβή διερευνά το Dial-a-Ride Problem (DARP), ένα κεντρικό μοντέλο συνδυαστικής βελτιστοποίησης για τη μεταφορά αγαθών και επιβατών. Η έρευνα εστιάζει στην περίπτωση ενός οχήματος με άπειρη χωρητικότητα και χωρίς δυνατότητα προσωρινής εκφόρτωσης (non-preemptive), επιδιώκοντας την ανάπτυξη αλγορίθμων ακριβούς επίλυσης σε θεμελιώδεις τοπολογίες. Στο πλαίσιο της θεωρητικής επισκόπησης, εξετάζονται υφιστάμενοι αλγόριθμοι πολυωνυμικού χρόνου, αποτελέσματα πολυπλοκότητας, το online πλαίσιο δυναμικής δρομολόγησης και η ενσωμάτωση προβλέψεων στον αλγοριθμικό σχεδιασμό. Ο κύριος κορμός της μελέτης επικεντρώνεται στην ημι-γραμμή, τη γραμμή και τους γράφους αστέρες. Οι τοπολογίες αυτές λειτουργούν ως δομικά στοιχεία για τη μελέτη πιο σύνθετων δικτύων, επιτρέποντας την απομόνωση των προκλήσεων που προκύπτουν από την αλληλεπίδραση της δικτυακής δομής με τους περιορισμούς προτεραιότητας των αιτημάτων μεταφοράς. Η βασική συνεισφορά της διατριβής περιλαμβάνει τον σχεδιασμό και την τυπική απόδειξη αλγορίθμων ακριβούς επίλυσης. Για την ημι-γραμμή και τη γραμμή, αναπτύσσονται μεθοδολογίες βέλτιστης δρομολόγησης σε πολυωνυμικό χρόνο. Στην περίπτωση των γράφων αστέρων, η έρευνα αποδεικνύει μια δομική ιδιότητα που επιτρέπει τον σχεδιασμό αλγορίθμων οι οποίοι κατατάσσουν το πρόβλημα στην κλάση πολυπλοκότητας $XP$. Συνοψίζοντας, η μελέτη προτείνει μια συστηματική μεθοδολογία για τη βέλτιστη δρομολόγηση, μεταβαίνοντας από απλές γεωμετρίες σε σύνθετες διακλαδώσεις. Τα αποτελέσματα αυτά θέτουν τις θεωρητικές βάσεις για τη μελλοντική επίλυση του DARP σε γενικευμένα δέντρα και αυθαίρετους μετρικούς χώρους.