Βελτιστοποίηση του χρόνου εξυπηρέτησης σημείων ζήτησης και φορτίου οχημάτων διανομής / συλλογής σε αστικό δίκτυο

Abstract

The Vehicle Routing Problems (VRP) consists in designing an optimal set of routes for a fleet of vehicles in order to serve a number of geographically dispersed demands in an urban network. In general the objective of the VRP’s is to serve a set of demand locations on minimum-cost vehicle routes. The VRP’s belong to the class of NP-Hard problems implying that the computational effort required to solve these problems increases exponentially with the problem size. Therefore, in real-life practical cases such problems are confronted by developing heuristic methods. Variations of VRP’s appear depending on the imposed side restrictions and/or on the optimality objective. A prevalent variation of the VRP called the capacitated VRP (CVRP) assumes that vehicle capacity is limited and that the sum of demands in a route served by a vehicle should not surpass its capacity. The CVRP investigated here consider the optimality objective that find a set of vehicle tours in order to complete the service of all the demands in a minimum possible time in the framework of attaining a maximum uniform vehicle utilization, simultaneously taking into account a smooth vehicle loading throughout the vehicle fleet. Regarding this problem two new heuristic algorithm BRL (Balance Routing Loading) and BRL-W are developed. The BRL-W algorithm additionally deals the case where a subset of demands require to be served within a specific time window. An extensive computational experiment on BRL and on generated data that meets real-world situation is performed for networks with sizes that vary from 50 to 1000 demands with a 50-demand step. Furthermore, both algorithm were tested on the network that enclose the center of the city of Thessaloniki comprising 103 demand points. The quality of the obtained computational results regarding the service completion time as well as vehicle utilization and loading balance seems to be quite encouraging, while the needed computational time is negligible, since the execution of BRL for 500 demands required one second and for 1000 demands 9 seconds respectively. Concerning the Thessaloniki center network the execution time for both algorithms needed a fraction of a second. The last chapter is dedicated to proposals for further research. The appendix contains the (Μicrosoft Visual Basic 6.0, 2003) computer programs that correspond to all procedures developed in this dissertation.

Ο αντικειμενικός στόχος της ερευνητικής προσπάθειας που αφορά αυτήν τη διατριβή είναι ο προσδιορισμός των διαδρομών k οχημάτων αντίστοιχου στόλου για την εξυπηρέτηση ( κάλυψη ) κορυφών ζήτησης σε δίκτυο με στόχο την εξισορρόπηση του χρόνου χρήσης των οχημάτων καθώς και του φορτίου τους με βασικό κριτήριο βελτιστοποίησης την ολοκλήρωση της κάλυψης όλων των κορυφών ζήτησης στο μικρότερο δυνατό χρόνο. Συγκεκριμένα για το σκοπό αυτό αναπτύχθηκε ένας νέος ευρετικός αλγόριθμος που ονομάστηκε BRL (Balance Routing Loading). Ακόμη σε πολλές περιπτώσεις συμβαίνει να υπάρχουν σημεία ζήτησης που το καθένα από αυτά απαιτεί όπως ο χρόνος επίσκεψης ενός οχήματος εξυπηρέτησης να είναι μέσα σε ένα χρονικό παράθυρο ( time window ). Για την περίπτωση αυτή και στα πλαίσια του BRL αναπτύχθηκε ο αλγόριθμος BRL-W. O BRL και BRL-W ως προβλήματα προσδιορισμού διαδρομών οχημάτων γνωστά στη διεθνή αρθρογραφία και ως VRP (Vehicle Routing Problem) ανήκουν στην κατηγορία των NP-σκληρών προβλημάτων και μπορεί να χαρακτηριστούν και ως πολύ-κριτήρια. Πραγματοποιήθηκε εκτεταμένη υπολογιστική εμπειρία για τον BRL σε δίκτυα που δημιουργήθηκαν με τυχαία δεδομένα που συναντούν πρακτικές καταστάσεις πραγματικού κόσμου και για μεγέθη που κυμαίνονταν από 50 έως 1000 κορυφές ζήτησης. Η ποιότητα των αποτελεσμάτων αναφορικά με τον συνολικό χρόνο κάλυψης όλων των σημείων ζήτησης καθώς και ως προς τον βαθμό εξισορρόπησης του χρόνου χρήσης των οχημάτων και του αντίστοιχου φορτίου του φαίνεται να είναι πολύ ενθαρρυντικά. Οι απαιτούμενοι υπολογιστικοί χρόνοι για 500 και 1000 κορυφές ζήτησης ήταν 1 και 9 δευτερόλεπτα αντίστοιχα. Οι δύο αλγόριθμοι εφαρμόστηκαν στο δίκτυο στον οποίο περικλείεται το κέντρο της Θεσσαλονίκης που αποτελείται από 103 κορυφές ζήτησης και ο απαιτούμενος υπολογιστικός χρόνος για κάθε ένα από αυτά ήταν κλάσματα του δευτερολέπτου. Το τελευταίο κεφάλαιο είναι αφιερωμένο σε προτάσεις για περαιτέρω έρευνα. Όλες οι αλγοριθμικές μέθοδοι που αναπτύσσονται στη διατριβή υλοποιήθηκαν σε προγράμματα Η/Υ σε γλώσσα Visual (Μicrosoft Visual Basic 6.0, 2003), τα αντίστοιχα προγράμματα είναι το περιεχόμενο του παραρτήματος.