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

На правах рукописи Бадашкин Владимир Александрович

ОПТИМИЗАЦИЯ ПЛАНИРОВАНИЯ ГРУЗОПЕРЕВОЗОК МЕЛКОТОННАЖНОЙ МНОГОАССОРТИМЕНТНОЙ ПРОДУКЦИИ (на примере химического предприятия)

Специальность:

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

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Иваново 2006

Работа выполнена в Ивановском государственном химико-технологическом университете и Ивановском государственном энергетическом университете.

Научный руководитель:

доктор технических наук, профессор Лабутин Александр Николаевич.

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

доктор технических наук, профессор Бытев Донат Олегович; доктор технических наук, профессор Холодное Владислав Алексеевич.

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

Ивановский государственный университет.

\ У"- '__на заседании диссертационного совета Д 212.063Ю5 при

ГОУ ВПО «Ивановский государственный химико-технологический университет» по адресу: 153460, г.Иваново, пр.Ф.Энгельса, д.7.

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

Зашита состоится

в_часов в аудитории

Автореферат разослан \

Ученый секретарь диссертационного совета,

д. ф.-м. н., профессор

Г.А.Зуева

Тогяё

1

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

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

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

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

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

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

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

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

4. На основании сделанных заказов и, исходя из имеющегося в распоряжении транспорта, планируются конкретные маршруты машин по потребителям. Маршруты планируются по созданным на втором этапе кластерам: сначала рассматриваются потребители, принадлежащие одной группе, после этого берутся потребители другой группы и процесс повторяется снова. Таким образом, задача оптимизации декомпозируется на несколько более мелких задач: выбирается некоторое подмножество потребителей и подмножество машин (часто одна или двсПр^ /£№ЖЯЯ|на

БИБЛИОТЕКА С.-Петербург 0 3 200£акт

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Методика построения транспортной модели местности. Простота модели не наносит ущерба её адекватности. Главная задача тран-

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

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

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

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

Публикации. По теме диссертации опубликовано 5 печатных работ.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

В данной работе указанная задача рассматривается в нижеследующей постановке. Допустим, предприятие занимается выпуском какой-то мелкотоннажной многоассортиментной продукции, которая может, к тому же, измеряться в разных единицах (объёмных и весовых). От потребителей, распределённых по местности, приходит заказ на продукцию, причём рассматривается ограниченный временной промежуток (допустим, день), за-

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

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

■ ограничение на длительность рабочего дня водителя: обычно ра- ( бочий день длится восемь или десять часов;

■ каждую заявку необходимо удовлетворить за один приезд мАшины: то есть вся продукция, заказанная одним потребителем, должна поместиться в одну машину;

■ некоторые машины, нанимаемые предприятием для развозки продукции у сторонних организаций, могут быть доступны только с определённого часа: например, химзавод хочет заказать у организации X две машины на следующий день для развозки продукции, эти машины могут приехать, но одна из них - только в 11 часов, а другая - в 13, так как до этого времени они будут заняты другими перевозками;

■ для разных типов машин (грузовые и легковые) могут строиться разные маршруты между торговыми точками: это ограничение обусловлено тем, что некоторые дороги могут быть закрыты для проезда грузовых автомобилей;

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

о типа машины;

о вида перевезённой продукции; '

о веса перевезённой продукции; о накатанного километража; о затраченного времени.

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

всех потребителей, минимизировав суммарную стоимость маршрутов Существуют несколько основных разновидностей УЯР-задачи, каждая из которых отличается некоторыми изменениями в формулировке: ограничениями на ёмкость машин, на время обслуживания потребителей и др.

Необходимо отметить, что рассматриваемая нами задача является одной из самых сложных и представляет собой комбинацию нескольких формулировок стандартных УЯР-задач.

УЯР-задача и её разновидности относятся к классу так называемых К'Р-сложных задач' то есть это те задачи, скорость решения которых (или требуемая для решения память) экспоненциально увеличивается при увеличении размерности задачи. В связи с этим основной способ решения таких задач - это некоторый эвристический алгоритм или точный алгоритм, ограничиваемый эвристиками, который позволяет получать за приемлемое время удовлетворительный результат. Критерии оценки алгоритмов:

• время, затрачиваемое алгоритмом на решение задачи;

• качество получаемого решения;

• сложность алгоритма.

Для каждого УИР-класса задач существуют типовые проблемы, на которых проверяется качество разрабатываемых алгоритмов.

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

• на первом этапе алгоритмы строят некоторые решения,

• на втором - с помощью эвристик улучшают полученные решения до приемлемых.

Основные минусы существующих алгоритмов:

• Сложность общей схемы алгоритма,

• Невозможность человеку вмешаться в процесс решения задачи.

Во второй главе поставленная задача формализуется и рассматривается с точки зрения теории алгоритмов, показывается ЫР-полнота задачи.

Рассмотрим более формальную постановку задачи. Задача решается на полносвязном графе С = (У,Е), где V = {0,1,...,/я,т + 1,...,я} - множество складов и потребителей (¡/> ), а Е - пути между ними, причём т +1 - количество складов, а п-т — количество потребителей. С каждой вершиной от т +1 до и связывается число дс - объём заказанной потребителем продукции: О? — = т + \,п] с каждой веткой графа связывается стоимость перемещения по этой ветке автомобиля:

с<|'2<з~ ''^!'2 - 0,и;/3 - 0,«;/г * «з - затраты на перемещение машины от точки /2 к точке /3. Каждого потребителя можно обслуживать строго в определённый промежуток времени: Т" = = т +1,/»}.

В задачу вводится множество машин: б1 = {</,А|| = 1,*}. Каждая машина имеет свою вместимость. Каждая машина может выполнять несколько маршрутов. В общем случае с каждой машиной связана своя формула

расчёта затрат на маршрутах / = 1,А : затраты машины - это

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

Решением задачи является множество перестановок потребителей

= \я,¡'= . Каждая перестановка - это множество маршрутов одной

машины. На перестановки накладываются естественные ограничения: к к Vе = - машины должны посетить всех потребителей и = 0 -

1=1

каждый потребитель посещается только один раз. Маршрут машины должен начинаться на складе и на нём же заканчиваться. Затраты на автотранспорт складываются из затрат на маршруты/^ и из затрат на ожидание между маршрутами/5. Таким образом, цель задачи - минимизация затрат: /№ —> ггнп. Кроме указанных ограничений, надо учесть ограничения на длительность маршрута, на время заезда к потребителю и другие.

Третья глава посвящена алгоритму решения распределительной задачи - реализации метода ветвей и границ.

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

a. имея на входе список неудовлетворённых заявок на определённый период времени и список свободных машин, для каждой машины из списка строим оптимальный маршрут;

b. сравнивая полученные маршруты по некоторому критерию оптимальности, выбираем из них наилучший;

c. машина, обслуживающая маршрут, становится занятой на время, необходимое для выполнения маршрута, а из списка заявок вычёркиваются заявки, входящие в маршрут;

<1. если неудовлетворённых заявок не осталось, то считаем задачу решённой;

е. если при наличии неудовлетворённых заявок список свободных машин пуст, то считаем, что решения задачи при заданных условиях не существует (требуется больше машин); {. иначе переходим к шагу номер один.

2) Второй этап - постоптимизация. Из полученных маршрутов на основании эвристик получаем решение более высокого качества.

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

Получаем список точек Ьт

Получаем список ; незанятых маоми им

Вт мяли-" мы в Ц< с мар-~ ^ шрутэ? /

| Постоптимизация Поиск лучшего решения на базе полученных маршрутов

К

выход

- В I,- асгь

Нет

ь

Да^ ' заведомо "" "-^удовлетворяемые,, точки? /

-Да

Выбираем машину Ме и < новый маршрут для нее 1

Нет

<С|Ив уже заказа на

Нет

I

Да

Определяем момент — времени на который ' эакаэыаать Ме

Расширяем гериод занятости Ме

иа время, необходимое для обслуживания заявок, входящих в маршрут ■

Вычеркиваем ^очки \ маршрута Мв иа общего \ списка точек (

РисЛ, Укрупненная схема алгоритма

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

1. Удаление «плохих» маршрутов:

1 1. Ранжируем маршруты в порядке убывания удельных затрат и пытаемся «разбить» маршруты с большими удельными затратами следующим образом:

1.2. берем последовательно каждую точку выбранного «плохого» маршрута ТУ;

1 3. ищем ближайшую к ней точку из другого маршрута М\

1.4. пробуем включить выбранную точку из маршрута N в маршрут М.

1.5. Если сумма стоимостей маршрутов М и N до вставки была больше, чем после, то принимаем такое изменение маршрутов.

2. Удаление «плохих» веток из маршрутов:

2.1. ищем все ветки на маршрутах, удельная стоимость которых больше удельной стоимости маршрута;

2 2. удаляем такую ветку и получаем, таким образом, два маршрута вместо одного;

2.3. из получившихся кусков пытаемся скомбинировать новые, более хорошие маршруты.

Указанные эвристики значительно улучшают решение, полученное на первом этапе. Получаемые результаты при решении тестовых задач в большинстве случаев близки к лучшим опубликованным результатам.

Рис.2. Пример выполнения первого этапа алгоритма для тестовой задачи с 25 потребителями. Суммарная стоимость маршрутов - 264,4467

Рис.3. После второго этапа алгоритма суммарная стоимость сокращена до 191,8136

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

В системе построения маршрутов следующими по важности после модуля оптимизации являются модуль реализации транспортной модели местности и геоинформационная система. Для того, чтобы получаемые модулем оптимизации результаты имели практическую ценность, расчёты должны производиться на базе реальных географических данных, что может обеспечить только геоинформационная система с картами необходимой точности. Кроме того, перед решением основной распределительной задачи системой рассчитываются кратчайшие маршруты между всеми парами потребителей и базами автотранспорта. Такие расчеты можно производить только на транспортной модели, корректно описывающей сеть дорог на местности. Основной вопрос при разработке транспортной модели: как много факторов должна учитывать модель? Особенно актуален этот вопрос, если рассматриваемая задача решается в рамках городской транспортной сети. Известно, что для того, чтобы точно рассчитывать маршруты по городу, необходимо учитывать следующие факторы: качество дорожного покрытия, ширину дорожного полотна, дорожные знаки и светофоры, возможность организации движения в городе по принципу «зеленых волн», удельное число перекрёстков, предписываемые средние скорости на разных участках дороги, проведение ремонтных и других работ на дорогах, взаимное расположение промышленных и жилых зон в городе, мощность пассажиропотока в часы пик и т.д. С другой стороны, понятно, что транспортную модель, учитывающую такое количество параметров, очень сложно поддерживать силами одного предприятия, поэтому необходимо найти компромисс между точностью транспортной модели и её сложностью. Практика показала, что для качественного решения задачи в рамках городской сети вполне достаточно простой транспортной модели, учитывающей только следующие параметры: средняя скорость движения на участках улиц, возможность проезда по улице вперёд/назад, типы машин, которым разрешён проезд по данной улице. Вопросы качества дорог, наличия светофоров и дорожных знаков решаются понижением или увеличением средней скорости перемещения транспорта по улице.

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

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

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

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

Вычислительные эксперименты, результаты которых также приведены в пятой главе, проводились над тестовыми задачами, предложенными профессором Мариусом Соломоном (Marius Solomon). Все задачи делятся по количеству потребителей на три группы: 25 заказчиков, 50 и 100. В каждой группе есть задачи с кластерным распределением заказчиков по территории, случайным распределением и кластерно-случайным. В каждой группе - 56 задач. Всего - 168 тестовых задач.

Полученные результаты сравнивались с лучшими опубликованными результатами. Обобщённые результаты показаны в таблице:

г. Min разница ШШШтт- ■ &epemeßt

С101-С208 0,20% 21,59% 4,19%

R101-R211 -2,80% 15,62% 5,78%

RC101-RC208 0,22% 31,82% 9,96%

Табл. 1. Обобщённые результаты вычислительных экспериментов

Разработка новых, более эффективных постоптимизационных эвристик - предмет дальнейшей работы над алгоритмом.

Кроме тестовых задач, приводится решение двух реальных задач по распределению продукции по потребителям: для химического завода и хлебозавода. Рассмотрим такую реальную задачу. Костромской химический завод выпускает химическую продукцию. На некоторый день потребители города сделали 89 заказов на продукцию завода. Заказанный ассортимент- 38 наименований выпускаемой продукции. В распоряжении завода имеется 15 автомобилей. Грузоподъёмность каждого - 4500 килограмм. Формула расчёта затрат для каждого автомобиля: /•' = 6,4*х + 101 *у, (руб)

В формулах х - количество накатанных машиной километров, у - количество часов, в течение которых машина работала.

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

Рис.4. Часть транспортной сети Костромы с нанесенными торговыми точками

После расчёта на указанных данных получаем 23 маршрута общей стоимостью 5189 рублей., один из которых показан на рисунке ниже:

Рис.5. Маршрут на карте

Для каждой машины, участвующей в развозке продукции, после расчёта становятся известны следующие параметры: на какое время заказы-

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

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

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

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

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

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

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

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

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

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

лением транспорта по маршрутам, что тоже даёт значительный экономический эффект.

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

ПУБЛИКАЦИИ

1. Бадашкин В.А., Косяков C.B., Никольский В.Н. Повышение эффективности городских грузоперевозок на основе применения геоинформационных систем. // Сборник статей международной научно-практической конференции 'Традиции и перспективы подготовки торгово-экономических кадров России. Формирование экономической культуры в условиях рыночных преобразований общества.", - Иваново, 2000.

2. Лабутин А.Н., Бадашкин В.А., Игнатьев Е.Б. Задача оптимизации грузоперевозок мелкотоннажной разноассортиментной продукции автомобильным транспортом. // Сборник научных трудов вузов России «Проблемы экономики, финансов и управления производством», шестнадцатый выпуск, - Иваново, 2004, - стр. 230-235.

3. Лабутин А.Н., Бадашкин В.А., Игнатьев Е.Б. Алгоритм решения задачи оптимизации грузоперевозок автомобильным транспортом. // Сборник научных трудов вузов России «Проблемы экономики, финансов и управления производством», шестнадцатый выпуск, - Иваново, 2004, - стр. 235-241.

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

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

Автор выражает признательность за консультации и помощь в подготовке работы кандидатам технических наук, доцентам кафедры Программного обеспечения компьютерных систем Ивановского государственного энергетического университета Игнатьеву Евгению Борисовичу и Зубкову Валентину Петровичу.

Подписано в печать 26.04.2006. Формат 60x84 1/16. Бумага писчая.

Усл. печ. л. 1,00 Уч.-изд. л. 1,03 Тираж 80 экз. Заказ 268

ГОУ ВПО Ивановский государственный химико-технологический университет Отпечатано на полиграфическом оборудовании кафедры экономики и финансов ГОУ ВПО «ИГХТУ»

153000, г. Иваново, пр. Ф. Энгельса, 7

^öOGji ! »102 88

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

ВВЕДЕНИЕ.

Глава 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. На базе разработанного алгоритма построена в внедрена система управления мелкотоннажными грузоперевозками.

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