Авторы: Костюк Ю. Л., Пожидаев М. С.
"Вестник ТГУ" (УВТиИ), 2010, №3.
Предлагается эвристический алгоритм приближённого решения задачи маршрутизации транспорта с учетом грузоподъемности экипажей и потребностями в товаре вершин-клиентов для случая метрических расстояний. Алгоритм состоит из двух фаз: кластеризации вершин на группы и фазы вычисления маршрутов отдельно по группам. Порядок трудоемкости первой фазы около O(n2), а второй фазы при использовании алгоритма Лина-Кернигана — не выше O(n3). Проведенный вычислительный эксперимент показал, что предложенный алгоритм почти не уступает алгоритму Османа по качеству получаемого решения при уменьшении времени работы в десятки раз. Еще лучшее по качеству решение получается при комбинированном применении этих двух алгоритмов.
Ключевые слова: дискретная оптимизация, приближённые алгоритмы, задача коммивояжера (\tsp), задача маршрутизации транспорта (\vrp), кластеризация.
Задача маршрутизации транспорта (ЗМТ) (Vehicle Routing Problem, VRP) — одно из обобщений задачи коммивояжёра (ЗК) (Traveling Salesman Problem, TSP). Она предусматривает построение нескольких замкнутых маршрутов, проходящих через общую вершину — депо, при минимизации суммарной стоимости маршрутов. При одинаковой размерности эта задача гораздо сложнее, чем ЗК, которая, в свою очередь, является NP-трудной. Поэтому в практических приложениях, где число вершин достигает 100 и более, возможно применение лишь приближённых алгоритмов.
Известно несколько вариантов ЗМТ, различающихся дополнительными параметрами входных данных и ограничениями на получаемое решение. В самом простом случае кроме матрицы расстояний между всеми парами вершин задается также либо количество маршрутов, либо максимальное количество вершин, которые могут входить в любой из маршрутов. Авторами был ранее предложен ряд алгоритмов решения этого простого варианта ЗМТ для случая метрических расстояний. В настоящей статье рассматривается более сложный вариант ЗМТ, когда для каждой из вершин-клиентов задается величина потребности в товаре и задается максимальная грузоподъёмность экипажа – транспортного средства, развозящего товар из вершины-депо по вершинам-клиентам маршрута. Количество маршрутов (задействованных экипажей) определяется в процессе вычислений.
В последние годы при создании алгоритмов решения задач дискретной оптимизации, в том числе и ЗМТ, используются такие метаэвристические стратегии, как детерминированный и моделируемый отжиг, поиск с исключениями, генетические алгоритмы, алгоритмы муравьиных колоний, нейронные сети и др. Полученные с помощью этих стратегий алгоритмы в некоторых случаях дают хорошие результаты, но обычно требуют подбора большого количества управляющих параметров, зависящих как от вида задачи, так и от конкретного набора входных данных, что существенно усложняет и ограничивает их практическое применение. Один из лучших по качеству алгоритмов решения ЗМТ, основанный на поиске с исключениями, алгоритм Османа, также имеет управляющий параметр — длину списка исключений, но диапазон изменений этого параметра и его наиболее вероятная величина вычисляется на основе входных данных, что является существенным преимуществом. Однако трудоемкость алгоритма растет очень быстро при увеличении размерности задачи, на обычном персональном компьютере его можно эффективно применять, если число вершин не превышает 200–300.
В статье рассматривается развитие лучшего из алгоритмов, ранее рассмотренных, — сбалансированного последовательного дихотомического разделения вершин на маршруты по критерию разности расстояний — для ЗМТ с учетом грузоподъемности экипажей и потребности в товаре. Сравнение с алгоритмом Османа проводится с помощью вычислительного эксперимента.
(Полный текст статьи см. в PDF-файле)