RULE-BASED CONSTRAINTS PROGRAMMING - APPLICATION TO CREW ASSIGNMENT

The purpose of this publication is to present an application on bus cr ew assignment, using Expert Systems technology. This technology is use d to design a programming system with constraints, called BUSDRIVER. T hus, the result observed in this work, is a computer program with a mo re flexible approach than those usually obtained from operational rese arch. In BUSDRIVER, scheduling system constraints are stated through a set of production rules, and their manipulation arises to a declarati ve conception. Under these conditions, scheduling system constraints a re more susceptible to accepting the inherent modifications to the nat ure of this kind of problem. Obviously these programming systems resou rces show an important combinatory component and, in the solution reac hed in this work, the utilization of another aspect of the Expert Syst ems technology that contributes to ease this problem can be observed. Indeed, BUSDRIVER search solutions are produced by an inference proces s with backtracking, associated to some heuristic natural strategies i ntroduced to accelerate the most adequate solutions. Naturally, backtr acking is associated to a cost function that manages the whole solutio ns search process. Another methodological contribution of the Expert S ystems technology proposed in this publication appears in the formulat ion of a set of rules that makes possible the decomposition of the pro blem. These rules solve automatically the search space segmentation in several fractions that Limit the combinatory dimensions linked to the problem resolving. Finally, this publication considers an example rel ated to a driver-assignment application in a public transport company. The company uses a progressive driver relief modality along the tour, from the origin city to the final destination of each path. The solut ion includes the drivers' assignment to the path and the attempted ini tial distribution of their homes in the cities where the relief operat ions are carried out. (C) 1998 Elsevier Science Ltd. All rights reserv ed.