The Pollution Routing Problem (PRP) is an extension of the Vehicle Routing problem that incorporates the cost of Greenhouse Emissions, particularly CO2. Similarly to the Vehicle Routing Problem, the Pollution Routing Problem is an NP-hard, combinatorial optimisation problem. Consequently, it cannot be solved with traditional computational techniques.
The Particle Swarm Optimisation (PSO) algorithm is an optimisation algorithm, initially
formulated by observing animal flocking behaviours in nature. The PSO is considered easily understood, easily implemented and computational inexpensive algorithm, making it a popular algorithm for optimisation problems. Versions of the algorithm adapted to a discrete solution space have been successfully applied to a variety of combinatorial optimisation problems, making the PSO a good candidate technique for solving a combinatorial problem such as the PRP.
A program solving the PRP using the discrete PSO is developed and presented in the current thesis. The PSO was initially formulated for a continuous search space, so the difficulties in applying it to a discrete solution space are discussed. Emphasis is given in the appropriate representation of the candidate solutions, to allow the effective use of the algorithm. The candidate solutions represent vehicle routes that are optimised to reduce the operational costs relevant to fuel consumption and driver wages, as well as costs relevant to produced CO2 emissions.
The program is run on datasets found in the bibliography. Due to not having incorporated all aspects of the PRP found in existing papers, most notably speed adjustment, direct comparison to results is considered pointless and a comparison is shown for completeness. A qualitative comparison on solution improvement is made instead. As such, the present implementation serves as an initial proof-of-concept for the application of the PRP, with suggestions to improve the implementation by incorporating extensions found in the bibliography.

Το Πρόβλημα Δρομολόγησης Ρύπανσης (Pollution Routing Problem - PRP) είναι μια
επέκταση του προβλήματος δρομολόγησης οχημάτων που ενσωματώνει το κόστος των
εκπομπών αερίων του θερμοκηπίου και ιδίως του CO2. Παρόμοια με το πρόβλημα
δρομολόγησης οχημάτων, το PRP είναι ένα NP-δύσκολο, συνδυαστικό πρόβλημα
βελτιστοποίησης. Συνεπώς, δεν μπορεί να επιλυθεί με παραδοσιακές υπολογιστικές τεχνικές.
Ο Αλγόριθμος Βελτιστοποίησης Σμήνους (Particle Swarm Optimisation - PSO) είναι ένας
αλγόριθμος βελτιστοποίησης, ο οποίος προέκυψε από την παρατήρηση της συμπεριφοράς οργανισμών που δημιουργούν σμήνη. Ο PSO θεωρείται εύκολα κατανοητός, εύκολα εφαρμόσιμος και υπολογιστικά φθηνός, γεγονός που τον καθιστά δημοφιλή αλγόριθμο για προβλήματα βελτιστοποίησης. Εκδόσεις του αλγορίθμου προσαρμοσμένες σε διακριτό χώρο λύσεων έχουν εφαρμοστεί με επιτυχία σε μια ποικιλία συνδυαστικών προβλημάτων
βελτιστοποίησης, καθιστώντας τον PSO έναν καλό υποψήφιο για την επίλυση ενός
συνδυαστικού προβλήματος όπως το PRP.
Στην παρούσα διατριβή αναπτύσσεται ένα πρόγραμμα επίλυσης του PRP με χρήση του
διακριτού PSO. Ο PSO αρχικά διατυπώθηκε για έναν συνεχή χώρο αναζήτησης, οπότε
συζητούνται οι δυσκολίες στην εφαρμογή του σε έναν διακριτό χώρο λύσεων. Δίνεται
έμφαση στην κατάλληλη αναπαράσταση των υποψήφιων λύσεων, ώστε να επιτρέπεται η αποτελεσματική χρήση του αλγορίθμου. Οι υποψήφιες λύσεις αντιπροσωπεύουν διαδρομές οχημάτων που έχουν βελτιστοποιηθεί ώστε να μειώνονται τα λειτουργικά κόστη που σχετίζονται με την κατανάλωση καυσίμων και τους μισθούς των οδηγών, καθώς και τα κόστη που σχετίζονται με τις εκπομπές διοξειδίου του άνθρακα.
Το πρόγραμμα εκτελείται σε σύνολα δεδομένων από τη βιβλιογραφία. Λόγω του ότι δεν
έχουν ενσωματωθεί όλες οι πτυχές του PRP που βρίσκονται σε υπάρχουσες εργασίες, κυρίως η τροποποίηση της ταχύτητας ανά τόξο διαδρομής, η άμεση σύγκριση με τα αποτελέσματα της βιβλιογραφίας θεωρήθηκε άσκοπη και παρουσιάζεται μόνο για λόγους πληρότητας. Αντί αυτού, πραγματοποιήθηκε μια ποιοτική σύγκριση σχετικά με τη βελτίωση της λύσης. Ως εκ τούτου, η παρούσα εφαρμογή χρησιμεύει ως αρχική απόδειξη της εγκυρότητας της εφαρμογής του PRP, με προτάσεις για τη βελτίωση της εφαρμογής μέσω της ενσωμάτωσης επεκτάσεων που βρίσκονται στη βιβλιογραφία.