Μοντελοποίηση και υλοποίηση αλγορίθμων επίλυσης προβλημάτων δρομολόγησης οχημάτων με επιλεκτική εξυπηρέτηση πελατών

Abstract

The present dissertation concerns the investigation of vehicle routing problems with selective customer service and the creation of appropriate algorithmic methods for their solution. In particular, it was considered the application of selective routing problems in emergency situations, e.g., fire or flood. As such, the Prize-Collecting Vehicle Routing Problem (PCVRP) was selected to simulate the routing of a homogeneous fleet of fire trucks. PCVRP covers the routing needs of firefighting vehicles, aiming at quick access to the points that need protection and the greatest benefit from the respective actions. Nevertheless, the launch of emergency vehicles must also take into account the related environmental impact. For this reason, two new mathematical models are proposed in this dissertation, as variants of PCVRP, the Environmental Prize-Collecting Vehicle Routing Problem (E-PCVRP) and the Green Prize-Collecting Vehicle Routing Problem (Green-PCVRP). Also, the Asset Protection Problem (APP) was chosen to simulate the routing of a heterogeneous fleet of fire trucks. This problem has been proposed for the coordinated and synchronized routing of fire trucks in the protection of key community assets. The APP is considered a particularly demanding problem due to the heterogeneous vehicle fleet, the different needs of each point (in type and number of vehicles), the time constraints for the protection of each point, and the need to synchronize the vehicles (spatial and temporal). The problems under consideration are variations of the classic routing problem, and nature-inspired algorithms are used to optimize them. Specifically, for the algorithmic optimization of the proposed Green-PCVRP problem, the Bat Algorithm (BA) was chosen, which, however, is designed to solve continuously variable problems, while the examined problem requires a discrete solution coding. Thus, two new algorithmic frameworks based on BA are proposed in the present dissertation. The first one concerns a discrete version of the Discrete Inspired Bat Algorithm (DIBA) and is based on replacing the algorithm's update equations with heuristic techniques. The second algorithmic framework proposed concerns applying the classical method using the proposed method of encoding/decoding solutions, Coordinates Related (CR), which is a novelty of this doctoral dissertation. Thus, the proposed algorithmic approach to solving Green-PCVRP is noted as Bat Algorithm based on Coordinates (BAC). The two proposed algorithmic methods are compared based on their effectiveness in solving the Green-PCVRP benchmark instances found in the literature. The enriched version of the classical algorithmic framework with the CR method has proven to be more efficient than the same algorithm's discrete version. Therefore, to solve the second proposed problem, the E-PCVRP, the application of the novel CR method to other metaheuristic algorithms has been studied. Specifically, the Firefly Algorithm, the Differential Evolution Algorithm with binomial and exponential crossover, the Particle Swarm Optimization Algorithm, and the Teaching-Learning Optimization Algorithm were used. Regarding the algorithmic solution of the APP, the above algorithms can not be used since this problem requires the use of a construction algorithm. Thus, the Ant Colony System algorithm was chosen, and its variant, the Modified Ant Colony System (MACS), is proposed. In comparison with the already published methods of solving the APP, the proposed MACS outperforms the previously published methods, providing new optimal solutions.

Η παρούσα διδακτορική διατριβή αφορά αφενός στη διερεύνηση προβλημάτων δρομολόγησης οχημάτων με επιλεκτική εξυπηρέτηση πελατών και αφετέρου, στη δημιουργία κατάλληλων αλγοριθμικών μεθόδων για την επίλυσή τους. Συγκεκριμένα, θεωρήθηκε η εφαρμογή των επιλεκτικών προβλημάτων δρομολόγησης σε καταστάσεις έκτακτης ανάγκης, όπως μία πυρκαγιά ή μία πλημμύρα. Για την προσομοίωση της δρομολόγησης ενός ομογενούς στόλου πυροσβεστικών οχημάτων, επιλέχθηκε το πρόβλημα δρομολόγησης οχημάτων συλλογής βραβείου (Prize-Collecting Vehicle Routing Problem (PCVRP)). Το επιλεγμένο πρόβλημα καλύπτει τις ανάγκες της δρομολόγησης των πυροσβεστικών οχημάτων, αποσκοπώντας στη γρήγορη πρόσβαση στα σημεία που χρειάζονται προστασία και στο μεγαλύτερο όφελος από τις αντίστοιχες ενέργειες. Πάραυτα, η δρομολόγηση οχημάτων σε έκτακτες καταστάσεις οφείλει να λαμβάνει υπόψιν και τον περιβαλλοντολογικό αντίκτυπο που έχει. Για αυτό το λόγο, στη παρούσα διατριβή προτείνονται δύο νέα μαθηματικά μοντέλα, ως παραλλαγές του PCVRP, το περιβαλλοντικό πρόβλημα δρομολόγησης οχημάτων με συλλογή βραβείου (E-PCVRP) και το πράσινο πρόβλημα δρομολόγησης οχημάτων με συλλογή βραβείου (Green-PCVRP). Για την προσομοίωση της δρομολόγησης ενός ετερογενούς στόλου πυροσβεστικών οχημάτων, επιλέχθηκε το πρόβλημα προστασίας καίριων σημείων (Asset Protection Problem (APP)). Το πρόβλημα αυτό έχει προταθεί για τη συντονισμένη και συγχρονισμένη δρομολόγηση πυροσβεστικών οχημάτων στη προστασία καίριων σημείων. Το APP θεωρείται ιδιαίτερα απαιτητικό πρόβλημα λόγω του ετερογενούς στόλου οχημάτων, των διαφοροποιημένων αναγκών (σε είδος και αριθμό οχημάτων) κάθε σημείου, των χρονικών περιορισμών για την προστασία κάθε σημείου και την ανάγκη συγχρονισμού των οχημάτων (χωρικά και χρονικά). Τα εξεταζόμενα προβλήματα αποτελούν παραλλαγές του κλασσικού προβλήματος δρομολόγησης, και για τη βελτιστοποίηση τους γίνεται χρήση αλγορίθμων εμπνευσμένων από τη φύση. Συγκεκριμένα, για την αλγοριθμική βελτιστοποίηση του προτεινόμενου προβλήματος Green-PCVRP, επιλέχθηκε ο Αλγόριθμος της Νυχτερίδας ο οποίος όμως έχει σχεδιαστεί για την επίλυση προβλημάτων συνεχών μεταβλητών, ενώ το εξεταζόμενο πρόβλημα απαιτεί διακριτή κωδικοποίηση των λύσεων. Για αυτό το λόγο, στη παρούσα διατριβή προτείνονται δύο νέα αλγοριθμικά πλαίσια. Το πρώτο αφορά σε διακριτοποιημένη εκδοχή του αλγορίθμου, η οποία δηλώνεται ως Discrete Inspired Bat Algorithm (DIBA) και βασίζεται στην αντικατάσταση των εξισώσεων κίνησης του αλγορίθμου από ευρετικές τεχνικές. Το δεύτερο αλγοριθμικό πλαίσιο που προτείνεται αφορά στην εφαρμογή της κλασσικής μεθόδου κάνοντας χρήση της προτεινόμενης μεθόδου κωδικοποίησης/αποκωδικοποίησης των λύσεων, Coordinates Related (CR), που αποτελεί πρωτοτυπία της παρούσας διδακτορικής διατριβής. Έτσι, η προτεινομένη αλγοριθμική προσέγγιση για την επίλυση του Green-PCVRP ονομάζεται Bat Algorithm based on Coordinates (BAC). Οι δύο προτεινόμενες αλγοριθμικές μέθοδοι συγκρίνονται βάση της αποτελεσματικότητάς τους στην επίλυση του προβλήματος Green-PCVRP, σε παραδείγματα αναφοράς της βιβλιογραφίας. Μάλιστα, εξάγεται το συμπέρασμα ότι η εμπλουτισμένη εκδοχή του κλασσικού αλγοριθμικού πλαισίου με την μέθοδο CR είναι αποτελεσματικότερη σε σύγκριση με την διακριτή εκδοχή του ίδιου αλγορίθμου. Συνεπώς, για την επίλυση του δεύτερου προτεινόμενου προβλήματος, του E-PCVRP μελετήθηκε η εφαρμογή της καινοτόμου μεθόδου CR και σε άλλους μεθευρετικούς αλγορίθμους. Συγκεκριμένα, χρησιμοποιήθηκαν ο Αλγόριθμος της Πυγολαμπίδας, ο Αλγόριθμος της Διαφορικής Εξέλιξης με διωνυμική και εκθετική διασταύρωση, ο Αλγόριθμος Βελτιστοποίησης Σμήνους Σωματιδίων και ο Αλγόριθμος Βελτιστοποίησης Διδασκαλίας-Μάθησης. Σε ότι αφορά την αλγοριθμική επίλυση του APP, οι παραπάνω αλγόριθμοι δεν μπορούν να χρησιμοποιηθούν, γιατί για το συγκεκριμένο πρόβλημα απαιτείται η χρήση ενός κατασκευαστικού αλγορίθμου. Έτσι, επιλέχθηκε ο αλγόριθμος «Σύστημα Αποικίας Μυρμηγκιών» (ACS και προτείνεται η παραλλαγή του ως το Προσαρμοσμένο Σύστημα Αποικίας Μυρμηγκιών (Modified Ant Colony System (MACS)). Η αποτελεσματικότητα του προτεινόμενου αλγορίθμου αποδεικνύεται μέσα από υπολογιστικά πειράματα, χρησιμοποιώντας παραδείγματα αναφοράς της βιβλιογραφίας, σε σύγκριση με τις ήδη δημοσιευμένες μεθόδους επίλυσης του APP. Συγκεκριμένα, αποδεικνύεται ότι ο MACS υπερισχύει των προηγούμενα δημοσιευμένων μεθόδων, αποδίδοντάς νέες βέλτιστες λύσεις.