IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v237y2014i2p729-737.html
   My bibliography  Save this article

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

Author

Listed:
  • Oliveira, Beatriz Brito
  • Carravilla, Maria Antónia
  • Oliveira, José Fernando
  • Toledo, Franklina M.B.

Abstract

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.

Suggested Citation

  • Oliveira, Beatriz Brito & Carravilla, Maria Antónia & Oliveira, José Fernando & Toledo, Franklina M.B., 2014. "A relax-and-fix-based algorithm for the vehicle-reservation assignment problem in a car rental company," European Journal of Operational Research, Elsevier, vol. 237(2), pages 729-737.
    • Handle: RePEc:eee:ejores:v:237:y:2014:i:2:p:729-737
    DOI: 10.1016/j.ejor.2014.02.018
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714001337
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.02.018?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. George J. Beaujon & Mark A. Turnquist, 1991. "A Model for Fleet Sizing and Vehicle Allocation," Transportation Science, INFORMS, vol. 25(1), pages 19-45, February.
    2. Guimarães, Luis & Klabjan, Diego & Almada-Lobo, Bernardo, 2013. "Pricing, relaxing and fixing under lot sizing and scheduling," European Journal of Operational Research, Elsevier, vol. 230(2), pages 399-411.
    3. Fink, Andreas & Reiners, Torsten, 2006. "Modeling and solving the short-term car rental logistics problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 42(4), pages 272-292, July.
    4. Sherali, Hanif D. & Lunday, Brian J., 2011. "Equitable apportionment of railcars within a pooling agreement for shipping automobiles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(2), pages 263-283, March.
    5. Spieckermann, Sven & Vo[ss], Stefan, 1995. "A case study in empty railcar distribution," European Journal of Operational Research, Elsevier, vol. 87(3), pages 586-598, December.
    6. Tarantilis, C.D. & Kiranoudis, C.T., 2007. "A flexible adaptive memory-based algorithm for real-life transportation operations: Two case studies from dairy and construction sector," European Journal of Operational Research, Elsevier, vol. 179(3), pages 806-822, June.
    7. Tan, K.C. & Chew, Y.H. & Lee, L.H., 2006. "A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 172(3), pages 855-885, August.
    8. Hanif D. Sherali & Cihan H. Tuncbilek, 1997. "Static and Dynamic Time-Space Strategic Models and Algorithms for Multilevel Rail-Car Fleet Management," Management Science, INFORMS, vol. 43(2), pages 235-250, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Amanda O. C. Ayres & Betania S. C. Campello & Washington A. Oliveira & Carla T. L. S. Ghidini, 2021. "A Bi-Integrated Model for coupling lot-sizing and cutting-stock problems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(4), pages 1047-1076, December.
    2. Oliveira, Beatriz Brito & Carravilla, Maria Antónia & Oliveira, José Fernando, 2017. "Fleet and revenue management in car rental companies: A literature review and an integrated conceptual framework," Omega, Elsevier, vol. 71(C), pages 11-26.
    3. Absi, Nabil & van den Heuvel, Wilco, 2019. "Worst case analysis of Relax and Fix heuristics for lot-sizing problems," European Journal of Operational Research, Elsevier, vol. 279(2), pages 449-458.
    4. Monnerat, Filipe & Dias, Joana & Alves, Maria João, 2019. "Fleet management: A vehicle and driver assignment model," European Journal of Operational Research, Elsevier, vol. 278(1), pages 64-75.
    5. Oliveira, Beatriz Brito & Carravilla, Maria Antónia & Oliveira, José Fernando, 2018. "Integrating pricing and capacity decisions in car rental: A matheuristic approach," Operations Research Perspectives, Elsevier, vol. 5(C), pages 334-356.
    6. Nikzad, Erfaneh & Bashiri, Mahdi & Abbasi, Babak, 2021. "A matheuristic algorithm for stochastic home health care planning," European Journal of Operational Research, Elsevier, vol. 288(3), pages 753-774.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sun, Yanshuo & Kirtonia, Sajeeb & Chen, Zhi-Long, 2021. "A survey of finished vehicle distribution and related problems from an optimization perspective," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    2. Peiling Wu & Joseph C. Hartman & George R. Wilson, 2005. "An Integrated Model and Solution Approach for Fleet Sizing with Heterogeneous Assets," Transportation Science, INFORMS, vol. 39(1), pages 87-103, February.
    3. José Carbajal & Alan Erera & Martin Savelsbergh, 2013. "Balancing fleet size and repositioning costs in LTL trucking," Annals of Operations Research, Springer, vol. 203(1), pages 235-254, March.
    4. Hanif D. Sherali & Lawrence W. Maguire, 2000. "Determining Rail Fleet Sizes for Shipping Automobiles," Interfaces, INFORMS, vol. 30(6), pages 80-90, December.
    5. Felix Papier & Ulrich W. Thonemann, 2008. "Queuing Models for Sizing and Structuring Rental Fleets," Transportation Science, INFORMS, vol. 42(3), pages 302-317, August.
    6. Oliveira, Beatriz Brito & Carravilla, Maria Antónia & Oliveira, José Fernando, 2017. "Fleet and revenue management in car rental companies: A literature review and an integrated conceptual framework," Omega, Elsevier, vol. 71(C), pages 11-26.
    7. Bojovic, Nebojsa J., 2002. "A general system theory approach to rail freight car fleet sizing," European Journal of Operational Research, Elsevier, vol. 136(1), pages 136-172, January.
    8. Hamid Sayarshad & Nikbakhsh Javadian & Reza Tavakkoli-Moghaddam & Nastaran Forghani, 2010. "Solving multi-objective optimization formulation for fleet planning in a railway industry," Annals of Operations Research, Springer, vol. 181(1), pages 185-197, December.
    9. Milenković, Miloš S. & Bojović, Nebojša J. & Švadlenka, Libor & Melichar, Vlastimil, 2015. "A stochastic model predictive control to heterogeneous rail freight car fleet sizing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 82(C), pages 162-198.
    10. Massimiliano Caramia & Francesca Guerriero, 2010. "A Milk Collection Problem with Incompatibility Constraints," Interfaces, INFORMS, vol. 40(2), pages 130-143, April.
    11. Yichen Lu & Chao Yang & Jun Yang, 2022. "A multi-objective humanitarian pickup and delivery vehicle routing problem with drones," Annals of Operations Research, Springer, vol. 319(1), pages 291-353, December.
    12. Ann-Kathrin Rothenbächer & Michael Drexl & Stefan Irnich, 2018. "Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 52(5), pages 1174-1190, October.
    13. Kochel, Peter & Kunze, Sophie & Nielander, Ulf, 2003. "Optimal control of a distributed service system with moving resources: Application to the fleet sizing and allocation problem," International Journal of Production Economics, Elsevier, vol. 81(1), pages 443-459, January.
    14. Zhu, Stuart X. & Ursavas, Evrim, 2018. "Design and analysis of a satellite network with direct delivery in the pharmaceutical industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 190-207.
    15. Oscar Dominguez & Angel A. Juan & Barry Barrios & Javier Faulin & Alba Agustin, 2016. "Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet," Annals of Operations Research, Springer, vol. 236(2), pages 383-404, January.
    16. Okitonyumbe Y.F., Joseph & Ulungu, Berthold E.-L. & Kapiamba Nt., Joel, 2015. "Cobweb Heuristic for solving Multi-Objective Vehicle Routing Problem," MPRA Paper 66121, University Library of Munich, Germany.
    17. D-P Song, 2007. "Characterizing optimal empty container reposition policy in periodic-review shuttle service systems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(1), pages 122-133, January.
    18. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    19. Zhang, Zhenzhen & Wei, Lijun & Lim, Andrew, 2015. "An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints," Transportation Research Part B: Methodological, Elsevier, vol. 82(C), pages 20-35.
    20. Boonmee, Atiwat & Sethanan, Kanchana, 2016. "A GLNPSO for multi-level capacitated lot-sizing and scheduling problem in the poultry industry," European Journal of Operational Research, Elsevier, vol. 250(2), pages 652-665.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:237:y:2014:i:2:p:729-737. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.