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/05/2017 16,897,987
39,539,519 Goerigk 14/06/2012
39,216,699 Grossmann 14/09/2012
38,384,557 Pätzold 04/07/2017
37,338,904 Herrigel 04/06/2013
33,711,523 Liebchen 20/04/2017
31,838,103 Goerigk & Liebchen 08/05/2017
31,194,961 Goerigk & Liebchen 25/06/2017
31,099,786 Goerigk & Liebchen 19/05/2017
R1L2 3668 6544 39,292,048 Goerigk 12/05/2017 4,975,398
38,313,354 Pätzold 04/07/2017
38,248,408 Goerigk 14/06/2012
31,682,263 Goerigk & Liebchen 25/06/2017
R1L3 4184 7032 40,180,266 Goerigk 12/05/2017 6,498,424
38,612,098 Goerigk 14/06/2012
38,160,248 Albino & Matos 03/10/2017
35,185,628 Pätzold 04/07/2017
30,535,261 Goerigk & Liebchen 25/06/2017
R1L4 4760 8529 36,576,079 Goerigk 14/06/2012 6,297,850
35,955,823 Goerigk 12/05/2017
33,777,047 Pätzold 04/07/2017
27,893,098 Goerigk & Liebchen 25/06/2017
R2L1 4156 7362 53,928,689 Goerigk 14/06/2012 9,507,113
53,708,802 Goerigk 12/05/2017
52,501,839 Albino & Matos 03/10/2017
48,729,230 Pätzold 04/07/2017
42,502,069 Goerigk & Liebchen 25/06/2017
R2L2 4204 7564 51,605,192 Goerigk 14/06/2012 7,768,806
49,022,206 Pätzold 04/07/2017
47,836,571 Goerigk 12/05/2017
43,068,782 Goerigk & Liebchen 25/06/2017
R2L3 5048 8287 46,777,845 Goerigk 14/06/2012 8,224,882
46,530,294 Goerigk 12/05/2017
45,861,236 Pätzold 04/07/2017
39,942,656 Goerigk & Liebchen 25/06/2017
R2L4 7660 13174 43,087,921 Goerigk 14/06/2012 5,217,025
42,848,107 Goerigk 12/05/2017
42,429,329 Albino & Matos 03/10/2017
39,807,766 Pätzold 04/07/2017
33,063,475 Goerigk & Liebchen 25/06/2017
R3L1 4516 9146 53,602,675 Goerigk 14/06/2012 7,906,870
53,299,647 Goerigk 12/05/2017
52,014,295 Pätzold 04/07/2017
45,483,668 Goerigk & Liebchen 25/06/2017
R3L2 4452 9252 55,959,006 Goerigk 14/06/2012 7,432,716
54,671,910 Pätzold 04/07/2017
53,441,333 Goerigk 12/05/2017
46,228,200 Goerigk & Liebchen 25/06/2017
R3L3 5724 11170 52,896,725 Goerigk 14/06/2012 6,628,317
48,707,212 Goerigk 12/05/2017
45,613,859 Pätzold 04/07/2017
43,039,089 Goerigk & Liebchen 25/06/2017
R3L4 8180 15658 41,280,091 Goerigk 14/06/2012 5,623,632
40,597,536 Goerigk 12/05/2017
39,314,628 Pätzold 04/07/2017
35,547,064 Goerigk & Liebchen 25/06/2017
R4L1 4932 10263 60,904,741 Goerigk 14/06/2012 10,089,083
59,225,243 Goerigk 12/05/2017
58,175,389 Pätzold 04/07/2017
51,650,471 Goerigk & Liebchen 25/06/2017
R4L2 5048 10755 63,744,148 Goerigk 14/06/2012 7,975,150
59,292,152 Goerigk 12/05/2017
55,483,714 Pätzold 04/07/2017
51,965,758 Goerigk & Liebchen 25/06/2017
R4L3 6368 13239 55,435,561 Goerigk 14/06/2012 7,477,035
54,975,374 Goerigk 12/05/2017
51,592,561 Pätzold 04/07/2017
45,881,499 Goerigk & Liebchen 25/06/2017
R4L4 8384 17755 47,283,768 Goerigk 14/06/2012 5,147,195
47,140,800 Goerigk 12/05/2017
43,234,156 Liebchen 20/04/2017
42,342,999 Pätzold 04/07/2017
40,608,497 Goerigk & Liebchen 12/05/2017
38,836,756 Liebchen 29/08/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/06/2012 1,477,565
7,440,845 Goerigk 12/05/2017
7,387,963 Albino & Matos 03/10/2017
BL2 2606 7488 8,691,995 Goerigk 15/06/2012 1,730,247
8,288,126 Goerigk 12/05/2017
8,143,507 Albino & Matos 03/10/2017
BL3 3044 9311 8,009,746 Goerigk 15/06/2012 1,205,501
7,983,383 Goerigk 12/05/2017
7,826,762 Albino & Matos 03/10/2017
BL4 3816 13502 10,263,808 Goerigk 15/06/2012 1,004,303
9,435,913 Goerigk 12/05/2017
7,359,779 Albino & Matos 03/10/2017




Last update: 9 October, 2017
   Contact

   Marc Goerigk
   Department of Management Science
   Lancaster University
   United Kingdom