The second Chvátal closure can yield better railway timetables
| dc.contributor.author | Liebchen, Christian | |
| dc.contributor.author | Swarat, Elmar | |
| dc.date.accessioned | 2022-05-11T12:11:46Z | |
| dc.date.available | 2022-05-11T12:11:46Z | |
| dc.date.issued | 2008 | |
| dc.description.abstract | We investigate the polyhedral structure of the Periodic Event Scheduling Problem (PESP), which is commonly used in periodic railway timetable optimization. This is the first investigation of Chvatal closures and of the Chvatal rank of PESP instances. In most detail, we first provide a PESP instance on only two events, whose Chvatal rank is very large. Second, we identify an instance for which we prove that it is feasible over the first Chvatal closure, and also feasible for another known prominent class of known valid inequalities, which we reveal to live in much larger Chvatal closures. In contrast, this instance turns out to be infeasible already over the second Chvatal closure. We obtain the latter result by introducing new valid inequalities for the PESP, the multi-circuit cuts. In the past, for other classes of valid inequalities for the PESP, it had been observed that these do not have any effect in practical computations. In contrast, the new multi-circuit cuts that we are introducing here, indeed show some effect in the computations that we perform on several real-world instances - a positive effect, in most of the cases. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/16906 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-15684 | |
| dc.language.iso | en | |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | Chvátal closure | en |
| dc.subject.other | periodic event scheduling problem | en |
| dc.subject.other | PESP | en |
| dc.subject.other | railway timetable optimization | en |
| dc.title | The second Chvátal closure can yield better railway timetables | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2008, 27 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
| tub.subject.msc2000 | 90B06 Transportation, logistics and supply chain management | en |
| tub.subject.msc2000 | 90B35 Deterministic scheduling theory in operations research | en |
Files
Original bundle
1 - 1 of 1