Application of genetic algorithms to a large-scale multiple-constraint vehicle routing problem

摘要

This paper presents a study on the application of a hybrid genetic algorithm (HGA) to an extended instance of the Vehicle Routing Problem. The actual problem is a complex reallife vehicle routing problem regarding the distribution of products to customers. A non homogenous fleet of vehicles with limited capacity and allowed travel time is available to satisfy the stochastic demand of a set of different types of customers with earliest and latest time for servicing. The objective is to minimize distribution costs respecting the imposed constraints (vehicle capacity, customer time windows, driver working hours and so on). The approach for solving the problem was based on a "cluster and route" HGA. Several genetic operators, selection and replacement methods were tested until the HGA became efficient for optimization of a multi-extrema search space system (multi-modal optimization). Finally, High Performance Computing (HPC) has been applied in order to provide near-optimal solutions in a sensible amount of time.