Framework for solving vehicle scheduling problems using AI techniques

Abstract

Transportation resource scheduling problems are of high academic as well as practical value. These are primarily concerned with generation of movement schedules for a set of vehicles (tankers, aircraft, etc) to distribute a set of items among a set of locations, under a variety of constraints. Due to the nature of constraints and other requirements that typically arise with these vehicle scheduling problems, classical O R approaches are difficult to use. There has been a lot of interest in using various AI techniques for such scheduling applications. These make use of various domain specific heuristics to prune the enormous search space typically associated with these problems. W e have worked on a few real-life applications belonging to this class. We have noticed some identifiable components and properties of this class of problems which seem to characterise this class. Based on this, we derive an abstract m odel of vehicle scheduling problems, with a view to develop a general solution framework for them. We also provide a language for specifying any instance of this class under this model. An implementation framework is developed for implementing a scheduling system based on such a user-defined specification of a problem. We adopt the technique of heuristic tree search for solving these problems. A prototype system has been implemented in Prolog for this. The problem of scheduling oil tankers for distributing petroleum products is presented and a specification for this under the framework is provided as a case study. The thesis also examines the issue of parallelising the solution of these problems in a problem-independent manner. The layered architecture followed in the implementation and the independence of the specification language from the control structure makes it possible to implement the solution under sequential or parallel machines without any change to the user specifications. The work provides a sound basis for developing application specific environments for solving these problems. This would help to increase the applicability of these techniques to a wider range of problems under this class. Also the work shows that controlindependent, application-oriented specifications can help realise efficient parallel implementation of software described in the thesis.