The Multiple Traveling Salesmen Problem with Shared Vertex Costs

The Multiple Traveling Salesmen Problem with Shared Vertex Costs is introduced as a novel extension of the classical Traveling Salesman Problem that integrates routing decisions, service times and cost-sharing among salesmen. In this variant, node-visiting costs are incurred with the presence of agents over consecutive days, and multiple salesmen may simultaneously visit the same node, allowing these costs to be shared among them. In this work, we formally define the problem and propose a mixed-integer linear programming formulation together with strengthening techniques and a upper bound to optimal solution. To evaluate the proposed formulation, we generated a benchmark dataset derived from TSPLIB instances.