A vehicle scheduling problem with fixed trips and time limitations

Abstract

We consider minimum-cost scheduling of different vehicle types on a predetermined set of one-way trips. Trips have predetermined ready times, deadlines and associated demands. All trips Must be performed. The total time of operations on any vehicle is limited. We develop a mixed integer model to find the optimal number of vehicles at a minimum cost. Based on the hard nature of the problem, we propose six heuristics. Computational results reveal that heuristics return exceptionally good solutions for problem instances with up to 100 jobs in very small computation times, and are likely to perform well for larger instances. (C) 2008 Elsevier B.V. All rights reserved.