Object oriented constraint programming for transportation problems

Constraint satisfaction techniques are a very powerful way to tackle highly combinatorial problems such as vehicle routing or crew scheduling. The author presents PECOS, an object oriented constraint programming library, used in various industrial applications, including transportation. It is available in two versions: a C++ library, or a Lisp library. PECOS offers some unique aspects such as: object oriented programming; expressing a constraint at the class level, which is shared by all the instances of the class; use of global optimization techniques such as simulated annealing; symbolic constraints for resource allocation problems; and so on. These features are described and illustrated by the CARAIBE system, which deals with locomotive scheduling for a French railway company. The inputs are the departure and arrival time and stations of all French trains. The system minimizes the number of locomotives and produces a detailed planning for each locomotive. The use of object oriented programming with class constraints allows the representation of the problem with five constraints only, whatever number of trains are considered. The use of simulated annealing enables a very good optimization. This application has clear counterparts within the air transport companies