Fulltext

A solution method for a car fleet management problem with maintenance constraints

Hertz, Alain ; Schindl, David ; Zufferey, Nicolas

In: Journal of Heuristics, 2009, vol. 15, no. 5, p. 425-450

Zum persönliche Liste hinzufügen
    Titel
    • A solution method for a car fleet management problem with maintenance constraints
    Autor
    • Hertz, Alain. Département de Mathématiques et de Génie Industriel, École Polytechnique, Montréal, Canada
    • Schindl, David. Département de Mathématiques et de Génie Industriel, École Polytechnique, Montréal, Canada
    • Zufferey, Nicolas. Faculté des Sciences Économiques et Sociales, Section des Hautes Études Commerciales (HEC), Université de Genève, Genève, Switzerland
    Dokumententyp
    • Postprint
    Sprache
    • Englisch
    Veröffentlicht in
    • Journal of Heuristics, 2009, vol. 15, no. 5, p. 425-450. Springer US; http://www.springer-ny.com
    Andere elektronische Ausgabe
    OAI-PMH-ID
    • oai:doc.rero.ch:317324
    Summary
    The problem retained for the ROADEF'99 international challenge was an inventory management problem for a car rental company. It consists in managing a given fleet of cars in order to satisfy requests from customers asking for some type of cars for a given time period. When requests exceed the stock of available cars, the company can either offer better cars than those requested, subcontract some requests to other providers, or buy new cars to enlarge the available stock. Moreover, the cars have to go through a maintenance process at a regular basis, and there is a limited number of workers that are available to perform these maintenances. The problem of satisfying all customer requests at minimum cost is known to be NP-hard. We propose a solution technique that combines two tabu search procedures with algorithms for the shortest path, the graph coloring and the maximum weighted independent set problems. Tests on benchmark instances used for the ROADEF'99 challenge give evidence that the proposed algorithm outperforms all other existing methods (thirteen competitors took part to this contest)