Содержание к диссертации
список используемых сокращений 5
ВВЕДЕНИЕ 6
Глава 1.
ПРОБЛЕМЫ ПЛАНИРОВАНИЯ ГРУЗОПЕРЕВОЗОК 12
1.1. Постановка задачи 13
Практическая постановка 14
Абстрактная формулировка задачи 18
1.2. Общий обзор области исследования 19
Выводы по главе 1 22
Глава 2.
ФОРМАЛИЗАЦИЯ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ.
ВОПРОС СЛОЖНОСТИ ЗАДАЧИ 23
2.1. Формальное описание задачи 23
Склады и потребители 23
Машины , 25
Маршруты 26
2.2. Поставленная задача с точки зрения
теории алгоритмов 31
2.3. Обоснование выбранного метода решения 32
Выводы по главе 2 34
Глава 3.
АЛГОРИТМ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ.
АДАПТАЦИЯ МЕТОДА ВЕТВЕЙ И ГРАНИЦ 35
Общая схема решения 35
Оценка множества решений 40
Деление множества решений на подмножества 45
Улучшение построенного расписания маршрутов 47
Пример работы алгоритма решения распределительной задачи. ..48 Выводы по главе 3 53
Глава 4.
СИСТЕМА АВТОМАТИЗИРОВАННОГО УПРАВЛЕНИЯ
ГРУЗОПЕРЕВОЗКАМИ МЕЛКОТОННАЖНОЙ
МНОГОАССОРТИМЕНТНОЙ ПРОДУКЦИИ 54
4.1. Функциональные модули системы 57
Модуль оптимизации 57
Геоинформационная система 57
База данных кратчайших маршрутов 57
База данных заявок 58
4.1.5. Автоматизированное рабочее место диспетчера 58
4.2. Задачи ГИС в системе планирования маршрутов 60
Транспортная сеть местности 61
Расчет и ведение системы
кратчайших маршрутов между потребителями 62
4.2.3. Отображение результатов расчета
оптимизационного модуля 65
Выводы по главе 4 66
Глава 5. РЕАЛИЗАЦИЯ СИСТЕМЫ АВТОМАТИЗИРОВАННОГО
ПЛАНИРОВАНИЯ МАРШРУТОВ.
ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ 67
Общее описание системы 67
Описание процесса функционирования системы 69
5.2.1. Процесс ведения системы кратчайших маршрутов 70
Реализация модуля оптимизации 75
Вычислительный экперимент 76
Реальные задачи 77
Тестовые задачи 112
Выводы по главе 5 114
ЗАКЛЮЧЕНИЕ 116
СПИСОК ЛИТЕРАТУРЫ 118
ПРИЛОЖЕНИЕ А.
Вычислительный эксперимент 123
Задачи с 25 потребителями 124
Задачи с 50 потребителями 139
Задачи с 100 потребителями 159
5 СПИСОК ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ
АРМ — автоматизированное рабочее место.
ИГТ — институт геоинформационных технологий.
ИГХТУ — Ивановский государственный химико-технологический
университет
ИГЭУ — Ивановский государственный энергетический
университет.
ПОКС — программное обеспечение компьютерных систем.
VRP — Vehicle Routing Problem.
Введение к работе
Актуальность темы диссертации. Многие предприятия химической промышленности выпускают мелкотоннажную многоассортиментную продукцию, имеющую фасовку различного объема и массы, что обусловлено технологией производства и заказами потребителей. Эти предприятия самостоятельно или с привлечением специализированных предприятий занимаются доставкой продукции потребителям, часто расположенным в пределах одного региона. Затраты на транспортировку продукции зачастую сравнимы с её себестоимостью и составляют значительную долю в конечной цене продукции. Эти обстоятельства обуславливают актуальность постановки и решения задачи оптимизации планирования грузоперевозок.
Задачи такого характера актуальны и для ряда других отраслей промышленности: заводы пищевой промышленности; доставка почты; предприятия оптовой и розничной торговли; автотранспортные, фармацевтические и другие предприятия.
Типичный процесс мелкотоннажных многоассортиментных грузоперевозок состоит из следующих этапов.
1. Формирование клиентской базы.
Перед тем, как начать работать с клиентом, предприятие фиксирует его в своей клиентской базе: на этом этапе определяются координаты клиента (адрес или адреса торговых точек).
Формирование укрупнённых маршрутов. Зарегистрированные потребители продукции формируются в кластеры по географическому признаку. Например, объединяются в группу потребители одного микрорайона (на предприятиях для обозначения таких групп часто употребляется термин «маршрут»).
От клиентов принимаются заказы на некоторый будущий период времени. При этом не все клиенты делают заказ. При создании заказа указывается предпочитаемое время завоза продукции.
На основании сделанных заказов и, исходя из имеющегося в распоряжении транспорта, планируются конкретные мар—шруты машин по потребителям. Маршруты планируются по созданным на втором этапе кластерам: сначала рассматриваются потребители,
7 принадлежащие одной группе, после этого берутся потребители другой группы и процесс повторяется снова. Таким образом, задача оптимизации декомпозируется на несколько более мелких задач: выбирается некоторое подмножество потребителей и подмножество машин (часто одна или две) и маршруты строятся на таком сокращённом объёме исходных данных. Окончательное множество маршрутов получается объединением маршрутов, получившихся при решении подзадач. Попыток оптимизации путём построения маршрутов, которые бы включали в себя потребителей из разных кластеров, обычно не проводится. 5. Управление самими грузоперевозками: распечатка накладных, выдача заданий водителям, контроль за развозкой продукции, устранение нештатных ситуаций (поломки машин, отказ клиентов от приёма продукции и т.д.). Рассмотренный процесс характерен для предприятий с постоянной клиентской базой (химическая, пищевая, фармацевтическая промышленность). В случае предприятий розничной торговли первые четыре этапа объединяются в один.
Средства автоматизации в этом процессе носят исключительно вспомогательный характер и используются только для следующих целей:
хранение информации о клиентах;
распечатка накладных/путевых листов;
проведение несложных расчетов по высчитыванию общего объёма развозимой продукции.
В таком режиме работы на диспетчера возлагается очень большая ответственность: необходимо чётко и слаженно управлять большим количеством автотранспорта, такая работа носит напряжённый характер. Кроме этого, у такого подхода есть и другие минусы, один из самых больших — это невозможность отследить перемещения водителей по маршрутам. Это часто приводит к перерасходу средств предприятия на оплату автотранспорта. Таким образом, основные финансовые потери в процессе управления мелкотоннажными грузоперевозками связаны с двумя факторами: плохое, далекое от оптимального, планирование маршрутов автотранспорта и отсутствие контроля за перемещением машин.
8 Учитывая всё вышесказанное, можно с уверенностью утверждать, что особую актуальность приобретают работы, позволяющие повысить контроль над транспортными средствами, а также сократить затраты на перевозку и затраты на персонал, занимающийся этими перевозками. Обозначая актуальность работ на эту тему, необходимо указать на отличие задачи в рассматриваемой постановке от классической транспортной задачи. В нашей постановке ёмкость транспортного средства значительно превосходит потребность в продукции одного потребителя. Это принципиально меняет характер задачи: вместо значений потоков на дугах сети (классическая транспортная задача) нас интересуют перестановки потребителей в рамках маршрута. Таким образом, мы решаем комбинаторную задачу. Эффективность системы, автоматизирующей процесс управления мелкотоннажными перевозками, зависит, в основном, от качества решения трёх проблем:
правдоподобность исходных данных; здесь, в первую очередь, имеется в виду наличие транспортной модели, на которой можно рассчитывать пути перемещения транспорта, которые не будут значительно отличаться от реальных путей;
качественное решение непосредственно самой распределительной задачи;
обеспечение грамотного взаимодействия человека и программного комплекса, который должен поддерживать возможность постоянного вмешательства человека в процесс решения распределительной задачи.
Объектом исследования в работе является процесс и система управления транспортом при организации мелкотоннажных перевозок, а предме—том исследования выбран алгоритм решения распределительной задачи как самое узкое место в указанной системе управления. При нахождении приемлемого решения указанных проблем можно добиться значительной экономии финансовых средств предприятий, повысить управляемость транспортным парком, что и обеспечивает актуальность темы настоящей работы.
Целью диссертационной работы является разработка алгоритма решения распределительной задачи, позволяющего получать приемлемые решения и построение на основе этого алгоритма системы, автоматизи-
9 рующей процесс планирования маршрутов транспорта. Алгоритм должен иметь настраиваемый параметр, с помощью которого можно управлять временем решения задачи. Критичные характеристики алгоритма: скорость работы (задача для 300 потребителей и трех десятков машин должна решаться примерно за 30 минут), численные решения, получаемые с помощью алгоритма, должны быть лучше решений, принимаемых человеком примерно на 10%. Критичные характеристики системы: предоставление человеку возможности вмешиваться в процесс решения задачи и корректировать его, совокупная стоимость владения, интеграция с существующими на предприятиях системами автоматизации. Основные задачи исследования:
Разработка максимально упрощенной модели транспортной сети города. При этом модель должна быть достаточно адекватной: время и километраж маршрута должны максимально соответствовать действительности.
Формализовать поставленную задачу и определить её место в общей математической теории.
Разработать алгоритм поиска приемлемых решений по построению систем маршрутов транспорта.
Разработка и внедрение в постоянную эксплуатацию на базе предложенного алгоритма системы автоматизированного управления грузоперевозками.
Основные методы исследования. При решении поставленных задач были использованы результаты, достигнутые в разделах теории исследования операций: теории множеств, теории графов, теории расписаний, теории вычислительных алгоритмов, комбинаторике.
Научная новизна результатов работы. Основными научными результатами работы, вынесенными на защиту, являются:
Распределительная задача формализована для случая, объединяющего множество типовых постановок задач маршрутизации автотранспорта и учитывающего множество ограничений на режимы и расписание работы автотранспорта и потребителей продукции;
Способ построения транспортной модели региона, представляющей собой ориентированный граф и учитывающей в качестве интегральных характеристик дорожного движения среднюю скорость перемещения и направление движения;
Разработан алгоритм решения распределительной задачи на базе метода ветвей и границ, включающий эвристические правила о: преимуществе того или иного маршрута среди множества других и неоптимальности отдельных ветвей маршрутов;
Обоснованность результатов работы обеспечивается тем, что предлагаемый алгоритм решения поставленной задачи разрабатывался с учетом последних достижений в области анализа задач VRP-класса (Vehicle Routing Problem). Алгоритм выдает более точные результаты по сравнению с решениями, получаемыми человеком, а также позволяет получать для многих тестовых задач решения, приближающиеся к оптимальным или лучшим опубликованным.
Практическую ценность работы составляют:
Реализация алгоритма решения задачи, позволяющая настраивать для каждой конкретной задачи характеристики «качество решения — скорость решения».
Методика построения транспортной модели местности. Простота модели не наносит ущерба её адекватности. Главная задача транспортной модели: быстрое построение кратчайших маршрутов между всеми парами потребителей и складов продукции.
На базе разработанного алгоритма построена и внедрена система управления мелкотоннажными многоассортиментными грузоперевозками химической продукции. Главные эффекты при внедрении системы: снижение затрат за счёт предложения более эффективных решений по системам маршрутов транспорта и качественное увеличение контроля за транспортными средствами благодаря предварительному автоматическому составлению планов перемещений для водителей.
Реализация результатов работы. Разработанный алгоритм и система используются в повседневной практической деятельности на предприятии: ОАО «Ивановохлеб», г.Иваново.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались: на научно-практической конференции "Традиции и перспективы подготовки торгово-экономических кадров России. Формирование экономической культуры в условиях рыночных преобразований общества." (Иваново, 2000) и на ГИС-форуме (организатор — ГИС-ассоциация, Москва, 2000).
Публикации. Основные результаты диссертационной работы изложены в работах [13, 14, 49, 50, 51].
Объём и структура работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложения, содержит 122 страницы основного текста, 23 рисунка, 129 таблиц (включая таблицы приложения).
Данная диссертационная работа в части алгоритма решения VRP-задачи является продолжением и развитием идей и методов, используемых для решения задач в теории расписаний и теории алгоритмов. Большое влияние на содержание работы оказали труды В.С.Танаева [71, 72, 73], В.С.Гордона [22], В.В.Шкурбы [20], Р.М.Карпа [36], А.Ахо, Дж.Хопкрофта и Дж.Ульмана [12], а также совместный труд американских специалистов в области исследования операций [34].
