Set Partitioning problems derived from the driver scheduling problem

Presented here are 12 set partitioning problems derived from small bus driver scheduling problems. These consist of a given set of tasks (pieces of work) to cover and a large set of possible shifts, where each shift covers a subset of the tasks and has an associated cost. We must select a subset of possible shifts that covers each piece of work once and only once: this is called a partition. Further, we desire the partition with the the minimum cost. In these problems the set of possible shifts is generated by a heuristic method described in [4].

There have been some constraint programming approaches applied to set partitioning problems derived from air crew scheduling. [3, 6, 7], show approaches for solving these set partitioning problems. There are benchmarks for these problems at ORlib. However there has been little work investigating driver scheduling problems. The internal structures of set partitioning problems derived from the two types of scheduling tasks are different and so may be of varying hardness to solve.

Apart from the internal structure there is a difference in the optimisation criteria between the two types of problem. In the driver scheduling set partitioning problems the main aim is to reduce the number of shifts used in the solution partition and the total cost of the partition is secondary. To simplify the problem we have made the cost of each shift the same. This means that to minimise the cost, we need to minimise the number of shifts used.

This type of problem is deemed to be hard for local search methods. The only successful heuristic method that has solved problems of a much larger size than those here is a GA approach discussed in [5]. However, this approach relies heavily on an LP solution to a relaxation of the problem.

The problems come from four different bus companies: Reading (r1 to r5a), CentreWest Ealing area (c1, c1a, c2), the former London Transport (t1 and t2). The problems have differing regulations and features (e.g. urban and short distance rural bus schedules can have very different features). Note that r1 and r1a are the same problem, but have different numbers of generated shifts. Similarly with the problems: c1, c1a and r5, r5a. See [4, 5] for a details on all these problems and how they have been solved using TRACS II, a system based on mathematical programming.

These problems have been tackled using a CP approach described in [1] and by the Local search method, GENET [8] described in [2]. The adapted GENET program has found solutions with the same number of shifts as TRACS II for several of the problems. The systematic CP approach has done this for all the problems except c2, r5 and r5a. These are slightly larger than the rest, c2 has 14771 potential shifts, 205 pieces of work and 29 shifts in the TRACS II solution and r5a is of similar size. However, these have been easily solved by TRACS II which can solve problems an order of magnitude larger (it can solve problems where the numbers of shifts, pieces of work and shifts in the solution are ten times bigger). Example solutions from the CP approach are given.

A word of warning is given about these problems. They are derived from small real bus driver scheduling problems but in practice, particularly in train driver scheduling, there are sometimes further restrictions to consider. Inclusion of problems with such restrictions may be provided to CSPlib in the future.

Format

The problems are formatted in the same way as the set partitioning problems that are given in ORlib. The first line gives the number of rows (pieces of work), columns (shifts) and the minimum number of columns need for a partition. Then each line after that corresponds to one column. It starts with the cost (which is always 1 in our case) then the number of rows it covers, followed by the rows it covers.

For example:
Cost nb of rows covered rows
1 4 5 12 145 201

Contacts for this work

Suniel Curtis suniel@scs.leeds.ac.uk
Barbara Smith bms@scs.leeds.ac.uk
Anthony Wren wren@scs.leeds.ac.uk

Set partitioning problems derived from other types of real world problems:

Dr. Ralf Borndorfer's homepage
ORlib

Bibliography

1
S. D. Curtis, B. M. Smith, and A. Wren.
Forming bus driver scheduling using constraint programming.
In Practical Application of Constraint Technologies and Logic Programming PACLP99, pages 239-254. The Practical Application Company Ltd, 1999.
To down load Tech. report version click here.

2
S. D. Curtis, B. M. Smith, and A. Wren.
Constructing Driver Schedules using Iterative Repair.
Submitted to PACLP00, The Practical Application Company Ltd, 2000.
Tech. report version will be available soon at this link.

3
N. Guerinik and M. V. Caneghem
Solving Crew Scheduling Problems by Constraint Programming.
In U. Montanari and F. Rossi, editor, Principles and Practice of Constraint Programming - CP '95, 482-498 Springer, 1995.

4
A.S.K. Kwan, R.S.K. Kwan, M.E. Parker, and A. Wren.
Producing train driver schedules under differing operating strategies.
In N.H.M. Wilson, editor, Computer-aided Transport Scheduling, 1999.
To down load Tech. report version click here.

5
A.S.K. Kwan, R.S.K. Kwan, and A. Wren.
Driver scheduling using genetic algorithms with embedded combinatorial traits.
In N.H.M. Wilson, editor, Computer-aided Transport Scheduling, 1999.
To down load Tech. report version click here.

6
T. Müller.
Solving set partitioning problems with constraint programming.
In PAPPACT98, pages 313-332. The Practical Application Company Ltd, 1998.

7
R. Rodosek and M. G. Wallace and T. Hajian
A New Approach to Integrate Mixed Integer Programming
In CP96 workshop on Constraint Programming Applications: An Inventory and Taxonomy, 1996.

8
E. P. K. Tsang and C. J. Wang.
A generic neural network approach for constraint satisfaction problems.
Neural Network Applications, pages 12-22, 1992.

9
A. Wren and R. S. K. Kwan.
Installing an urban transport scheduling system.
Journal of Scheduling, 2:3-17, 1999.
To down load Tech. report version click here.