DM204 – Scheduling, Timetabling and Routing
Supervised Practice 2, Autumn 2013 [pdf format]

Crew Scheduling

The goal of this activity is to make hands on experience with column generation for solving the regional crew scheduling problem. The problem is formulated by model (7)-(9) in the slides of the lecture.

Download the file cg-template.py that contains a skeleton with TODO spots where you are going to add your python code.

Unconstrained case (no resources)

We consider first a simplified case where there are no resource constraints on the drivers’ duties. Download the file ist-0.dat. We use the implemented function readDataNoResource to read it.

1. Create an initial covering of the pieces of work. Complete the function heuristicPaths. Do not use much of your time on this.
2. Solve the LP relaxation of the problem with only the initial set of variables/columns. For this task we prepared a function called solveRestrictedMaster. A peculiarity of the column generation approach is that constraints are introduced empty, since the variables are not all known at the beginning and we will need to introduce them together with their coefficients in the constraints iteratively. Hence, to introduce the initial variables we need to declare them with their coefficient in the objective function and in the constraints. In gurobi we achieve this by passing the additional argument column to the function Model.addVar. For details read the documentation from the gurobi page. Type in the search bar: addVar and Column.
3. Next we look for columns to add using the function columnGeneration. We solve the relaxed restricted master and take the values of the dual variables. Your task is now creating the network for the pricing problem. In particular you have to define the costs on the arcs. Set your arcs in a list B of triples, each triple made by (i,j,c_ij), that is, starting node, ending node and cost.
4. Implement by MIP the pricing problem in pricingProblem.
5. Write the condition in columnGeneration that checks which of the path(s) found are worth inserting in the master problem. Check here also when the column generation procedure has to stop.

Resource Constrained case

We now turn to the case where there are resources with constrains to take care of in the composition of the drivers’ duties. Download the file ist-1.dat that includes specifications on the resources and their constraints. We use the implemented function readDataWithResource to read it.

• 6. Implement by MIP the pricing problem for this case.

  Compare the results in terms of computation time of your MIP implementation against the use of path-solver (you find executables for Linux, Mac and Windows together with the source archive in the course web page).