У меня около 300 адресов в городе, и я пытаюсь найти программное обеспечение, которое может решить проблему коммивояжера. Я пробовал OptiMap - решение на основе браузера, которое использует Google API, но оно ограничено 100 пунктами назначения (даже если вы изменяете жестко заданные ограничения), а браузерам, которые я пытаюсь, в конечном итоге не хватает памяти. Я знаю, что проблема NP трудна, но это не новая проблема, конечно, кто-то уже написал программное обеспечение. Единственные коммерческие решения, которые я видел, базируются только в США (это австралийский город) или имеют низкие ограничения.
Есть ли бесплатное или коммерческое программное обеспечение для решения этой задачи и его размер?
software-rec
calculator
user348998
источник
источник
Ответы:
Не совсем «бесплатно» - но, возможно, реализует алгоритм аппроксимации для TSP, изложенный в этом учебнике .
IIRC, это дает решение TSP для плоских графов в 2 раза в рамках оптимального решения.
источник