A Toolkit for the Optimal Solution of the Vehicle Routing Problem with Time Windows and Capacity Constraints - PDF

Please download to get full document.

View again

of 32
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Literature

Published:

Views: 51 | Pages: 32

Extension: PDF | Download: 0

Share
Related documents
Description
UNIVERSITY OF THE AEGEAN SCHOOL OF BUSINESS DEPARTMENT OF FINANCIAL AND MANAGEMENT ENGINEERING A Toolkit for the Optimal Solution of the Vehicle Routing Problem with Time Windows and Capacity Constraints
Transcript
UNIVERSITY OF THE AEGEAN SCHOOL OF BUSINESS DEPARTMENT OF FINANCIAL AND MANAGEMENT ENGINEERING A Toolkit for the Optimal Solution of the Vehicle Routing Problem with Time Windows and Capacity Constraints Georgios Dikas Supervisor: Ioannis Minis Chios, 2008 to my parents i University of the Aegean Department of Financial and Management Engineering ACKNOWLEDGMENTS Firstly, I would like to thank my Professor Ioannis Minis for giving me the opportunity to undertake the present diploma thesis, for his valuable supervision and guidance. I gratefully thank Athanasopoulos Theodore and Ninikas Georgios, PhD Candidates of the University of the Aegean, for encouragement, countless discussions and for their help with writing the thesis. Their support was really significant for me. Furthermore, I am grateful to Vasilis Koutras PhD Candidate of the University of the Aegean, for his advises and support throughout the project. I would also like to acknowledge the support and the recourses made available to me through the DeOPSys Lab of the Financial and Management Engineering (FME) Department of the University of the Aegean, and especially to Taxiarxis Kourounis PhD Candidate of the University of the Aegean, for encouragement and for making the average work day more fun and interesting. Finally, I would like to thank my family and friends for their support during all these years of my educational period. Thank you ii ΠΕΡΊΛΗΨΗ (IN GREEK) Σε παρούσα την διπλωματική εργασία παρουσιάζεται η δημιουργία προγραμματιστικών εργαλείων για την επίλυση του προβλήματος δρομολόγησης οχημάτων με χρονικά παράθυρα (Vehicle Routing Problem with Time Windows - VRPTW). Τα εργαλεία αυτά βασίστηκαν στην μέθοδο γραμμικού προγραμματισμού Column Generation για την εύρεση του κατώτερου ορίου (lower bound) του χαλαρωμένου (relaxed) προβλήματος και στον αλγόριθμο Branch and Bound για την επίτευξη της βέλτιστης ακεραία λύσης του προβλήματος. Η ανάπτυξη της μεθόδου έχει βασιστεί στην διδακτορική εργασία του Larsen (2001) και τις εργασίες άλλων ερευνητών οι οποίοι έχουν ασχοληθεί με το VRPTW. Το συγκεκριμένο εργαλείο θα χρησιμοποιηθεί από το εργαστήριο Συστημάτων Σχεδιασμού Παραγωγής και Λειτουργιών του τμήματος Μηχανικών Οικονομίας και Διοίκησης (ΤΜΟΔ), του Πανεπιστημίου Αιγαίου, στα πλαίσια του ερευνητικού του αντικειμένου που σχετίζεται με διάφορες παραλλαγές των προβλημάτων δρομολόγησης οχημάτων. Η μέθοδος Column Generation αποτελεί μια ευρέως χρησιμοποιούμενη μέθοδο τα τελευταία χρόνια και θα μπορούσε να εφαρμοστεί σε πολλά και διαφορετικά προβλήματα του πεδίου της Επιχειρησιακής Έρευνας που μελετούνται στον χώρο του ΤΜΟΔ και του Πανεπιστημίου Αιγαίου. Το πρόβλημα VRPTW αφόρα την εύρεση των δρομολογίων ελάχιστου κόστους για ένα στόλο οχημάτων που ξεκινούν και επιστρέφουν σε μία κοινή αποθήκη, με σκοπό να εξυπηρετήσουν ακριβώς μία φορά κάθε πελάτη από ένα σύνολο πελατών. Οι πελάτες χαρακτηρίζονται από την ζήτηση, τον χρόνο εξυπηρέτησης και το χρονικό παράθυρο εξυπηρέτησης τους (time windows). Το κάθε όχημα έχει συγκεκριμένη χωρητικότητα (περιορίζοντας τον αριθμό των πελατών οι οποίοι μπορούν να εξυπηρετηθούν από ένα όχημα) και χαρακτηρίζεται από ένα μέγιστο χρόνο διαδρομής. Τα χρονικά παράθυρα και η ζήτηση του κάθε πελάτη θεωρούνται γνωστά εκ των προτέρων. Η μέθοδος Column Generation εκμεταλλεύεται την ιδιαίτερη δομή των περιορισμών του προβλήματος (η οποία μπορεί να αποσυντεθεί σε μικρότερα προβλήματα) και είναι ιδιαιτέρα αποτελεσματική σε προβλήματα, όπου ο αριθμός των μεταβλητών ξεπερνάει κατά πολύ τον αριθμό τον περιορισμών (όπως στην περίπτωση του VRPTW). Βασικό χαρακτηριστικό της μεθόδου είναι ότι, σε αντίθεση με τις κοινές μεθόδους γραμμικού προγραμματισμού, αρχικά μόνο μια μικρή ομάδα μεταβλητών συμμετέχει στο πρόβλημα και σταδιακά προστίθενται νέες μεταβλητές. Η μέθοδος διαχωρίζεται σε δύο προβλήματα τα οποία συνδέονται μεταξύ τους, το Κυρίως Πρόβλημα (Master Problem) και το Υπό-Πρόβλημα (Sub-Problem). Στην περίπτωση μας, το Κυρίως Πρόβλημα μοντελοποιήθηκε ως ένα πρόβλημα Κατάτμησης Συνόλου (Set Partitioning Problem) του οποίου έχουν χαλαρωθεί (relaxed) οι περιορισμοί ακεραιότητας των μεταβλητών. Η επίλυση του διεξάχθηκε με την Revised Simplex μέθοδο, η οποία αποτελεί παραλλαγή του κλασσικού αλγορίθμου Simplex, επιτυγχάνοντας μείωση του υπολογιστικού χρόνου και της iii University of the Aegean Department of Financial and Management Engineering απαιτούμενης υπολογιστικής μνήμης. Ως μεταβλητές του συγκεκριμένου προβλήματος ορίστηκαν ολόκληρα μονοπάτια (δρομολόγια), σε αντίθεση με την κλασσική/ πλήρη μοντελοποίηση του VRPTW όπου οι μεταβλητές του προβλήματος αντιστοιχούν στις ακμές οι οποίες συνδέουν τους πελάτες. Οι μεταβλητές που συμμετέχουν σε αυτό το μοντέλο είναι όλα τα πιθανά εφικτά δρομολόγια. Οι περιορισμοί του μοντέλου αφορούν μόνο το πλήθος εξυπηρέτησης του κάθε πελάτη (κάθε πελάτης επιτρέπεται να μόνο μία φόρα και από ένα δρομολόγιο). Η διαδικασία επίλυσης αρχικοποιείται με μία «γρήγορη» λύση όπου κάθε δρομολόγιο συντίθεται από ένα πελάτη (αριθμός δρομολογίων ίσος με αριθμό πελατών). Η εύρεση των πιθανών εφικτών δρομολογίων παρέχεται από την επίλυση του Υπό-Προβλήματος, μέσω του οποίου σε κάθε επανάληψη προστίθενται καινούργια δρομολόγια. Το Υπό-Πρόβλημα μοντελοποιήθηκε ως ένα πρόβλημα ελάχιστης διαδρομής (Shortest Path Problem) με επιπλέον περιορισμούς, οι οποίοι αφορούν τα χρονικά παράθυρα και την χωρητικότητα του οχήματος (Elementary Shortest Path with Time Windows ad Capacity Constraints). Ο όρος elementary αφορά την απαγόρευση δημιουργίας κύκλων στα μονοπάτια του προβλήματος. Ως κόστη κάθε ακμής του προβλήματος έχουν οριστεί τροποποιημένα κόστη (modified costs) με βάση της σκιώδης τιμές (shadow prices) που παράγονται από την λύση του Κυρίως Προβλήματος. Με τον τρόπο αυτό αναπαράγονται τα reduced cost coefficients της μεθόδου Simplex αν η επίλυση του προβλήματος διενεργούταν με τον κλασσικό τρόπο. Η επίλυση του Υπό-Προβλήματος διεξάχθηκε μέσω χρήσης δυναμικού προγραμματισμού, όπως περιγράφεται στην εργασία του Larsen (2001). Στην συγκεκριμένη εργασία αντιμετωπίζεται το non-elementary πρόβλημα, όπου επιτρέπονται κύκλοι στα δρομολόγια. Σε άλλες αντιμετωπίσεις του προβλήματος, Chabrier (2005), επιλύεται το πρόβλημα με την μορφή που παρουσιάζεται στην παρούσα εργασία, δηλαδή δεν επιτρέπονται κύκλοι. Ο αλγόριθμος βασίστηκε στον αλγόριθμο του Dijkstra (1959) όπου για κάθε πελάτη δημιουργείται μία ταμπέλα (label), η οποία επισημαίνει το κόστος της συντομότερης διαδρομής για τον κάθε πελάτη. Οι επιπλέον περιορισμοί, καθώς και η ύπαρξη αρνητικού κόστους στις ακμές του προβλήματος, απαιτούν την δημιουργία σύνθετων labels τα οποία χαρακτηρίζονται από το κόστος της συντομότερης διαδρομής, την αθροισμένη ζήτηση, τον αθροισμένο χρόνο και το δρομολόγιο μέχρι τον πελάτη τον οποίο αφορά το κάθε label. Επίσης απαιτείται να διατηρούνται περισσότερες από μία ταμπέλες για κάθε πελάτη καθώς τα επιπρόσθετα αυτά χαρακτηριστικά καθιστούν δύσκολη την αναγνώριση και την απόρριψη των labels «χαμηλής ποιότητας». Η απόρριψη των labels «χαμηλής ποιότητας» αποτελεί σημαντικό παράγοντα ο οποίος επηρεάζει τόσο τον υπολογιστικό χρόνο επίλυσης του προβλήματος, όσο και την επίτευξη της βέλτιστης λύσης. Η διαδικασία αυτή διενεργείται μέσω κριτηρίων κυριαρχίας (Dominance Rules) ενός label σε ένα άλλο. Τα κριτήρια κυριαρχίας τα οποία χρησιμοποιήθηκαν στην παρούσα εργασία έχουν παρουσιαστεί από τους Larsen (2001) και Chabrier (2005). Τα βήματα της συνολικής μεθόδου παρουσιάζονται συνοπτικά κατωτέρω: iv 1. Εύρεση της αρχικής λύσης για το Κυρίως Πρόβλημα. 2. Επίλυση του Υπό-Προβλήματος με την μέθοδο Revised Simplex και παράγωγη των σκιωδών τιμών της καλύτερης λύσης (lower bound). 3. Υπολογισμός των τροποποιημένων κοστών (modified costs). 4. Επίλυση του Υπό-Προβλήματος 5. Εάν υπάρχουν δρομολόγια με αρνητικό συνολικό κόστος (reduced cost), εισαγωγή των δρομολογίων αυτών στο Κυρίως Πρόβλημα και επιστροφή στο βήμα 2. Αλλιώς, αν δεν υπάρχει κανένα δρομολόγιο με αρνητικό κόστος συνέχεια στο Βήμα Τερματισμός της διαδικασίας. Η λύση του τελευταίου προβλήματος είναι και η καλύτερη. Η λύση που παράγεται από την παραπάνω μέθοδο αποτελεί το κατώτερο όριο (lower bound) του προβλήματος μιας και έχουν χαλαρωθεί (relaxed) οι περιορισμοί ακεραιότητας των μεταβλητών. Στην συνέχεια, η εύρεση της ακέραιας λύσης διενεργείται μέσω του αλγορίθμου Branch and Bound, μέσα στον οποίο έχει ενσωματωθεί η μέθοδος Column Generation. Μέσω του αλγορίθμου αυτού και εάν η Column Generation καταλήξει σε μη ακεραία λύση δημιουργεί δύο νέα Υπό- Προβλήματα με επιπλέον περιορισμούς, οι οποίοι αφορούν την επιλεγμένη μεταβλητή διακλάδωσης (branching). Στην συνεχεία επιλύονται τα νέα Υπό- Προβλήματα και η διαδικασία αυτή επαναλαμβάνεται μέχρι να βρεθεί η κατάλληλη ακέραια λύση. Η πειραματική διερεύνηση διεξήχθη μέσω των πειραμάτων του Solomon (Solomon, 1987) τα οποία έχουν δημιουργηθεί ειδικά για το πρόβλημα VRPTW. Σκοπός των πειραμάτων ήταν η μελέτη των χαρακτηριστικών της προτεινόμενης μεθόδου, του μεγέθους των προβλημάτων που μπορούν να επιλυθούν, καθώς και η αποτελεσματικότητα της. Τα πειράματα επικεντρώθηκαν στην μελέτη των διαφορετικών κανόνων κυριαρχίας μιας και επηρεάζουν σημαντικά τόσο τον υπολογιστικό χρόνο όσο και την επίτευξη βέλτιστων λύσεων. Για την διεξαγωγή προβλημάτων με μικρό αριθμό πελατών, για τα οποία δεν υπάρχουν δημοσιοποιημένες οι βέλτιστες λύσεις, και τον έλεγχο της αποτελεσματικότητας της προτεινόμενης μεθόδου, χρησιμοποιήθηκε ένας εξαντλητικός αλγόριθμος (Athanasopoulos, 2008b). Ως βασικά συμπεράσματα, σχετικά με την προτεινομένη μέθοδο, αναφέρονται τα εξής: Η μέθοδος χωρίς την χρησιμοποίηση κριτηρίων κυριαρχίας στο Υπό- Πρόβλημα παρουσιάζει μικρότερο χρόνο επίλυσης συγκριτικά με τον εξαντλητικό αλγόριθμο και επιτυγχάνει βέλτιστες λύσεις. Τα κριτήρια κυριαρχίας που προτάθηκαν από τον Chabrier (2005) βοηθούν στην βελτίωση της ταχύτητας επίλυσης των προβλημάτων, επιτυγχάνοντας πάλι την βέλτιστη λύση. Τα κριτήρια κυριαρχίας που προτάθηκαν από τον Larsen (2001) βελτιώνουν σημαντικά της ταχύτητας επίλυσης των προβλημάτων, αλλά v University of the Aegean Department of Financial and Management Engineering σε ορισμένες περιπτώσεις η βέλτιστη λύση δεν επιτυγχάνετε σε συνδυασμό με την μέθοδο επίλυσης του elementary Υπό-Προβλήματος. Μέσω του εξαντλητικού αλγορίθμου και της Column Generation χωρίς την χρησιμοποίηση κριτηρίων κυριαρχίας, επιλύθηκαν προβλήματα έως 9 πελάτες. Μέσω της χρήσης των κριτηρίων κυριαρχίας του Chabrier (2005) επιλύθηκαν προβλήματα έως 25 πελάτες. Προβλήματα περισσοτέρων πελατών αύξαναν δραματικά τον επιθυμητό υπολογιστικό χρόνο. Αντίθετα, μέσω των κριτηρίων κυριαρχίας του Larsen (2001) επιτεύχθηκε επίλυση προβλημάτων μέχρι και 100 πελατών. Από τα 44 προβλήματα με 25, 50 και 100 πελάτες, που επιλύθηκαν με την με την χρήση των κριτηρίων κυριαρχίας του Larsen (2001) στα 31 βρέθηκε η βέλτιστη λύση. Αντίστοιχα, η διαδικασία εισαγωγής πολλαπλών στηλών (δρομολογίων) από κάθε Υπό-Πρόβλημα στο Κυρίως Πρόβλημα παρουσίασε σημαντική μείωση του υπολογιστικού χρόνου επίλυσης (περισσότερο από 600%). Γενικότερα, παρότι η μέθοδος αποτελεί μία σημαντική μέθοδο για την ακριβή επίλυση του VRPTW, περεταίρω έρευνα για την δημιουργία πιο αποτελεσματικών κριτηρίων κυριαρχίας και τεχνικών που θα μειώσουν τον απαιτούμενο υπολογιστικό χρόνο και θα διατηρήσουν την ποιότητα της παρεχόμενης λύσης, θα πρέπει να μελετηθούν και να αναπτυχθούν. vi ABSTRACT In this thesis we develop a toolkit to obtain efficient solutions for the Vehicle Routing Problem with Time Windows and Capacity Constraints (VRPTW) This toolkit has been based on the work of Larsen (2001) and Chabrier (2005) and has implemented the following methods / algorithms proposed in these references: A Linear Programming Algorithm that uses the revised simplex method A Column Generation Technique for linear problems A Dynamic Labeling Algorithm for the Shortest Path Problem with additional constraints. A Branch and Bound Algorithm to obtain integer solutions These techniques are used in the following framework originally proposed by Larsen (2001): To obtain a good lower bound, the integrality constraints are relaxed, and the resulting general linear problem is divided in two separate problems; the Master Problem and the Sub-problem. The first one is formulated as a Set Partitioning Problem and it is solved through the revised simplex method. The dual (shadow) prices produced by this problem are sent to the sub-problem. The latter is formulated as an Elementary Shortest Path Problem with Time Windows and Capacity Constraints (ESPPTWCC). It is solved through
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks