Обобщённая задача коммивояжёра для определения рациональных маршрутов поставки
Маршрутом является путь между городами, по которому перевозится определенный логистический объект. Необходимо найти оптимальный обход городов, побывав в каждом городе ровно один раз. Оптимальным считается маршрут, по которому возможно доставить логистический объект, в кратчайшие сроки (или предусмотренные сроки) с минимальными затратами, а также с минимальным вредом для объекта доставки. Время работы линейного поиска для N городов равно факториалу числа N. Необходимо использовать эвристический поиск, который хоть и не гарантирует нахождение единственного решения, но выдает оптимальный результат за установленное время поиска. В качестве эвристического поиска предлагается использовать генетический алгоритм. За счет использования функции мутации, скрещивания и отбора лучших результатов, генетические алгоритмы позволяют оптимизировать определенные виды NP-полных задач. Несмотря на то, что задача коммивояжера является NP-полной, она широко применяется в прикладных транспортных системах.
( Читать дальше )
- 0
- 7 октября 2010, 03:55
- комментировать
