Railway track possession assignment using constraint satisfaction

Abstract

Resource allocation is the problem of allocating a set of resources to accomplish some task(s). Many real-world problems are resource-allocation problems, such as production planning and manpower planning. This paper reports on a case study on applying constraint-satisfaction techniques to solve a real-world resource allocation problem, referred to as the Railway Track Possession Assignment Problem, using the CHIP constraint language. The problem is to assign railway tracks to a given set of scheduled maintenance tasks according to a set of constraints. The manual problem-solving method is heuristic in nature. Experienced personnel were involved in the manual process. An expert system, called the Engineering Work Track Possession Assignment System (EWTPAS), was developed to carry out the assignment using constraint-satisfaction techniques. A new, two-phase resource allocation strategy based on constraint relaxation was developed and implemented in EWTPAS. EWTPAS succeeded in replacing the manual assignment process after test running for 1 year. EWTPAS is now in use. Besides having the advantage of being free of careless human errors, and the advantage of being independent of the availability of experienced staff, EWTPAS was found to be about 10 times more efficient than the manual method. © 1999 Elsevier Science Ltd. All rights reserved.