Rule-based constraints programming: application to crew assignment

摘要

The purpose of this publication is to present an application on bus crew assignment, using Expert Systems technology. This technology is used to design a programming system with constraints, called busdriver. Thus, the result observed in this work, is a computer program with a more flexible approach than those usually obtained from operational research. In busdriver, scheduling system constraints are stated through a set of production rules, and their manipulation arises to a declarative conception. Under these conditions, scheduling system constraints are more susceptible to accepting the inherent modifications to the nature of this kind of problem. Obviously these programming systems resources show an important combinatory component and, in the solution reached in this work, the utilization of another aspect of the Expert Systems technology that contributes to ease this problem can be observed. Indeed, busdriver search solutions are produced by an inference process with backtracking, associated to some heuristic natural strategies introduced to accelerate the most adequate solutions. Naturally, backtracking is associated to a cost function that manages the whole solutions search process. Another methodological contribution of the Expert Systems technology proposed in this publication appears in the formulation of a set of rules that makes possible the decomposition of the problem. 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 related 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 solution includes the drivers' assignment to the path and the attempted initial distribution of their homes in the cities where the relief operations are carried out.