Montag, 29. Mai 2017, 16:45 - 17:45 iCal
ISOR Colloquium
"Exact Methods for Non-Hamiltonian Routing Problems"
Speaker: Hande Yaman (Bilkent Univ.)
HS 7 OMP1 (#01.303, 1st floor)
Oskar-Morgenstern-Platz 1, 1090 Vienna
Vortrag
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.
Zur Webseite der Veranstaltung
Veranstalter
Institut für Statistik und Operations Research
Kontakt
Mag. Vera Lehmwald
Fakultät für Wirtschaftswissenschaften
Institut für Statistik und Operations Research
+43 1 4277 38651
vera.lehmwald@univie.ac.at
Erstellt am Sonntag, 19. März 2017, 11:09
Letzte Änderung am Montag, 20. März 2017, 08:48