AUEB Library - Digital Repository

PYXIDA Institutional Repository
and Digital Library

Username
Password

Collections :	Ιδρυματικό Αποθετήριο ΟΠΑ / AUEB Institutional Repository Σχολή Διοίκησης Επιχειρήσεων / School of Business Τμήμα Οργάνωσης και Διοίκησης Επιχειρήσεων / Department of Business Administration Μεταπτυχιακές Εργασίες / Postgraduate dissertations Τμήμα Επικοινωνίας και Μάρκετινγκ / Department of Marketing and Communication Μεταπτυχιακές Εργασίες / Postgraduate dissertations

Title :	Local search algorithms for the pickup and delivery problem with cross-docking

Creator :	Fidanis, Ioannis

Contributor :	Tarantilis, Christos (Επιβλέπων καθηγητής) Athens University of Economics and Business, Department of Business Administration (Degree granting institution) Athens University of Economics and Business, Department of Marketing and Communication (Degree granting institution)

Type :	Text

Extent :	48p.

Language :	en

Abstract :	The efficient management of a distribution network is crucial for logistic companies and transportation service providers. Transportation costs represent a large percentage of the logistics costs. The costs associated with transport, have a direct impact on the final value consumers must pay. Therefore, the academic community and practitioners have put substantial effort in conducting research for finding optimal ways to decrease transportation costs and increase customer service.The Vehicle Routing Problem (VRP) represents a class of problems that are commonly encountered by transportation companies. In its general form, the objective of the VRP is to design a set of minimum cost routes in order to serve a set of customers under several constraints. Large scale VRPs are very difficult to be solved optimally by an exact algorithm and thus, approximate methods have been developed in order to address these problems and produce solutions of high quality.In practical applications, the distribution of products from a set of suppliers to a set of customers can be performed through two different distribution strategies: i) direct-shipping, and ii) cross-docking. A Cross-dock (CD) can be considered as an intermediate station for consolidating shipments from various suppliers, before delivering them to their final destinations.This work studies a distribution network where both of the aforementioned strategies may appear and it is referred in the literature as the Pickup and Delivery problem with Cross-Docking (PDPCD). The objective of this problem is to find the least cost set of vehicle routes for distributing products from a set of suppliers to a set of customers. The cost representation may vary through various implementations. In this work, the total transportation cost is considered to be the total routing cost (or total distance travelled).Three different algorithms are introduced in order to solve the PDPCD problem. The first algorithm is a Greedy Algorithm which is based on the best decision that can be made at each step of the execution. A vehicle starts from the origin point (depot or CD) and visits the closest node to its current position. It continues visiting nodes till any of the predefined problem’s constraint is met (capacity and time constraints). At this point, a decision is made whether the vehicle will return to the origin point or it will start delivering the loaded goods. This procedure is being repeated for all the vehicles and until all the nodes are served. At the end of this algorithm, a total transportation cost is calculated.Next, we present two tabu search algorithms in an effort to improve the initial solution. For this purpose, two different move types are applied: a relocation move type and an exchange move type. The relocation move aims to reduce the total cost by relocating a node from a vehicle to another vehicle. The exchange move aims to reduce the total cost by exchanging two nodes with each other belonging to different vehicles. The tabu search algorithm introduces a tabu list to forbid certain moves from being applied to the current solution. Moves are considered feasible if they do not violate any of the problem constraints. In addition, an enhanced tabu search algorithm is developed which is able to simultaneously consider both move types at each execution step. The algorithm selects the best solution out of them as the candidate one at each step. We examine the impact on the total routing costs compared to the simple tabu search algorithm.Various computational experiments are conducted in order to examine the performance of the two developed algorithms on benchmark problem instances of the literature. For this purpose, we investigate the impact on total routing costs by using the simple tabu search algorithm considering only a move type each time, as well as the enhanced tabu search algorithm which considers both move types simultaneously. Η αποτελεσματική διαχείριση ενός δικτύου διανομής προϊόντων είναι πολύ σημαντική για τις εταιρίες εφοδιασμού και μεταφορών. Το κόστος μεταφοράς αγαθών αποτελεί ένα μεγάλο μέρος του συνολικού κόστους των εταιρειών και συνδέεται άμεσα με την τελική τιμή του προϊόντος. Για το λόγο αυτό, τόσο ακαδημαϊκοί όσο και επαγγελματίες στον τομέα των μεταφορών έχουν αφοσιωθεί στην αναζήτηση βέλτιστων τρόπων μείωσης του κόστους μεταφοράς καθώς και αύξησης του επιπέδου εξυπηρέτησης των καταναλωτών.Το πρόβλημα δρομολόγησης στόλου οχημάτων (Vehicle Routing Problem – VRP) αποτελεί μια ευρύτερη κλάση προβλημάτων δρομολόγησης που αντιμετωπίζουν σε καθημερινή βάση οι εταιρίες μεταφορών. Ο σκοπός του VRP είναι να βρεθεί ένα σύνολο από διαδρομές που ελαχιστοποιούν το συνολικό κόστος μεταφοράς, έχοντας εξυπηρετηθεί όλοι οι ενδιάμεσοι σταθμοί, χωρίς να παραβιάζεται κάποιος περιορισμός. Ωστόσο, η επίλυση μεγάλης κλίμακας προβλημάτων, απαιτεί μεγάλους υπολογιστικούς χρόνους και είναι δύσκολο να πραγματοποιηθεί από έναν ακριβή αλγόριθμο. Για τον λόγο αυτό, χρησιμοποιούνται προσεγγιστικές μέθοδοι οι οποίες είναι σε θέση να βρίσκουν πολύ καλές λύσεις εντός αποδεκτών υπολογιστικών χρόνων.Η διανομή των προϊόντων από ένα σύνολο προμηθευτών σε ένα σύνολο πελατών μπορεί να επιτευχθεί με δύο τρόπους: α) μέσω απευθείας μεταφοράς από προμηθευτή σε πελάτη β) μέσω ενός σταθμού φόρτωσης/εκφόρτωσης (Cross-Dock - CD). Ο σταθμός CD αποτελεί έναν ενδιάμεσο σταθμό για την διαχείριση των μεταφορών.Η παρούσα εργασία μελετά ένα δίκτυο διανομής στο οποίο χρησιμοποιούνται και οι δύο προαναφερθείσες μέθοδοι διανομής. Το πρόβλημα αυτό είναι γνωστό ως πρόβλημα Παραλαβής και Παράδοσης με την χρήση σταθμού φόρτωσης/εκφόρτωσης (Pickup and Delivery problem with Cross-Docking – PDPCD). Σκοπός είναι η εύρεση του βέλτιστου συνόλου διαδρομών που ελαχιστοποιούν το συνολικό κόστος μεταφοράς. Στην εργασία αυτή, ως κόστος μεταφοράς ορίζεται η συνολική απόσταση που διανύεται από τα οχήματα.Για την επίλυση του PDPCD υλοποιήθηκαν τρεις διαφορετικοί αλγόριθμοι. Ο πρώτος αλγόριθμος είναι ένας Greedy αλγόριθμος και βασίζεται στην βέλτιστη απόφαση σε κάθε βήμα εκτέλεσης. Ένα όχημα ξεκινάει από το αρχικό σημείο εκκίνησης (αποθήκη ή σταθμός φόρτωσης/εκφόρτωσης), μεταβαίνει στον πλησιέστερο κόμβο και συνεχίζει να επισκέπτεται κόμβους έως ότου παραβιαστεί κάποιος περιορισμός. Στο σημεία αυτό, το όχημα καλείται να πάρει μία σημαντική απόφαση: αν θα επιστρέψει στο σημείο εκκίνησης ή θα ξεκινήσει την διαδικασία παράδοσης. Η διαδικασία αυτή επαναλαμβάνεται για όλα τα οχήματα και για όλους τους κόμβους και ολοκληρώνεται μέχρις ότου να εξυπηρετηθούν όλοι οι κόμβοι. Τέλος, υπολογίζεται το συνολικό κόστος μεταφοράς.Στη συνέχεια υλοποιείται ένας αλγόριθμος απαγορευμένης αναζήτησης (tabu search) με σκοπό την βελτίωση της αρχικής λύσης. Εφαρμόζονται δύο διαφορετικές κινήσεις: μία κίνηση μετάθεσης ενός κόμβου από ένα όχημα σε κάποιο άλλο και, μία κίνηση ανταλλαγής δύο κόμβων από διαφορετικά οχήματα. Κατά την εκτέλεση του αλγορίθμου, διατηρείται μία λίστα με τις προηγούμενες κινήσεις για να είναι δυνατή η σύγκριση και η πιθανή απαγόρευση της επόμενης. Επιπρόσθετα, σχεδιάζεται ένας βελτιωμένος αλγόριθμος, ο οποίος εξετάζει ταυτόχρονα σε κάθε βήμα εκτέλεσης και τις δύο κινήσεις. Ο αλγόριθμός επιλέγει κάθε φορά την κίνηση που οδηγεί σε καλύτερη λύση (μειωμένο κόστος μεταφοράς).Τέλος, παρουσιάζονται αποτελέσματα από την υλοποίηση του αλγορίθμου απαγορευμένης αναζήτησης καθώς και του βελτιωμένου αλγορίθμου σε πρότυπα προβλήματα της βιβλιογραφίας. Τα αποτελέσματα χρησιμοποιούνται συγκριτικά προκειμένου να γίνει αξιολόγηση της επίδοσης των δυο αλγορίθμων.

Abstract :

The efficient management of a distribution network is crucial for logistic companies and transportation service providers. Transportation costs represent a large percentage of the logistics costs. The costs associated with transport, have a direct impact on the final value consumers must pay. Therefore, the academic community and practitioners have put substantial effort in conducting research for finding optimal ways to decrease transportation costs and increase customer service.The Vehicle Routing Problem (VRP) represents a class of problems that are commonly encountered by transportation companies. In its general form, the objective of the VRP is to design a set of minimum cost routes in order to serve a set of customers under several constraints. Large scale VRPs are very difficult to be solved optimally by an exact algorithm and thus, approximate methods have been developed in order to address these problems and produce solutions of high quality.In practical applications, the distribution of products from a set of suppliers to a set of customers can be performed through two different distribution strategies: i) direct-shipping, and ii) cross-docking. A Cross-dock (CD) can be considered as an intermediate station for consolidating shipments from various suppliers, before delivering them to their final destinations.This work studies a distribution network where both of the aforementioned strategies may appear and it is referred in the literature as the Pickup and Delivery problem with Cross-Docking (PDPCD). The objective of this problem is to find the least cost set of vehicle routes for distributing products from a set of suppliers to a set of customers. The cost representation may vary through various implementations. In this work, the total transportation cost is considered to be the total routing cost (or total distance travelled).Three different algorithms are introduced in order to solve the PDPCD problem. The first algorithm is a Greedy Algorithm which is based on the best decision that can be made at each step of the execution. A vehicle starts from the origin point (depot or CD) and visits the closest node to its current position. It continues visiting nodes till any of the predefined problem’s constraint is met (capacity and time constraints). At this point, a decision is made whether the vehicle will return to the origin point or it will start delivering the loaded goods. This procedure is being repeated for all the vehicles and until all the nodes are served. At the end of this algorithm, a total transportation cost is calculated.Next, we present two tabu search algorithms in an effort to improve the initial solution. For this purpose, two different move types are applied: a relocation move type and an exchange move type. The relocation move aims to reduce the total cost by relocating a node from a vehicle to another vehicle. The exchange move aims to reduce the total cost by exchanging two nodes with each other belonging to different vehicles. The tabu search algorithm introduces a tabu list to forbid certain moves from being applied to the current solution. Moves are considered feasible if they do not violate any of the problem constraints. In addition, an enhanced tabu search algorithm is developed which is able to simultaneously consider both move types at each execution step. The algorithm selects the best solution out of them as the candidate one at each step. We examine the impact on the total routing costs compared to the simple tabu search algorithm.Various computational experiments are conducted in order to examine the performance of the two developed algorithms on benchmark problem instances of the literature. For this purpose, we investigate the impact on total routing costs by using the simple tabu search algorithm considering only a move type each time, as well as the enhanced tabu search algorithm which considers both move types simultaneously.
Η αποτελεσματική διαχείριση ενός δικτύου διανομής προϊόντων είναι πολύ σημαντική για τις εταιρίες εφοδιασμού και μεταφορών. Το κόστος μεταφοράς αγαθών αποτελεί ένα μεγάλο μέρος του συνολικού κόστους των εταιρειών και συνδέεται άμεσα με την τελική τιμή του προϊόντος. Για το λόγο αυτό, τόσο ακαδημαϊκοί όσο και επαγγελματίες στον τομέα των μεταφορών έχουν αφοσιωθεί στην αναζήτηση βέλτιστων τρόπων μείωσης του κόστους μεταφοράς καθώς και αύξησης του επιπέδου εξυπηρέτησης των καταναλωτών.Το πρόβλημα δρομολόγησης στόλου οχημάτων (Vehicle Routing Problem – VRP) αποτελεί μια ευρύτερη κλάση προβλημάτων δρομολόγησης που αντιμετωπίζουν σε καθημερινή βάση οι εταιρίες μεταφορών. Ο σκοπός του VRP είναι να βρεθεί ένα σύνολο από διαδρομές που ελαχιστοποιούν το συνολικό κόστος μεταφοράς, έχοντας εξυπηρετηθεί όλοι οι ενδιάμεσοι σταθμοί, χωρίς να παραβιάζεται κάποιος περιορισμός. Ωστόσο, η επίλυση μεγάλης κλίμακας προβλημάτων, απαιτεί μεγάλους υπολογιστικούς χρόνους και είναι δύσκολο να πραγματοποιηθεί από έναν ακριβή αλγόριθμο. Για τον λόγο αυτό, χρησιμοποιούνται προσεγγιστικές μέθοδοι οι οποίες είναι σε θέση να βρίσκουν πολύ καλές λύσεις εντός αποδεκτών υπολογιστικών χρόνων.Η διανομή των προϊόντων από ένα σύνολο προμηθευτών σε ένα σύνολο πελατών μπορεί να επιτευχθεί με δύο τρόπους: α) μέσω απευθείας μεταφοράς από προμηθευτή σε πελάτη β) μέσω ενός σταθμού φόρτωσης/εκφόρτωσης (Cross-Dock - CD). Ο σταθμός CD αποτελεί έναν ενδιάμεσο σταθμό για την διαχείριση των μεταφορών.Η παρούσα εργασία μελετά ένα δίκτυο διανομής στο οποίο χρησιμοποιούνται και οι δύο προαναφερθείσες μέθοδοι διανομής. Το πρόβλημα αυτό είναι γνωστό ως πρόβλημα Παραλαβής και Παράδοσης με την χρήση σταθμού φόρτωσης/εκφόρτωσης (Pickup and Delivery problem with Cross-Docking – PDPCD). Σκοπός είναι η εύρεση του βέλτιστου συνόλου διαδρομών που ελαχιστοποιούν το συνολικό κόστος μεταφοράς. Στην εργασία αυτή, ως κόστος μεταφοράς ορίζεται η συνολική απόσταση που διανύεται από τα οχήματα.Για την επίλυση του PDPCD υλοποιήθηκαν τρεις διαφορετικοί αλγόριθμοι. Ο πρώτος αλγόριθμος είναι ένας Greedy αλγόριθμος και βασίζεται στην βέλτιστη απόφαση σε κάθε βήμα εκτέλεσης. Ένα όχημα ξεκινάει από το αρχικό σημείο εκκίνησης (αποθήκη ή σταθμός φόρτωσης/εκφόρτωσης), μεταβαίνει στον πλησιέστερο κόμβο και συνεχίζει να επισκέπτεται κόμβους έως ότου παραβιαστεί κάποιος περιορισμός. Στο σημεία αυτό, το όχημα καλείται να πάρει μία σημαντική απόφαση: αν θα επιστρέψει στο σημείο εκκίνησης ή θα ξεκινήσει την διαδικασία παράδοσης. Η διαδικασία αυτή επαναλαμβάνεται για όλα τα οχήματα και για όλους τους κόμβους και ολοκληρώνεται μέχρις ότου να εξυπηρετηθούν όλοι οι κόμβοι. Τέλος, υπολογίζεται το συνολικό κόστος μεταφοράς.Στη συνέχεια υλοποιείται ένας αλγόριθμος απαγορευμένης αναζήτησης (tabu search) με σκοπό την βελτίωση της αρχικής λύσης. Εφαρμόζονται δύο διαφορετικές κινήσεις: μία κίνηση μετάθεσης ενός κόμβου από ένα όχημα σε κάποιο άλλο και, μία κίνηση ανταλλαγής δύο κόμβων από διαφορετικά οχήματα. Κατά την εκτέλεση του αλγορίθμου, διατηρείται μία λίστα με τις προηγούμενες κινήσεις για να είναι δυνατή η σύγκριση και η πιθανή απαγόρευση της επόμενης. Επιπρόσθετα, σχεδιάζεται ένας βελτιωμένος αλγόριθμος, ο οποίος εξετάζει ταυτόχρονα σε κάθε βήμα εκτέλεσης και τις δύο κινήσεις. Ο αλγόριθμός επιλέγει κάθε φορά την κίνηση που οδηγεί σε καλύτερη λύση (μειωμένο κόστος μεταφοράς).Τέλος, παρουσιάζονται αποτελέσματα από την υλοποίηση του αλγορίθμου απαγορευμένης αναζήτησης καθώς και του βελτιωμένου αλγορίθμου σε πρότυπα προβλήματα της βιβλιογραφίας. Τα αποτελέσματα χρησιμοποιούνται συγκριτικά προκειμένου να γίνει αξιολόγηση της επίδοσης των δυο αλγορίθμων.

Subject :	Pickup and Delivery problem with Cross-Docking (PDPCD) Vehicle Routing Problem (VRP) Tabu search Greedy algorithm Πρόβλημα παραλαβής και παράδοσης με την χρήση σταθμού φόρτωσης/εκφόρτωσης Πρόβλημα δρομολόγησης στόλου οχημάτων Αλγόριθμος απαγορευμένης αναζήτησης Greedy αλγόριθμος

Subject :

Pickup and Delivery problem with Cross-Docking (PDPCD)
Vehicle Routing Problem (VRP)
Tabu search
Greedy algorithm
Πρόβλημα παραλαβής και παράδοσης με την χρήση σταθμού φόρτωσης/εκφόρτωσης
Πρόβλημα δρομολόγησης στόλου οχημάτων
Αλγόριθμος απαγορευμένης αναζήτησης
Greedy αλγόριθμος

Date :	29-11-2016

Licence :

File: Fidanis_2016.pdf

Type: application/pdf

Login