## The m-Cost ATSP

Please always quote using this URN: urn:nbn:de:0297-zib-4374

- Although the m-ATSP (or multi traveling salesman problem) is well known for its importance in scheduling and vehicle routing, it has, to the best of our knowledge, never been studied polyhedraly, i.e., it has always been transformed to the standard ATSP. This transformation is valid only if the cost of an arc from node $i$ to node $j$ is the same for all machines. In many practical applications this is not the case, machines produce with different speeds and require different (usually sequence dependent) setup times. We present first results of a polyhedral analysis of the m-ATSP in full generality. For this we exploit the tight relation between the subproblem for one machine and the prize collecting traveling salesman problem. We show that, for $m\ge 3$ machines, all facets of the one machine subproblem also define facets of the m-ATSP polytope. In particular the inequalities corresponding to the subtour elimination constraints in the one machine subproblems are facet defining for m-ATSP for $m\ge 2$ and can be separated in polynomial time. Furthermore, they imply the subtour elimination constraints for the ATSP-problem obtained via the standard transformation for identical machines. In addition, we identify a new class of facet defining inequalities of the one machine subproblem, that are also facet defining for m-ATSP for $m\ge 2$. To illustrate the efficacy of the approach we present numerical results for a scheduling problem with non-identical machines, arising in the production of gift wrap at Herlitz PBS AG.

Author: | Christoph Helmberg |
---|---|

Document Type: | ZIB-Report |

Tag: | ATSP; nonidentical machines; polyhedral relaxations; scheduling |

MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B30 Production models |

90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C09 Boolean programming | |

90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming | |

Date of first Publication: | 1999/12/23 |

Series (Serial Number): | ZIB-Report (SC-99-48) |

ZIB-Reportnumber: | SC-99-48 |

Published in: | Appeared in: G. Cornuejols; R. E. Burkard; G. J. Woegingner, Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 1610, Springer 1999, 242-258 |