A Hybrid Metaheuristic for a Multi-Objective Mixed Capaciated General Routing Problem
MetadataVis full innførsel
In this thesis, we have studied a bi-objective variant of the Mixed Capacitated General Routing Problem (MCGRP). The MCGRP is a generalization of other well known routing problems. It is defined on a mixed, weighted graph, where a homogeneous fleet of vehicles with capacity constraints services a set of required entities. These entities can be nodes, directed arcs and undirected edges. The aim of the problem is to find a set of vehicle routes so that every required entity is serviced exactly once and the total route cost is minimized. In the current work, a bi-objective variant of the MCGRP is proposed, where also route balance is optimized. To solve the problem, a hybrid metaheuristic solution method is proposed. The aim of the method is to find a diversified set of Pareto optimal solutions with high quality objective values. The solution method is a variant of a genetic algorithm to obtain a diversified set of solutions, combined with local search based heuristics to improve the quality of the objective values. This is the first study of multi-objective variants of the MCGRP, hence the results cannot be compared directly with results from other studies. Instead, the performance of the method is evaluated by visual inspection of the plotted Pareto front and by comparing the quality of the objective values with the best known solutions to the single-objective MCGRP. The solution method is conducted on 23 instances. Solutions that are as good as the best known solutions of the single-objective MCGRP was found for two of them, of which one is known to be optimal. The solutions were well spread out along the Pareto front for most of the instances, but a large population size or multiple runs of the same instance is necessary to obtain a good approximation of the Pareto front. For most of the instances, the objectives are conflicting, meaning they cannot be simultaneously optimized. There is still a lot of research potential for the multi-objective MCGRP, and we hope this thesis will motivate further research.