Общая архитектура механизма оптимизации

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

Этот механизм оптимизации, изображенный на рисунке 3.8, состоит из двух типов алгоритмов: алгоритмов, связанных с определением маршрутов (алгоритмы 1 и 3), и алгоритмов, связанных с планированием маршрута (алгоритмы 2 и 4). Алгоритмы 1 и 3 используются, когда поступает новый транспортный заказ, для того, чтобы сразу оценить влияние этого дополнения. Алгоритмы 2 и 4 используются, когда определяется новый план деятельности автопарка.

Механизм оптимизации

Рисунок 3.8. Механизм оптимизации

Расчет маршрута и оценка длины

Задача вычисления маршрутов в сети является классическим предметом исследований операционных задач, для которых было предложено несколько алгоритмов. Основная трудность заключается в количестве имеющихся данных. Географическая база данных французской дорожной сети приводит к ориентированному графу более 6 миллионов узлов и 15 миллионов дуг, соединяющих их. Таким образом, классическая реализация алгоритма кратчайшего пути, например алгоритма Дейкстры, приводит к огромному количеству вычислений, несовместимых со средой реального времени, в которой должен развиваться механизм оптимизации. Например, для вычисления кратчайшего пути между Байонне и Тулузе (273 км) требуется более 1000 секунд на Pentium IV 1,2 ГГц. Отметим, что этот путь был получен без учета ограничений вместимости. Поэтому мы пришли к необходимости разработки процедуры для оценки длины маршрута (Алгоритм 3) и изменению алгоритма Дейкстры таким образом, чтобы сделать его более эффективным с точки зрения вычислительного времени (Алгоритм 1).

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

Для вычисления маршрута (Алгоритм 1) мы изменили алгоритм Дейкстры путем вовлечения оценки оставшейся длины и получения двойного поиска: от начальной точки до конечной, а также от конечной до начальной. Кроме того, в поиске мы сосредоточились на использовании главных осей. Наконец, мы разложили сети на составные части, выделив основную сеть дорог и вторичную сеть. Эти различные модификации трансформировали точный алгоритм в эвристический подход. Тем не менее это привело к нахождению высококачественных путей за очень короткое время вычислений. Так, например, для Тулузы— Байонны мы получили путь в 296 км за 0,3 секунды.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >