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

Kulkarni, S. S., Ernst, A., Ranade, A., & Krishnamoorthy, M. (2016). A linear programming based iterative heuristic for the recreational vehicle scheduling problem. In N. Chen, & M. Xie (Eds.), Industrial Engineering and Engineering Management (IEEM), 2016 IEEE International Conference on (Vol. 2016-December, pp. 784-788). [7797983] IEEE Computer Society. https://doi.org/10.1109/IEEM.2016.7797983
Kulkarni, Sarang Shashikant ; Ernst, Andreas ; Ranade, A. ; Krishnamoorthy, Mohan. / A linear programming based iterative heuristic for the recreational vehicle scheduling problem. Industrial Engineering and Engineering Management (IEEM), 2016 IEEE International Conference on. editor / Nan Chen ; Min Xie. Vol. 2016-December IEEE Computer Society, 2016. pp. 784-788
@inproceedings{065c1067ccd84e06a1d7fe68a215c220,
title = "A linear programming based iterative heuristic for the recreational vehicle scheduling problem",
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.",
keywords = "assignment problem, heuristic, integer programming, subgradient optimisation, vehicle scheduling",
author = "Kulkarni, {Sarang Shashikant} and Andreas Ernst and A. Ranade and Mohan Krishnamoorthy",
year = "2016",
month = "12",
day = "27",
doi = "10.1109/IEEM.2016.7797983",
language = "English",
volume = "2016-December",
pages = "784--788",
editor = "Chen, {Nan } and Xie, {Min }",
booktitle = "Industrial Engineering and Engineering Management (IEEM), 2016 IEEE International Conference on",
publisher = "IEEE Computer Society",
address = "United States of America",

}

Kulkarni, SS, Ernst, A, Ranade, A & Krishnamoorthy, M 2016, A linear programming based iterative heuristic for the recreational vehicle scheduling problem. in N Chen & M Xie (eds), Industrial Engineering and Engineering Management (IEEM), 2016 IEEE International Conference on. vol. 2016-December, 7797983, IEEE Computer Society, pp. 784-788, IEEE International Conference on Industrial Engineering and Engineering Management (IEEM) 2016, Bali, Indonesia, 4/12/16. https://doi.org/10.1109/IEEM.2016.7797983

A linear programming based iterative heuristic for the recreational vehicle scheduling problem. / Kulkarni, Sarang Shashikant; Ernst, Andreas; Ranade, A.; Krishnamoorthy, Mohan.

Industrial Engineering and Engineering Management (IEEM), 2016 IEEE International Conference on. ed. / Nan Chen; Min Xie. Vol. 2016-December IEEE Computer Society, 2016. p. 784-788 7797983.

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

TY - GEN

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

AU - Kulkarni, Sarang Shashikant

AU - Ernst, Andreas

AU - Ranade, A.

AU - Krishnamoorthy, Mohan

PY - 2016/12/27

Y1 - 2016/12/27

N2 - 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.

AB - 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.

KW - assignment problem

KW - heuristic

KW - integer programming

KW - subgradient optimisation

KW - vehicle scheduling

UR - http://www.scopus.com/inward/record.url?scp=85009889583&partnerID=8YFLogxK

U2 - 10.1109/IEEM.2016.7797983

DO - 10.1109/IEEM.2016.7797983

M3 - Conference Paper

VL - 2016-December

SP - 784

EP - 788

BT - Industrial Engineering and Engineering Management (IEEM), 2016 IEEE International Conference on

A2 - Chen, Nan

A2 - Xie, Min

PB - IEEE Computer Society

ER -

Kulkarni SS, Ernst A, Ranade A, Krishnamoorthy M. A linear programming based iterative heuristic for the recreational vehicle scheduling problem. In Chen N, Xie M, editors, Industrial Engineering and Engineering Management (IEEM), 2016 IEEE International Conference on. Vol. 2016-December. IEEE Computer Society. 2016. p. 784-788. 7797983 https://doi.org/10.1109/IEEM.2016.7797983