Project Details

In this project MDL team was responsible for the definition and formulation of a real-life Multi-Objective Optimization Waste Collection Vehicle Routing Problem, as well as the design, development and analysis of a prototype that primarily enhances realistic traceable information from the environment, then tackles the problem in the context of Multi-Objective Optimization, and thus provides a set of Pareto optimal routing schedules for waste collection, and finally decides what is the best solution to be applied based on particular constraints. The actions undertaken by MDL were divided into the following phases: In the first phase of the project MDL provided a thorough description of the requirement specifications, as well as the definition and formulation of the Waste Collection Vehicle Routing Problem in the context of Multi-Objective Optimization taking into consideration real-time traceable and spatiotemporal information provided by GEOMATIC. During the requirement specifications the objectives and the constraints of the projects were identified as well as the necessary data and the algorithm to be utilized for tackling the Multi-Objective Optimization Problem (MOP). In the second phase, MDL analyzed the real-time traceable and spatiotemporal data. In particular, a real case-study of Waste Collection Optimization of Lakatamia region was defined, designed and analyzed including the following: the customers were clustered and a directional graph was designed, the k nearest neighbors of each customer were calculated using geographical distances, the “orphan” customers, in terms of nearest neighbors, were found and handled individually, the customers were sorted in terms of distance to parking and in terms of distance to depot. These pre-processing steps helped the ease incorporation of the input data to the scheduling module. In the third phase of the project, the design and development of the scheduling module that host the Multi-Objective Evolutionary Algorithms (MOEAs), i.e., several variations of the MOEA based on Decomposition (MOEA/D), followed that provide a set of Pareto optimal truck routes for waste collection. At this point it is important to notice that several variations of the MOEA/D were designed and implemented by changing the genetic operators and the local search heuristics. In particular, the following genetic operators and heuirstics were used: (i) random and tournament-based selection heuristic, (ii) 1x-crossover and Partially Mapped crossover, (iii) random swap and adjacent swap mutations, (iv) random and problem-specific population initialization, (v) random and nearest-neighbor local search heuristic. All algorithm were generated using JAVA. The developed MOEAs are evaluated using well-known performance metrics such as the IGD, C-metric and Dominance-metric as well as visual comparison in order to select the most appropriate MOEA/D variant. The fourth phase of the project focused on the design and development of the posterior Decision-Making module that will autonomously propose a solution to be adopted and applied based on instant requirements. For example, with the generation of the Pareto Front the algorithm could proposed solutions for particular constraints (e.g., number of available vehicles equal to 13) and preferences (e.g., closest near-optimal solution to a total distance cost equal to 1200 KMs). For example, Figure 2 shows an obtained Pareto Front in a .log file, its visual representation using Matlab and the proposed solution of the above example. The fifth phase included a series of tests for system validation after integrating all the individual modules of phases two to four. This phase also included the visual representation of the final result using the QGIS software.