Vehicle Scheduling with Multiple Trips and Time Windows and Long Planning Horizon

Abstract

We consider scheduling a vehicle/mobile robot in intelligent material transportation systems with multiple trips, time windows and long planning horizon. We propose a novel approach for the scheduling problem which consists of two parts: a) a framework for splitting the long planning horizon problem into many problems with short planning horizons; b) a fast algorithm for scheduling with short planning horizons based on a flexible and effective two-index mixed integer programming (MIP) model. Numerical results show our algorithm can get optimal solutions in seconds/minutes for the short planning horizon problems for which existing three-index MIP model in literature needs hours or cannot obtain optimal solutions after six hours. For long planning horizon problems, our method is also fast and has good scalability, and can significantly reduce cost compared with the Genetic Algorithm in the literature.