ISOR Colloquium

Montag, 29. Mai 2017, 16:45 - 17:45 iCal

"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.

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