An efficient Lagrangean heuristic for rental vehicle scheduling

In this article we present a heuristic based on Lagrangean relaxation for scheduling rental vehicles. The scheduling problem can be formulated as a set of large assignment problems with linking constraints. We discuss the theory behind the heuristic, including the ability to obtain lower bounds. The heuristic is based on ideas first introduced by D. Wedelin.Empirical testing shows that our heuristic is superior to the exact solution procedure of the MILP formulation with the commercial ILOG Cplex solver as it generally produces better solutions within a set time limit. Moreover, the heuristic can easily be parallelized to take advantage of multicore CPUs.The work presented here has been motivated by a real-life application and is currently being used by companies that rent out recreational vehicles. Testing on data sets from these companies shows the practicality of our algorithm.