|
ViPRos,
Ты всё верно говоришь. В той задаче, которую решал я, тоже были похожие ограничения. Но я выкрутился. Выбрал один из способов решения задачи коммивояжера, который находит решение, близкое к оптимальному, который мне удалось приспособить для решения задач множества коммивояжеров и попутно решить совокупность еще и других задач, которые требовали решения.
Вкратце опишу постановку задачи. Утром в начале каждого дня все линейные радиомеханики приходили в диспетчерскую, где получали наряд и маршрутную карту с указанием заявленного времени прихода радиомеханика и краткого описания неисправности (модели телевизора и характерных признаков неисправности и плановое время ремонта). Старый способ распределения заказов предполагал закрепление за каждым радиомехаником определенного района города с фиксированными границами. В таком подходе были плюсы и минусы. Плюсом являлся тот факт, что при повторном вызове на один и тот же адрес приходил один и тот же радиомеханик, и если он по каким-либо причинам что-то плохо сделал в прошлый раз, то доделывать ему приходилось самому, а не кому-либо другому. Минусом был тот факт, что случайный характер флуктуаций заказов зачастую приводил к большому количеству заказов в одном районе, и почти полному отсутствию их в другом, в результате один радиомеханик буквально "разрывался на части", а в соседнем районе при этом прохлаждался его коллега, который сидел и "плевал в потолок". Стояла задача оставить систему закрепления линейных радиомехаников за определенными районами города, но при этом сделать границы между районами более "размытыми", чтобы радиомеханики из соседних районов могли бы приходить на выручку к своим коллегам, обслуживая заказы на границе своего района, чтобы сделать нагрузку на линейных радиомехаников более равномерной. Требовалось также учесть, что часть радиомехаников ходят пешком (либо пользуются общественным транспортом), а часть ездят на автомобилях. Требовалось учесть предварительную оценку сложности ремонта для примерной оценки планового времени пребывания радиомеханика на заказе, а также время его передвижения в пути таким образом, чтобы он успевал обслужить заказы в озвученном клиенту временном интервале. Клиенту озвучивался интервал прихода радиомеханика продолжительностью 1 час, и требовалось с максимально возможной точностью обеспечить приход радиомеханика именно в пределах озвученного часа. М еще один нюанс - при повторных вызовах обслуживать заказ должен именно тот радиомеханик, который его обслуживал ранее. При этом требовалось учесть доступность конкретного радиомеханика в случае его выхода в отпуск, больничного и т.п. После обслуживания последнего заказа радиомеханики обычно ехали по домам, и привозили заполненные документы по обслуженным за прошлый день заказам в диспетчерскую на следующее утро. Кроме того, требовалось учесть различную квалификацию разных радиомехаников, поскольку радиомеханики разной квалификации находили и устраняли неисправность за существенно разное время.
И, самый главный нюанс, который создавал самую большую сложность... Требовалось определить возможность приема заказа на заданную дату и часовой диапазон времени "на лету", пока клиент говорит с диспетчером по телефону. При этом требовалось оценить возможность включения поступившего заказа в различные даты и в различные временные интервалы таким образом, чтобы ранее принятые заказы остались выполнимыми, чтобы наиболее оптимально решалась задача распределения заказов между радиомеханиками, и чтобы перемещения каждого радиомеханика также были наиболее оптимальными.
Так вот, собственно, алгоритм... За основу я взял способ решения задачи одного коммивояжера, о котором прочитал в книжке по комбинаторике, и который находил решение, близкое к оптимальному, "скрестив" его с методом ветвей и границ и привнеся с него свои "фичи". Для каждого радиомеханика задавалась его средняя скорость перемещения (в зависимости от того, пеший он или на автомобиле) и начальное значение уровня квалификации, которым определялся поправочный коэффициент к среднему времени ремонта, определенному диспетчером исходя из первичных признаков неисправности без учета квалификации радиомеханика. Изначально на каждый рабочий день задавалась траектория движения каждого радиомеханика в виде направленного отрезка, который начинался в диспетчерской и заканчивался в условном центре района. Постепенно, по мере включения в траектории новых заказов, траектории превращались в ломанные. При поступлении нового заказа, прежде всего, вычислялись расстояния от поступающего нового заказа С до всех уже имеющихся в системе отрезков ломанных. Если перпендикуляр от заказа С мог пересечь направленный отрезок [AB) между точками A и B, то расстояние определялось по формуле расстояния от точки до прямой (AB), в противном случае он определяется как расстояние до ближайшей из точек A либо B. Далее находится отрезок, до которого наименьшее расстояние, и производится попытка включения нового заказа в данный отрезок с его "разрывом". Включение заказа C в отрезок [AB) производится заменой отрезка [AB) двумя отрезками [AC) и [CB). Далее отрабатывает метод ветвей и границ, который проверят допустимость такого включения - если включенный заказ не привел к выходу за пределы часовых интервалов ранее принятых заказов, он фиксируется в данной траектории, в противном случае включение в данную траекторию отвергается и выбирается следующий по близости к точке C отрезок из всей совокупности траекторий радиомехаников (то есть, в процессе перебора отрезков они могут выбираться из траекторий разных радиомехаников). Если не находится ни одна траектория ни одного радиомеханика в желаемое клиентом время и дату, заказ отвергается и предлагается другое время и дата. Подобный расчет делается для различных дат и часовых интервалов, для них определяется степень оптимальности всех допустимых часовых зон, и на экране диспетчера допустимые для клиента зоны ранжируются по степени оптимальности (определяется по минимальному времени холостых "простоев"). Это ранжирование, как правило, выводит в первую очередь, ближайшие даты и время (наиболее "плотные" траектории), если включение в них нового заказа всё еще возможно.
Далее клиент выбирает ту дату и время, которое его устраивает, и заказ фиксируется в системе в конкретном маршруте коммивояжера.
"Расстояние" между точками определяется не в метрах или километрах, а в минутах и секундах, требуемых, во-первых, для выполнения планового времени ремонта (с учетом сложности ремонта и с учетом квалификации) и с учетом времени, требуемого на перемещение (с учетом разной средней скорости перемещения радиомехаников). Фактические данные по произведенным ремонтам - время прибытия и время выполнения ремонта - фиксируются в системе. И в дальнейшем используются для автоматической корректировки средней скорости перемещения и коэффициента квалификации.
В процессе выстраивания траектории каждого радиомеханика его траектория движения на протяжении рабочего дня представляет ломанную, которая начинается в диспетчерской и заканчивается в условном геометрическом центре обслуживаемого им района. Этот самый центр является "виртуальным заказом", который изначально включается в маршрут каждого радиомеханика. Он учитывается при выборе отрезка, но не учитывается на фазе отработки метода ветвей и границ. Таким образом, система на самом деле не принуждает линейного радиомеханика на самом деле посещать эту точку, но выбирает заказы таким образом, что они располагаются преимущественно на траектории между диспетчерской и обслуживаемым им районом.
В принципе, если требуется включить дополнительные компоненты, учитывающие какие-либо иные факторы, в этот алгоритм их можно включить тоже. Потому что "расстояние" от A до B может состоять из многих компонентов, а не из двух. В моем алгоритме "расстояние" определялось во времени, требуемом для двух фаз - ремонта и перемещения. Но в общем случае может большее количество фаз и большее количество факторов, которые отрабатывают, как минимум, на уровне метода ветвей и границ.
Вот, вкратце, суть алгоритма. Имеется тысяча нюансов и деталей, которые каждый может додумать самостоятельно. Надеюсь, описал понятно...
|
