Aristotle University Of Thessaloniki (AUTH)
Βελτιστοποίηση του χρόνου εξυπηρέτησης σημείων ζήτησης και φορτίου οχημάτων διανομής / συλλογής σε αστικό δίκτυο
Abstract
dc:descriptionThe 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.
Degree
thesis:*- Grantor dc:publisher
- Aristotle University Of Thessaloniki (AUTH)
- Year dc:date
- 2010
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Tsouros, Michael-Aggelos
- Τσούρος, Άγγελος-Μιχαήλ
Subjects
dc:subject × 20- Βελτιστοποίηση
- Εξισορρόπηση
- Αλγόριθμοι
- Διαδρομές οχημάτων
- Χρονικά παράθυρα
- Σημεία ζήτησης
- Ελαχιστοποίηση συνολικού χρόνου εξυπηρέτησης
- NP-σκληρό πρόβλημα
- Optimization
- Balancing
- Algorithms
- Vehicle routing
- Time windows
- Demand nodes
- Minimize total time
- NP-hard problem
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Πολιτικού Μηχανικού
- Engineering and Technology
- Civil Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/19901