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.
Homepage of Hande Yaman