A Multi Objective Genetic Algorithm Approach for The Solution of Vehicle Routing Problem with Time Windows

Abstract

In this study, Vehicle Routing Problem with Time Windows (VRPTW) which is a type of classical Vehicle Routing Problem (VRP) includes customers with known demands, a single depot with known location and a certain number of identical vehicles with identical capacities and characteristics, is considered. Minimizing the total distance and the number of vehicles are determined as objective functions for VRPTW which is capable to serve the customers in a prespecified time interval. A hybridized version of genetic algorithm with heuristic methods is proposed to produce effective solutions for VRPTW. By using sweep algorithm and nearest neighbor-based algorithm at initial population generation phase of genetic algorithm, it is planned to begin the search with quality solution sets and in this way, get the optimum solutions faster. It has been tested whether the use of different heuristic methods in generation of initial population in genetic algorithm influences the desired solution. A benchmark problem in the literature has been solved and it is observed that the genetic algorithm beginning with sweep algorithm at initial population generation step reaches more effective solutions.

Keywords

• Vehicle routing
• Multi-objective optimization
• Genetic algorithm
• NSGA-II
• Sweep algorithm