Groupe d’études et de recherche en analyse des décisions

Tabu Search and Network Flows for Tank Refueling

David Schindl HEG Genève, Suisse

We consider the problem of optimizing the refueling costs of a fleet of locomotives over a railway network. Fuel is brought into the locomotives tanks by trucks which are located at yards (train stations) and have to be contracted at a given rate, the price of a unit of fuel being dependent on the corresponding yard. The goal is to determine the number of trucks contracted at each yard and to design the refueling plan of each locomotive, such as to minimize the total costs related to refueling while satisfying some additional constraints. We show that a subproblem of this NP-hard problem can be modeled as a minimum cost flow problem in a network. A polynomial time resolution algorithm of this subproblem is used as a subprocedure of a tabu-search heuristic for the whole problem. This heuristic was tested within an optimization contest proposed by INFORMS, for which competitive results were obtained.

Co-author: Prof. Nicolas Zufferey, HEC Geneva, Switzerland