Paper Info

Title | ||
---|---|---|

A cut-based heuristic to produce almost feasible periodic railway timetables |

Abstract | ||
---|---|---|

We consider the problem of satisfying the maximum number of constraints of an instance of the Periodic Event Scheduling Problem (Pesp). This is a key issue in periodic railway timetable construction, and has many other applications, e.g. for traffic light scheduling. We generalize two (in-) approximability results, which are known for Maximum-K-Colorable-Subgraph. Moreover, we present a deterministic combinatorial polynomial time algorithm. Its output violates only very few constraints for five real-world instances. |

Year | DOI | Venue |
---|---|---|

2005 | 10.1007/11427186_31 | WEA |

Keywords | Field | DocType |

cut-based heuristic,approximability result,periodic event scheduling problem,deterministic combinatorial polynomial time,traffic light scheduling,feasible periodic railway timetable,periodic railway timetable construction,maximum number,key issue,real-world instance,scheduling problem,satisfiability | Mathematical optimization,Heuristic,Traffic signal,Algorithmics,Computer science,Scheduling (computing),Algorithm,Schedule,Periodic event scheduling problem,Time complexity,Periodic graph (geometry) | Conference |

Volume | ISSN | ISBN |

3503 | 0302-9743 | 3-540-25920-1 |

Citations | PageRank | References |

6 | 0.74 | 9 |

Authors | ||

1 |

Authors (1 rows)

Cited by (6 rows)

References (9 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Christian Liebchen | 1 | 325 | 28.64 |