Feasibility-Preserving Genetic Operators for Hybrid Algorithms using TSP solvers for the Inventory Routing Problem.

In this paper feasibility-preserving genetic operators for hybrid algorithms using TSP solvers for the Inventory Routing Problem (IRP) are studied. The IRP is a problem of jointly optimizing delivery schedules and routes for vehicles transporting products from a supplier to a number of retailers. This optimization problem is highly constrained, because limits on inventory levels as well as the vehicle capacity have to be taken into account. Moreover, the IRP is a generalization of the TSP and solving the TSP effectively is an important part of obtaining good solutions to the IRP. In this paper evolutionary algorithms are used for solving the IRP, but finding good routes is delegated to a state-of-the-art TSP solver. Therefore, genetic operators used in this paper focus on constructing the delivery schedule and not on optimizing the routes. In the experimental part of the paper an evolutionary algorithm using feasibility-preserving genetic operators is compared to the Infeasibility Driven Evolutionary Algorithm (IDEA) that uses the selective pressure to obtain feasible solutions. Presented results suggest that designing good feasibility-preserving genetic operators is important, because allowing the optimization algorithm to generate infeasible solutions and handling infeasibility in IDEA using the selective pressure leads to inferior results. [ABSTRACT FROM AUTHOR]