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

被引:24
作者
Oliveira, Beatriz Brito [1 ]
Carravilla, Maria Antonia [1 ]
Oliveira, Jose Fernando [1 ]
Toledo, Franklina M. B. [2 ]
机构
[1] Univ Porto, Fac Engn, INESC TEC, P-4100 Oporto, Portugal
[2] Univ Sao Paulo, Inst Ciencias Matemat & Comp, BR-05508 Sao Paulo, Brazil
关键词
Assignment; Empty repositions; Car rental; Network-flow; Relax-and-fix; RAIL-CAR; FLEET; MODELS;
D O I
10.1016/j.ejor.2014.02.018
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
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. (C) 2014 Elsevier B.V. All rights reserved.
引用
收藏
页码:729 / 737
页数:9
相关论文
共 21 条
[1]   A MODEL FOR FLEET SIZING AND VEHICLE ALLOCATION [J].
BEAUJON, GJ ;
TURNQUIST, MA .
TRANSPORTATION SCIENCE, 1991, 25 (01) :19-45
[2]   A general system theory approach to rail freight car fleet sizing [J].
Bojovic, NJ .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 136 (01) :136-172
[3]   A Modeling Framework for Railcar Fleet Sizing in the Chemical Industry [J].
Cheon, Myun-Seok ;
Furman, Kevin C. ;
Timothy, D. Shaffer .
INDUSTRIAL & ENGINEERING CHEMISTRY RESEARCH, 2012, 51 (29) :9825-9834
[4]  
Cherri L. H., 2013, 45 SBPO S BRAS PESQ
[5]   A REVIEW OF EMPTY FLOWS AND FLEET MANAGEMENT MODELS IN FREIGHT TRANSPORTATION [J].
DEJAX, PJ ;
CRAINIC, TG .
TRANSPORTATION SCIENCE, 1987, 21 (04) :227-247
[6]   Modeling and solving the short-term car rental logistics problem [J].
Fink, Andreas ;
Reiners, Torsten .
TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2006, 42 (04) :272-292
[7]   Pricing, relaxing and fixing under lot sizing and scheduling [J].
Guimaraes, Luis ;
Klabjan, Diego ;
Almada-Lobo, Bernardo .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2013, 230 (02) :399-411
[8]  
ITM, 2013, CAR RENT IND OV
[9]   On determining optimal fleet size and vehicle transfer policy for a car rental company [J].
Lia, Zhaolin ;
Tao, Feng .
COMPUTERS & OPERATIONS RESEARCH, 2010, 37 (02) :341-350
[10]   A stochastic fleet composition problem [J].
Loxton, Ryan ;
Lin, Qun ;
Teo, Kok Lay .
COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (12) :3177-3184