автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Мультиноменклатурная оптимизационная задача маршрутизации транспортных средств с ограничениями на перевозку

На правах рукописи

ЯКОВЛЕВА Таисия Александровна

МУЛЬТИНОМЕНКЛАТУРНАЯ ОПТИМИЗАЦИОННАЯ ЗАДАЧА МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ С ОГРАНИЧЕНИЯМИ НА ПЕРЕВОЗКУ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в промышленности)

, ъшш

АВТОРЕФЕРАТ на соискание ученой степени кандидата физико-математических наук

Уфа 2012

005018918

Официальные оппоненты

Работа выполнена на кафедре вычислительной математики и кибернетики

ФГБОУВПО

«Уфимский государственный авиационный технический университет»

Научный руководитель д.р физ.-мат. наук, проф. каф.

вычислительной математики и кибернетики Уфимского государственного авиационного технического университета БРОНШТЕЙН Ефим Михайлович

д-р физ.-мат. наук, проф., в.н.с. Института математики с ВЦ УНЦРАН

ГОЛИЧЕВ Иосиф Иосифович

д-р физ.-мат. наук, проф., зав.каф. экономико-математических методов и статистики Южно-Уральского государственного университета

ПАНЮКОВ Анатолий Васильевич

Омский филиал Федерального государственного бюджетного учреждения науки Института математики им. С.Л. Соболева Сибирского отделения Российской академии наук (ОФ ИМ СО РАН)

Защита диссертации состоится «17» мая 2012 года в 14:00 часов на заседании диссертационного совета Д-212.288.06 при Уфимском государственном авиационном техническом университете по адресу: 45000, г.Уфа, ул. К.Маркса, 12, корп. 1

С диссертационной работой можно ознакомиться в библиотеке Уфимского государственного авиационного технического университета.

Ведущая организация

Автореферат разослан «//■» апреля 2012 года.

Ученый секретарь диссертационного совета, д-р физ.-мат. наук, проф.

'.Т. Булгакова

ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИИ

Актуальность темы.

Реальные логистические системы характеризуются сложными связями как внутри этих систем, так и с внешней средой. В качестве логистических связей могут выступать материальные, денежные, информационные потоки. Элементами логистической системы являются: промышленные и транспортные предприятия, склады, предприятия оптовой и розничной торговли, перегрузочная и перевозочная техника и другие. Таким образом, логистическая система - это сложная адаптивная система, для исследования подобных систем применяют системный подход. Он позволяет рассматривать такие логистические подсистемы, как транспортная логистика, в качестве находящихся во взаимосвязи и взаимодействии элементов системы. Системный подход выступает в виде совокупности познавательных принципов, соблюдение которых позволяет определенным образом сориентировать конкретные исследования на изучение наиболее востребованных задач и их ограничений.

Большое число современных промышленных предприятий осуществляют выпуск мелкотоннажной продукции широкой номенклатуры, характеризующейся различной по массе фасовкой, которая может определяться как технологическим процессом, так и заказами потребителей. К таким относятся предприятия химической промышленности, фармацевтической промышленности, пищевой промышленности, предприятия оптовой и розничной торговли, автотранспортные предприятия, доставка почты и т.д. Все эти предприятия самостоятельно или с привлечением сторонних организаций доставляют свою продукцию потребителям. Особенность перевозки подобных грузов заключается в том, что, к примеру, для транспортировки химических реагентов или радиоактивных веществ требуется спецтранспорт, а для некоторых грузов (продовольственных товаров или фармакологических препаратов) критичным фактором является особый температурный режим. Перевозку грузов с учетом всех норм и правил осуществляет самостоятельная отрасль производства - транспортная промышленность. Она выполняет перемещение грузов как внутри сфер

материального производства, так и между ними, управляя транспортными и транспортно-производственными процессами с целью повышения их рентабельности. Эффективное распределение транспортных средств с учетом их грузоподъемности по маршрутам передвижения позволяет добиться максимально полного обеспечения грузопотоков. Кроме того, рациональное использование производительности транспортных средств удерживает предприятие от увеличения транспортного парка и расходов на его обслуживание.

Планирование грузоперевозок затрагивает еще один важный аспект -маршрутизацию транспортных средств. Повышенное внимание к задачам этой области объясняется тем, что по разным оценкам от 30% до 50 % всех затрат на логистику связано с транспортными издержками. При этом наиболее сложными и дорогостоящими являются международные перевозки, затраты на которые в 2,5-3 раза выше, чем перевозки на внутреннем рынке. Определение и эксплуатация рациональных маршрутов при строгом соблюдении сроков поставок помогают добиться не только минимизации эксплуатационных затрат или тонно-километрового пробега, но и сократить товарно-производственные запасы на складах в 1,5-2 раза.

Учитывая всё вышесказанное, можно утверждать, что особую актуальность приобретают работы, позволяющие точно вычислять объемы грузоперевозок, рассчитывать количество единиц транспорта, необходимых для обеспечения грузопотоков, определять рациональные маршруты движения, а также сократить суммарные затраты на транспортировку.

Поставленная задача относится к классу задач маршрутизации транспортных средств при перевозке грузов - VRP (Vehicle Routing Problem). Первая задача данного класса была сформулирована Г. Данцигом и Дж. Рамсером в 1959 году как классическая задача маршрутизации транспортных средств и инициировала важный класс задач оптимизации. Наиболее часто встречающиеся постановки задач данного класса предполагают доставку однородных грузов из пункта производства или склада потребителям. Предполагается, что целью является минимизация стоимости транспортировки. Встречаются задачи и с другой целевой функцией (например, временем доставки грузов), но их, как правило, можно переформулировать таким образом, что целевая функция будет носить

экономический смысл. На сегодняшний день сформулировано много подобных задач, в которых учитываются различные реальные ограничения, разработан ряд алгоритмов приближенного поиска оптимальных решений -для большинства задач нахождение точного решения является сложным в вычислительном отношении. Однако развитие логистических процессов и потребность в учете новых факторов ведут к постановке новых задач, требующих, в свою очередь, применения новых не рассматривавшихся ранее методов решения.

Обозначая актуальность работ на эту тему, необходимо указать на отличие задачи в рассматриваемой постановке от классической задачи маршрутизации транспортных средств. Особенностями рассматриваемой задачи являются мультнноменклатурность и запреты на перевозку некоторых видов грузов отдельными транспортными средствами. Поставленная задача относится к классу нелинейных оптимизационных задач и является обобщением двух известных задач: задачи коммивояжера и задачи о загрузке рюкзака. Тем самым рассматриваемая задача является ЫР-сложной.

Область исследования. Задачи организации транспортировки грузов.

Цель работы. Исследование и разработка эффективных методов решения мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку.

Задачи исследования. Для достижения цели работы были поставлены и решены следующие задачи:

1. Классификация задач организации транспортировки грузов в соответствии с принципами системного анализа на основе их базовых характеристик.

2. Постановка и формализация мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку отдельных видов грузов определенными транспортными средствами.

3. Разработка алгоритма построения локально оптимального решения целочисленной мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку.

4. Разработка эвристических алгоритмов решения мультиноменклатурной оптимизационной задачи маршрутизации с ограничениями на перевозку на основе различных подходов к решению задачи коммивояжера.

5. Реализация предложенных методов на ЭВМ, экспериментальная проверка эффективности работы предложенных алгоритмов.

Методы исследования. В работе применяются методы математического программирования, теории графов, комбинаторной оптимизации, а также современная технология экспериментальных исследований с применением ЭВМ.

Информационная база исследования включает сгенерированные псевдослучайным образом по равномерному закону распределения исходные данные о заказах пунктов потребления на доставку различных видов грузов, а также о количестве и характеристиках транспортных средств. Данные о координатах пунктов потребления и базы включают 2 способа задания: 1) с помощью датчика псевдослучайных чисел, расстояния между пунктами при этом принимаются равными евклидовым расстояниям; 2) примеры из библиотеки задачи коммивояжера (ТБРНЬ).

На защиту выносятся следующие результаты исследований:

1. Математическая модель мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку (п.2 Паспорта специальности 05.13.01).

2. Алгоритм построения локально оптимального решения мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку в случае целочисленности исходных данных (п.4 Паспорта специальности 05.13.01).

3. Эвристические алгоритмы решения мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку на основе эвристических подходов к решению задачи коммивояжера (п.4 Паспорта специальности 05.13.01).

4. Сравнительный анализ эффективности предложенных методов (п.9 Паспорта специальности 05.13.01).

Научная новизна. Получены следующие основные результаты, обладающие научной новизной:

1. Постановка и формализация (в том числе в форме задачи частично целочисленного линейного программирования) оптимизационной задачи маршрутизации транспортных средств, в которой, в отличие от известных, учтена мультиноменклатурность перевозимых грузов и запреты на перевозку некоторых видов грузов отдельными транспортными средствами.

2. Доказательство допустимости исходной задачи в случае совместности редуцированной задачи. Решение редуцированной задачи дает возможность определить план перевозок (сколько груза того или иного вида каждое транспортное средство должно доставить в каждый пункт потребления) или сделать вывод об их недопустимости.

3. Доказательство существования для любого допустимого способа перевозки грузов при целых исходных данных, способа перевозки по тем же маршрутам, в котором все веса грузов целые. Существование загрузки транспортных средств грузами с целочисленными весами позволило разработать алгоритм локальной оптимизации для целочисленного случая задачи.

4. Методы и алгоритмы решения мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку. Разработан и программно реализован трехэтапный алгоритм, в котором применены различные подходы к решению задачи коммивояжера. Проведен вычислительный эксперимент для оценки эффективности предложенных алгоритмов.

Практическая и теоретическая значимость. Теоретическая значимость заключается в постановке и решении новой мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку, относящейся к классу УКР. Исследуемая задача позволила учесть ассортимент грузов, а также приспособленность транспортных средств к их перевозке. Предложенные методы и алгоритмы могут применяться для решения родственных задач организации транспортировки грузов.

Практическую ценность работы составляет определение минимальных суммарных затрат на транспортировку, плана перевозок, а также маршрутов движения транспортных средств. Это делает программную реализацию методов практически применимой для решения реальных транспортно-логистических задач на производстве. Программное обеспечение, разработанное в рамках диссертационной работы, зарегистрировано Федеральной службой по интеллектуальной собственности, патентам и товарным знакам, свидетельство № 2011613654.

Апробация работы. Работа была поддержана стипендией Президента Республики Башкортостан (2010-2011 учебный год), Российским фондом фундаментальных исследований (проект 10-06-00001) и грантом Президента Российской Федерации для государственной поддержки ведущих научных школ Российской Федерации № НШ-65497.2010.9.

Основные результаты диссертационной работы докладывались и обсуждались на:

• четвертой Всероссийской зимней школе-семинаре аспирантов и молодых ученых "Актуальные проблемы науки и техники" (Уфа, 19-21 февраля 2009 г.)

• пятой Всероссийской зимней школе-семинаре аспирантов и молодых ученых "Актуальные проблемы науки и техники" (Уфа, 17-20 февраля 2010 г.)

• XII международной конференции "Компьютерные науки и информационные технологии" (Москва-СПб., 13-19 сентября 2010 г.)

• 33-й международной научной школе-семинаре имени академика С.С. Шаталина "Системное моделирование социально-экономических процессов" (Звенигород, 1-5 октября 2010 г.)

• 14 -й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 28 февраля - 4 марта 2011 г.)

• шестой Всероссийской зимней школе-семинаре аспирантов и молодых ученых "Актуальные проблемы науки и техники" (Уфа, 15-18 февраля 2011 г.)

• VII международной научно-практической конференции "Актуальные задачи математического моделирования и информациошйк технологий" (Сочи, 18-25 мая 2011 г.)

• VI Специальном симпозиуме по исследованию операций, безопасности информации и технической кибернетики (Баден-Баден, 3-7 августа 2011г.)

• научных семинарах в Башкирском государственном университете, Омском филиале института математики им. C.JI. Соболева СО РАН, институте математики с вычислительным центром УНЦ РАН.

Публикации. Список публикаций автора по теме диссертации включает 13 научных трудов, в том числе 4 статьи в рецензируемых научных журналах из списка ВАК, свидетельство об официальной регистрации программного продукта, 4 публикации в трудах международных конференций. Шесть публикаций выполнено без соавторов.

Структура и объем диссертации. Диссертационная работа состоит из введения, 4 глав, разбитых на параграфы, основных результатов работы, библиографического списка литературы, включающего 109 источников, 1 приложения, содержит 7 таблиц, 24 рисунка. Общий объем работы составляет 125 страниц.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Введение. Во введении обоснована актуальность работы, сформулированы цели и выделены задачи исследования. Кроме того, описана научная новизна и практическая значимость полученных результатов, приведены методы и информационная база исследования, а также сведения об апробации работы.

Глава 1. Апализ оптимизационных задач транспортной логистики.

Глава начинается с раздела 1.1, посвященного анализу актуальности задач транспортной логистики для промышленности. При этом показано, что реальные логистические системы являются сложными системами, для исследования которых необходимо применение системного подхода. Введены основные понятия: транспортировка, транспортная логистика, грузопоток,

маршрут, маршрутизация. Определены основные направления сокращения затрат в сфере транспортировки грузов. В разделе 1.2 в соответствии с принципами системного анализа (анализ и синтез, композиция и декомпозиция, кластеризация и классификация и др.) выделены 16 типов характеристик, позволяющих строить широкий круг как известных, так и новых, важных для конкретных приложений, задач транспортной логистики.

С помощью систематизированной совокупности характеристик в разделе 1.3 описаны наиболее часто встречающиеся задачи организации транспортных перевозок, включая дискретные (классическая задача маршрутизации Г. Данцига - Дж. Рамсера) и непрерывные (классическая транспортная) задачи. Приведена формализация рассматриваемых задач, описаны подходы к их решению. В разделе 1.4 проведен анализ требований к учету дополнительных ограничений, наиболее часто встречающихся на предприятиях, выпускающих мелкотоннажную продукцию широкой номенклатуры или имеющих дело с транспортировкой сборных грузов, выявивший необходимость постановки новой мультиноменклатурной оптимизационной задачи транспортной логистики с ограничениями на перевозку:

Пусть требуется доставить с базы в п пунктов потребления (ПП) товары к видов согласно заказу. Доставка товара осуществляется т транспортными средствами (ТС), каждый из которых характеризуется грузоподъемностью, транспортными затратами на 1 км пути, а также указанием, какие именно виды товаров можно перевозить данным ТС. Требуется организовать доставку груза минимизируя транспортные издержки.

Глава 2. Математическая модель мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку. Раздел 2.1 начинается с формализации поставленной задачи, для этого вводятся следующие обозначения: N = {1 ,...,п}, К = {1,...,Аг}, М = {1,..., т) - ПП, виды грузов, ТС, Б" - грузоподъемность р -го ТС,

Ь0- вес груза /'-го вида, который необходимо доставить в ПП

Ар с К - множество грузов, недопустимых к перевозке р -м ТС, Вр - затраты на проезд р -го ТС на единицу расстояния,

ся+1,л*1 - матрица расстояний между ПП и базой.

Пусть с(и) (и а Ы) - минимальная из длин циклов, содержащих ПП из и и нулевой пункт,

Х1 - вес груза г -го вида, перевозимого р -м ТС в ] -й ПП (г е К, ./' е N, реМ),

Задача имеет следующий вид. Найти числа такие, что: х^О, х* = 0 щт!еАр jeN

т

¡=1М

(3)

(4)

0)

= V/ 6 N: ЩхЦ > о| - множество ПП, в которые груз доставляется р-м ТС. Показано, что выполнения необходимого условия (суммарный вес грузов не превышает общей грузоподъемности ТС) не достаточно для реализуемости перевозки. Рассмотрим редуцированную задачу.

Пусть -и?, - - суммарная потребность в грузе г -го вида, У? - общий вес груза ¡' -го вида, перевозимого р -м ТС.

вспомогательная система уравнений и неравенств:

(5) уР> О

у, = 0 при г е Ар

р=1

(6)

(7)

(8)

ТЕОРЕМА 1. Задача (1)-(4) допустима тогда и только тогда, когда совместна вспомогательная система (5)-(8).

Графически: для каждого вида груза проводится построение, представленное на рисунке 2 для груза первого вида. Нижние индексы величин х наследуются от Ь, а верхние от у. Определяется план перевозок: сколько груза того или иного вида каждое ТС должно доставить в каждый ПП.

у! л2 ^

А.,

Рисунок 1 - Формирование плана перевозок для груза 1 -го вида

В разделе 2.2 поставленная задача рассматривается как задача линейного частично целочисленного программирования: хр>0, хр=0 при г е Ар,

Цх^Я'

ы м

Введем в рассмотрение булевы переменные

_ Г1, если хЦ > 0, т.е. груз / - го вида перевозится - м ТС в у - й ПП " [0, в противном случае хр

-—Г <ир.

гхтах^'} "

Г1, если при некотором I 17? >0 1 [0, в противном случае

I

У0р = 1, /7 = 1,...,/«

п

Рр = V/ - число ПП, в которые груз доставляется р -м ТС

м

[1, если р - е ТС переезжает из ПП а в ПП /7

<*Р) ' I п

[0, в противном случае Матрица расстояний между городами С(а/!) задана в условии задачи. Считаем,

что.

п

Л - УЦ, р-\,...,т, р- 0,...,« - условие означает, что р -е ТС выезжает из

о=0

каждого подходящего ПП только один раз;

п

2 2(а/1) ~ ^а > Р = а-0,...,п - условие означает, что р -е ТС въезжает в

/»-0

каждый подходящий ПП только один раз.

= 0, р-1,...,т - это условие обеспечит замыкание цикла через базу.

Введем целочисленные переменные ,0,рв е[1, Рр\ такие, что

<2Р -<2в + пх2,рав) < я -1, а,Р = \,...,п, р = \,...,т - условие, обеспечивающее

отсутствие циклов, содержащих не все пункты, через которые должно

проходить ТС (кроме базы).

Требуется минимизировать

Z £ H C(aß)BPZ(aß) + и X тах{с(оЛ}х «хЦЕЕ^У ->min

Р ß a pit

Линейная модель мультиноменклатурной оптимизационной задачи маршрутизации ТС с ограничениями была реализована в среде IBM CPLEX Optimization Studio V12.2. CPLEX - специализированный пакет программного обеспечения, предназначенный для решения задач линейного и квадратичного программирования. Его особенностью является наличие встроенных методов решения подобных задач, способ решения может быть задан автоматически.

Применение данного пакета для решения поставленной задачи оказалось невозможным для т>9 (ТС>9). Кроме размерностей задачи, критичными для CPLEX являются условия недопустимости перевозки.

Это обосновывает целесообразность разработки эвристических алгоритмов.

В разделе 2.3 описан трсхэтапный алгоритм решения задачи. На первом этапе в случае совместности ищется какое-нибудь решение вспомогательной системы уравнений и неравенств, определяется загрузка каждого транспортного средства у?. На втором этапе для каждого вида груза производится построение (рисунок 1), в ходе которого для каждого ТС вычисляется значение х?, определяется множество пунктов потребления, которые ему необходимо посетить. На третьем этапе для каждого множества пунктов решается задача коммивояжера, позволяющая вычислить значение целевой функции (4). Третий этап является наиболее трудоемким в вычислительном смысле.

В разделе 2.4 рассматривается частный целочисленный случай задачи.

ТЕОРЕМА 2. Пусть потребность в каждом виде груза каждого пункта потребления и грузоподъемность каждого ТС - целые. Тогда для любого допустимого способа перевозки грузов существует способ перевозки по тем же маршрутам, для которого все веса грузов (х?) - целые.

Для целочисленного варианта задачи может быть разработан алгоритм локальной оптимизации. Применение процедур, позволяющих найти локально оптимальное решение, возможно лишь для небольших размерностей задачи - в случае, если имеются два транспортных средства или два пункта потребления. На первом этапе решения определяется загрузка ТС в случае совместности вспомогательной системы. Осуществляется переход от системы

уравнений и неравенств (5)-(8) к системе уравнений вида Ау = Ь, где А = KL„ " Целочисленная матрица; b = (bi,...,bm) - целочисленный вектор. Приведение А к эрмитовой нормальной форме позволяет установить разрешимость системы линейных уравнений в целых (не обязательно неотрицательных) числах. В случае разрешимости, определяются значения у" на множестве неотрицательных целочисленных решений системы Ау = Ь. На втором этапе, согласно схеме трехэтапного алгоритма, по значениям у? и !.. находятся значения х?. Третий этап предусматривает решение задачи коммивояжера точным методом для каждого ТС.

ТЕОРЕМА 3. Имея некоторое целочисленное решение подзадачи загрузки транспортных средств, для грузов, разрешенных к перевозке двумя ТС, можно получить такую загрузку, в которой не более чем один пункт потребления будет посещен обоими ТС.

На основе приведенной теоремы разработан алгоритм получения уточненного решения:

I

Шаг 1. Присвоим 7=1. L, - потребность 1 -го IJU1 в грузе, которую потенциально могут разделить между собой оба ТС.

г t t

Шаг 2. Удалим из рассмотрения Z, . Оставшиеся грузы L2 ,...!„ последовательно проверяются на загрузку в первое ТС. При каждом очередном добавлении груза выполняется проверка, не превосходит ли его вес величины оставшегося запаса грузоподъемности первого ТС, а общая загрузка удовлетворяет условию: S1 -Z, < <5' . Грузы, не загруженные в первое ТС, автоматически подлежат загрузке во второе ТС.

Шаг 3. Вычислим значение целевой функции.

Шаг 4. Присвоим j = j +1. Возврат к Шагу 2.

Окончание просмотра всех потенциально разделяемых грузов и соответствующих им загрузок ТС, завершает процедуру вычисления значений целевой функции при всевозможных перестановках исходных данных.

Раздел 2.5 посвящен решению мультиноменклатурной оптимизационной задачи эвристическим методом. Эвристический метод решения следует основной идее трехэтапного алгоритма решения задачи. На первом этапе для проверки совместности и определения загрузки ТС к системе добавляется

к m

линейная целевая функция I] /'Г^Г ™ах, где ^ - числа, последовательно

î» I 1

генерируемые датчиком псевдослучайных чисел из интервала [-1;1], и

решается полученная задача линейного программирования. На втором этапе по значениям у* и Ц определяются значения х?. Для каждого вида груза производится построение (рисунок 1), которое позволяет однозначно присвоить ПП каждому из ТС в соответствии с произведенной загрузкой. Последовательность посещения ПП каждым ТС определяется на третьем этапе решения. Для решения задачи коммивояжера используются эвристические алгоритмы.

В качестве основного подхода к решению задачи коммивояжера был выбран генетический алгоритм, т.к. он обеспечивает весьма эффективную адаптивную генерацию лучших решений. Эффективность генетического алгоритма может быть улучшена двумя путями: использованием более мощного алгоритма локальной оптимизации либо увеличением размеров популяции. В работе представлены оба подхода.

Реализацией первого подхода является генетический алгоритм, дополненный алгоритмом Лпна-Кернигана и эвристиками 4-орг, З-орС, 2-орК применяющимися как к родительской популяции, так и к популяции -потомку. Размер популяции для данного алгоритма - 1 особь.

Вторрй подход реализован генетическим алгоритмом с большим размером популяции (100 особей) и различными вариантами мутаций. В качестве алгоритмов мутации применены: эвристика 2-ор1, перестановка вершин, сдвиг вершин.

В главе 3 описана программная реализация предложенных алгоритмов в среде инженерных и научных расчетов МАТЬАВ И2011а. Раздел 3.1 посвящен организации функционирования, архитектуре и реализации программного обеспечения. Примеры результатов работы программного обеспечения на разных этапах решения задачи проиллюстрированы экранными формами в разделе 3.2.

Глава 4 Исследование разработанных алгоритмов решения мультиноменклатурной оптимизационной задачи маршрутизации транспорта ых средств с ограничениями на перевозку. Приведены результаты нескольких вычислительных экспериментов. Анализируя полученные результаты можно сделать следующие выводы:

• Методом локальной оптимизации для 92% примеров было получено решение, совпадающее с оптимальным. Для оставшихся 8% примеров отклонение от оптимального решения не превысило 5%. В среднем для 100% задач отклонение составило 0,1%.

• Эвристический метод с применением ГА с различными вариантами мутаций: из 100% задач в 62% получены решения, совпадающие с оптимальными, в 30% задач отклонение не превосходит 5%. В среднем для 100% задач отклонение составило 1,6%.

• Эвристический метод с применением ГА с эвристикой Лина-Кернагана: из 100% задач в 55% получены решения, совпадающие с оптимальными, в 37% задач отклонение не превосходит 5%. В среднем для 100% задач отклонение составило 1,7%.

Оценка предложенных в работе эвристик решения задачи коммивояжера как подэтапа эвристического метода решения мультиноменклатурной оптимизационной задачи маршрутизации с запретами показала, что при одинаковом времени выполнения эвристика Лина-Кернигана является более успешной в качестве алгоритма оптимизации в генетическом алгоритме (на примерах, сгенерированных псевдослучайным образом и задачах библиотеки ТБИЛЪ).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. В соответствии с принципами системного анализа разработана классификация задач организации транспортировки грузов на основе выделенных 16-ти типов характеристик, что позволяет ставить широкий спектр новых задач.

2. Поставлена новая мультиноменклатурная оптимизационная задача маршрутизации транспортных средств с ограничениями на перевозку, проведена её формализация.

3. Разработан алгоритм нахождения локально оптимального решения поставленной задачи при условии целочисленности исходных данных на основе трехэтапного алгоритма.

4. Разработаны эвристические методы решения мультиноменклатурной задачи маршрутизации с ограничениями на основе трехэтапного алгоритма и эвристических подходов к решению задачи коммивояжера.

5. Разработан программный продукт в среде MATLAB, проведен вычислительный эксперимент, подтвердивший эффективность работы предложенных алгоритмов.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

в рецензируемых журналах из списка ВАК

1. Бронштейн Е.М., Заико (Яковлева) Т. А. Детерминированные оптимизационные задачи транспортной логистики (на англ. и рус. языках) // Автоматика и телемеханика, 2010.-№10-С.133-147. // ISSN 0005-1179, Automation and Remote Control, 2010, Vol. 71, No. 10, pp. 2132-2144.

2. Бронштейн E.M., Заико (Яковлева) T.A. Задача маршрутизации с запретами // Информационные технологии - М.: Изд-во "Новые технологии", 2011.-№6-С.42-44.

3. Бронштейн Е.М., Яковлева Т.А. Сравнительный анализ эвристических алгоритмов решения мультиноменклатурной задачи маршрутизации с запретами // Логистика и управление цепями поставок, 2011,- №4 (45) -С.90-98.

4. Яковлева Т.А. Целочисленная мультиноменклатурная оптимизационная задача маршрутизации транспортных средств с ограничениями на перевозку // Современные проблемы науки и образования. -2011.-№ 5; URL: www.science-education.ru/99-4830

в других изданиях

5. Заико (Яковлева) Т.А. Об одной задаче транспортной логистики // "Актуальные проблемы науки и техники": Труды 4-ой Всерос. зимней школы-семинара аспирантов и молодых ученых.- Уфа: Изд. "Диалог", 2009.-T.l~ С.207-210.

6. Заико (Яковлева) Т.А. Мультиноменклатурная задача транспортной логистики И "Актуальные проблемы науки и техники": Труды 5-ой Всерос. зимней школы-семинара аспирантов и молодых ученых,- Уфа: Изд. "УГАТУ", 2010.-T.3-C.134-138.

7. Заико (Яковлева) Т. А. Мультиноменклатурная задача маршрутизации транспортных средств с ограничениями на перевозку (на англ. языке) // "Компьютерные науки и информационные технологии": Труды 12-ой междунар. конф,- Москва-СПб.: Россия, 2010.-Т.2.-С.72-74.

8. Бронштейн Е.М., Заико (Яковлева) Т.А. О мультиноменклатурной задаче маршрутизации транспортных средств // "Системное моделирование социально-экономических процессов": Труды 33-й международной научной школы-семинара имени С.С. Шаталина.- Звенигород: Изд. ВГУ, 2010-С.78-79.

9. Бронштейн ЕМ., Яковлева Т.А. Трехэтапный эвристический алгоритам решения мультиноменклатурной задачи маршрутизации // "Математическое программирование и приложения": Труды 14-ой Всероссийской конф.- Екатеринбург: Изд., 2011-С.158-159.

10. Яковлева Т.А. Решение задачи коммивояжера как подзадачи маршрутизации транспортных средств // "Актуальные проблемы науки и техники": Труды б-ой Всерос. зимней школы-семинара аспирантов и молодых ученых.- Уфа: Изд. "УГАТУ", 2011 .-Т. 1-С.282-284.

11. Яковлева Т.А. Генетический алгоритм с эвристикой Лина-Кернигана как подэтап решения мультиноменклатурной задачи маршрутизации // "Актуальные задачи математического моделирования и информационных технологий": Труды междунар. научно-практ. конф,- Сочи: Изд. "European resercher", 2011. №5-1(7)-С.660-661.

12. Бронштейн Е.М., Яковлева Т.А. Мультиноменклатурная задача маршрутизации с ограничениями как предмет исследования (на англ. языке) П Труды 6-го Специального Симпозиума по исследованию операций, безопасности информации и технической кибернетики - Баден-Баден: ФРГ, 2011.-С. 89-92.

13. Пакет решения мультиноменклатурной задачи транспортной логистики / Яковлева Т.А. Свид. №2011613654 о гос. регистрации программы для ЭВМ, 2011г.

ЯКОВЛЕВА Таисия Александровна

МУЛЬТИНОМЕНКЛАТУРНАЯ ОПТИМИЗАЦИОННАЯ ЗАДАЧА МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ С ОГРАНИЧЕНИЯМИ НА ПЕРЕВОЗКУ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в промышленности)

АВТОРЕФЕРАТ на соискание ученой степени кандидата физико-математических наук

Подписано в печать 11.04.2012. Формат 60x84 1/16. Бумага офсетная. Печать плоская. Гарнитура Times New Roman. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ № 683.

ФГБОУ ВПО «Уфимский государственный авиационный технический университет» Центр оперативной полиграфии 450000, Уфа-центр, ул. К.Маркса, 12

61 12-1/940

На правах рукописи

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Уфимский государственный авиационный технический университет

ЯКОВЛЕВА Таисия Александровна

МУЛЬТИНОМЕНКЛАТУРНАЯ ОПТИМИЗАЦИОННАЯ ЗАДАЧА МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ С ОГРАНИЧЕНИЯМИ НА ПЕРЕВОЗКУ

Специальность 05.13.01 - Системный анализ, управление и обработка

информации (в промышленности)

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель доктор физико-математических наук

БРОНШТЕЙН Е.М.

Уфа 2012

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ.................................................................................................................4

Глава 1. Анализ оптимизационных задач транспортной логистики...................12

1.1. Актуальность задач транспортной логистики для промышленности.........12

1.2. Характеристики задач организации транспортных перевозок.....................17

1.3. Некоторые задачи организации транспортных перевозок............................21

1.4 Мультиноменклатурная оптимизационная задача маршрутизации транспортных средств с ограничениями на перевозку........................................35

Выводы по главе:......................................................................................................40

Глава 2. Математическая модель мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку 41

2.1. Концептуальная постановка задачи................................................................41

2.2. Линейная постановка задачи............................................................................47

2.3. Трехэтапный алгоритм решения задачи.........................................................49

2.4. Целочисленный вариант мультиноменклатурной оптимизационной задачи ....................................................................................................................................53

2.5. Эвристический метод решения задачи...........................................................62

Выводы по главе:......................................................................................................72

Глава 3. Программная реализация алгоритмов решения мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку...................................................................................74

3.1. Организация функционирования, архитектура и реализация программного обеспечения...............................................................................................................74

3.2. Экранные формы программного обеспечения...............................................92

Выводы по главе:......................................................................................................97

Глава 4. Исследование разработанных алгоритмов решения мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку........................................98

4.1. Анализ эффективности разработанных методов решения...........................98

4.2. Анализ эффективности процедуры улучшения в методе локальной оптимизации для целочисленной задачи.............................................................102

4.3. Определение управляющих параметров (способов упорядочения) при прикреплении ТС к ПП..........................................................................................105

4.4. Анализ эффективности эвристических алгоритмов на примерах псевдослучайных исходных данных и задач из TSPLib....................................109

Выводы по главе:....................................................................................................112

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ...............................................................114

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ..............................................115

ВВЕДЕНИЕ

Актуальность темы.

Реальные логистические системы характеризуются сложными связями как внутри этих систем, так и с внешней средой. В качестве логистических связей могут выступать материальные, денежные, информационные потоки. Элементами логистической системы являются: промышленные и транспортные предприятия, склады, предприятия оптовой и розничной торговли, перегрузочная и перевозочная техника и другие. Таким образом, логистическая система - это сложная адаптивная система, для исследования подобных систем применяют системный подход. Он позволяет рассматривать такие логистические подсистемы, как транспортная логистика, в качестве находящихся во взаимосвязи и взаимодействии элементов системы. Системный подход выступает в виде совокупности познавательных принципов, соблюдение которых позволяет определенным образом сориентировать конкретные исследования на изучение наиболее востребованных задач и их ограничений.

Большое число современных промышленных предприятий осуществляют выпуск мелкотоннажной продукции широкой номенклатуры, характеризующейся различной по массе фасовкой, которая может определяться как технологическим процессом, так и заказами потребителей. К таким относятся предприятия химической промышленности, фармацевтической промышленности, пищевой промышленности, предприятия оптовой и розничной торговли, автотранспортные предприятия, доставка почты и т.д. Все эти предприятия самостоятельно или с привлечением сторонних организаций доставляют свою продукцию потребителям. Особенность перевозки подобных грузов заключается в том, что, к примеру, для транспортировки химических реагентов или радиоактивных веществ требуется спецтранспорт, а для некоторых грузов (продовольственных товаров

или фармакологических препаратов) критичным фактором является особый температурный режим. Перевозку грузов с учетом всех норм и правил осуществляет самостоятельная отрасль производства - транспортная промышленность. Она выполняет перемещение грузов как внутри сфер материального производства, так и между ними, управляя транспортными и транспортно-производственными процессами с целью повышения их рентабельности. Эффективное распределение транспортных средств с учетом их грузоподъемности по маршрутам передвижения позволяет добиться максимально полного обеспечения грузопотоков. Кроме того, рациональное использование производительности транспортных средств удерживает предприятие от увеличения транспортного парка и расходов на его обслуживание.

Планирование грузоперевозок затрагивает еще один важный аспект -маршрутизацию транспортных средств. Повышенное внимание к задачам этой области объясняется тем, что по разным оценкам от 30% до 50 % всех затрат на логистику связано с транспортными издержками. При этом наиболее сложными и дорогостоящими являются международные перевозки, затраты на которые в 2,5-3 раза выше, чем перевозки на внутреннем рынке. Определение и эксплуатация рациональных маршрутов при строгом соблюдении сроков поставок помогают добиться не только минимизации эксплуатационных затрат или тонно-километрового пробега, но и сократить товарно-производственные запасы на складах в 1,5-2 раза.

Учитывая всё вышесказанное, можно утверждать, что особую актуальность приобретают работы, позволяющие точно вычислять объемы грузоперевозок, рассчитывать количество единиц транспорта, необходимых для обеспечения грузопотоков, определять рациональные маршруты движения, а также сократить суммарные затраты на транспортировку.

Поставленная задача относится к классу задач маршрутизации транспортных средств при перевозке грузов - VRP (Vehicle Routing Problem).

Первая задача данного класса была сформулирована Г. Данцигом и Дж. Рамсером в 1959 году как классическая задача маршрутизации транспортных средств и инициировала важный класс задач оптимизации. Наиболее часто встречающиеся постановки задач данного класса предполагают доставку однородных грузов из пункта производства или склада потребителям. Предполагается, что целью является минимизация стоимости транспортировки. Встречаются задачи и с другой целевой функцией (например, временем доставки грузов), но их, как правило, можно переформулировать таким образом, что целевая функция будет носить экономический смысл. На сегодняшний день сформулировано много подобных задач, в которых учитываются различные реальные ограничения, разработан ряд алгоритмов приближенного поиска оптимальных решений -для большинства задач нахождение точного решения является сложным в вычислительном отношении. Однако развитие логистических процессов и потребность в учете новых факторов ведут к постановке новых задач, требующих, в свою очередь, применения новых не рассматривавшихся ранее методов решения.

Обозначая актуальность работ на эту тему, необходимо указать на отличие задачи в рассматриваемой постановке от классической задачи маршрутизации транспортных средств. Особенностями рассматриваемой задачи являются мультиноменклатурность и запреты на перевозку некоторых видов грузов отдельными транспортными средствами. Поставленная задача относится к классу нелинейных оптимизационных задач и является обобщением двух известных задач: задачи коммивояжера и задачи о загрузке рюкзака. Тем самым рассматриваемая задача является ЫР-сложной.

Область исследования. Задачи организации транспортировки грузов.

Цель работы. Исследование и разработка эффективных методов решения мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку.

Задачи исследования. Для достижения цели работы были поставлены и решены следующие задачи:

1. Классификация задач организации транспортировки грузов в соответствии с принципами системного анализа на основе их базовых характеристик.

2. Постановка и формализация мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку отдельных видов грузов определенными транспортными средствами.

3. Разработка алгоритма построения локально оптимального решения целочисленной мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку.

4. Разработка эвристических алгоритмов решения мультиноменклатурной оптимизационной задачи маршрутизации с ограничениями на перевозку на основе различных подходов к решению задачи коммивояжера.

5. Реализация предложенных методов на ЭВМ, экспериментальная проверка эффективности работы предложенных алгоритмов.

Методы исследования. В работе применяются методы математического программирования, теории графов, комбинаторной оптимизации, а также современная технология экспериментальных исследований с применением ЭВМ.

Информационная база исследования включает сгенерированные псевдослучайным образом по равномерному закону распределения исходные данные о заказах пунктов потребления на доставку различных видов грузов, а также о количестве и характеристиках транспортных средств. Данные о координатах пунктов потребления и базы включают 2 способа задания: 1) с помощью датчика псевдослучайных чисел, расстояния между пунктами при

этом принимаются равными евклидовым расстояниям; 2) примеры из библиотеки задачи коммивояжера (Т8РНЬ).

На защиту выносятся следующие результаты исследований:

1. Математическая модель мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку (п.2 Паспорта специальности 05.13.01).

2. Алгоритм построения локально оптимального решения мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку в случае целочисленности исходных данных (п.4 Паспорта специальности 05.13.01).

3. Эвристические алгоритмы решения мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку на основе эвристических подходов к решению задачи коммивояжера (п.4 Паспорта специальности 05.13.01).

4. Сравнительный анализ эффективности предложенных методов (п.9 Паспорта специальности 05.13.01).

Научная новизна. Получены следующие основные результаты, обладающие научной новизной:

1. Постановка и формализация (в том числе в форме задачи частично целочисленного линейного программирования) оптимизационной задачи маршрутизации транспортных средств, в которой, в отличие от известных, учтена мультиноменклатурность перевозимых грузов и запреты на перевозку некоторых видов грузов отдельными транспортными средствами.

2. Доказательство допустимости исходной задачи в случае совместности редуцированной задачи. Решение редуцированной задачи дает возможность определить план перевозок (сколько груза того или иного вида каждое транспортное средство должно доставить в каждый пункт потребления) или сделать вывод об их недопустимости.

3. Доказательство существования для любого допустимого способа

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

4. Методы и алгоритмы решения мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку. Разработан и программно реализован трехэтапный алгоритм, в котором применены различные подходы к решению задачи коммивояжера. Проведен вычислительный эксперимент для оценки эффективности предложенных алгоритмов.

Практическая и теоретическая значимость. Теоретическая значимость заключается в постановке и решении новой мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку, относящейся к классу УКР. Исследуемая задача позволила учесть ассортимент грузов, а также приспособленность транспортных средств к их перевозке. Предложенные методы и алгоритмы могут применяться для решения родственных задач организации транспортировки грузов.

Практическую ценность работы составляет определение минимальных суммарных затрат на транспортировку, плана перевозок, а также маршрутов движения транспортных средств. Это делает программную реализацию методов практически применимой для решения реальных транспортно-логистических задач на производстве. Программное обеспечение, разработанное в рамках диссертационной работы, зарегистрировано Федеральной службой по интеллектуальной собственности, патентам и товарным знакам, свидетельство № 2011613654.

Апробация работы. Работа была поддержана стипендией Президента Республики Башкортостан (2010-2011 учебный год), Российским фондом

фундаментальных исследований (проект 10-06-00001) и грантом Президента Российской Федерации для государственной поддержки ведущих научных школ Российской Федерации № НШ-65497.2010.9.

Основные результаты диссертационной работы докладывались и обсуждались на:

• четвертой Всероссийской зимней школе-семинаре аспирантов и молодых ученых "Актуальные проблемы науки и техники" (Уфа, 19-21 февраля 2009 г.)

• пятой Всероссийской зимней школе-семинаре аспирантов и молодых ученых "Актуальные проблемы науки и техники" (Уфа, 17-20 февраля 2010 г.)

• XII международной конференции "Компьютерные науки и информационные технологии" (Москва-СПб., 13-19 сентября 2010 г.)

• 33-й международной научной школе-семинаре имени академика С.С. Шаталина "Системное моделирование социально-экономических процессов" (Звенигород, 1-5 октября 2010 г.)

• 14-й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 28 февраля - 4 марта 2011 г.)

• шестой Всероссийской зимней школе-семинаре аспирантов и молодых ученых "Актуальные проблемы науки и техники" (Уфа, 15-18 февраля 2011 г.)

• VII международной научно-практической конференции "Актуальные задачи математического моделирования и информационных технологий" (Сочи, 18-25 мая 2011 г.)

• VI Специальном симпозиуме по исследованию операций, безопасности информации и технической кибернетики (Баден-Баден, 3-7 августа 2011г.)

• научных семинарах в Башкирском государственном университете, Омском филиале института математики им. C.JI. Соболева СО РАН, институте математики с вычислительным центром УНЦ РАН.

Публикации. Список публикаций автора по теме диссертации включает 13 научных трудов, в том числе 4 статьи в рецензируемых научных журналах из списка ВАК, свидетельство об официальной регистрации программного продукта, 4 публикации в трудах международных конференций. Шесть публикаций выполнено без соавторов.

Структура и объем диссертации. Диссертационная работа состоит из введения, 4 глав, разбитых на параграфы, основных результатов работы, библиографического списка литературы, включающего 109 источников, 1 приложения, содержит 7 таблиц, 24 рисунка. Общий объем работы составляет 125 страниц.

Глава 1. Анализ оптимизационных задач транспортной

логистики

1.1. Актуальность задач транспортной логистики для промышленности

Реальные логистические системы характеризуются сложными связями как внутри этих систем, так и с внешней средой. В качестве логистических связей могут выступать материальные, денежные, информационные потоки, в зависимости от направления они могут быть прямыми и обратными, по поведе�