В последнее время говоря о маршрутизации чаще всего имеют в виду задачу развозки и в большинстве случаев внутригородской развозки. Решение этой задачи представлено в ОТМ рядом оптимизационных алгоритмов, в результате работы которых из массива заказов мы получаем массив идеальных рейсов с точки зрения их длительности, соблюдения временных ограничений, подбора подвижного состава и его загрузки. Рейсы могут содержать множественные погрузки и выгрузки, а также остановки с погрузкой и выгрузкой одновременно.
Но интрига в том, что рассказать я хочу не об этом, а совсем о другом типе маршрутизации. Речь пойдет о маршрутной или транспортной сети, которая позволяет с одной стороны жестко зафиксировать возможные направления перевозок, а с другой — предоставляет выбор оптимального варианта из нескольких допустимых в зависимости от текущих грузопотоков.
При городской развозке маршрутизация выполняется исходя из предположения, что в принципе ехать можно из любой точки в любую. Это предположение позволяет в том числе перебирать множество комбинаций в поиске оптимальной последовательности. Для построения решения, конечно, нужны все взаимные расстояния между всеми точками из заказов (матрица расстояний). Оценка расстояний в ОТМ возможна как на основе географических координат по прямой, так и по дорогам на основе внешней картографической информации. Последняя опция, кстати, стала доступна не так давно, но я лично успела удостовериться, что все работает, расстояния определяются и даже отображаются на карте по автодорогам. Так что нападки со стороны локальных систем о том, что «у вас в ОТМ нет дорог» мы теперь с полной уверенностью отметаем. Честно говоря мы и раньше не слишком страдали, поскольку возможность загрузить матрицу расстояний по дорогам в ОТМ была всегда, но теперь он еще и подтягивает ее динамически.
Вообще я всегда призывала трезво оценивать реальную пользу картографической информации: при очень продвинутой математике и даже возможности полного перебора для поиска решения (то что мы имеем в ОТМ) матрица расстояний вполне может быть построена и по координатам точек. Качество решения заведомо будет выше и точнее чем у многих других систем даже с учетом погрешности, которую внесут неточные расстояния. В конце концов исключительные ситуации вроде рек, мостов и переправ легко можно отразить в справочнике расстояний, а остальное и так будет прекрасно работать.
Надеюсь внимательного читателя запутать не удалось — возвращаемся к транспортной задаче в сетевой постановке. Отличие, на которое я хочу обратить внимание, состоит в том, что в случае транспортной сети ехать прямиком из любой точки в любую нельзя. Иногда из одной точки в другую можно проехать только через одну или несколько промежуточных точек, где будет производиться консолидация или деконсолидация грузов. При чем таких вариантов проезда через промежуточные точки может быть несколько. Некоторые точки вообще могут оказаться не связанными друг с другом — это означает запрет перевозок между ними.
Главная прелесть в том, что сеть любой сложности можно задать очень просто — описав возможные направления перевозок. Направления соединяют регионы отгрузки и доставки с точками перегрузки. Типов таких направлений всего три:
- От региона отгрузки до первой точки перегрузки (консолидации);
- Между точками перегрузки (таких отрезков на маршруте может быть несколько);
- От точки перегрузки (распределительный центр) до региона доставки.
Подчеркну, что при этом нет необходимости описывать все возможные вариации конкретных маршрутов по транспортной сети. В случае сложной сети этих вариаций может быть очень много. При поиске решения для определенного массива заказов ОТМ динамически выстроит маршрут из доступных участков по критерию кратчайшего пути/минимальной стоимости. Кроме поиска кратчайшего пути основной способ оптимизации здесь — использование возможностей консолидации на промежуточных точках.
Предлагаю рассмотреть как работает эта функциональность на простом примере. Пример будет про такие близкие моему сердцу города Западной Сибири: Томск и Барнаул — это точки отгрузки, Ленинск-Кузнецкий — это точка доставки, Новосибирск и Кемерово — это промежуточные точки консолидации и перегрузки. При чем из Томска потенциально попасть в Ленинск-Кузнецкий можно через Новосибирск и Кемерово, а из Барнаула — только через Новосибирск. Соответствующую сеть задаем описанными отрезками.
Дальше в ОТМ был проведен следующий эксперимент:
- Создаем два заказа: 1 Томск — Ленинск-Кузнецкий; 2 Барнаул — Ленинск-Кузнецкий;
- Планируем отдельно заказ 1 Томск — Ленинск-Кузнецкий — ОТМ выбирает кратчайший путь через Кемерово, хотя вариантов было два, но ехать через Новосибирск дальше;
- Планируем отдельно заказ 2 Барнаул — Ленинск-Кузнецкий — ОТМ выбирает единственный доступный путь через Новосибирск;
- Планируем совместно заказы 1 и 2 — ОТМ находит возможность консолидации грузов в Новосибирске и поэтому направляет заказ 1 туда, несмотря на то, что это дальше чем Кемерово, но в целом получается значительный выигрыш по стоимости, так как в этом варианте перевозку удается выполнить тремя машинами вместо четырех.
Теперь этапы эксперимента в картинках:
Возвращаясь к задаче городской развозки (не зря же о ней было так много сказано в начале) отмечу, что она отлично сочетается с маршрутизацией по сети. Например, когда нужно собрать груз по региону отгрузки или развести из кросс-дока по региону доставки одной машиной. То есть оптимизация развозки будет работать на первом и/или на последнем плече сетевого маршрута.
Надеюсь удалось убедить, что перевозки на перекладных при должном уровне планирования — это не только не сложно, но и очень выгодно.