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

For the sake of transparency, solutions generated by myself (marked with Goerigk) are 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 20,230,655
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
30,780,097 Pätzold 11/10/2018
30,463,638 Lindner & Roth 30/01/2019
30,415,672 Lindner 23/10/2018
29,894,745 Lindner & Liebchen 24/02/2021
R1L2 3668 6544 39,292,048 Goerigk 12/05/2017 19,414,800
38,313,354 Pätzold 04/07/2017
38,248,408 Goerigk 14/06/2012
34,330,602 Pätzold 11/10/2018
31,682,263 Goerigk & Liebchen 25/06/2017
30,507,180 Lindner & Roth 30/01/2019
R1L3 4184 7032 40,180,266 Goerigk 12/05/2017 18,786,300
38,612,098 Goerigk 14/06/2012
38,160,248 Matos & Albino 03/10/2017
35,185,628 Pätzold 04/07/2017
30,535,261 Goerigk & Liebchen 25/06/2017
30,307,719 Pätzold 11/10/2018
29,319,593 Lindner & Roth 30/01/2019
R1L4 4760 8529 36,576,079 Goerigk 14/06/2012 16,822,200
35,955,823 Goerigk 12/05/2017
33,777,047 Pätzold 04/07/2017
27,893,098 Goerigk & Liebchen 25/06/2017
27,326,571 Pätzold 11/10/2018
26,516,727 Lindner & Roth 30/01/2019
R2L1 4156 7362 53,928,689 Goerigk 14/06/2012 25,082,000
53,708,802 Goerigk 12/05/2017
52,501,839 Matos & Albino 03/10/2017
48,729,230 Pätzold 04/07/2017
43,316,018 Pätzold 11/10/2018
42,502,069 Goerigk & Liebchen 25/06/2017
42,422,038 Lindner & Roth 30/01/2019
R2L2 4204 7564 51,605,192 Goerigk 14/06/2012 24,867,400
49,022,206 Pätzold 04/07/2017
47,836,571 Goerigk 12/05/2017
43,068,782 Goerigk & Liebchen 25/06/2017
41,534,563 Pätzold 11/10/2018
40,642,186 Lindner & Roth 30/01/2019
R2L3 5048 8287 46,777,845 Goerigk 14/06/2012 23,152,300
46,530,294 Goerigk 12/05/2017
45,861,236 Pätzold 04/07/2017
40,873,361 Pätzold 11/10/2018
39,942,656 Goerigk & Liebchen 25/06/2017
38,558,371 Lindner & Roth 30/01/2019
R2L4 7660 13174 43,087,921 Goerigk 14/06/2012 18,941,500
42,848,107 Goerigk 12/05/2017
42,429,329 Matos & Albino 03/10/2017
39,807,766 Pätzold 04/07/2017
33,137,957 Pätzold 11/10/2018
33,063,475 Goerigk & Liebchen 25/06/2017
32,483,894 Lindner & Roth 30/01/2019
R3L1 4516 9146 53,602,675 Goerigk 14/06/2012 25,077,800
53,299,647 Goerigk 12/05/2017
52,014,295 Pätzold 04/07/2017
45,483,668 Goerigk & Liebchen 25/06/2017
44,396,635 Pätzold 11/10/2018
43,271,824 Lindner & Roth 30/01/2019
R3L2 4452 9252 55,959,006 Goerigk 14/06/2012 25,272,600
54,671,910 Pätzold 04/07/2017
53,441,333 Goerigk 12/05/2017
46,228,200 Goerigk & Liebchen 25/06/2017
46,048,483 Pätzold 11/10/2018
45,220,083 Lindner & Roth 30/01/2019
R3L3 5724 11170 52,896,725 Goerigk 14/06/2012 21,642,500
48,707,212 Goerigk 12/05/2017
45,613,859 Pätzold 04/07/2017
43,039,089 Goerigk & Liebchen 25/06/2017
42,833,223 Pätzold 11/10/2018
40,849,585 Lindner & Roth 30/01/2019
40,483,617 Bortoletto, Lindner & Masing 08/07/2022
R3L4 8180 15658 41,280,091 Goerigk 14/06/2012 16,479,500
40,597,536 Goerigk 12/05/2017
39,314,628 Pätzold 04/07/2017
35,547,064 Goerigk & Liebchen 25/06/2017
34,694,043 Pätzold 11/10/2018
33,335,852 Lindner & Roth 30/01/2019
R4L1 4932 10263 60,904,741 Goerigk 14/06/2012 27,243,900
59,225,243 Goerigk 12/05/2017
58,175,389 Pätzold 04/07/2017
52,271,661 Pätzold 11/10/2018
51,650,471 Goerigk & Liebchen 25/06/2017
49,426,919 Lindner & Roth 30/01/2019
R4L2 5048 10755 63,744,148 Goerigk 14/06/2012 26,368,200
59,292,152 Goerigk 12/05/2017
55,483,714 Pätzold 04/07/2017
51,965,758 Goerigk & Liebchen 25/06/2017
49,579,843 Pätzold 11/10/2018
48,764,793 Lindner & Roth 30/01/2019
R4L3 6368 13239 55,435,561 Goerigk 14/06/2012 22,701,400
54,975,374 Goerigk 12/05/2017
51,592,561 Pätzold 04/07/2017
48,071,296 Pätzold 11/10/2018
45,881,499 Goerigk & Liebchen 25/06/2017
45,493,081 Lindner & Roth 30/01/2019
R4L4 8384 17755 47,283,768 Goerigk 14/06/2012 17,961,400
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
39,686,936 Pätzold 11/10/2018
38,836,756 Liebchen 29/08/2017
38,381,922 Lindner & Roth 30/01/2019
36,728,402 Lindner & Liebchen 24/02/2021
36,703,391 Bortoletto, Lindner & Masing 08/07/2022
 
 
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 3,668,148
7,440,845 Goerigk 12/05/2017
7,387,963 Matos & Albino 03/10/2017
6,333,641 Lindner & Roth 30/01/2019
BL2 2606 7488 8,691,995 Goerigk 15/06/2012 3,943,811
8,288,126 Goerigk 12/05/2017
8,143,507 Matos & Albino 03/10/2017
6,799,331 Lindner & Roth 30/01/2019
BL3 3044 9311 8,009,746 Goerigk 15/06/2012 3,571,976
7,983,383 Goerigk 12/05/2017
7,826,762 Matos & Albino 03/10/2017
6,999,313 Lindner & Roth 30/01/2019
6,675,098 Bortoletto, Lindner & Masing 08/07/2022
BL4 3816 13502 10,263,808 Goerigk 15/06/2012 3,131,491
9,435,913 Goerigk 12/05/2017
7,359,779 Matos & Albino 03/10/2017
6,562,147 Lindner & Roth 30/01/2019
 
Set-03

Instance variants, submitted by Niels Lindner, Christian Liebchen, Berenike Masing, based on this paper.
Name Events Activities Best objective (weighted slack) Author, Date Best lower bound
R1L1v 3664 6495 42,667,746 Lindner, Liebchen & Masing 06/07/2021 29,620,775
42,591,141 Bortoletto, Lindner & Masing 08/07/2022
R4L4v 8384 18020 64,327,217 Lindner, Liebchen & Masing 06/07/2021 32,296,041
61,968,380 Bortoletto, Lindner & Masing 08/07/2022




Last update: 11 July, 2022



   Contact

   Marc Goerigk
   Network and Data Science Management
   University of Siegen
   Germany