Logo der Universität Wien

Upcoming events:

Optimized train speed profiles
(PLIS/ PROLOG Colloquium)

       by David Pisinger (DTU)


Date:           05.04.2017 - Time: 17:00

Location:      SE 15
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)




We present a novel solution method to generate energy-efficient train speed profiles. As opposed to previous analytical methods, we propose a graph representation of the problem, making it possible to generate pareto-optimal train speed profiles by use of Dynamic Programming (DP). Instead of using uniform discretization of space, time or speed, we rely on an event-based decomposition that drastically reduces the search space. Moreover, we are able to handle speed limitations, passage point time windows, as well as various measures of robustness (buffer time, number of speed changes). Such additional constraints were difficult to handle by previous approaches. Based on an extensive number of real-life problem instances our benchmark shows that the proposed solution method is able to reduce the energy consumption by 3.3% on average compared to existing solutions. The computational times are very low, making it possible to handle unexpected changes in speed restrictions or timings by recalculating the schedule. This is a great advantage compared to static offline lookup tables.

(co-authors: Jørgen Thorlund Haahr)

Exact Methods for Non-Hamiltonian Routing Problems (ISOR Colloquium)
       by Hande Yaman (Bilkent Univ.)


Date:           29th May 2017 - Time: 16:45 - 17:45

Location:      Hörsaal 7
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

The classical traveling salesman problem (TSP) seeks a Hamitonian cycle (a cycle that visits every node exactly once) of minimum cost. Even though early routing problems focus on finding Hamiltonian cycles, many routing applications also require the choice of nodes that are to be visited or the number of times a node is visited. In this talk, we present exact methods for three non-Hamiltonian routing problems; namely, the split delivery VRP, the time constrained maximal covering TSP and the VRP with roaming delivery locations. We propose an iterative approach to solve the split delivery VRP where a relaxation is tigthened at each iteration by adding new variables and constraints. For the time constrained maximal covering TSP, we give a new family of facet defining inequalities and use them in a branch-and-cut approach. Finally, we present a branch-and-price algorithm to solve the VRP with roaming delivery locations. This is joint work with O.E. Karasan, M. Savelsbergh and G. Ozbaygin.

Faculty of Business, Economics and Statistics
University of Vienna
Oskar-Morgenstern-Platz 1
A-1090 Vienna

T: +43-1-4277-38092
F: 43-1-4277-838094
University of Vienna | Universitätsring 1 | 1010 Vienna | T +43-1-4277-0