A relax-and-fix-based algorithm for the vehicle-reservation assignment problem in a car rental company

• Type: Article in International Scientific Journal
• Date: 2014

Authors

Beatriz Brito Oliveira (Author) Other; Maria Antonia Carravilla (Author) FEUP; Jose Fernando Oliveira (Author) FEUP; Franklina M B Toledo (Author) Other

Journal

Title: European Journal of Operational Research

Vol. 237

Pages: 729-737

ISSN: 0377-2217

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 15 Citations

ISI Web of Science

Scopus - 16 Citations

Scientific classification

FOS: Engineering and technology > Industrial biotechnology

Other information

Authenticus ID: P-009-9T0

DOI: 10.1016/j.ejor.2014.02.018

Abstract (EN): Empty repositions are a major problem for car rental companies that deal with special types of vehicles whose number of units is small. In order to meet reservation requirements concerning time and location, companies are forced to transfer cars between rental stations, bearing significant costs and increasing the environmental impact of their activity due to the fuel consumption and CO2 emission. In this paper, this problem is tackled under a vehicle-reservation assignment framework as a network-flow model in which the profit is maximized. The reservations are allocated considering the initial and future availability of each car, interdependencies between rental groups, and different reservation priorities. To solve this model, a relax-and-fix heuristic procedure is proposed, including a constraint based on local branching that enables and controls modifications between iterations. Using real instances, the value of this approach is established and an improvement of 33% was achieved when compared to the company's current practices.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 9