| MaximuS_G |
|---|
| Могли бы Вы уточнить что означает распределение источников по приемникам (оптимизация распределения) и оптимизация маршрута? |
Транспортная задача решает задачу оптимального
распределения источников по приемникам. Имеется N возможных источников груза и M возможных приемников груза. Но при этом каждый маршрут от источника к приемнику является "однозвенным", то есть предполагается, что транспорт движется из одного источника в один приемник и не предполагается использовать идеологию "молоковоза", когда один транспорт должен объехать несколько пунктов по очереди.
Для отдельно взятого "молоковоза",
если перечень пунктов, которые он должен объехать, уже за ним закреплен (то есть, если задача распределения пунктов по транспортам уже решена каким-либо способом) задача построения оптимальной последовательности объезда этих пунктов решается с помощью
задачи коммивояжера.
Однако, задача оптимизации распределения пунктов по транспорту (в моем случае это были адреса заказчиков, которые нужно было распределить по линейным радиомеханикам) одновременно с задачей оптимизации маршрута отдельного транспорта (в моем случае оптимизации маршрута движания каждого отдельно взятого радиомеханика) при построении последовательности прохождения нескольких пунктов - такая задача "классического" решения не имеет, по крайней мере, я, когда его искал, мне его найти не удалось.
Мне пришлось изучить примерно дюжину методов решения задачи коммивояжера при нахождении решения, близкого к оптимальному. Я решал одновременно несколько оптимизационных задач одновременно, и если бы они решались методом "тупого перебора вариантов", время их решения. заняло бы несколько суток. А решение, может быть принят заказ на данный час в данном районе и если может, то за каким конкретно радиомехаником его нужно закрепить, нужно было принимать буквально "на лету" (пока клиент висит на телефоне). При этом нужно было попутно соблюсти совокупность специфических ограничений. В частности, если это повторный заказ, то он должен быть жестко закреплен за тем же радиомехаником, который его обслуживал в прошлый раз. И еще, по возможности каждый радиомеханик должен обслуживать примерно свой район города, чтобы в случае повторных заказов или не-повторных заказов, но от одних и тех же клиентов на них по возможности выходил один и тот же специалист, который уже знаком с проблемами конкретного аппарата. При этом, однако, если в двух соседних районах сложилась такая ситуация, что в одном районе заказов очень мало, а в другом их перебор, нужно привлечь радиомеханика соседнего района на обслуживание заказов соседнего района ближе к границе со своим районом.
У Дейкстры я нашел специфический алгоритм незамкнутого решения задачи коммивояжера, который в своей работе помимо использования метода ветвей и границ разделял точки, которые необходимо объехать/обойти на "окончательно включенные" в конкретный граф, "временно включенные" и "пока еще не включенные". Именно эта особенность и позволила решать весь комплекс оптимизационных задач одновременно. Для того, чтобы привязать траекторию движения конкретного радиомеханика к конкретному району города, я изначально включал точку в центре района, закрепленного за радиомеханиками, в граф каждого радиомеханика в качестве "виртуальной исходной точки" и "виртуальной конечной точки" для каждой полосы времени длительностью в 2 часа в середине рабочего дня. Для полосы времени в начале рабочего дня в качестве "исходной точки" (не виртуальной) обозначалась сама диспетчерская, в которой линейные радиомеханики каждое утро получали наряды, а в качестве "виртуальной конечной точки" - центр района каждого радиомеханика. Для последних 2 часов "виртуальной исходной точкой" обозначался центр района, а конечной точкой (не виртуальной) - место проживания радиомеханика. Таким образом, на протяжении рабочего дня заказы распределялись таким образом, что радиомеханики обслуживали их по утрам "по дороге из диспетчерской в свой район", к концу рабочего дня "по дороге из своего района домой", а в середине рабочего дня перемещаясь "вокруг центра своего района".
Далее в граф каждого радиомеханика включаются точки, требующие обязательного присутсвия на данном заказе данного радиомеханика (например, связанные с повторным ремонтом бытовой радиоаппаратуры), которые помечались как "окончательно включенные в граф". Далее каждый из пока еще не включенных заказов пытался включиться по очереди в ребра всех уже имеющихся графов таким образом, чтобы среднее время на перемещение всех радиомехаников было наименьшим (с учетом средней скорости перемещения разных радиомехаников, часть из которых перемещалась на автомобилях, а часть передвигались пешком). При этом должно было не нарушиться граничное условие - с запланированного времени на ремонт время движения по всему графу не должно превысить двух часов (ширины временной полосы, в которой работает оптимизационный алгоритм). Включение точки в ребро графа происходит очень просто - направленный отрезок от точки A к точке B разрывается и между ними включается точка C, после чего оценивается среднее время по всем графам. Для поиска локального оптимума каждая точка по очереди ключаяется во все ребра всех графов. После того как определен граф и ребро графа, включение в который конкретной точки наиболее оптимально, точка закрепляется за этим графом (она остается "временно включенной" в данный граф). Далее происходит включение следующей пока еще не включенной точки в ребра графов - опять же исходя из этих же оптимизационных критериев и ограничений на время движения по каждому графу не более 2 часов. Каждая включенная точка получает статус "временно включенной". Если включение какой-либо в какой-либо граф наиболее оптимально с точки зрения минимизации среднего времени перемещения по графам, но приводит к нарушению граничного условия (по двум часам перемещения по данному графу), то такая точка временно фиксируется в данном графе, а все ранее "временно включенные" точки по очереди исключаются из него до тех пор, пока не будет выявлена точка, которую наиболее оптимально исключить из данного графа, чтобы не нарушились граничные условия. В итоге исключена из данного графа может быть как текущая точка, так и та, которая ранее в него была включена.
Если после пробегания исключаемой точкой по всему набору графов выясняется, что такая точка не может быть включена ни в один из графов без нарушения граничных условий, алгоритм генерит ошибку, которая сигнализирует о факте "переполнения" данной временной полосы. Диспетчер, который в этот момент пытался включить некий заказ в эту полосу (шириной в 2 часа), получив сообщение об ошибке, сообщал клиенту, что на данный диапазон времени все диспетчеры заняты и предлагал выбрать другой.
После отработки оптимизационного алгоритма из маршрутов исключались начальные и конечные "виртуальные точки". Оценка граничных условий происходила, разумеется, без отрезков, концами которых являлись "виртуальные точки".
Ну вот, описал алгоритм во всех подробностях. Может быть, кому-нибудь пригодится... :) К слову сказать, для его корректной работы пришлось получать допуск у КГБ-шников к детальной карте города Таллинна (22 листа формата А0) и вколачивать эту карту в базу данных. :) Сейчас подобные задачи решают GPS-навигаторы на полном автомате, причем учитывают дорожные знаки.
| MaximuS_G |
|---|
| То-есть насколько я понял, лучше не разрабатывать этот механизм, а предоставить возможность менеджеру самостоятельно сформировать маршрут на основании опыта? И внести в систему все затраты по маршруту вручную? |
Затрудняюсь ответить. Не знаю, что лучше, каждый решает сам. Тут, видимо, нужно смотреть, какой опыт у этих самых менеджеров. Если я еду по незнакомой местности, то, скорее всего, GPS-навигатор предложит более оптимальный маршрут, нежели я высосу из пальца. А вот ежели я уже хорошо знаю дорогу, все нюансы и нюансики, то GPS-навигатор очень часто выдает менее оптимальное решение. Ему, например, может быть невдомек, что поворот налево на нерегулируемом перекрестке с плотным движением может сильно задержать из-за того, что нужно пропускать транспорт в обе стороны и лучше проехать чуть более длинным путем, но без подобных задержек.
| MaximuS_G |
|---|
| PS. Как Ваш робот-пылесос? ) |
Фурычит, куда ж он денется... :)