Задача комивояжера

Question

[KLUBS]

Допустим есть агентство курьерских услуг по городу. Пусть есть 5 курьеров. Метро, автобусы и курьеры ходить пешком тоже умеют Каждый курьер должен съездить в несколько мест.

Вопрос — КАК проложить оптимальный (по времени (в первую очередь) и деньгам) маршрут? (алгоритм). Да это задача комивояжера, но немного измененная.

Хотелось бы чтобы программа отправила курьера с ветки на ветки метро на автобусе за 10 минут и 20 рублей, а не на метро через центр за 40 минут и 19 рублей.

т.е. есть список метро и адрес куда отвести (метро привязано к адресу). Есть 5 курьеров и 25 передач которые нужно вести (по 5 на каждого). Нужно каждому курьеру передать 5 передач чтобы время и стоимость были оптимальны. Ну и вес туда, же.

Как представлю что это такое… становится не по себе. Уже морально готов к полному перебору, но не могу пока придумать алгоритм

Comments

[KLUBS]

Для начала видимо подойдет просто распределение передач по курьерам и оптимальные ходы по метро + переезд с одной ветки на другую по верху если они рядом

Answer 1

[kekekeks]

Прикинул. В общем, вам нужно где-то раздобыть списки маршрутов и вытащить откуда-нибудь карту метро. После чего вам понадобится построить полный граф стоимостей перемещения с каждой остановки на каждую. Это делается один раз. Потом, когда распределяете посылки, надо будет найти опять же кратчайшие маршруты между точками следования, используя предворительно подготовленный граф цен перемещений. И уже по этому графу точка-точка делать полный перебор. Ресурсов сожрать много не должно, да и у нас не олимпиада, когда надо в секунду уложиться. Как-то вот так.

Answer 2

[kekekeks]

У вас каких-то 25 передач и 5 курьеров. На таких объёмах можно смело использовать полный перебор и не заморачиваться. Единственное, постройте полный граф цен перемещения от каждой точки до каждой.

Comments

[KLUBS]

С такой задачей сталкиваюсь впервые. В универе делал гораздо проще и не для бизнеса :) Хотелось бы что-нибудь быстро прочитать по этой теме. Банально — как правильно составить граф. Полный перебор то я организовать сумею))

[kekekeks]

Банальная матрица n на n, где в ячейке [n,m] хранится расстояние от n до m.

Первоначально, когда подгружаете карту путей сообщения для всех элементов ставите ценой какое-либо большое число, которое означает, что пути нет. Потом, например, для станции метро заполняете стоимость перемещения до соседних станций и до ближайших остановок наземного транспорта (для остановок считайте по разнице координат, поставьте лимит в 500 метров, на водные преграды пока наплюйте — в процессе эксплуатации вычистите). Соответственно, стоимость перемещения складывается из суммы времени и денег, помноженных на константы. Константы подберите сами, первое время можете деньги вообще не учитывать. Таким образом получите первоначальную карту путей. Она вам в будущем очень понадобится. Далее. Строим новый, на этот раз полный граф. То есть, необходимо обсчитать стоимость перемещения от каждой точки до каждой. Используем для этого тот же алгоритм Дейкстры. Получаем полный граф возможных перемещений. Этот граф у нас обычно лежит в файлике и мы его только считываем.

Answer 3

[kekekeks]

После чего для каждую точку назначения привязываем к 3 ближайшим станциям. И ищем кратчайшие пути от каждой точки до каджой + до пункта отправки. И уже на основании этих данных можно рисовать полный перебор возможностей. Как-то вот так.

Answer 4

[MiniM]

Ещё нужно определиться с весовой функцие время-деньги — в любом случае по двум критериям оптимизация не делается и тут есть два пути:
1) ставить один из критериев в ограничение, например не дольше чем за день доставиться все посылки
2) ввести весовую функцию, но тут необходимо отнормировать время и деньги, например время к количеству часов в рабочем дне, а стоимость к максимальному бюджету курьера.

Answer 5

[eternals]

Перебором, конечно. И как написали выше, с применением «динамического программирования», т.е. запоминать и использовать уже рассчитанные варианты и подварианты.

В реальной жизни такие задачи стараются решать зональным способом. А для Москвы и, наверное, Питера в виде секторов вокруг веток метро. Чтобы в секторе было удобно перемещаться. Сектора могут немного накладываться друг на друга. Затем для леммингов подбираете маршрут исходя из предпочтения находиться в одном секторе или максимум смежных. Ну и количество точек учитываете. Можно далее учесть и их отдалённость и последовательность обхода задать.

Просто решать перебором на полной карте — это строить ветки метро, наземного транспорта, учитывать водные преграды, сраные железнодорожные пути, пробки, стоимость проезда сложнее высчитать. В итоге вы одного курьера на 50% будете использовать, а другого на 150%.