Маршрутизация транспортного потока с ограничением по грузоподъемности

ВВЕДЕНИЕ
Успех любого предприятия, занятого транспортировкой грузов, всегда связан с эффективным принятием решений в области транспортной логистики. Настоящая дипломная работа посвящена исследованию одной из наиболее важных задач в данной области – исследованию формирования маршрутов доставки груза клиентам некоторым количеством транспортных средств с обязательным возвращением в исходный пункт после окончания поездки. Практическая значимость рассмотрения данной задачи связана с тем, что указанная проблема возникает во всех компаниях, занимающихся транспортировкой продукции от места производства к местам потребления, а также осуществляющих перевозку однотипных товаров с некоторого склада до точек розничной торговли.
Математическая формулировка данной задачи известна как задача маршрутизации транспорта, ЗМТ (Vehicle Routing Problem, VRP). Цель решения ЗМТ состоит в минимизации общей длины маршрутов транспортных средств, обслуживающих клиентов сети. Данный класс задач является обобщением задачи коммивояжера на случай построения нескольких замкнутых маршрутов, имеющих начало и конец в одной общей вершине. Задача маршрутизации транспорта принадлежит к классу задач дискретной оптимизации и являются NP-трудными, что означает, что вычислительная сложность задачи имеет экспоненциальную зависимость от размера входных данных, а именно от количества клиентов, входящих в рассматриваемую транспортную сеть.
Все методы решения задач маршрутизации транспорта можно разделить на следующие группы:
1) Точные методы.
Методы данной группы основываются на переборе всех возможных решений, пока не будет найдено оптимальное. Примерами таких методов могут служить метод полного перебора, метод ветвей и границ.

2) Эвристические методы.
Осуществляют относительно ограниченный поиск по пространству решений. Также такие методы называются классическими. В рамках рассматриваемой группы могут быть выделены две подгруппы.
2.1) Конструктивные методы.
Методы, принадлежащие данной подгруппе, осуществляют постепенное построение подходящего решения в зависимости от влияния каждого шага на значение целевой функции. Отличительной чертой таких алгоритмов является то, что они не предусматривают возможности дальнейшего улучшения уже построенного решения.
2.2) Двухфазные (кластерные) алгоритмы.
При использовании методов данной группы задача разделяется на две части: разбиение вершин по кластерам и формирование порядка обхода вершин в каждом полученном кластере.
3) Метаэвристические методы.
В основе данных методов лежит тщательное изучение наиболее перспективных частей пространства решений. Такие алгоритмы являются итеративными, на каждой итерации осуществляется переход от одного решения к другому до тех пор, пока не будет выполнено некоторое условие остановки вычислений. Важной особенностью таких методов является способность преодоления локального минимума и продолжения поиска.
В связи с тем, что задачи маршрутизации являются NP-трудными, применение точных методов решения является затруднительным – из-за чрезмерного быстрого роста времени вычислений их невозможно применять для задач с более чем 25 вершинами. Реальные же транспортные сети могут включать в себя гораздо большее количество узлов. Поэтому наибольшее внимание уделяется приближенным алгоритмам, позволяющим найти приемлемое решение за полиномиальное время. В настоящее время ученые и специалисты всего мира занимаются усовершенствованием имеющихся и поиском новых методов, которые позволят получить еще большую производительность алгоритмов и будут в состоянии находить новые лучшие решения для задачи маршрутизации транспортных средств.
На основе различных методов создаются инструментальные средства, специализирующиеся на решении поставленной задачи. Рассмотрим существующие программные комплексы, применяемые ведущими фирмами, работающими в области транспортной логистики.
 ArcLogistics 9.3.
Данный программный продукт разработан известной американской фирмой ESRI [1]. Корпорация ESRI (США) – один из мировых лидеров в разработке, создании и продвижении геоинформационных систем. ArcLogistics 9.3 — это инструмент для планирования и оптимизации работы парка транспортных средств: импорта заказов, расчета оптимальных маршрутов, создания маршрутных листов, построения отчетов, анализа эффективности работы. Основными преимуществами ArcLogistics являются: распределение заказов по парку транспортных средств, наличие дорожных данных на всю территорию Европы (включая Россию) и Северной Америки, использование множества складов, разнообразные отчеты. Рассматриваемый программный комплекс позволяет учитывать временные окна клиентов и поставщиков, время простоя транспорта, вместимость транспорта.
 TruckStops.
TruckStops – программный продукт, разработанный фирмой MicroAnalytics (США) [2]. TruckStops – программное обеспечение для маршрутизации транспортных средств и планирования. Оно спроектировано для компаний, использующих 5 или больше транспортных средств. Использование TruckStops позволяет фирмам уменьшать стоимость поставки, улучшает предоставляемый клиенту сервис, производит эффективные по стоимости маршруты, увеличивает административное управление.
 Деловая карта.
Деловая карта – программный продукт, разработанный фирмой ИНГИТ (Россия) [3]. Она обладает мощным и гибким механизмом расчета доставки грузов. За счет своей гибкости этот механизм можно применить практически к любой конкретной задаче - развозка грузов с центрального склада, завоз грузов из разных мест на центральный склад, развозка с нескольких складов, завоз на несколько складов, а также к задачам, не имеющим центральных точек - доставка корреспонденции из разных мест в разные места, перевозка мебели при переездах и т.д. Однако у гибкости есть и обратная сторона - для постановки задачи необходимо большое количество входных данных. Главная особенность данной программы – она встраивается и работает с системой 1С.
Однако программные продукты всех этих фирм имеют один общий недостаток – их покупка влечет за собой огромную переплату за функциональные возможности системы, которые являются дополнительными расширениями и не являются необходимыми при решении рассматриваемой задачи. Кроме того, заказ и установка продуктов зарубежных производителей повлекут за собой дополнительные транспортные расходы, и их цена значительно возрастет. Сохраняя авторское право, любой купленный программный продукт поставляется без исходных кодов программных модулей, и каждая дополнительная настройка или изменение каких-либо условий работы связаны с дополнительной оплатой. Кроме того ни для одного рассмотренного программного средства нет возможности получить достоверную и полную информацию о методе, использующемся в программе, и это не позволяет оценить эффективность использования данного программного продукта.
Из всего выше изложенного видно, что исследование ЗМТ является актуальной проблемой в транспортной логистике. Интерес к данной теме вызван практической значимостью в сочетании со значительной сложностью. Особое внимание к рассматриваемым задачам в практическом применении объясняется тем, что по разным оценкам от 30 до 50 процентов всех затрат на логистику связано с транспортными издержками [4]. Формирование рациональных маршрутов помогает добиться сокращения не только общего расстояния и, как следствие, пробега транспортных средств, но и временных, и материальных затрат. Кроме того оптимизация процесса доставки ведет к снижению товарно-производственных запасов на складах, что приводит к оптимизации всей совокупности логистических мероприятий.
Целью данной дипломной работы является исследование отдельной разновидности ЗМТ – задачи с дополнительным ограничением, связанным с грузоподъемностью транспортных средств. Поставленная цель достигается путем решения ряда задач, из которых основными являются: формализация подхода к исследуемому классу ЗМТ путем построения математической модели, а также анализ способов решения выделенного класса с применением полученных знаний на практике.

ВВЕДЕНИЕ 5
1ЗАДАЧА МАРШРУТИЗАЦИИ ТРАНСПОРТА С ОГРАНИЧЕНИЕМ ПО ГРУЗОПОДЪЕМНОСТИ 9
1.1МАТЕМАТИЧЕСКАЯ МОДЕЛЬ 10
1.2ПОСТАНОВКА ПРАКТИЧЕСКОЙ ЗАДАЧИ 12
2ТОЧНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА 15
2.1ОСНОВНЫЕ ХАРАКТЕРИСТИКИ ТОЧНЫХ МЕТОДОВ 15
2.2МЕТОД ПОЛНОГО ПЕРЕБОРА. АЛГОРИТМ ПРИМЕНЕНИЯ В ЗАДАЧАХ С УЧЕТОМ ГРУЗОПОДЪЕМНОСТИ 17
2.3РЕШЕНИЕ ПРАКТИЧЕСКОЙ ЗАДАЧИ. АНАЛИЗ РЕЗУЛЬТАТОВ 21
3ЭВРИСТИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА 24
3.1КОНСТРУКТИВНЫЕ ЭВРИСТИЧЕСКИЕ МЕТОДЫ НА ПРИМЕРЕ АЛГОРИТМА КЛАРКА-РАЙТА 25
3.2КЛАСТЕРНЫЕ ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ. МЕТОД ФИШЕРА-ДЖЕКУМЕРА 27
3.3МОДИФИКАЦИЯ МЕТОДА ФИШЕРА-ДЖЕКУМЕРА. РАЗРАБОТКА АЛГОРИТМА НАЧАЛЬНОГО ЗАПОЛНЕНИЯ КЛАСТЕРОВ 29
3.4РЕШЕНИЕ ПРАКТИЧЕСКОЙ ЗАДАЧИ. АНАЛИЗ РЕЗУЛЬТАТОВ 31
4МЕТАЭВРИСТИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА 35
4.1ГЕНЕТИЧЕСКИЙ АЛГОРИТМ КАК ПРИМЕР ПРИМЕНЕНИЯ МЕТАЭВРИСТИК В РЕШЕНИИ ЗАДАЧ С УЧЕТОМ ГРУЗОПОДЪЕМНОСТИ 36
4.2РЕШЕНИЕ ПРАКТИЧЕСКОЙ ЗАДАЧИ. АНАЛИЗ РЕЗУЛЬТАТОВ 41
5БЕЗОПАСНОСТЬ И САНИТАРНО-ГИГИЕНИЧЕСКИЕ УСЛОВИЯ ТРУДА НА РАБОЧЕМ МЕСТЕ ПОЛЬЗОВАТЕЛЯ ПЭВМ 44
5.1ХАРАКТЕРИСТИКА САНПИН УСЛОВИЙ ТРУДА СОГЛАСНО ГОСТ 12.005-88 44
5.2РАСЧЕТ ПАРАМЕТРОВ МИКРОКЛИМАТА НА РАБОЧЕМ МЕСТЕ 45
5.3АНАЛИЗ И РАСЧЕТ МЕР ПО ОБЕСПЕЧЕНИЮ ЭЛЕКТРОБЕЗОПАСНОСТИ 55
5.4 АНАЛИЗ И РАСЧЕТ МЕР ПО ОБЕСПЕЧЕНИЮ ШУМОПОДАВЛЕНИЯ 59
заключение

Данная дипломная работа посвящена исследованию одной из наиболее насущных проблем, связанных с принятием решений в области транспортной логистики. А именно задаче маршрутизации транспорта, целью решения которой является формирование наиболее эффективного набора маршрутов для доставки заказов клиентам компании-перевозчика, обеспечивающего наименьшие затраты. В связи с тем, что детальное знакомство с поставленной проблемой показало существование достаточно широкого круга специфических разновидностей ЗМТ, было принято решение о выборе в качестве предмета исследования отдельного класса задачи – с ограничением на грузоподъемность, всегда имеющим место в реальных жизненных ситуациях. Следствием такого выбора явилась необходимость формализации содержательной постановки задачи. С этой целью в первой главе была построена математическая модель, приведшая все требования к задаче в строго определенную форму. Использование построенной модели в дальнейшем позволило сформировать единый подход к изложению методов решения проблемы маршрутизации.
Исследование поставленной задачи было проведено с позиции анализа ее разрешимости известными методами, а также анализа возможности практического применения каждого из них. Общее число групп, на которые можно разделить все методы решения ЗМТ, невелико. Это позволило выделить на каждую группу отдельную главу работы для более подробного рассмотрения.
Анализ первой группы методов – точных – показал, что они пригодны для решения задач маршрутизации с небольшим числом клиентов (n

1. www.esri-cis.ru
2. www.bestroutes.com
3. www.ingit.ru
4. Сумец А.М. Логистика: теория, ситуации, практические задания: учебное пособие. М.: Альфа-Пресс, 2008.
5. Меламед И.И. Задача коммивояжера. Приближенные алгоритмы./И.И. Меламед, С. Сергеев, И. Сигал //Автоматика и телемеханика, 1989, №4.
6. Гэри В., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
7. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
8. Потемкин В.Г. Введение в MATLAB. М.: Диалог-МИФИ, 2000.
9. Clarke G. Scheduling of vehicles from a central depot to a number of delivery points/ G. Clarke, J.W. Wright // Operation Reserch, 1964, №12.
10. Fisher M.L. A generalized assignment heuristic for vehicle routing./M.L. Fisher, R. Jaikumar// Networks, 1981, №11.
11. Олбрайт К. Моделирование с помощью Microsoft Excel и VBA: разработка систем принятия решений /перевод с англ. М.: Вильямс, 2005.
12. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: Физматлит, 2003.
13. Бочкарев А.А. Планирование и моделирование цепи поставок. М.: Альфа-Пресс, 2008.
14. СанПиН 2.2.2/2.4.1340-03 «Гигиенические требования к персональным электронно-вычислительным машинам и организации работы».
15. ГОСТ 12.1.005-88 «Система стандартов безопасности труда. Общие санитарно-гигиенические требования к воздуху рабочей зоны».