New formulation for the high multiplicity asymmetric traveling salesman problem with application to the Chesapeake problem

This paper presents a new model for a special type of traveling salesman problem called the High Multiplicity Asymmetric Traveling Salesman Problem (HMATSP). The formulation adopts a flow‐based subtour elimination structure and establishes its validity for this problem. Also, we present computational results to demonstrate the efficacy of our modeling approach. The model is then incorporated as a substructure in a formulation for the lot‐sizing problem involving parallel machines and sequence‐dependent setup costs, also known as the Chesapeake Problem, and related test problems are solved to optimality for the first time in the literature.