Оптимизация планирования грузоперевозок мелкотоннажной многоассортиментной продукции: На примере химического предприятия тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Бадашкин, Владимир Александрович

• Бадашкин, Владимир Александрович
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Бадашкин, Владимир Александрович

СПИСОК ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

Глава 1.

ПРОБЛЕМЫ ПЛАНИРОВАНИЯ ГРУЗОПЕРЕВОЗОК.

1.1. Постановка задачи.

1.1.1. Практическая постановка.

1.1.2. Абстрактная формулировка задачи.

1.2. Общий обзор области исследования.

Выводы по главе

Глава 2.

ФОРМАЛИЗАЦИЯ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ.

ВОПРОС СЛОЖНОСТИ ЗАДАЧИ.

2.1. Формальное описание задачи.

2.1.1. Склады и потребители.

2.1.2. Машины.

2.1.3. Маршруты.

2.2. Поставленная задача с точки зрения теории алгоритмов.

2.3. Обоснование выбранного метода решения.

Выводы по главе 2.

Глава 3.

АЛГОРИТМ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ. АДАПТАЦИЯ МЕТОДА ВЕТВЕЙ И ГРАНИЦ.

3.1. Общая схема решения.

3.2. Оценка множества решений.

3.3. Деление множества решений на подмножества.

3.4. Улучшение построенного расписания маршрутов.

3.5. Пример работы алгоритма решения распределительной задачи. .48 Выводы по главе 3.

Глава 4.

СИСТЕМА АВТОМАТИЗИРОВАННОГО УПРАВЛЕНИЯ ГРУЗОПЕРЕВОЗКАМИ МЕЛКОТОННАЖНОЙ

МНОГОАССОРТИМЕНТНОЙ ПРОДУКЦИИ.

4.1. Функциональные модули системы.

4.1.1. Модуль оптимизации.

4.1.2. Геоинформационная система.

4.1.3. База данных кратчайших маршрутов.

4.1.4. База данных заявок.

4.1.5. Автоматизированное рабочее место диспетчера.

4.2. Задачи ГИС в системе планирования маршрутов.

4.2.1. Транспортная сеть местности.

4.2.2. Расчет и ведение системы кратчайших маршрутов между потребителями.

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

Выводы по главе 4.

Глава 5. РЕАЛИЗАЦИЯ СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПЛАНИРОВАНИЯ МАРШРУТОВ.

ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ.

5.1. Общее описание системы.

5.2. Описание процесса функционирования системы.

5.2.1. Процесс ведения системы кратчайших маршрутов.

5.3. Реализация модуля оптимизации.

5.4. Вычислительный экперимент.

5.4.1. Реальные задачи.

5.4.2. Тестовые задачи.

Выводы по главе 5.

Введение диссертации (часть автореферата) на тему «Оптимизация планирования грузоперевозок мелкотоннажной многоассортиментной продукции: На примере химического предприятия»

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

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

Типичный процесс мелкотоннажных многоассортиментных грузоперевозок состоит из следующих этапов.

1. Формирование клиентской базы.

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

2. Формирование укрупнённых маршрутов. Зарегистрированные потребители продукции формируются в кластеры по географическому признаку. Например, объединяются в группу потребители одного микрорайона (на предприятиях для обозначения таких групп часто употребляется термин «маршрут»).

3. От клиентов принимаются заказы на некоторый будущий период времени. При этом не все клиенты делают заказ. При создании заказа указывается предпочитаемое время завоза продукции.

4. На основании сделанных заказов и, исходя из имеющегося в распоряжении транспорта, планируются конкретные мар—шруты машин по потребителям. Маршруты планируются по созданным на втором этапе кластерам: сначала рассматриваются потребители, принадлежащие одной группе, после этого берутся потребители другой группы и процесс повторяется снова. Таким образом, задача оптимизации декомпозируется на несколько более мелких задач: выбирается некоторое подмножество потребителей и подмножество машин (часто одна или две) и маршруты строятся на таком сокращённом объёме исходных данных. Окончательное множество маршрутов получается объединением маршрутов, получившихся при решении подзадач. Попыток оптимизации путём построения маршрутов, которые бы включали в себя потребителей из разных кластеров, обычно не проводится.

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

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

Средства автоматизации в этом процессе носят исключительно вспомогательный характер и используются только для следующих целей:

• хранение информации о клиентах;

• распечатка накладных/путевых листов;

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

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

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

1) правдоподобность исходных данных; здесь, в первую очередь, имеется в виду наличие транспортной модели, на которой можно рассчитывать пути перемещения транспорта, которые не будут значительно отличаться от реальных путей;

2) качественное решение непосредственно самой распределительной задачи;

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

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

Целью диссертационной работы является разработка алгоритма решения распределительной задачи, позволяющего получать приемлемые решения и построение на основе этого алгоритма системы, автоматизирующей процесс планирования маршрутов транспорта. Алгоритм должен иметь настраиваемый параметр, с помощью которого можно управлять временем решения задачи. Критичные характеристики алгоритма: скорость работы (задача для 300 потребителей и трех десятков машин должна решаться примерно за 30 минут), численные решения, получаемые с помощью алгоритма, должны быть лучше решений, принимаемых человеком примерно на 10%. Критичные характеристики системы: предоставление человеку возможности вмешиваться в процесс решения задачи и корректировать его, совокупная стоимость владения, интеграция с существующими на предприятиях системами автоматизации.

Основные задачи исследования:

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

2. Формализовать поставленную задачу и определить её место в общей математической теории.

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

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

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

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

• Распределительная задача формализована для случая, объединяющего множество типовых постановок задач маршрутизации автотранспорта и учитывающего множество ограничений на режимы и расписание работы автотранспорта и потребителей продукции;

• Способ построения транспортной модели региона, представляющей собой ориентированный граф и учитывающей в качестве интегральных характеристик дорожного движения среднюю скорость перемещения и направление движения;

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

Обоснованность результатов работы обеспечивается тем, что предлагаемый алгоритм решения поставленной задачи разрабатывался с учетом последних достижений в области анализа задач VRP-класса (Vehicle Routing Problem). Алгоритм выдает более точные результаты по сравнению с решениями, получаемыми человеком, а также позволяет получать для многих тестовых задач решения, приближающиеся к оптимальным или лучшим опубликованным.

Практическую ценность работы составляют:

1. Реализация алгоритма решения задачи, позволяющая настраивать для каждой конкретной задачи характеристики «качество решения — скорость решения».

2. Методика построения транспортной модели местности. Простота модели не наносит ущерба её адекватности. Главная задача транспортной модели: быстрое построение кратчайших маршрутов между всеми парами потребителей и складов продукции.

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

Реализация результатов работы. Разработанный алгоритм и система используются в повседневной практической деятельности на предприятии: ОАО «Ивановохлеб», г.Иваново.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались: на научно-практической конференции "Традиции и перспективы подготовки торгово-экономических кадров России. Формирование экономической культуры в условиях рыночных преобразований общества." (Иваново, 2000) и на ГИС-форуме (организатор — ГИС-ассоциация, Москва, 2000).

Публикации. Основные результаты диссертационной работы изложены в работах [13, 14, 49, 50, 51].

Объём и структура работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложения, содержит 122 страницы основного текста, 23 рисунка, 129 таблиц (включая таблицы приложения).

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Бадашкин, Владимир Александрович

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

1.Распределительная задача рассмотрена в постановке, учитывающей множество ограничений.

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

2. Разработан новый простой алгоритм решения VRP-задачи. Важные преимущества данного алгоритма - возможность человеку вмешиваться в процесс решения, а также возможность управлять алгоритмом, настраивая отношение скорость решения / качество получаемого ре-шения.

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

Математически транспортная модель - это ориентирован-ный связный граф, к каждой ветке которого привязана информация о средней скорости на данной ветке и воз-можность перемещения по ней вперед/назад.

4. На базе разработанного алгоритма и транспортной модели реализована система по планированию маршрутов транспорта по развозке продукции.

5. Апробация разработанной системы доказала ее высокую эффективность. Качество решения, получаемого систе-мой, в среднем выше качества решения, получаемого че-ловеком на 1015%.

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

6. В работе указаны существующие недостатки разработанного алгоритма и направления для дальнейшего исследования с целью минимизации указанных недостатков.

Разработанная при участии и под руководством автора система планирования маршрутов внедрена в АО "Ивановохлеб" и ОАО "Русский хлеб", г.Кострома.

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

118

ЗАКЛЮЧЕНИЕ

В диссертационной работе рассмотрены вопросы автоматизации процесса проектирования систем маршрутов в задачах, имеющих комбинаторный характер.

Научная новизна работы заключается в следующем:

1. Распределительная задача рассмотрена в постановке, учитывающей множество ограничений на машины и торговые точки;

2. В качестве критерия при решении задачи используются удельные затраты на маршрутах;

3. Разработана простая транспортная модель, позволяющая строить близкие к реальности маршруты;

4. Разработан новый алгоритм решения распределительной задачи;

5. На базе разработанного алгоритма построена в внедрена система управления мелкотоннажными грузоперевозками.

Список литературы диссертационного исследования кандидат технических наук Бадашкин, Владимир Александрович, 2006 год

1. Berge С. Principles of Combinatorics. New York, London: Academic Press,1971.

2. Davis M. Unsolvable problems, A review, Proc. Sympos. Math. Theory of Automata, N.Y., 1962.

3. Gapp W., Mannkekar P.S., Mitten L.G., Sequencing Operations to Minimize1.-Process Inventory Costs, Management Sci., 11, No.3, 476-484 (1965).

4. Gilmore P., Gomory R.E., Sequencing of One State-Variable Machine, Operations Res., 12, No5, 655-679 (1964).

5. Jackson J.R., An Extension of Jonson's Results on Job-Lot Sheduling, Nav.

6. Res. Log. Quart., 7, No.3, 201-204 (1956).

7. Johnson S.M., Optimal Two- and Three-Stage Production Shedules with

8. Setup Times Included, Nav. Res. Log. Quart., 1, 61-68 (1954).

9. Miller R.E., Tatcher J.W. Complexity of computer computations, Plenum1. Press, New York, 1972.

10. Адельсон-Вельский Г.М., Диниц E.A., Карзанов А.Б. Потоковые алгоритмы.1. М.: Наука, 1975.

11. Айгнер М. Комбинаторная теория. — М.: Мир, 1982.

12. Алгебраическая теория автоматов, языков и полугрупп. Под ред. М.А.Арбиба. М.: Статистика, 1975.

13. Алгоритмические исследования в комбинаторике. Сборник статей., — М.: Наука, 1978.

14. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

15. Бадашкин В.А., Косяков С.В. Опыт создания системы планирования грузоперевозок по городу с использованием ГИС. // Информационный бюллетень ГИС-Ассоциации. №3, 2000 г. стр. 61-62.

16. Бардзинь Я.М. Об одном классе машин Тьюринга (машины Минского), Алгебра и логика (семинар) 1, N6, 1962, 42-51.

17. Бахтин А.Е. Дискретные задачи производственно-транспортного типа.

18. Беллман Р. Динамическое программирование. — М.: ИЛ, 1960.

19. Берж К. Теория графов и ее применения. М.: Изд-во иностранной литературы, 1962.

20. Васильева Е.М., Левит Б.Ю., Лившиц В.Н. Нелинейные транспортные задачи на сетях М.: "Финансы и статистика", 1981.

21. Виленкин Н.Я. Комбинаторика. — М.: Наука, 1969.

22. Виленкин Н.Я. Популярная комбинаторика. — М.: Наука, 1975.

23. Гильберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики. — М.: Наука, 1979.

24. Глушков В.М. Теория алгоритмов. — Киев, 1961.

25. Горбатов В.А. Основы дискретной математики. — М.: ВШ, 1986.

26. Горский Д.П. Логика. — М.: Учпедгиз, 1963.

27. Грин Д., Кнут Д. Математические методы анализа алгоритмов. — М.: Мир, 1987.

28. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов М.: "Мир", 1981.

29. Дискретная математика и математические вопросы кибернетики. Т.1 / Под общей редакцией С.В.Яблонского и О.Б.Лупанова. — М.: Наука, 1974.

30. Евстигнеев В.А., Касьянов В.Н. Теория графов. Алгоритмы обработки бесконтурных графов. — Новосибирск: Наука, 1998.

31. Ежов И.И. и др. Элементы комбинаторики. — М.: Наука, 1977.

32. Зуховицкий С.И., Радчик И.А. Математические методы сетевого планирования. — М.: Наука, 1965.

33. Зыков А.А. Теория конечных графов. — Новосибирск: Наука, 1969.

34. Исследование операций. В 2-х томах. Под ред. Дж.Моудера и С.Элмаграби. -М.: Мир, 1981.

35. Исследования по дискретной математике. — М.: Наука, 1973.

36. Карп P.M. Сводимость комбинаторных проблем. — Кибернетический сборник, вып. 12, М.: Мир, 1975, с.16-38.

37. Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. М.: ИЛ, 1964.

38. Клини С. Введение в метаматематику. — М.: ИЛ, 1957.

39. Кнут Д. Искусство программирования для ЭВМ. В 2-х томах. — М.: Мир, 1976.

40. Колмогоров А.Н., Успенский В.А. К определению алгоритма, Успехи матем. наук 13, N4 (1958), 3-28.

41. Компьютер и задачи выбора / Автор предисл. Ю.И.Журавлев. М.: Наука, 1989.

42. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука, 1975.

43. Коршунов Ю.М. Математические основы кибернетики М.: "Энергоатомиздат", 1987.

44. Кострикин А.И. Введение в алгебру. — М.: Наука, 1977.

45. Кратко М.И. Формальные исчисления Поста и конечные автоматы. — Проблемы кибернетики, вып. 17. М.: Физматгиз, 1966, с.41-65.

46. Кузнецов А.В. Руководство к решению задач по математическому программированию.

47. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера М.: Энергия, 1980.

48. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. М.:ВШ, 1980.

49. Лабутин А.Н., Бадашкин В.А., Игнатьев Е.Б. Оптимизация грузоперевозок мелкотоннажной разноассортиментной продукции автомобильным транспортом. // Вестник компьютерных и информационных технологий, №6, 2004 г. Москва.

50. Левин Л.А. Об универсальных задачах перебора. — Проблемы передачи информации, 1973, N3, с. 115-116.

51. Лескин А.Л. Сети Петри в моделировании и управлении Л.: Наука, 1989

52. Линдон Р.К., Шупп П. Комбинаторная теория групп. — М.: Мир, 1980.

53. Липский В. Комбинаторика для программистов. — М.: Мир, 1988.

54. Майника Э. Алгоритмы оптимизации на сетях и графах.

55. Мальцев А.И. Алгоритмы и рекурсивные функции. — М.: Наука, 1965.

56. Марков А.А. Теория алгоритмов. — М.: Изд-во АН СССР, 1954.

57. Маркова Е.В., Лисенков А.Н. Комбинаторные планы в задачах многофакторного эксперимента М.: "Наука", 1979.

58. Машины Тьюринга и рекурсивные функции / Эббинхауз Г.Д., Якобе К., Ман Ф.К., Хермес Г.М. М.: Мир, 1972.

59. Моделирование пассажиропотоков в транспортной системе. Пер. с англ. Е.М.Шлафштейна М.: "Транспорт", 1982.

60. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. -Новосибирск: Наука, 1977.

61. Нечепуренко М.И. и др. Алгоритмы и программы решения задач на графах и сетях Новосибирск: Наука, 1990.

62. Пискунов Н.С. Дифференциальное и интегральное исчисления. — М.: Наука, 1985.

63. Прикладная комбинаторная математика. Сб. статей. — М.: Мир, 1968.

64. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: Теория и практика. — М.: Мир, 1980.

65. Риордан Дж. Введение в комбинаторный анализ. — М.: ИЛ, 1963.

66. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.

67. Савельев JI.Я. Комбинаторика и вероятность. — Новосибирск: Наука, 1975.

68. Сачков В.Н. Комбинаторные методы дискретной математики. — М.: Наука, 1977.

69. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984.

70. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука, 1989.

71. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975.

72. Теория расписаний и вычислительные машины. Под ред. Э.Г.Коффмана. М.: Наука, 1984.

73. Трахтенброт Б.А. Алгоритмы и машинное решение задач. — М.: Гос. изд-во Физ-мат лит-ры, 1960.

74. Финкельштейн Ю.Ю., Корбут А.А. Дискретное программирование М.: Наука, 1969.

75. Холл М. Комбинаторика. — М.: Мир, 1970.

76. Ху Т. Целочисленное программирование и потоки в сетях М.: Мир, 1974.

77. Шафиркин Б.И. Единая транспортная сеть и взаимодействие различных видов транспорта М.: ВШ, 1977.

78. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория, методы и приложения. — М.: Наука, 1969.123