The balanced heuristics for vehicle routing problem with capacity restriction for instances..pdf Задача маршрутизации транспорта (ЗМТ) (Vehicle Routing Problem, VRP) - од-но из обобщений задачи коммивояжёра (ЗК) (Traveling Salesman Problem, TSP). Она предусматривает построение нескольких замкнутых маршрутов, проходящих через общую вершину-депо, при минимизации суммарной стоимости маршрутов. При одинаковой размерности эта задача гораздо сложнее, чем ЗК, которая, в свою очередь, является NP-трудной. Поэтому в практических приложениях, где число вершин достигает 100 и более, возможно применение лишь приближённых алго-ритмов.Известно несколько вариантов ЗМТ, различающихся дополнительными пара-метрами входных данных и ограничениями на получаемое решение. В самом про-стом случае кроме матрицы расстояний между всеми парами вершин задается также либо количество маршрутов, либо максимальное количество вершин, кото-рые могут входить в любой из маршрутов. Авторами в работе [1] предложен ряд алгоритмов решения этого простого варианта ЗМТ для случая метрических рас-стояний. В настоящей статье рассматривается более сложный вариант ЗМТ, когда для каждой из вершин-клиентов задается величина потребности в товаре и задает-ся максимальная грузоподъёмность экипажа - транспортного средства, развозя-щего товар из вершины-депо по вершинам-клиентам маршрута. Количество мар-шрутов (задействованных экипажей) определяется в процессе вычислений.В последние годы при создании алгоритмов решения задач дискретной опти-мизации, в том числе и ЗМТ, используются такие метаэвристические стратегии, как детерминированный и моделируемый отжиг, поиск с исключениями, генети-ческие алгоритмы, алгоритмы муравьиных колоний, нейронные сети и др. Полу-ченные с помощью этих стратегий алгоритмы в некоторых случаях дают хорошие результаты, но обычно требуют подбора большого количества управляющих па-раметров, зависящих как от вида задачи, так и от конкретного набора входных66Ю.Л. Костюк, М.С. Пожидаевданных, что существенно усложняет и ограничивает их практическое применение. Один из лучших по качеству алгоритмов решения ЗМТ, основанный на поиске с исключениями, алгоритм Османа [2], также имеет управляющий параметр - дли-ну списка исключений, но диапазон изменений этого параметра и его наиболее вероятная величина вычисляется на основе входных данных, что является суще-ственным преимуществом. Однако трудоемкость алгоритма растет очень быстро при увеличении размерности задачи, на обычном персональном компьютере его можно эффективно применять, если число вершин не превышает 200 - 300.В статье рассматривается развитие лучшего из алгоритмов, рассмотренных в [1], - сбалансированного последовательного дихотомического разделения вершин на маршруты по критерию разности расстояний - для ЗМТ с учетом грузоподъем-ности экипажей и потребности в товаре. Сравнение с алгоритмом Османа прово-дится с помощью вычислительного эксперимента.1. Сбалансированный алгоритм кластеризацииПредлагаемый алгоритм содержит две фазы: вначале решается задача класте-ризации (разделение общего множества вершин на группы для каждого экипажа), затем выполняется построение конечных маршрутов путём решения традицион-ной ЗК. Ниже приведено подробное описание сбалансированной процедуры кла-стеризации; последующий способ решения ЗК может быть выбран произвольно среди известных методов. Алгоритм работает без заданного заранее числа экипа-жей, вычисляя его в ходе работы.Алгоритм содержит дополнительные условия, определяющие требование сба-лансированности. Такой подход позволяет уменьшить объём вычислений, но не-обходимо решить вопрос о его влиянии на качество получаемых результатов. Ос-новная сложность в реализации алгоритма связана с тем, что в его работе посто-янно учитываются две величины: стоимость маршрута и суммарная потребность в товаре вершин-клиентов, включенных в маршрут. Стремление к наилучшему рас-пределению загрузки экипажей может негативно сказываться на стоимости мар-шрута, и наоборот. Другая сложность заключается в том, что потребность в това-ре у клиентов может быть достаточно неравномерной, и существует риск, что до-бавление вершин на основе оценки стоимости решения в самый последний мо-мент нарушит ограничение грузоподъёмности.Рассмотрим описание алгоритма. Дано множество из n вершин V = {v1 ,…, vn}. Для каждой вершины vi, принадлежащей V, задана величина потребности в товаре Q(vi) > 0. Все экипажи имеют заданную заранее одинаковую грузоподъёмность q. Также задаётся особая вершина - депо v0, представляющая точку начала и конца всех построенных маршрутов. Для общности полагаем, что Q(v0) = 0. Для любой пары вершин i и j из {v0, v1,…, vn} определены расстояния (стоимость переезда) D(i¸ j) из i в j. Будем считать, что расстояния метрические, т.е. они симметричны и для них выполняется условие треугольника.Алгоритм строит множество R = {r1,…, rk} из k замкнутых маршрутов (k не за-дано), таких, что:1))вершина v0 принадлежит каждому из k маршрутов;2))каждая из вершин vi, принадлежащая множеству V, принадлежит одному и только одному из k маршрутов;3))для каждого из k маршрутов ri, которому принадлежат m(i) вершин {v0,vi ,vi ,…,vi }, должно выполняться следующее условие:1 2m(i)Сбалансированная эвристика для решения задачи маршрутизации транспорта67m(i)j Q(vi j ) 1. Процедура может возвратить в виде результата множество групп, меньшее, чем k, это допустимое поведение. Если процедура завершила свою работу аварийно, то увеличиваем значение k на единицу и повторяем попытку до тех пор, пока результат не будет получен.3..Вычисляем совокупность маршрутов, решая ЗК для вершин каждой из полученных групп. В вычислительном эксперименте использован один из лучших приближенных алгоритмов - алгоритм Лина - Кернигана [3].Оценим трудоемкость алгоритма. При работе процедуры divide каждый из шагов 2, 3, …, 7 имеет порядок трудоемкости не выше O(n2). С учетом рекурсивных вызовов на шаге 8 получаем рекуррентное соотношение для трудоемкости T(n) = T(n/2) + c · n2. Решив его, получаем величину общей трудоемкости O(n2). При выводе не было учтено, что выполнение процедуры divide может закончиться аварийно, и тогда все вычисления повторяются с самого начала. Если количество таких ситуаций не превысит константы, то трудоемкость будет иметь тот же порядок O(n2). Трудоемкость алгоритма Лина - Кернигана близка к O(n3), но так как70Ю.Л. Костюк, М.С. Пожидаевэтот алгоритм применяется по отдельности к каждой из k групп вершин, то общая трудоемкость на этой фазе алгоритма - O ( k · n 3/ k 3) = O( n 3/k2). Если с ростом n количество групп k растет пропорционально n, то трудоемкость 2-й фазы будет O(n), а если при росте n количество групп k остается константой, то трудоемкость -O ( n 3). Таким образом, порядок общей трудоемкости всего алгоритма будет между O ( n2) и O(n 3).3. Вычислительный экспериментКачество предложенного алгоритма оценивалось путём постановки вычислительного эксперимента. Одни и те же наборы входных данных подавались на вход алгоритма Османа, описанного в работе сбалансированного алгоритма, и комбинированного алгоритма, когда на первом этапе исполняется алгоритм Османа, а на втором - сбалансированный алгоритм. В алгоритме Османа параметру, определяющему количество обмениваемых между маршрутами вершин, задано значение 1. Как отмечено в [3], хотя большее значение этого параметра и позволяет несколько повысить качество решения, однако при этом существенно возрастает время выполнения алгоритма. В алгоритме Османа имеется другой важный целочисленный параметр: длина списка исключений. Его наиболее предпочтительное значение вычисляется по эмпирической формуле [3]4 = max{7; 9,6·ln (n·k) - 40},(2)где ts - значение параметра, n - общее количество вершин, k - текущее количество маршрутов.В первой части вычислительного эксперимента алгоритмы испытывались на задачах (наборах данных), предложенных Кристофидесом, Мингоззи и Тоссом [4], на которых испытывались также многие другие алгоритмы решения ЗМТ. Всех задач 14, из них выбраны те, которые соответствуют постановке ЗМТ с учетом грузоподъемности. Для получения более высокого качества получаемых решений алгоритм Османа выполнялся многократно с изменением параметра длины списка исключений в диапазоне от 7 до 2·ts и выбирался самый лучший из полученных результатов. Результаты вычислений, приведенные в табл. 1, содержат суммарные длины вычисленных алгоритмами маршрутов, количества получившихся при этом маршрутов (экипажей), а также общее затраченное время.Таблица 1Качество и время решения задач Кристофидеса, Мингоззи и Тосса№ задачи, число вершинКачество решения, получившееся число экипажей, время работы в секундах Алгоритм ОсманаСбалансированныйКомбинированный1 (50)537,6 (5 эк.), 9 с.559,7 (5 эк.), 0,07 с.558,2 (5 эк.), 6 с.2 (75)885,1 (11 эк.), 35 с.937,9 (11 эк.), 0,11 с.881,6 (11 эк.), 26 с.3 (100)867,2 (8 эк.), 161 с.1088,5 (8 эк.), 0,16 с.863,2 (8 эк.), 201 с.4 (150)1122,5 (12 эк.), 993 с.1171,9 (12 эк.), 0,41 с.1078,9 (12 эк.), 682 с.5 (199)1419,6 (17 эк.), 2749 с.1462,7 (17 эк.), 1,8 с.1379,4 (17 эк.), 3715 с11 (120)1223,7 (7 эк.), 227 с.1170,2 (7 эк.), 1,2 с.1059,2 (7 эк.), 203 с.12 (100)905,2 (10 эк.), 220 с.1066,2 (10 эк.), 0,6 с.841,4 (10 эк.), 167 с.Из табл. 1 видно, что сбалансированный алгоритм уступает алгоритму Османа по качеству решения на шести примерах из семи, но затрачивает на вычисления в сотни раз меньше времени. В то же время, если решение, полученное сбалансиро-Сбалансированная эвристика для решения задачи маршрутизации транспорта71ванным алгоритмом, использовать как начальное для алгоритма Османа, то во всех случаях достигается наилучшее качество.Во второй части вычислительного эксперимента алгоритмы испытывались на случайно сгенерированных наборах данных. Вершины в виде точек на плоскости размещались согласно равномерному распределению внутри единичного квадра-та, депо помещалось в центре. Матрица расстояний вычислялась в виде евклидо-вых расстояний между точками. Веса вершин (потребности в товаре) генерирова-лись согласно дискретному равномерному распределению в диапазоне от 1 до 10. Для наборов данных из 50 вершин алгоритмы запускались по 100 раз, для 100 вершин - 50 раз, для 150 вершин - 25 раз и для 200 вершин - 10 раз. Результаты вычислений, приведенные в табл. 2, содержат отношения суммарных длин полу-ченных маршрутов к их оценке снизу - сумме длин рёбер минимального остова на всех вершинах и длины самого длинного ребра остова. В табл. 2 приведены ми-нимальные, средние и максимальные величины этих отношений по всем выбор-кам, а также среднее время работы алгоритмов на одном наборе данных. При этом, в отличие от табл. 1, алгоритм Османа выполнялся только при одном значе-нии параметра длины списка исключений, вычисляемом по формуле (2).Таблица 2Качество и время решения на случайных выборкахЧисло вершин, грузоподъ- емностьКачество алгоритма: минимум, среднее значение, максимум; среднее время работы в секундах Алгоритм ОсманаСбалансированныйКомбинированный50 (50)1,60/1,83/2,17; 0,5 с.1,58/1,84/2,14; 0,04 с.1,46/1,73/2,10; 0,5 с.100 (50)1,97/2,19/2,52; 3,6 с.1,96/2,23/2,56; 0,2 с.1,87/2,10/ 2,33; 2,7 с.150 (50)2,16/2,43/2,68; 23 с.2,34/2,52/2,69; 0,5 с.2,17/2,37/2,53; 17 с.200 (50)2,53/2,73/2,86; 87 с.2,60/2,83/2,99; 0,9 с.2,48/2,66/2,79; 58 с.100 (100)1,53/1,73/1,99; 5,5 с.1,49/1,60/1,73; 0,3 с.1,40/1,51/1,67; 4,1 с150 (150)1,53/1,66/1,82; 33 с.1,42/1,52/1,63; 0,8 с.1,36/1,43/1,50; 19 с.200 (200)1,51/1,62/1,79; 144 с.1,37/1,45/1,52; 2,1 с.1,33/1,38/1,43; 59 с.Из табл. 2 видно, что на первых четырех выборках, когда количество вершин в каждом из полученных маршрутов было в среднем менее 10, сбалансированный алгоритм оказался хуже алгоритма Османа по качеству решения в среднем от 0,5 до 3 %, при времени работы в десятки раз меньшем. На последних трех выборках, когда количество вершин в каждом из полученных маршрутов росло с ростом общего числа вершин, картина обратная, при этом преимущество сбалансирован-ного алгоритма достигает более 10 % при n = 200. При этом сбалансированный алгоритм затрачивает на вычисления в десятки раз меньше времени. Применение же комбинации этих двух алгоритмов всегда дает выигрыш (в среднем) по срав-нению с алгоритмом Османа, который при n = 200 и грузоподъемности 200 дохо-дит до 15 % при заметном уменьшении времени вычислений.Для вынесения решения о том, какой из алгоритмов оказался лучшим на той или иной случайной выборке, в табл. 3 приведены результаты сравнения алго-ритмов между собой по качеству получаемых решений в таком виде, чтобы было можно применить знаковый статистический критерий.Применение критерия знаков к табл. 3 подтверждает преимущество сбаланси-рованного алгоритма над алгоритмом Османа для последних трех выборок и пре-имущество комбинированного алгоритма над алгоритмом Османа для всех семи72Ю.Л. Костюк, М.С. Пожидаеввыборок. Согласно статистическим таблицам [5, с. 354], это утверждение имеет вероятность ошибки менее 0,005.Таблица 3Сравнение алгоритмов по качеству получаемых решенийЧисло вершин, грузоподъ- емностьКоличество проигрышей алгоритма Османа из общего количества выборок Проигрыши сбалансированному алгоритмуПроигрыши комбинированному алгоритму50 (50)45 из 10089 из 100100 (50)17 из 5045 из 50150 (50)4 из 2523 из 25200 (50)2 из 1010 из 10100 (100)45 из 5050 из 50150 (150)24 из 2525 из 25200 (200)10 из 1010 из 10ЗаключениеПредложенный в статье сбалансированный алгоритм кластеризации путем многократного дихотомического разделения вершин в сочетании с алгоритмом Лина - Кернигана получает приближенное решение задачи маршрутизации транспорта с учетом грузоподъемности экипажей и потребностями в товаре вер-шин-клиентов. Как показал вычислительный эксперимент, качество его решения в некоторых ситуациях незначительно уступает одному из лучших алгоритмов - ал-горитму Османа, однако при увеличении количества вершин до 150 и более при пропорциональном увеличении вершин в отдельных маршрутах предложенный алгоритм начинает превосходить алгоритм Османа при одновременном уменьше-нии времени вычислений в десятки раз. Благодаря относительно невысокому по-рядку трудоемкости (менее O(n3)) алгоритм можно применять для задач размер-ности до 1000 вершин и более, что недоступно алгоритму Османа.Особенно эффективно применение предложенного алгоритма, дающего на-чальное приближение, для алгоритма Османа. Интересно, что при этом время ра-боты алгоритма Османа на второй стадии заметно уменьшается. На практике применение комбинированного алгоритма удобно тем, что если время работы на второй стадии оказывается чрезмерным, процесс вычислений можно прервать и использовать полученный к этому моменту вариант решения задачи.

Скачать электронную версию публикации