Сабж.

В общих чертах — раздача заказов водителям такси с целью минимизировать время ожидания, холостые пробеги итп.. Количество вариантов до 50 на 50 в пиках, но рабочая нагрузка поменьше. Работает все это в реальном времени, то есть скажем секунды две на расчет — это допустимо, а 10 — уже нет.

В принципе требуется экспертная система, которая бы давала рекомендации человеку как поступить в той или иной ситуации.

Сейчас реализован частичный перебор вариантов, но он работает не совсем так как хочется и есть ряд условий, которые он учесть в принципе не может (например, нельзя точно предсказать время, за которое водитель доедет по нужному адресу). Кроме того, из-за того что перебор частичный он очень часто находит совершенно неоптимальное решение (если бы перебор был полный, то было бы лучше, но количество вариантов при полном переборе растет по факториалу и при хоть сколько-то значительной нагрузке алгоритм умирает)

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

Как решаются подобные задачи и решаются ли они вообще?




ЗЫ. Если у кого-то есть опыт в подобных делах и желание помочь (естественно не бесплатно), пишите на мне на мыло.

Здравствуйте, Sshur, Вы писали:

S>Сабж.

S>В общих чертах — раздача заказов водителям такси с целью минимизировать время ожидания, холостые пробеги итп.. Количество вариантов до 50 на 50 в пиках, но рабочая нагрузка поменьше. Работает все это в реальном времени, то есть скажем секунды две на расчет — это допустимо, а 10 — уже нет.

...

S>Как решаются подобные задачи и решаются ли они вообще?

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

Здравствуйте, Bell, Вы писали:


B>Вообще-то маловато данных для более-менее полного ответа. Может быть, тут подойдет здача о назначениях (в этом случае нужно просто определиться с понятием стоимости выполнения заказа), а может быть подойдет что-то из арсенала решения VRP...


Какие еще нужны данные? Могу написать более подробно, просто не знаю, что важно, а что нет.


Буду писать в терминах предметной области:


Есть некоторое количество водителей на линии. Они могут находится в состоянии свободен либо на заказе. Для свободного водителя есть место его нахождения. Для водителя на заказе есть статус заказа (начался/не начался) и место освобождения (если есть).
Есть некоторое количество неотданных заказов. Для каждого заказа есть его адрес, для некоторых заказов есть время когда надо начать его выполнение (предварительные заказы), их надо начать очень близко к заданному времени (но не позже). Остальные заказы необходимо начать как можно быстрее.
Необходимо составить такие пары водитель/заказ, чтобы минимизировать суммарный пробег водителей от точек их нахождения до адресов заказов и время ожидания заказчиков, то есть критериев несколько, но в принципе можно выработать один интегральный. При этом заказы отдаются не только свободным, но также и едущим по заказам водителям, вероятность освобождения которых недалеко от нового заказа в ближайшее время велика (если все свободные находятся далеко или их нет).

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

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

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

Вот в общих чертах что требуется.

Здравствуйте, Sshur, Вы писали:

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

Здравствуйте, Sshur, Вы писали:

S>Здравствуйте, Bell, Вы писали:


B>>Вообще-то маловато данных для более-менее полного ответа. Может быть, тут подойдет здача о назначениях (в этом случае нужно просто определиться с понятием стоимости выполнения заказа), а может быть подойдет что-то из арсенала решения VRP...


S>Какие еще нужны данные? Могу написать более подробно, просто не знаю, что важно, а что нет.


S>Буду писать в терминах предметной области:


S>Есть некоторое количество водителей на линии. Они могут находится в состоянии свободен либо на заказе. Для свободного водителя есть место его нахождения. Для водителя на заказе есть статус заказа (начался/не начался) и место освобождения (если есть).
S>Есть некоторое количество неотданных заказов. Для каждого заказа есть его адрес, для некоторых заказов есть время когда надо начать его выполнение (предварительные заказы), их надо начать очень близко к заданному времени (но не позже). Остальные заказы необходимо начать как можно быстрее.
S>Необходимо составить такие пары водитель/заказ, чтобы минимизировать суммарный пробег водителей от точек их нахождения до адресов заказов и время ожидания заказчиков, то есть критериев несколько, но в принципе можно выработать один интегральный. При этом заказы отдаются не только свободным, но также и едущим по заказам водителям, вероятность освобождения которых недалеко от нового заказа в ближайшее время велика (если все свободные находятся далеко или их нет).

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

S>Основная неопределенность здесь именно в предсказании вероятности освобождения водителя в нужной точке, так как ситуации бывают разные (либо заказчик передумал, либо водитель недобросовестный, либо пробки на дорогах).

S>Плюс исходя из скачкообразной нагрузки наиболее характерны две ситуации: когда свободных водителей гораздо больше чем заказов (тут прекрасно работает и перебор) и когда заказов гораздо больше чем водителей (тут начинает очень большую роль играть предсказание).

S>Вот в общих чертах что требуется.


согласен с Bell, VRP тут не нужен, надо решать задачу о назначении
сам алгоритм имеет кубовую сложность, за секунду решит даже 1000 и больше таксистов
для свободных таксистов есть расстояние до пунктов
у пунктов — время начала
для времени начала для таксистов несвободных, но имеющих вероятность освобождения можно внести коэффециент на расстояние, который зависил бы от времени до освобождения, и вообще экспертно по статистике своевременности освобождения водителя
ну и желательно чтобы на лету постоянно перерасчет шел, когда поступает новый заказ, освобождается таксист или назначен и поехал (почти доехал, приехал — насколько серьезно отменять таксиста если кто ближе есть), для 50 таксистов и 50 пунктов это незаметно

Здравствуйте, ilnar, Вы писали:


I>согласен с Bell, VRP тут не нужен, надо решать задачу о назначении
I>сам алгоритм имеет кубовую сложность, за секунду решит даже 1000 и больше таксистов
I>для свободных таксистов есть расстояние до пунктов
I>у пунктов — время начала
I>для времени начала для таксистов несвободных, но имеющих вероятность освобождения можно внести коэффециент на расстояние, который зависил бы от времени до освобождения, и вообще экспертно по статистике своевременности освобождения водителя
I>ну и желательно чтобы на лету постоянно перерасчет шел, когда поступает новый заказ, освобождается таксист или назначен и поехал (почти доехал, приехал — насколько серьезно отменять таксиста если кто ближе есть), для 50 таксистов и 50 пунктов это незаметно


В принципе так все и делается, только задача решалась методом перебора Буду теперь использовать венгерский метод.