Задача о коммивояжере коммивояжера - PullRequest
6 голосов
/ 14 апреля 2010

Я прочитал пару статей и пример кода о том, как решить TSP с помощью генетических алгоритмов, оптимизации колоний муравьев и т. Д. Но все, что я обнаружил, не включало временные (оконные) ограничения, например. «Я должен быть у клиента х до 12 утра)» и предположил симметрию.

Может ли кто-нибудь указать мне направление некоторых примеров кода или статей, которые объясняют, как я могу добавить ограничения в TSP и как я могу представить их в коде.

Спасибо!

Ответы [ 2 ]

7 голосов
/ 14 апреля 2010

Профессор Рейнельт из университета Гейдельбурга в Германии является одним из ведущих экспертов TSP. У него есть сборник статей по различным вариантам TSP.

см. http://www.iwr.uni -heidelberg.de / groups / comopt / software / TSPLIB95 /

Я думаю, что ваш вариант называется проблема маршрутизации транспортных средств с временными окнами. (http://en.wikipedia.org/wiki/Vehicle_routing_problem)

2 голосов
/ 13 мая 2010

Вам следует взглянуть на то, что может сделать для вас современный уровень независимого планирования домена: http://ipc.informatik.uni -freiburg.de /

...