EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
1208. A novel and effective integer linear programming formulation for the train routing selection problem
Invited abstract in session TB-52: Mixed Integer Optimization II, stream Combinatorial Optimization.
Tuesday, 10:30-12:00Room: 8003 (building: 202)
Authors (first author is the speaker)
| 1. | Anna Livia Croella
|
| Sapienza University of Rome | |
| 2. | Fabio Furini
|
| DIAG, La Sapienza | |
| 3. | Ivana Ljubic
|
| IDS, ESSEC Business School of Paris | |
| 4. | Bianca Pascariu
|
| COSYS-ESTAS, Université Gustave Eiffel | |
| 5. | Paola Pellegrini
|
| Université Gustave Eiffel | |
| 6. | Pablo San Segundo
|
| Polytechnic University of Madrid |
Abstract
Given a set of train routes associated with route costs and a set of compatible route pairs associated with pairing costs, the train routing selection problem (TRSP) aims to assign a route to each train, minimizing the sum of the route and pairing costs while ensuring pairwise compatibility among the selected routes. This problem holds significant practical importance, particularly in rail traffic management, where it plays a central role.
We propose a binary quadratic programming formulation for the TRSP and employ a linearization technique from the literature, with a linear number of additional variables and constraints, to derive a novel and effective integer linear programming (ILP) formulation.
Exploiting the specific nature of the TRSP, we devise a technique to enhance the strength of the linear programming (LP) relaxation of the ILP model, resulting in a significant improvement in its computational performance.
We obtain in this manner the first effective exact approach for solving the TRSP with proven optimality. Our approach is capable of solving real-world instances of the French railway network in very short computational times. These instances have typically been tackled only by heuristic algorithms in the existing literature.
Furthermore, we theoretically and computationally compare the new linearization against the classical one with a quadratic number of additional variables and constraints and against the only ILP model from the literature.
Keywords
- Railway Applications
- Graphs and Networks
- Programming, Linear
Status: accepted
Back to the list of papers