Back to search

Aristotle University Of Thessaloniki (AUTH)

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

Abstract

dc:description

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.

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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/19901

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Tsouros, Michael-Aggelos; Τσούρος, Άγγελος-Μιχαήλ. Βελτιστοποίηση του χρόνου εξυπηρέτησης σημείων ζήτησης και φορτίου οχημάτων διανομής / συλλογής σε αστικό δίκτυο. Aristotle University Of Thessaloniki (AUTH), 2010. http://hdl.handle.net/10442/hedi/19901