Эвристические методы приближенного поиска оптимальной топологии маршрута (2007, 384с., MET0033-15)

Существует несколько эвристических методов приближенного поиска оптимальной топологии маршрута.

1. Метод ближайшего соседа (Nearest Neighbor). Пункты обхода плана последовательно включаются в маршрут, причем каждый следующий должен быть ближайшим к предыдущему.

2. Метод ближайшего города (Nearest Town). На каждом шаге алгоритма к текущему множеству пунктов, уже входящих в маршрут, добавляется новый, для которого найдется ближайший к любому из них, после чего полученный маршрут заново оптимизируется по выбранному критерию.

3. Метод самого дешевого включения (Most Cheap Inclusion). Алгоритм аналогичен предыдущему, только включение нового пункта производится по принципу минимального увеличения стоимости (длины) маршрута.

4. Метод минимального остовного дерева (Minimum Spanning Tree). Он представляет собой три последовательно выполняемых шага. На первом для множества пунктов плана строится кратчайшее остовное дерево (с помощью алгоритма Прима, заключающегося в построении каркаса наименьшего веса графа путем его наращивания за счет присоединения ребра с наименьшим весом, только один конец которого принадлежит фрагменту каркаса). На втором в построенном графе выделяется маршрут минимальной длины, который проходит через каждый пункт не менее 1 раза. На третьем из последовательности перемещения исключаются все пункты, повторно вошедшие в маршрут. Полученная топология является искомым приближением решения «задачи коммивояжера» и образует допустимый маршрут.

Эвристические методы перечислены в порядке повышения качества приближенного решения и, соответственно, увеличения вычислительной трудоемкости. Каждый из них обладает своими плюсами и минусами. Наилучшее решение для конкретных исходных данных может быть найдено в результате последовательного применения, а затем выбора того варианта, который отвечает вашим требованиям. В качестве критерия оптимальности могут быть выбраны пробег, время на маршруте, грузооборот, количество задействованного транспорта (либо их комбинация). В системах планирования подбор оптимального метода чаще всего происходит без участия оператора, который может регулировать данный процесс, лишь оценивая результаты планирования и изменяя критерии оптимальности. Программные продукты данного класса имеют разные интерфейсы, но принципы их функционирования приблизительно одинаковы. В отделе планирования должен быть как минимум один сотрудник, квалификация которого достаточна для работы с электронными справочниками и определения коэффициентов расчетной скорости движения автотранспорта в зависимости от погодных условий (на его рабочем месте можно повесить таблицу с утвержденным перечнем вариантов «погода/коэффициент»). В соответствии с заранее определенной периодичностью менеджер запускает процесс планирования и выводит на печать готовые маршрутные листы. Преимущества данного метода заключаются в сокращении времени планирования рейсов (на 1000 заявок в среднем затрачивается 10 минут) и формировании оптимального маршрута с использованием множества параметров, которые сложно учесть при расчете вручную. Благодаря использованию описываемого метода снижаются расходы на обслуживание автопарка (экономия пробега/расхода бензина в среднем достигает 22,5 %), сокращается штат планировщиков, повышается эффективность использования автотранспорта (сокращение парка в отдельных случаях достигает 15 %).

Источник: Беспалов Р. С. Транспортная логистика. Новейшие технологии построения эффективной системы доставки. — Москва : Вершина, 2007. – С. 285-286 (384 с.)