Iterated Local Search Approach to a Single-Product, Multiple-Source, Inventory-Routing Problem

Abstract

We address an inventory-routing problem that arises in a liquid oxygen-producing company. Decisions must be made for the efficient transport of the product from sources to destinations by means of a heterogeneous fleet of trucks. This combinatorial problem has been stated as a constrained minimization one, whose objective function is the quotient of the operating cost divided by the total amount of delivered product. The operating cost comes from the distances traveled, the drivers’ salary, and the drivers’ overnight accommodation. The constraints include time windows for drivers and destinations, inventory safety levels, lower bounds for the quantity of product delivered to destinations, and maximum driving times. To approximate the optimal solution of this challenging problem, we developed a heuristic algorithm that first finds a feasible solution, and then iteratively improves it by combining the Metropolis criterion with local search. Our results are competitive with the best proposals in the literature.

Keywords

• combinatorial optimization
• iterated local search
• heuristic
• inventory routing problem
• local search
• simulated annealing