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.



Submit a solution or instance!

You were able to improve a benchmark solution? Please send me your solution files, and I will update the table accordingly.

Also, further benchmark sets are greatly appreciated.



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:

The current version is still quite slow - better versions are yet to come.



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.
My results are based on a variant of the modulo simplex algorith, as described 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

Some solutions are now available for download! Lower bounds are not verified.

Set-01

Railway timetabling instances
Name Events Activities Best objective (weighted slack) Author, Date Best lower bound
R1L1 3664 6386 39,656,259 Goerigk 12/5/2017 16,897,987
39,539,519 Goerigk 14/6/2012
39,216,699 Grossmann 14/9/2012
37,338,904 Herrigel 4/6/2013
33,711,523 Liebchen 20/4/2017
31,838,103 Goerigk & Liebchen 8/5/2017
R1L2 3668 6544 39,292,048 Goerigk 12/5/2017 4,975,398
38,248,408 Goerigk 14/6/2012
R1L3 4184 7032 40,180,266 Goerigk 12/5/2017 6,498,424
38,612,098 Goerigk 14/6/2012
R1L4 4760 8529 36,576,079 Goerigk 14/6/2012 6,297,850
35,955,823 Goerigk 12/5/2017
R2L1 4156 7362 53,928,689 Goerigk 14/6/2012 9,507,113
53,708,802 Goerigk 12/5/2017
R2L2 4204 7564 51,605,192 Goerigk 14/6/2012 7,768,806
47,836,571 Goerigk 12/5/2017
R2L3 5048 8287 46,777,845 Goerigk 14/6/2012 8,224,882
46,530,294 Goerigk 12/5/2017
R2L4 7660 13174 43,087,921 Goerigk 14/6/2012 5,217,025
42,848,107 Goerigk 12/5/2017
R3L1 4516 9146 53,602,675 Goerigk 14/6/2012 7,906,870
53,299,647 Goerigk 12/5/2017
R3L2 4452 9252 55,959,006 Goerigk 14/6/2012 7,432,716
53,441,333 Goerigk 12/5/2017
R3L3 5724 11170 52,896,725 Goerigk 14/6/2012 6,628,317
48,707,212 Goerigk 12/5/2017
R3L4 8180 15658 41,280,091 Goerigk 14/6/2012 5,623,632
40,597,536 Goerigk 12/5/2017
R4L1 4932 10263 60,904,741 Goerigk 14/6/2012 10,089,083
59,225,243 Goerigk 12/5/2017
R4L2 5048 10755 63,744,148 Goerigk 14/6/2012 7,975,150
59,292,152 Goerigk 12/5/2017
R4L3 6368 13239 55,435,561 Goerigk 14/6/2012 7,477,035
54,975,374 Goerigk 12/5/2017
R4L4 8384 17755 47,283,768 Goerigk 14/6/2012 5,147,195
47,140,800 Goerigk 12/5/2017
43,234,156 Liebchen 20/4/2017
40,608,497 Goerigk & Liebchen 12/5/2017
 
 
Set-02

Bus timetabling instances
Name Events Activities Best objective (weighted slack) Author, Date Best lower bound
BL1 2688 7988 7,670,068 Goerigk 15/6/2012 1,477,565
7,440,845 Goerigk 12/5/2017
BL2 2606 7488 8,691,995 Goerigk 15/6/2012 1,730,247
8,288,126 Goerigk 12/5/2017
BL3 3044 9311 8,009,746 Goerigk 15/6/2012 1,205,501
7,983,383 Goerigk 12/5/2017
BL4 3816 13502 10,263,808 Goerigk 15/6/2012 1,004,303
9,435,913 Goerigk 12/5/2017




Last update: 12 May, 2017
   Contact

   Marc Goerigk
   Department of Management Science
   Lancaster University
   United Kingdom