Transport optimization Assignments

Deadline May 7

Assignment 4 - Airline Scheduling

The questions

The literature:

• Optimization in Airline Scheduling, by George Nemhauser, 2000, (1 page).
  An aperitif.
• Aircraft Scheduling, by Mattias Grönkvist, 2000, (14 pages).
  Fleet assignment and aircraft routing.
• Carmen Systems' Recent Advances in Crew Scheduling, by Hjorring, Karisch, Kohl, 2000, (17 pages).
  An overview of Carmen's current approach to both crew pairing and crew assignment.
• The Use of Linear and Integer Programming in Airline Crew Scheduling, by Niklas Kohl, 1999, (4 pages).
  About formulations of the crew scheduling problems.
• Crew Pairing Optimization, by Andersson, Housos, Kohl, Wedelin, 1998, (31 pages).
  Describes the "classic" Carmen system, on top of which all others Carmen products have been developed.
• Crew Scheduling in Air Transportation, by Desaulniers, Desrosiers, Gamache, Soumis, 1997, (16 pages).
  The approach of Carmen's worst competitor: AD OPT. (Only available on paper).

The exercise we did Friday, May 4: Umlaufspiel

Deadline May 21

Assignment 5 - Specialization

Deadline June 1

Unlike the other assignments, this one should be handed in by mailing it to ek@cs.chalmers.se.
We will set up a web page so that everybody can read each others reports.
Mail in your report in Postscript (.ps) or Acrobat (.pdf) format.
Since your report will be made available for a wider audience it should be written in English.
Include a reference list of used literature in your report.

Assignment 5 can either be a literature study or a programming assignment:

Literature Study

Select a topic and a set of articles (either pick one of the prepared kits or select three articles on your own). Read the articles in order to study your selected topic in depth. Write a report on the topic based on your aquired knowledge.

Topics and articles to choose from.

Think of that this report will not only be read by me when grading, but also by several other people. You write for other people taking the course (or with similar background) that would like to get a quick understanding of your special topic. You also write for yourself in order to be able to easily pick this up at some later point e.g. when you will have to work with it.

For this purpose it is useful if you not just summarize the content of the papers but also that you try to put them in a context (of your choice), including any of your own reflections, comparisons, and recommendations.

Programming assignment

Make a program that solves crew pairing problems.
Rules and flight timetable can be used from the Umlaufspiel.
Data (flights) in electronic format can be found here.

You may work in groups. A report describing the algorithms and other implementation tricks has to be mailed in (no source code listings in the report). Also mail in the directory path (in a lab account) to a working program. The report may go further than your implementation, and describe ideas for solving pairing problems larger than (or different from) the Umlaufspiel. Not all of your ideas has to be implemented, but the program must solve the Umlaufspiel.

Additional Assignment for GU students

Deadline June 1

(This assignment only has to be done by GU students. You do not have to do it though if you made a programming assignment in Assignment 5.)

Write a summarizing report about one of the following topics:

• Logistics (lecture April 23 by Kenth Lumsden). Article.
• Railway Freight Cars (lecture May 14 by Martin Joborn). Article.
• Winter Road Management (lecture May 17 by Magnus Oskarsson). Article.

Optional exercise

With the knowledge you have aquired in the course you now have the tools to solve crew pairing problems like the Umlaufspiel. Use the column generation technique that you have learned in Assignment 3 (tasks 3 and 4).

Since the exercise means solving the subproblem by hand, we have to make the problem small enough by applying the following modifications to the Umlaufspiel:

The subproblem is now small enough to be solved by hand. It has to be solved as a shortest path problem with resource constraints. That means that we have to keep track of used duty time, number of legs, and the required rest time length along the search. A connection in the graph is not guaranteed to be legal for all paths that lead to it.

If you do this exercise you will get a good understanding that will be useful both in assignment 4 and 5. And you will also be well prepared for solving real world routing problems (a program can be written to handle the steps that you now do manually).

Practical info about the assignments

To the left of this box, you will find spare copies of material that has been handed out at lectures. However, most material you will be able to download from the course web page.

If you need to book a computer for the practical parts of the assignments, there is a booking list in the same hall as the hand-in box.

Here is a list of currently available lab hours.

It is part of the grading if the report is well written. We accept hand written reports, but encourage you to use a word processor. The important thing anyhow is that the report is well structured, clear and readable. Do not spend hours fighting with a word processor, to enter formulas or graphs, if you are not used to it. Consider adding hand drawings of graphs, and such, as an appendix instead, if it saves you time. Use the stapling machine in the HelpDesk before handing in (or bring paper clips to school), please...