Technical University of Crete (TUC)
Μοντελοποίηση και υλοποίηση αλγορίθμων επίλυσης προβλημάτων δρομολόγησης οχημάτων με επιλεκτική εξυπηρέτηση πελατών
Abstract
dc:descriptionThe present dissertation concerns the investigation of vehicle routing problems with selective customer service and the creation of appropriate algorithmic methods for their solution. In particular, it was considered the application of selective routing problems in emergency situations, e.g., fire or flood. As such, the Prize-Collecting Vehicle Routing Problem (PCVRP) was selected to simulate the routing of a homogeneous fleet of fire trucks. PCVRP covers the routing needs of firefighting vehicles, aiming at quick access to the points that need protection and the greatest benefit from the respective actions. Nevertheless, the launch of emergency vehicles must also take into account the related environmental impact. For this reason, two new mathematical models are proposed in this dissertation, as variants of PCVRP, the Environmental Prize-Collecting Vehicle Routing Problem (E-PCVRP) and the Green Prize-Collecting Vehicle Routing Problem (Green-PCVRP). Also, the Asset Protection Problem (APP) was chosen to simulate the routing of a heterogeneous fleet of fire trucks. This problem has been proposed for the coordinated and synchronized routing of fire trucks in the protection of key community assets. The APP is considered a particularly demanding problem due to the heterogeneous vehicle fleet, the different needs of each point (in type and number of vehicles), the time constraints for the protection of each point, and the need to synchronize the vehicles (spatial and temporal). The problems under consideration are variations of the classic routing problem, and nature-inspired algorithms are used to optimize them. Specifically, for the algorithmic optimization of the proposed Green-PCVRP problem, the Bat Algorithm (BA) was chosen, which, however, is designed to solve continuously variable problems, while the examined problem requires a discrete solution coding. Thus, two new algorithmic frameworks based on BA are proposed in the present dissertation. The first one concerns a discrete version of the Discrete Inspired Bat Algorithm (DIBA) and is based on replacing the algorithm's update equations with heuristic techniques. The second algorithmic framework proposed concerns applying the classical method using the proposed method of encoding/decoding solutions, Coordinates Related (CR), which is a novelty of this doctoral dissertation. Thus, the proposed algorithmic approach to solving Green-PCVRP is noted as Bat Algorithm based on Coordinates (BAC). The two proposed algorithmic methods are compared based on their effectiveness in solving the Green-PCVRP benchmark instances found in the literature. The enriched version of the classical algorithmic framework with the CR method has proven to be more efficient than the same algorithm's discrete version. Therefore, to solve the second proposed problem, the E-PCVRP, the application of the novel CR method to other metaheuristic algorithms has been studied. Specifically, the Firefly Algorithm, the Differential Evolution Algorithm with binomial and exponential crossover, the Particle Swarm Optimization Algorithm, and the Teaching-Learning Optimization Algorithm were used. Regarding the algorithmic solution of the APP, the above algorithms can not be used since this problem requires the use of a construction algorithm. Thus, the Ant Colony System algorithm was chosen, and its variant, the Modified Ant Colony System (MACS), is proposed. In comparison with the already published methods of solving the APP, the proposed MACS outperforms the previously published methods, providing new optimal solutions.
Degree
thesis:*- Grantor dc:publisher
- Technical University of Crete (TUC)
- Year dc:date
- 2021
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Trachanatzi, Dimitra
- Τραχανατζή, Δήμητρα
Subjects
dc:subject × 20- Δρομολόγηση οχημάτων
- Αλγοριθμική βελτιστοποίηση
- Πρόβλημα επιλεκτικής δρομολόγησης
- Δρομολόγηση σε έκτακτη κατάσταση
- Vehicle routing
- Algorithmic optimization
- Selective routing problem
- Emergency routing
- Μαθηματικά
- Φυσικές Επιστήμες
- Έλεγχος και Βελτιστοποίηση
- Οικονομικά και Επιχειρήσεις
- Κοινωνικές Επιστήμες
- Διοικητική Επιστήμη και Επιχειρησιακή Έρευνα
- Mathematics
- Natural Sciences
- Control and Optimization
- Economics and Business
- Social Sciences
- Management Science and Operations Research
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/49958