Автореферат (Эффективные алгоритмы планирования транспортировки продукции (на примере продуктов с особыми условиями перевозки)), страница 3

Условие (6) означает, что еслитранспортное средство прибывает в вершину, то оно также и покидает даннуювершину.Условие(9)исключаетвозможностьрасщеплениямаршрутатранспортного средства на несвязные циклы.В разделе 2.3 приведен обзор точных методов решения ЗМТ, которые могутбыть разбиты на 3 большие группы: методы прямого поиска в дереве,динамическое программирование и целочисленное линейное программирование.В разделе 2.4 приведен обзор классических эвристических алгоритмов дляЗМТ, среди которых: конструктивные алгоритмы — Кларка–Райта и Соломона;двухфазные алгоритмы — заметания и Фишера–Джекумера; улучшающиеалгоритмы.В 2.5 представлены метаэвристические алгоритмы, которые составляютоснову современных исследований в области приближенных методов решенияЗМТ.

Среди них описаны алгоритмы моделируемого отжига и имитации отжига,методы поиска с запретами, генетические и меметические алгоритмы.В разделе 2.6 на основе проведенного обзора и анализа методов решенияЗМТ сформулированы следующие выводы. Для задач маршрутизации транспортаизвестно большое количество методов и подходов, направленных на получениекак точных оптимальных решений, так и решений, которые дают неплохиеприближениякоптимальному.Точныеметодынасегодняшнийденьпредставляют в большей степени теоретический интерес, так как время,требуемое ими на получение решения, достаточно велико, что неприемлемо дляих внедрения в информационные системы. Поэтому с 60-х годов ХХ векаосновные усилия были брошены на разработку приближенных алгоритмов.Эвристические алгоритмы достаточно просты, однако чаще всего ограничиваютсянахождением хорошего решения лишь в относительно небольшой области, в товремя как метаэвристики направлены на то, чтобы преодолеть этот недостаток и12максимально расширить пространство поиска, где может быть найдено лучшеерешение.

Одними из наиболее перспективных метаэвристических алгоритмов длязадачмаршрутизациитранспортасчитаютсяметодыэволюционногомоделирования и роевого интеллекта.В третьей главе описаны различные вариации метаэвристическогоалгоритма муравьиных колоний, в том числе и новые модификации алгоритма,предложенные автором. Здесь также представлены результаты проведениявычислительных экспериментов, подтверждающих эффективность предложенныхмодификаций.Наосновеанализаэтихрезультатовпостроеныоценкифункциональных зависимостей оптимальных значений управляющих параметровалгоритма от размерности задачи (числа клиентов).Раздел 3.1 описывает общие положения алгоритмов муравьиных колоний.Суть подхода заключается в использовании модели поиска пищи в колонияхмуравьёв, которые помечают пройденный путь специальным химическимвеществом — феромоном. Оставленные следы привлекают других муравьев,которые, проходя по помеченным путям, в свою очередь усиливают запахферомона.Современемферомониспаряется,чтопозволяетмуравьямадаптировать свое поведение под изменения внешней среды.

На рисунке 1проиллюстрировано, как меняется поведение муравьев и след феромона привозникновении препятствия на пути от источника пищи к муравейнику. Сначалапри появлении преграды муравьи с равной вероятностью будут обходить ее совсех сторон (1c), однако за несколько передвижений по кратчайшему путиконцентрация феромонов на нем будет больше, чем на остальных более длинныхучастках, поэтому он станет более привлекательным. Таким образом, муравьи всёчаще проходят по кратчайшему пути, ведущему от муравейника к источникупищи и обратно (1d).13Рис.

1. Динамика поведения муравьев при возникновении препятствияВ разделе 3.2 описан классический муравьиный алгоритм для задачикоммивояжера, которая является частным случаем задачи маршрутизациитранспорта.Раздел 3.3 содержит описание классического алгоритма муравьиныхколонийнепосредственнодлязадачимаршрутизациитранспортасограничениями грузоподъемности. Каждый «муравей» рассматривается какмодель транспортного средства.

Изначально, каждый «муравей» k начинает своймаршрут со склада, причем множество M k — клиентов, включенных в егомаршрут, пусто. Далее «муравей», находящийся у клиента i, выбираетследующего клиента j, который будет посещен, по вероятностному критериюarg max[ju Mkiu(iu) ] с вероятностью q0 ,(10)S с вероятностью 1 q0 ,гдеiu— количество феромона на пути между клиентами i и u;iu— величина,обратно пропорциональная расстоянию между клиентами (ее иногда называют«видимостью» между клиентами i и u, можно взять, например,параметр,характеризующийотносительнуюсравнению с количеством феромона (при14«важность»1 / diu );—расстоянияпоiu0 муравей ориентируется только наколичествоферомона);—q0 (0 q0 1)вероятностьиспользованиядетерминированного принципа при выборе следующего клиента; S — случайнаявеличина, подчиняющаяся следующему закону распределения вероятностей:isP{Ss}pk (i, s)(is) /iv(iv) , если s M k ;(11)v Mk0, если s M k ,т.е.

pk (i, s ) — вероятность, с которой муравей k выбирает передвижение отклиента i к клиенту s. Таким образом, вероятность посещения клиентапропорциональна количеству феромона на данном участке пути и обратнопропорциональна расстоянию до этого клиента.«Муравей» возвращается в депо, когда исчерпана его «грузоподъемность»либо все клиенты посещены. Алгоритм строит полный маршрут для первого«муравья» и лишь затем начинает строить для второго.

Это происходит до техпор, пока для каждого из заранее заданного числа «муравьев» m не построенвыполнимый маршрут.Для улучшения последующих решений необходимо обновлять следыферомона в зависимости от качества получаемых решений. Локальное обновлениеферомона моделирует его естественное испарение и гарантирует, что никакоймаршрут не станет слишком превалирующим. Это обновление происходит послепостроения полного маршрута каждым муравьем и выражается формулой:newijгде(1)oldij0,— параметр, характеризующий скорость испарения феромона,(12)0–начальное значение феромона.После того, как все m муравьев проложили допустимые маршруты,происходит глобальное обновление феромона, заключающееся в добавленииферомона ко всем дугам лучшего из решений, найденного одним муравьем.

Следферомона на этих ребрах обновляется следующим образом:newij(1)15oldijL,(13)где L — длина лучшего маршрута. Такое обновление поощряет использованиеболее «дешевых» маршрутов, увеличивая вероятность того, что будущиемаршруты будут включать дуги, содержавшиеся в лучших решениях.В 3.4 описаны существующиев настоящее времяразновидностимуравьиных алгоритмов, среди которых выделены «элитная» муравьиная система,максиминная муравьиная система, ранжированная муравьиная система имуравьиная система «лучший-худший».В разделе 3.5 проводится анализ применения муравьиных алгоритмов,выделяются их преимущества и недостатки по сравнению с другими методами. Кдостоинствам можно отнести следующее:успешное применение к множеству задач дискретной оптимизации (в томчисле к задаче коммивояжера и ЗМТ);возможность использования в гибридных оптимизационных алгоритмах,хорошая сочетаемость с алгоритмами локальной оптимизации;легкая адаптация к дополнительным ограничениям и динамическомуизменению исходных данных.Из недостатков стоит отметить, прежде всего, трудности, возникающие припопытках теоретического анализа алгоритмов.

Этот анализ затруднен тем, чторезультат представляет собой последовательность случайных решений, неявляющихся независимыми. Тем не менее, было доказано (Dorigo, Stutzle, 2004),что при положительной нижней границе количества феромонаlim P* ( AN ) 1 ,N(14)где P* ( AN ) — вероятность нахождения оптимального решения за N итераций.Однако время нахождения этого решения может быть сколько угодно большим. Сточки зрения практического применения основные трудности и неудобствавозникают из-за большого числа управляющих параметров алгоритма, значениякоторых оказывают сильное влияние на качество получаемых решений.

Могутвозникать ситуации, когда при одних и тех же значениях управляющихпараметров отклонение полученного решения от оптимального значения для16разных исходных данных отличается на порядок. Поэтому значения параметровобычно подбираются экспериментально для каждой конкретной задачи, чтоявляется неприемлемым для применения в информационных системах.В разделе 3.6 представлен модифицированный алгоритм муравьиныхколонийдлязадачимаршрутизациитранспортасограничениямигрузоподъемности. Начальное значение феромона в нем определяется поформуле:0((n 1) min dij ) 1 ,(15)i jгде n — число клиентов. Кроме того, распределение вероятностей, котороеопределяет выбор следующего клиента, заданное формулой (11), изменяетсяследующим образом:после построения полного маршрута каждым «муравьем» предлагаетсязапоминать лучший и худший маршруты одного муравья (среди всех муравьев), Lи R, соответственно, затраты на этих маршрутах;в случае, если путь от клиента i к клиенту j входит в худший маршрут, товероятностьвыбораэтогопередвиженияуменьшаетсяпропорциональноотношению затрат лучшего маршрута к худшему, т.е.pk (i, j )LRij(ijiv(iv)L ij (ij) R ;(16)v j ,v M kв остальных случаях ( spk (i, s ))ij(ijj ) распределение имеет вид)iv(iv)L ij (ij) R , если s M k ;v j ,v M k(17)0, если s M k .Для задачи с одним транспортным средством (по-существу, для задачикоммивояжера) модифицированный алгоритм совпадет с классическим.Приведем упрощенное описание модифицированного алгоритма.1.