Коммивояжер с несколькими продавцами?

У меня проблема, которая фактически была сведена к проблеме коммивояжера с несколькими продавцами. У меня есть список городов, которые нужно посетить с самого начала, и я должен посетить все города с ограниченным числом продавцов.

Я пытаюсь придумать эвристику, и мне интересно, может ли кто-нибудь помочь. Например, если у меня есть 20 городов с двумя продавцами, я подумал о двухэтапном подходе. Сначала разделите 20 городов случайным образом на 10 городов по 2 продавца в каждом, и я найду тур для каждого, как если бы он был независимым, на несколько итераций. После этого я бы хотел либо поменять местами, либо передать город другому продавцу и найти тур. По сути, это была бы проблема с TSP, а затем с минимальным сроком изготовления. Проблема в том, что это было бы слишком медленно, и создание хороших соседей для замены или назначения города затруднено.

Может ли кто-нибудь дать совет, как я могу улучшить вышеуказанное?

EDIT:

The геолокация для каждого города известна, и продавцы начинают и заканчивают в одних и тех же местах. Цель состоит в том, чтобы свести к минимуму максимальное время в пути, создав проблему минимального времени изготовления. Так, например, если продавец1 занимает 10 часов, а продавец2 - 20 часов, максимальное время в пути составит 20 часов.