Εφαρμογή τεχνικών ομαδοποίησης σε μοντέλα κάλυψης ζήτησης

Abstract

The present thesis offers alternative techniques for the solution of difficult and time-consuming location problems. The need of solutions with satisfying results in the minimum possible time for a great range of location problems with applications in everyday life, encourages the search of alternative solution methods. These methods can derive from different scientific fields. In this thesis, a specific clustering technique from data mining is evaluated, the biclustering technique.The key factors in most location problems are the demand points and the facilities which serve these demand points according to a distance metric. The possibility of service or non-service of demand points by the facilities is based on this metric.The biclustering approach adopted in this thesis, gets as input a table with rows and columns that correspondingly represent the demand points and the facilities and leads to the creation of sub-groups of lines and columns which have some common behavior when compared to other sub-groups.The possible combinations created by the biclusters offer alternative solutions to the location problem under study, i.e. groups of facilities that serve groups of demand points. Based on an evaluation function of biclusters, which is slightly modified depending on the problem which is solved, one or more that give the best result are chosen. It should be noted that the application of this technique is also considered in some extensions of the basic problems, which have not yet been studied in the bibliography.This method provides solutions close to the optimal ones, but in negligible time for various location problems. The primary feature of the proposed technique is its flexibility and adaptability. In the dissertation, experimental tests were performed on various data sets that are considered as benchmarks in the literature for a series of location problems. Therefore, It has been shown that the technique can be applied to different location problems with slight modifications in order to meet the different objectives of each problem and offers satisfactory solutions in comparison to the optimal ones provided by the optimization package.A further contribution of this dissertation is the implementation of a location problem in Recommender Systems, which, due to their multiple applications in various fields but mainly in Marketing, are considered as an important field of research.

Η παρούσα Διδακτορική Διατριβή επιχειρεί να προσφέρει εναλλακτικές τεχνικές επίλυσης πολύπλοκων και χρονοβόρων προβλημάτων χωροθέτησης. Η ανάγκη για παροχή λύσεων με ικανοποιητικά αποτελέσματα σε ελάχιστο χρόνο, για πληθώρα προβλημάτων χωροθέτησης με πολλαπλές εφαρμογές στην καθημερινότητα, ενθαρρύνει την αναζήτηση εναλλακτικών τρόπων επίλυσης. Οι εναλλακτικοί αυτοί τρόποι επίλυσης μπορεί να προέρχονται από διάφορα επιστημονικά πεδία. Στην παρούσα Διατριβή, εξετάζεται για πρώτη φορά η αξιοποίηση μίας ειδικής τεχνικής ομαδοποίησης, από το πεδίο της εξόρυξης δεδομένων (data mining), η ευρετική μέθοδος biclustering.Οι βασικοί παράγοντες στα περισσότερα προβλήματα χωροθέτησης είναι τα σημεία που εκφράζουν ζήτηση και τα κέντρα που εξυπηρετούν αυτά τα σημεία, με βάση μία μετρική απόστασης με βάση την οποία προκύπτει η δυνατότητα ή μη εξυπηρέτησης των σημείων ζήτησης από τα κέντρα εξυπηρέτησης. Η μέθοδος biclustering που υιοθετείται στην παρούσα Διατριβή, λαμβάνει έναν αρχικό πίνακα εισόδου με γραμμές και στήλες που αντιπροσωπεύουν αντίστοιχα σημεία ζήτησης και κέντρα εξυπηρέτησης και οδηγεί στη δημιουργία υπο-ομάδων από γραμμές και στήλες, οι οποίες έχουν κάποια κοινή συμπεριφορά έναντι των υπολοίπων ομάδων.Οι δυνατοί συνδυασμοί που δημιουργούνται μέσω των biclusters προτείνουν ουσιαστικά εναλλακτικές λύσεις στο εκάστοτε πρόβλημα χωροθέτησης, δηλαδή ομάδες από κέντρα που εξυπηρετούν ομάδες από σημεία ζήτησης. Με βάση μία συνάρτηση αξιολόγησης των biclusters, η οποία τροποποιείται ελάχιστα ανάλογα με το πρόβλημα που επιλύεται, επιλέγεται αυτό ή αυτά που δίνουν το καλύτερο αποτέλεσμα, αυτό δηλαδή που είναι πιο κοντά στη βέλτιστη λύση. Ας σημειωθεί, ότι εξετάζεται η εφαρμογή αυτής της τεχνικής και σε επεκτάσεις των βασικών προβλημάτων, οι οποίες δεν έχουν μελετηθεί ιδιαίτερα στη βιβλιογραφία.Η μέθοδος αυτή παρέχει λύσεις κοντά στις βέλτιστες, αλλά σε ελάχιστο χρόνο για διάφορα προβλήματα χωροθέτησης. Χαρακτηριστικό της προτεινόμενης τεχνικής είναι η ευελιξία και η προσαρμοστικότητά της. Στη Διατριβή διενεργήθηκαν δοκιμές σε διάφορα σύνολα δεδομένων που χρησιμοποιούνται ευρέως στη βιβλιογραφία, για μία σειρά από προβλήματα χωροθέτησης. Παρατηρήθηκε, λοιπόν, ότι η τεχνική προσαρμόζεται, με ελάχιστες τροποποιήσεις, για την εκπλήρωση των διαφορετικών αντικειμενικών στόχων του κάθε προβλήματος και προσφέρει ικανοποιητικές λύσεις σε σύγκριση με τις βέλτιστες λύσεις που παρέχει κάθε φορά το πακέτο βελτιστοποίησης.Μία επιπλέον συνεισφορά της παρούσας Διατριβής είναι η εφαρμογή ενός προβλήματος χωροθέτησης στα Συστήματα Συστάσεων (Recommender Systems), τα οποία λόγω των πολλαπλών τους εφαρμογών σε διάφορους τομείς, αλλά κυρίως στο Μάρκετινγκ, αποτελούν σημαντικό τομέα έρευνας.