The vehicle routing problem is one of the most known combinatorial problems due to an increase in logistics worldwide activities. The general problem is described as the delivery of goods to customers for whom their demand is given. The solution represents the optimal route with minimal transportation cost, where each customer is visited only once, by only one vehicle. Each vehicle starts and ends at the depot. The complexity of the problem increases exponentially with the size. Because of this property, the vehicle routing problem belongs to the class of NP-hard combinatorial problems that can be solved with metaheuristic methods, among which is also a genetic algorithm.
This thesis has two main goals. The first is a thorough presentation of vehicle routing problem and genetic algorithm. Genetic algorithm is one of the most important global search methods commonly used for solving combinatorial problems and is based on mimicking the processes observed during natural evolution. Selection, crossover and mutation are three main genetic operators. The second goal of the master's thesis is to develop an application that allows users to solve the vehicle routing problem using a genetic algorithm. In addition to these two goals, the thesis also focuses on some practical examples.
|
