Frequency of service in retail distribution networks: enhancement and implementation of an optimal approach

Abstract

Η προτεινόμενη διπλωματική εργασία εστιάζει στο πρόβληµα Καθορισμού της Επισκεψιµότητας σε ∆ίκτυο ∆ιανοµής με στόχο την μεγιστοποίηση του κέρδους σε συγκεκριμένο χρονικό ορίζοντα. Το πρόβλημα περιγράφεται από μοντέλο ακέραιου προγραμματισμού και επιλύεται µε τον αλγόριθμο διαδοχικών ορίων (Branch and Bound) για την εύρεση των βέλτιστων λύσεων και µε προτεινόμενο ευρετικό αλγόριθμο για την επίλυση προβλημάτων πρακτικού μεγέθους. Το συγκεκριμένο πρόβλημα έχει επιλυθεί προηγουμένως από προπτυχιακή διπλωματική εργασία που αναπτύχθηκε στο εργαστήριο ΣυΣΠαΛ του Πανεπιστημίου Αιγαίου. Στη προσπάθεια αυτή, το πρόβλημα επιλύθηκε για προβλήματα πρακτικού μεγέθους με ευρετικό αλγόριθμο. Η προσέγγιση βέλτιστης επίλυσης του προβλήματος αυτού με τη μέθοδο των διαδοχικών ορίων περιορίστηκε μόνο σε ένα μικρό πλήθος πελατών λόγω της μεγάλης πολυπλοκότητας του προβλήματος (μεγάλο πλήθος μεταβλητών και περιορισμών). Συνεπώς, στο πλαίσιο της παρούσας Διπλωματικής εργασίας υλοποιήσαμε το πρόγραμμα με εργαλεία C++ και συνεισφέραμε στα εξής:• Επίλυση υφισταμένων προβλημάτων σε ταχύτερους υπολογιστικούς χρόνους• Επίλυση προβλημάτων μεγαλύτερης κλίμακας συγκριτικά με τη δυνατότητα του προηγούμενου αλγορίθμου.Επιπρόσθετα, στα πλαίσια της παρούσας διατριβής αναπτύχθηκε κατάλληλη εφαρμογή με δυνατότητα γραφικού περιβάλλοντος χρήστη, η οποία πέρα από την υλοποίηση του αλγόριθμου, παρέχει γραφικό περιβάλλον με πραγματικούς γεωγραφικούς χάρτες για τον καθορισμό των δεδομένων εισόδου αλλά και την οπτικοποίηση των παραγόμενων αποτελεσμάτων (διαδρομή και κόστος αυτής).

The focus of the current master thesis is set on the definition of the frequency of service in a distribution network by maximizing the profit in a specific time window. The problem is modeled using integer mathematical programming and is solved using the Brach and Bound algorithm in order to find the optimal solution.This problem has already been solved within an Undergraduate thesis developed by the DeOpSys team of the University of the Aegean by Asimakopoulos (2006). In that effort the focus was given in solving practical sized problems using a specific heuristic algorithm. The actual solution of the problem using the Branch and Bound algorithm was narrowed down to a small number of clients due to the high complexity of the problem (number of variables and constraints).Therefore, primary goal of this thesis is to enhanced solution method in order to have better computational times than the previous approach and be able to solve larger problems.More specifically, we developed a software tool in C++ that implements the above mentioned algorithm and provides:• Better solution times for problems being solved by Asimakopoulos (2006) application• Solution of bigger problems while keeping the same algorithmFinally, a windows application as interface of the algorithm was implemented. This application provides interface for entering the project’s input data and representation of coordinates in geographical maps (Google maps) as well as generation of the results (route and cost) on the same maps.