построить маршрут

[radostelenka]

есть энное количество точек с координатами Х, У
есть ср. скорость движения, есть ограничение на продолжительность маршрута
задача построить маршруты прохождения через точки так чтобы:
1. необходимо пройти все точки
2. каждый маршрут начинается с коорд.00
3. маршрут не может быть дольше предельного значения
4. маршрутов - минимум
5. общая продолжительность - минимальна
и еще в каждой точке задано время выполнения задания.
задача такая: есть точки доставки, необходимо минимальным количеством курьеров обойти все точки, чтобы курьеры не перерабатывали 8 часов (480 минут в задаче).
задача №1 сократить до мин. кол-во курьеров (выданных зарплат)

подскажите где можно прочесть варианты алгоритма решения... на транспортную задачу, на задачу коммивояжёра и тд не совсем похоже...

[Shtorm]

Очевидно Теория графов

[mserg]

При относительно небольшом количестве точек, скорее всего, задачу можно решить с помощью линейного программирования. Пример чем-то похожей задачи можно посмотреть здесь (задача о курьерах)

При большом количестве потребуется более эффективное моделирование – в описанной постановке задача, скорее всего, «труднорешаема» – приближенные алгоритмы будут давать плохое решение. Уж так у нас повелось: по книжкам можно научиться создавать комбинаторный ужас вместо реальных моделей.

[vlad_light]

Задача реальная или учебная? Рекомендую полный перебор (по кол-ву курьеров)! Фиксированное время выполнения задания значительно сужает поиск (на раннем этапе помогает отбросить ложные пути).

[sup]

Это таки один из вариантов задачи коммивояжера. Есть специализированный сайт VRP.

[radostelenka]

задача реальная, только точек много
ручной перебор занимает очень много времени...хотелось хоть немного автоматизировать процесс...
перебрала много литературы, но нигде не могу найти хоть на что-то похожий алгоритм...
Уж так у нас повелось: по книжкам можно научиться создавать комбинаторный ужас вместо реальных моделей. Это точно...
ведь задача не сократить длину маршрута(надо что бы курьер работал 8 часов), а минимизировать количество курьеров...то есть самих маршрутов...
так что транспортной задачей ничего не сделать, а задача коммивояжера, в том варианте (классическом), тоже не удовлетворяет всем требованиям, она находит обход всех точек, а мне надо разбить их на несколько маршрутов...
Благодарю всех кто старался подсказать, может все же найду вариант

[nikvic]

sup в сообщении #705082 писал(а):

Это таки один из вариантов задачи коммивояжера.

Осложнён дважды.
1/ На выходе - разбиение множества вершин на минимальное число зон.
2/ Маршруты по зонам не закольцованы.

[sup]

nikvic в сообщении #705205 писал(а):

Осложнён дважды.
1/ На выходе - разбиение множества вершин на минимальное число зон.
2/ Маршруты по зонам не закольцованы.

Это все и есть вариации на тему. Если бы не ограничение на величину каждого маршрута, то все свелось бы к чистой задаче коммивояжера (с помощью фиктивных вершин и/или асимметричой TSP).
Коль скоро решение ищется вручную (!), то можно попробовать такой подход хотя бы в качестве начального приближения. А уж задачу коммивояжера решать с помощью приближения Хелда-Карпа.