A two-stage optimization framework for last-mile delivery using a mobile depot

Abstract

This thesis investigates the use of a Mobile Depot as a means of reducing total vehicle travel time in last-mile delivery operations. A two-stage optimization framework is proposed in which a Mobile Depot moves between selected urban locations to resupply delivery vehicles, enabling loading activities to occur closer to customer clusters and reducing the need for frequent returns to a remote central depot. In the first stage, a Mixed-Integer Linear Programming (MILP) model determines the route and schedule of the Mobile Depot, incorporating capacity, time-window and synchronization constraints. The objective of this stage is to minimize the travel effort imposed on the delivery vehicles by optimally selecting depot stops and assigning customer requests. In the second stage, a Pickup and Delivery Problem with Time Windows (PDPTW) is solved using the LKH-3 heuristic to construct feasible and efficient vehicle routes that respect the Mobile Depot’s availability and vehicle capacity limits. Using real-world last-mile delivery data, the proposed framework is evaluated against a conventional fixed-depot system. The results show that Mobile Depots do not provide uniform benefits across all operating conditions. Instead, their effectiveness depends on demand intensity and capacity constraints. In particular, the analysis identifies the circumstances under which the Mobile Depot significantly reduces total vehicle travel time, as well as scenarios where its impact is limited.Η παρούσα εργασία μελετά τη χρήση μίας Κινητής Αποθήκης (Mobile Depot) με στόχο τη μείωση του συνολικού χρόνου διαδρομής των οχημάτων στη διανομή του τελευταίου σταδίου (last-mile delivery). Προτείνεται ένα πλαίσιο βελτιστοποίησης δύο σταδίων, στο οποίο η Κινητή Αποθήκη μετακινείται μεταξύ επιλεγμένων αστικών τοποθεσιών και λειτουργεί ως ενδιάμεσο σημείο ανατροφοδότησης για τα οχήματα διανομής. Με αυτόν τον τρόπο, οι δραστηριότητες φόρτωσης πραγματοποιούνται εγγύτερα στα σημεία ζήτησης των πελατών, περιορίζοντας την ανάγκη για συχνές και χρονοβόρες επιστροφές στην απομακρυσμένη κεντρική αποθήκη. Στο πρώτο στάδιο, αναπτύσσεται ένα μοντέλο Μικτού Ακέραιου Γραμμικού Προγραμματισμού (MILP), το οποίο καθορίζει τη βέλτιστη διαδρομή και τον χρονικό προγραμματισμό της Κινητής Αποθήκης. Το μοντέλο ενσωματώνει περιορισμούς χωρητικότητας, χρονικών παραθύρων και συγχρονισμού, λαμβάνοντας υπόψην τις αλληλεξαρτήσεις μεταξύ της κίνησης της Κινητής Αποθήκης και των οχημάτων διανομής. Ο στόχος του πρώτου σταδίου είναι η ελαχιστοποίηση του μεταφορικού κόστους των οχημάτων, μέσω της βέλτιστης επιλογής στάσεων της Κινητής Αποθήκης και της αποδοτικής ανάθεσης των δεμάτων προς παράδοση. Στο δεύτερο στάδιο, το πρόβλημα δρομολόγησης των μικρότερων οχημάτων διατυπώνεται ως Πρόβλημα Παραλαβής και Παράδοσης με Χρονικά Παράθυρα (PDPTW) και επιλύεται με τη χρήση του ευρετικού αλγορίθμου LKH-3. Το στάδιο αυτό επικεντρώνεται στη δημιουργία εφικτών και αποδοτικών διαδρομών για τα οχήματα, οι οποίες σέβονται τόσο τους περιορισμούς χωρητικότητας των οχημάτων όσο και τη διαθεσιμότητα της Κινητής Αποθήκης, όπως αυτή προκύπτει από το πρώτο στάδιο. Η προτεινόμενη μεθοδολογία αξιολογείται χρησιμοποιώντας πραγματικά δεδομένα διανομής τελευταίου σταδίου και συγκρίνεται με ένα συμβατικό σύστημα σταθερής αποθήκης. Τα αποτελέσματα δείχνουν ότι η χρήση Κινητής Αποθήκης δεν οδηγεί σε ομοιόμορφη βελτίωση υπό όλες τις συνθήκες λειτουργίας. Αντιθέτως, η αποτελεσματικότητά της εξαρτάται σε σημαντικό βαθμό από την ένταση της ζήτησης και τους περιορισμούς χωρητικότητας του συστήματος. Η ανάλυση προσδιορίζει τις περιπτώσεις στις οποίες η Κινητή Αποθήκη επιτυγχάνει σημαντική μείωση του συνολικού χρόνου διαδρομής των οχημάτων, καθώς και τα σενάρια όπου το όφελος είναι περιορισμένο.