A linear programming based iterative heuristic for the recreational vehicle scheduling problem

Sarang Shashikant Kulkarni, Andreas Ernst, A. Ranade, Mohan Krishnamoorthy

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

In the recreational vehicle rental business, the problem of preparing a schedule for each vehicle in the fleet (by assigning accepted bookings to available vehicles over the planning horizon) is known as the recreational vehicle scheduling problem (RVSP). The problem belongs to the class of minimum cost multicommodity network flow problems which is known to be NP-hard. A formulation of the RVSP from literature is modified to reduce the size of the problem instance. We propose an iterative construction heuristic combined with an improvement heuristic based on the solution of the LP relaxation of the problem. The heuristic exploits the integrality property of the formulation and reduces infeasibility successively at each iteration. The approach is compared with a subgradient optimisation and with CPLEX using a real-life dataset. The heuristic outperforms the subgradient optimisation for most of the datasets while it produces results within 5% of optimality when compared with CPLEX.

Original languageEnglish
Title of host publicationIndustrial Engineering and Engineering Management (IEEM), 2016 IEEE International Conference on
EditorsNan Chen, Min Xie
PublisherIEEE Computer Society
Pages784-788
Number of pages5
Volume2016-December
ISBN (Electronic)9781509036653
DOIs
Publication statusPublished - 27 Dec 2016
EventIEEE International Conference on Industrial Engineering and Engineering Management (IEEM) 2016 - Bali Nusa Dua Convention Center, Bali, Indonesia
Duration: 4 Dec 20167 Dec 2016
http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=7787014
https://web.archive.org/web/20160730191159/http://www.ieem.org/public.asp?page=home.htm

Conference

ConferenceIEEE International Conference on Industrial Engineering and Engineering Management (IEEM) 2016
Abbreviated titleIEEM 2016
CountryIndonesia
CityBali
Period4/12/167/12/16
Internet address

Keywords

  • assignment problem
  • heuristic
  • integer programming
  • subgradient optimisation
  • vehicle scheduling

Cite this