PESPlib

Problem Description

This is a benchmark library for Periodic Event Scheduling Problems as introduced by P. Serafini and W. Ukovich: A mathematical model for periodic scheduling problems. SIAM J. Disc. Math., pages 550-581, 1989, which are frequently encountered in timetabling problems.

Instance and Solution Format

Instances are given in csv format. For a line

N; O; T; L; U; W

• N is the activity number,
• O is the activity origin,
• T is the activity target,
• L is the lower bound of the activity,
• U its upper bound,
• and W the weight.

The periodid is given by T=60 in all cases.
Solutions should be given in the format

N; D

• where N is the activity number,
• and D its duration.

Comments must be preceeded by "#". We seek to minimize the weighted slack.

Example

For an instance

#instance example
1; 1; 2; 50; 55; 10
2; 2; 3; 40; 50; 20
3; 1; 3; 30; 40; 15

an optimal solution is given by

 
#solution example
1; 50
2; 40
3; 30

with objective value 0.

Verification Program

A small C++ program checking the feasibility and objective value of a solution can be downloaded here:

• verification.cpp

The current version is still quite slow.

Citations

Instances are based on the LinTim software project. When citing LinTim, please use the paper M. Goerigk, M. Schachtebeck, A. Schöbel. Evaluating Line Concepts using Travel Times and Robustness: Simulations with the Lintim toolbox. Public Transport. Volume 5, Issue 3, October 2013, pp 267-284.

The railway instances presented here were first used in M. Goerigk, A. Schöbel. Improving the Modulo Simplex Algorithm for Large-Scale Periodic Timetabling. Computers & Operations Research. Volume 40, Issue 5, May 2013, Pages 1363-1370.

Instances

Lower bounds are not verified.