New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints |
| |
| Authors: | Subhash C Sarin Ajay Bhootra |
| |
| Institution: | Grado Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, 250 Durham Hall, Blacksburg, VA 24061, USA |
| |
| Abstract: | We propose a new formulation for the asymmetric traveling salesman problem, with and without precedence relationships, which employs a polynomial number of subtour elimination constraints that imply an exponential subset of certain relaxed Dantzig-Fulkerson-Johnson subtour constraints. Promising computational results are presented, particularly in the presence of precedence constraints. |
| |
| Keywords: | Asymmetric traveling salesman problem Precedence constraints Subtour elimination constraints |
| 本文献已被 ScienceDirect 等数据库收录！ |
