A column generation approach to train timetabling on a corridor.

*(English)*Zbl 1151.90323Summary: We propose heuristic and exact algorithms for the (periodic and non-periodic) train timetabling problem on a corridor that are based on the solution of the LP relaxation of an ILP formulation in which each variable corresponds to a full timetable for a train. This is in contrast with previous approaches to the same problem, which were based on ILP formulations in which each variable is associated with a departure and/or arrival of a train at a specific station in a specific time instant, whose LP relaxation is too expensive to be solved exactly. Experimental results on real-world instances of the problem show that the proposed approach is capable of producing heuristic solutions of better quality than those obtained by these previous approaches, and of solving some small-size instances to proven optimality.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90C10 | Integer programming |

90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

train timetabling; ILP-formulation; column generation; separation; constructive heuristics; experimental results##### Software:

PESPLib
Full Text:
DOI

**OpenURL**

##### References:

[1] | Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs. Oper Res 46:316–329 · Zbl 0979.90092 |

[2] | Borndörfer R, Grötschel M, Lukac S, Mitusch K, Schlechte T, Schultz S, Tanner A (2005) An auctioning approach to railway slot allocation. ZIB Technical Report ZR-05-45 |

[3] | Brännlund U, Lindberg PO, Nöu A, Nilsson JE (1998) Allocation of scarce track capacity using Lagrangian relaxation. Transp Sci 32:358–369 · Zbl 1004.90035 |

[4] | Cai X, Goh CJ (1994) A fast heuristic for the train scheduling problem. Comput Oper Res 21:499–510 · Zbl 0799.90068 |

[5] | Caprara A, Fischetti M, Toth P (2002) Modeling and solving the train timetabling problem. Oper Res 50:851–861 · Zbl 1163.90482 |

[6] | Caprara A, Kroon L, Monaci M, Peeters M, Toth P (2006) Passenger railway optimization. In: Barnhart C, Laporte G (eds) Handbooks in operations research and management science, vol 14. Elsevier, Amsterdam, pp 129–187 |

[7] | Caprara A, Monaci M, Toth P, Guida PL (2006) A Lagrangian heuristic approach to real-world train timetabling problems. Disc Appl Math 154:738–753 · Zbl 1120.90324 |

[8] | Carey M, Lockwood D (1995) A model, algorithms and strategy for train pathing. J Oper Res Soc 46:988–1005 · Zbl 0832.90068 |

[9] | Higgings A, Kozan E, Ferreira L (1997) Heuristic techniques for single line train scheduling. J Heuristics 3:43–62 · Zbl 1071.90535 |

[10] | Jovanovic D, Harker PT (1991) Tactical scheduling of rail operations: the SCAN I system. Transp Sci 25:46–64 |

[11] | Kroon LG, Peeters LWP (2003) A variable trip time model for cyclic railway timetabling. Transp Sci 37:198–212 |

[12] | Liebchen C, Proksch M, Wagner FH (2004) Performance of algorithms for periodic timetable optimization. TU Preprint 021/2004, TU Berlin Computer-aided transit scheduling. Lecture notes in economics and mathematical systems. Springer, Berlin (to appear) |

[13] | Lindner T (2000) Train schedule optimization in public rail transport. Ph.D. Thesis, University of Technology, Braunschweig · Zbl 1048.90114 |

[14] | Lindner T, Zimmermann UT (2005) Cost optimal periodic train scheduling. Math Methods Oper Res 62:281–295 · Zbl 1109.90042 |

[15] | Odijk M (1996) A constraint generation algorithm for the construction of periodic railway timetables. Transp Res 30:455–464 |

[16] | E. Oliveira and B.M. Smith, ”A Job-Shop Scheduling Model for the Single-Track Railway Scheduling Problem ”, Technical Report 2000.21, School of Computing Research Report, University of Leeds, 2000. |

[17] | Peeters LWP (2003) Cyclic railway timetable optimization. Ph.D. Thesis, Erasmus Research Institute of Management, Erasmus University, Rotterdam |

[18] | Peeters LWP, Kroon LG (2001) A cycle based optimization model for the cyclic railway timetabling problem. In: Daduna J, Voss S (eds) Computer-aided transit scheduling, lecture notes in economics and mathematical systems, vol 505. Springer, Berlin, pp 275–296 |

[19] | Serafini P, Ukovich W (1989) A mathematical model for periodic event scheduling problems. SIAM J Disc Math 2:550–581 · Zbl 0676.90030 |

[20] | Schrijver A, Steenbeek A (1994) Timetable construction for railned. Technical Report, CWI, Amsterdam (in Dutch) |

[21] | Szpigel B (1973) Optimal train scheduling on a single track railway. In: Ross M (ed) OR’72. North-Holland, Amsterdam, pp 343–351 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.