Επίλυση δικτύων δρομολόγησης με χρήση γενετικών αλγορίθμων

Abstract

In recent years, many service suppliers and distributors have recognized the importance of designing efficient routing strategies to improve the level of customer's service and reduce freight transportation costs. Traditionally, routing problems have been modeled as mixed integer or dynamic programming problems in order to be solved with advanced techniques of mathematical programming. There exists an extended literature on these efforts, many of which have been used with great success in real world applications and continue to take up time of many researchers throughout the world, due to their importance and their applicability to most real world problems. However, in many cases these approaches have important drawbacks, and fail to model all the dynamic and stochastic parameters involved. The dissertation's objective is to provide a deeper understanding of real life routing problems with various characteristics and to investigate and invent new and effective algorithms that produce near-optimal solutions. A strategy that uses genetic algorithms is presented, which proves to be efficient in routing problems. A new chromosome representation suitable for routing and scheduling problems is introduced. The proposed algorithm is supported by domain specific, intelligent genetic operators which boost the genetic search towards near optimal solutions. In order to deal with premature convergence and degeneration of population, a dynamic population sizing technique is proposed that provides a desired level of genetic diversity throughout the evolution. The proposed approach produces competitive results, comparing to best published results reported thus far by other researchers on classical vehicle routing benchmarks problems. Extensive tests with real operational data sets have also been performed, leading to high-quality results. Furthermore, in order to reduce computation time, methods for deriving parallel versions of the algorithm have been proposed. Applying the methodology in HPCN Platforms, the algorithm is able to solve problems faster or solve larger problems. Finally, a decision support system based on the presented genetic algorithm methodology has been developed, aiming at providing efficient support to companies involved in distribution. The integrated system enhances the ability of a company for fast and high quality routing and scheduling decisions towards cost-effectiveness.