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

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

КОПЫЛОВ Роман Васильевич

ТЕРРИТОРИАЛЬНОЙ СИСТЕМЕ ДОСТАВКИ СЖИЖЕННОГО ГАЗА

Специальность: 05.13.18 - Математическое моделирование, численные

методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Воронеж - 2006

Работа выполнена в Вощэнежском государственном техническом университете

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

доктор технических наук, профессор Кравец Олег Яковлевич

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

доктор физико-математических наук, профессор

Блюмин Семен Львович;

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

кандидат технических наук Мачтаков Сергей Геннадьевич

Курский государственный технический университет (г. Курск)

С диссертацией можно государственного технического

Защита состоится 28 декабр! 2006 г. в 10 00 часов в конференц-зале на заседании диссертационного совета Д 212.037.01 Воронежского государственного технического у ¡иверситета по адресу: 394026, г. Воронеж, Московский просп., 14.

( шакомиться в библиотеке Воронежского уфверситета.

Автореферат разослан 27 »ября 2006 г.

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

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

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

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

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

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

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

Диссертационная работа выполнена в рамках основного научного направления Воронежского государственного технического университета — «Вычислительные системы и программно-аппаратные комплексы».

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

сложности в рамках задачи гарантированной доставки сжиженных углеводородных газов.

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

1. Провести анализ и сформулировать проблемы территориальной доставки на основе оптимального планирования транспортного обслуживания.

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

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

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

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

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

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

• три базовых метода построения алгоритмов обхода, основанные на расчете оптимальных циклических покрытий для обхода «границы», преобразовании циклических покрытий в обходы и использовании оптимальных (или близких к оптимальным) «полосовых покрытий», отличающиеся учетом стоимости возврата;

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

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

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

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

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

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

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

Апробаиия работы. Основные результаты работы докладывались и обсуждались на Всероссийской НТК «Актуальные проблемы информатики и информационных технологий» (Тамбов, 2004), II Международной НПК «Единое информационное пространство '2004» (Украина, Днепропетровск, 2004), Всероссийской НТК «Наука на рубеже тысячелетий» (Тамбов, 2004), X Международной НТК «Современные проблемы информатизации в непромышленной сфере и экономике» (Воронеж, 2005), Всероссийской НТК «Информационные технологии» (Воронеж, 2005), 3-й Всероссийской НПК «Актуальные проблемы профессионального образования: проблемы и перспективы» (Воронеж, 2005), Международной НПК «Составляющие научно-технического прогресса» (Тамбов, 2005), Всероссийской НТК «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2005, 2006), X Международной НТК «Современные проблемы информатизации в прикладных задачах» (Воронеж, 2006), а также на научных семинарах кафедры ABC ВГТУ в 2004-2006 гг.

Публикации. Основные результаты диссертации опубликованы в 17 научных работах, в том числе две - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежит в: [2, 8] - способ формализованного описания процессов планирования транспортного обслуживания удаленных объектов; [3, 9] -оптимизационная задача доставки газа с учетом временных особенностей; [4, 10, 11] — модели и алгоритмы оптимизации доставки в условиях территории и города; [5, 12, 16] — особенности программного проектирования информационно-управляющей системы базы сжиженного газа; [1,6, 13, 17] — методы и технологии создания компонент территориально распределенной информационной системы.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 111 наименований, приложения. Основная часть работы изложена на 126 страницах, содержит 9 таблиц и 31 рисунок.

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

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

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

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

К задачам маршрутизации автотранспорта и планирования транспортных систем относится целый класс задач, в которых набор маршрутов для парка автомобилей, расположенных в одном или нескольких «депо» (рис. 1), должен быть определен для нескольких географически отдаленных пунктов потребления, в которых размещаются клиенты. Целью решения задач маршрутизации является оптимизация выполнения серии запросов клиентов.

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

Анализ показал, что задача гарантированной доставки с минимизацией стоимости не является в чистом виде ни транспортной задачей, ни задачей классической теории расписаний.

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

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

зации движения

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

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

Q - количество клиентов. Для i-ro клиента, помимо его местоположения, заданы: kj,- количество баллонов, привозимых за одну поставку; d, - период, через который необходимо привезти данное число баллонов. М - число машин. Для j-й машины определены: virij - вместимость; cnij - цена 1 км перевозки;

Рг - число прицепов. Для s-ro прицепа также определена его вместимость vps и цена 1 км перевозки cps.

В качестве целевой функции рассмотрена минимизацию затрат, требующихся на доставку газа в течение периода t^L.T. Эта целевая функция будет

складываться из двух составляющих: затраты на перевозку газа Рег() и штраф

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

]Г(.Perit) + Shtr{ О) -> min. (1)

f=i

Задача сводится к выбору на каждом шаге таких вершин графа Qt, его рёбер Vt и транспорта таким образом, чтобы суммарные затраты (на перевозку и штраф) были минимальны. Из всего графа G возможных позиций (вершин) и соединений между позициями (рёбер) выбираются подграфы Gi, G2,...,Gkoi„ и каждому подграфу ставится в соответствие транспортное средство. Тогда функция затрат на перевозку будет определяться как сумма затрат в каждом подграфе, а каждое слагаемое - как произведение длины подграфа на цену 1 км перевозки:

Рег.(!)=ь(0^)) Тг(С;{!)) . (2)

Здесь L,{Gj(t)) - дайна подграфа Gj, т.е. сумма длин всех его рёбер, Tr(Gj{t)) - затраты на перевозку 1 км в подграфе Gj, которые определяются лишь выбором транспорта для соответствующего подграфа:

Tr(Gj(t))=.

тм> m, +р,,

тм +Pi» ш, + рР,

(3)

тм + рр.

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

Сформулируем ограничения. Число имеющихся в наличии машин должно быть не меньше числа подграфов:

М>к,. (5)

Вместимость выбранного транспортного средства должна быть не меньше потребности газа в каждом подграфе.]:

хтг > ,>=1,...,ко1,. (6)

<бО,<о

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

1. Выбрать множество пунктов С^, которые в данный момент времени будут обеспечены газом.

2. Выбрать множество маршрутов, с помощью которых в данный момент времени I будут обеспечены газом пункты

3. Выбрать транспорт Тг, для каждого маршрута.

Задача выбора множества пунктов <3, должна решаться таким образом, чтобы минимизировать стоимость перевозок и сумму штрафа. В этом плане задачи 1 и 2 являются взаимосвязанными. Задача 2 — это проектирование структуры сети с заданными ограничениями на объём поставляемого газа (фактически задача структурного синтеза). Задача 3 также частично зависит от решения задачи 1, поскольку выбор машин напрямую связан с объёмом поставок для данного подграфа. Зависимость задач представлена на рис. 2.

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

1 2

\

Рис. 2. Взаимодействие задач

2 ФЛО)-Тг(о £ БЬ^О

1=1 V .и н )

1=1 V, .И

тип

(7)

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

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

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

С применением технологии слияния двух соприкасающихся обходов (рис. 3) показано, что циклическое покрытие с числом поворотов I может быть преобразовано в обход с количеством поворотов не более 1+2(с-1), где с - число

циклов.

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

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

Используем следующие подходы для построения алгоритмов создания обходов (далее 5 означает максимальную степень вершины, а р означает максимальное число различных «направлений», сходящихся в одной вершине):

м

рх

Рл

3

р1 л

р I

Рис. 3. Слияние двух соприкасающихся обходов. Имеется три возможных варианта обхода Т2 с посещением позиции р2 (вверху). В каждом случае можно преобразовать Т2 в маршрут с посещением позиции Р|бТ1 (внизу); за счет возможного одного дополнительного поворота на оба конца маршрута возможно слить его с обходом Т|

1. Звезда+дублирование+слияние: область покрывается множеством звёзд. Результатом «дублирования» этих звёзд будет совокупность циклов, которые затем могут быть объединены в обход с использованием обычных методов.

Первоначально берётся звездное покрытие, которое аппроксимирует оптимальное полосовое покрытие в пределах коэффициента р. Для обхода каждой звезды с центром в вершине v используем следующий метод (рис. 4). Рассмотрим полосу s в этой звезде и предположим, что её концами являются вершины щ и uj. Полосу, обе конечных точки которой отличны от v, назовем полной; если одна из конечных точек совпадает с v, назовем полуполосой. Полуполосы покрываются тремя рёбрами, (v, uj), (uj, uj), и {uj, v), образуя поворот на 180° в конечной точке uj . Это покрытие показано для полуполосы (v, uj) на рис. 46). Полные полосы покрываются пятью рёбрами, (v, uj, (и„ uj, (щ и), (uj, и¡), и (uj, у), с поворотами на 180° на обоих концах, н, и му. Это покрытие показано для полной полосы (щ.щ) на рис. 46). Теперь есть несколько путей из рёбер, начинающихся и заканчивающихся в v. Соединяя их концы, легко можно объединить эти пути в цикл. Показано, что число звёзд — нижняя граница числа поворотов в циклическом покрытии области. U5.

1

.4

U4

4 • и

*ч

а) б)

Рис. 4. а) Звезда степени 5 вокруг вершины V: (у,^), (у,и3), (у,и4) - полуполосы, (и2,и5) - полная полоса; б) покрытие тремя рёбрами для полуполосы и покрытие пятью рёбрами для полной полосы

Также показано, что существует линейный по времени (25+р+2)-апгоритм дискретного обхода с минимальным числом поворотов. Кроме того, максимальное покрытие вершины равно 5, а обход есть 5-алгоритм по длине.

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

Показано, что для целочисленного прямоугольного многоугольника (графа) с п рёбрами и N позициями существуют 2.5-алгоритмы с временами выполнения порядка 0(Ы2 376+п3) и 0(п2 51о§Ы+п3) для циклического покрытия с ми-

нимальным числом поворотов и, следовательно, существует полиномиальный по времени 3.75-алгоритм для обходов с минимальным числом возвратов.

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

непокрытая область

"р граница лбласти

целочисленные позиции

граничное циклическое покрытие оЬходной путь в граничном оЬходе

нецелочисленная область вдоль границы

Рис. 5. Обход нецелочисленного прямоугольного многоугольника

Для мультипрямоугольного целочисленного покрытия показано существование алгоритма сложности 0(п*1о§п) для получения циклического покрытия с минимальным числом поворотов. Также показано, что при нецелочисленном прямоугольном обходе многоугольной области с п рёбрами и N позициями существует полиномиальный по времени 4.5-алгоритм для циклических покрытий с минимальным числом возвратов. Время выполнения равно 0(1М2 376+п3).

Определим теперь цену обхода как его длину плюс С, умноженное на число поворотов (на 90 градусов). В работе показано, что для любого фиксированного б>0 существует (1+е)-алгоритм с временем выполнения 2°(Ь)-№(С) минимизации стоимости обхода для целочисленного прямоугольного многоугольника Р с Ь отверстиями и N позициями.

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

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

• 0{т) точек присоединения, где рёбра пересекаются с границей в точках, отличных от расположенных вдоль ш-участка;

• кратность (1 или 2) каждой точки присоединения и схема соединений (если есть) смежных точек присоединения вдоль границы прямоугольника;

• конечные точки моста с каждой стороны прямоугольника (из которых можно вывести субмосты — рис. 6);

• требования к межсоединениям для точек присоединения и классов субмостов;

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

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

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

ного удалением подмножества рёбер на каждом дублированном субмосте. Из условий чётности следует, что такой Эйлеров подграф существует. Эйлеров обход этого подграфа является покрывающим обходом, и его стоимость не более, чем на 0(С/т) больше оптимальной. Для любого фиксированного е >0 положим ш=Гс/е1, получая в результате (1+е)-алгоритм с временем выполнения

0(л/0(С/с).20(Л)).

В четвертой главе рассматриваются результаты программной реализации разработанных алгоритмов для Воронежского филиала ОАО «СГ-Транс» (базы сжиженного газа).

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

газоснабжения СУГ - на рис. 8._

СПЕЦИАЛЬНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

Рис. 7. Укрупненная функциональная структура специального программ ного обеспечения системы реализации и доставки сжиженного углеводородного газа

Специальное программное обеспечение выполнено на базе программных средств 1С:Предприятие 7.7 и использует методологию построения программных модулей и интерфейс принятый в указанной среде разработки. Основное конфигурирование производится ( разработчиком в процессе проектирования системы - формируется структура информационной базы, алгоритмы обработки, формы диалогов и выходных документов. Информационная структура проектируется на уровне предусмотренных в системе типов обрабатываемых объектов предметной области (константы, справочники, документы, журналы, перечисления и др.) В процессе исполнения система оперирует понятиями, описанными на этапе конфигурирования (справочниками организаций, товаров, счетами, накладными). j

Практическая реализация автоматизированного рабочего места управления маршрутной сетью газоснабжения СУГ осуществлена в программной среде Borland Delphi 6.0. Рабочее место взаимодействует с основной информационной системой через механизмы OLE Automation и базу данных.

Рис. 8. Обобщенная структура автоматизированного рабочего места диспетчера службы доставки

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

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

Таблица

№ Штраф Стоимость доставки для базового маршрута Стоимость доставки для маршрута, сформированного новыми алгоритмами

1 0.0 0.0 0.0

2 0.1 0.1 0.03

3 0.2 0.2 0.12

4 0.3 0.3 0.19

5 0.4 0.4 0.29

6 0.5 0.5 0.43

7 0.6 0.6 0.57

8 0.7 0.7 0.7

9 0.8 0.8 0.76

10 0.9 0.9 0.73

11 1.0 1.0 0.7

Вкладка «Карта», представленная на рис. 9, предназначена для вывода информации о вариантах наиболее экономичных путей доставки СУГ. В таблице, расположенной в левой части окна, указана стоимость перевозок.

В результате внедрения в Воронежском филиале Государственного унитарного предприятия "СГ-Транс" получен годовой экономический эффект 688 тыс. руб. (в ценах 2006 г.). Подсистема, предназначенная для оптимизации поставок в распределенной транспортно-складской системе, зарегистрирована в Государственном фонде алгоритмов и программ.

В результате внедрения в Воронежском филиале ОАО "СГ-Транс" получен годовой экономический эффект 688 тыс. руб. (в ценах 2006 г.). Подсистема, предназначенная для оптимизации поставок в распределенной транспортно-складской системе, зарегистрирована в Государственном фонде алгоритмов и программ.

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

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

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

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

4. Создан общий алгоритм для нахождения циклического покрытия с минимальным числом поворотов в дискретном обходе на основе мультизвезд-ного покрытия, выполняемый за линейное относительно длины границ время. Для мультипрямоугольного целочисленного покрытия показано существование алгоритма сложности 0(п*^п) для получения циклического покрытия с минимальным числом поворотов.

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

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

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

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

9. Основные теоретические и практические результаты внедрены в Воронежском филиале ОАО "СГ-Транс" с годовым экономическим эффектом 688 тыс. руб. (в ценах 2006 г.). Подсистема, предназначенная для оптимизации поставок в распределенной транспортно-складской системе, зарегистрирована в Государственном фонде алгоритмов и программ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ:

Публикации в изданиях, рекомендованных ВАК РФ

I. Копылов Р.В. Оптимизация движения информации в телекоммуникационных подсистемах корпоративной вычислительной сети / Р.В. Копылов, А.Д. Поваляев // Вестник Воронежского государственного технического университета. 2005. Т. 1. № 5. С.97-99.

2. Бурковский В.Л. К постановке задачи оптимизации управления доставкой для многоуровневой древовидной сети с учетом сроков / В.Л. Бурковский, Р.В. Копылов // Системы управления и информационные технологии. -2006. № 2.1(24). - С. 149-154.

Статьи

3. Багирова М.А. Рационализация диспетчеризации мобильных комплексов для обслуживания социально-экономического объекта / М.А. Багирова, Р.В. Копылов, О.Я. Кравец // Единое информационное пространство '2004: сб. докл. Н-й междунар. науч.-практ. конф. - Днепропетровск: ИПК ИнКомЦентра УГХТУ, 2004. - С.132-134.

4. Копылов Р.В. Проблемы моделирования структуры многоуровневой древовидной информационно-телекоммуникационной сети предприятия по распределению сжиженного углеводородного газа / Р.В. Копылов, Е.А. Солда-тов, С.А. Олейникова // Фундаментальные исследования. 2004. № 6. С. 116-117.

5. Копылов Р.В. Разработка высокоэффективной региональной информационно-управляющей системы производства и снабжения сжиженным углеводородным газом / Р.В. Копылов, О .Я. Кравец // Наука на рубеже тысячелетий: сб. науч. ст. - Тамбов: Изд-во БМА, 2004. - С. 166-167.

6. Копылов Р.В. Анализ эффективности мероприятий по оптимизации движения информации в корпоративной вычислительной сети / Р.В. Копылов, О.Я. Кравец // Информационные технологии моделирования и управления: междунар. сб. тр. Воронеж: Изд-во "Научная книга", 2004. Вып. 18. С. 144-148.

7. Копылов Р.В. Оптимизационные задачи для управления распределением поставок сжиженного газа / Р.В. Копылов // Шаг в будущее, Центральная Россия. - Липецк: ЛГТУ, 2004. С. 23-24.

8. Копылов Р.В. Минимизация обобщенной стоимости обслуживания в территориально распределенной системе доставки сжиженного углеводородного газа / Р.В. Копылов, О.Я. Кравец // Информационные технологии: материалы всерос. науч.-техн. конф. - Воронеж: Изд-во "Научная книга", 2005. С. 131-133.

9. Копылов Р.В. Многоуровневая оптимизационная задача управления поставками сжиженного газа / Р.В. Копылов, О.Я. Кравец // Актуальные проблемы информатики и информационных технологий: сб. тр. - Тамбов: Изд-во ТГУ, 2004. - С. 104.

10. Копылов Р.В. Исследование и оптимизация обслуживания потребности в сжиженном углеводородном газе в территориально распределенной системе / Р.В. Копылов, О.Я. Кравец // Информационные технологии моделирования и управления. - 2005. № 2(20). С. 14-18.

11. Копылов Р.В. Оптимизация обслуживания в территориально распределенной системе доставки сжиженного углеводородного газа / Р.В. Копылов, О.Я. Кравец // Актуальные проблемы профессионального образования: проблемы и перспективы: материалы 3-й всерос. науч.-практ. конф. - Воронеж: Изд-во "Научная книга", 2005. С. 127-128.

12. Копылов P.B. Реализация оперативного взаимодействия информационной системы с весовым оборудованием в подсистеме учета сжиженного газа на основе технологии OLE Automation / Р.В. Копылов, О.Я. Кравец, Е.А. Сол-датов // Информационные технологии моделирования и управления. - 2005, № 6(24). С. 895-899.

13. Копылов Р.В. Разработка методов структурного проектирования распределенных информационно-вычислительных систем / Р.В. Копылов, О.Я. Кравец, С.А. Олейникова // Составляющие научно-технического прогресса: сб. материалов междунар. науч.-практ. конф. - Тамбов: Першина, 2005. - С. 166167.

14. Копылов Р.В. Обобщенный стоимостной критерий в задаче оптимизации доставки сжиженного углеводородного газа в регионе / Р.В. Копылов // Новые технологии в научных исследованиях, проектировании, управлении, производстве: тр. всерос. конф. Воронеж: ВГТУ, 2005. С. 22-23.

15. Копылов Р.В. Теоретические основы оптимизации потоков в системе транспортировки сжиженного углеводородного газа / Р.В. Копылов // Современные проблемы информатизации в непромышленной сфере и экономике: междунар. сб. науч. тр. - Воронеж: Изд-во "Научная книга", 2005. Вып. 10. С. 111-113.

16. Копылов Р.В. Особенности реализации корпоративной информационной системы учета сжиженного газа / Р.В. Копылов, ОЛ. Кравец, Е.А. Сол-датов // Современные проблемы информатизации в прикладных задачах: сб. тр. Воронеж: Научная книга, 2006. - Вып. 11. - С. 88-90.

17. Копылов Р.В., Кравец О.Я. Программный модуль «Оптимизация поставок в распределенной транспортно-складской системе». - ФАП ВНТИЦ. Per. N50200600123 от 06.02.2006.

Подписано в печать 23.11.2006. Формат 60x84/16. Бумага для множительных аппаратов. Усл. печ. л. 1,0. Тираж 90 экз. Заказ №

ГОУВПО «Воронежский государственный технический университет» 394026 Воронеж, Московский просп., 14

Введение.

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

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

1.2. Проблемы территориальной доставки на основе оптимального планирования транспортного обслуживания.

1.3. Особенности оптимизации транспортного обслуживания в городских условиях.

1.4. Цель работы и задачи исследования.

2. Оптимизация доставки сжиженного углеводородного газа.

2.1. Задача оптимизации доставки сжиженного газа с учетом штрафов

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

2.3. Минимизация числа возвратов через минимизацию числа поворотов.

2.4. Выводы.

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

3.1. Алгоритмизация построения мультизвездного покрытия.

3.2. Алгоритмизация построения мультипрямоугольного покрытия (целочисленный случай).

3.3. Алгоритмизация построения мультипрямоугольного покрытия (произвольный случай).

3.4. Полиномиальный по времени алгоритм обхода.

3.5. Выводы.

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

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

4.2. Формирование информационных потоков.

4.3. Автоматизированное рабочее место диспетчера службы доставки

4.4. Выводы.

Основные результаты работы.

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

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

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

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

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

Диссертационная работа выполнена в рамках основного научного направления Воронежского государственного технического университета -«Вычислительные системы и программно-аппаратные электротехнические комплексы».

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

Исходя из этого в работе определены следующие задачи исследования:

1. Провести анализ и сформулировать проблемы территориальной доставки на основе оптимального планирования транспортного обслуживания.

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

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

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

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

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

• Доказательство NP-полноты задачи нахождения циклического покрытия, покрывающего определенное подмножество, расположенное вдоль границы области, отличающегося минимальным числом возвратов.

• Три базовых метода построения алгоритмов обхода, основанные на расчете оптимальных циклических покрытий для обхода «границы», преобразовании циклических покрытий в обходы и использовании оптимальных (или близких к оптимальным) «полосовых покрытий», отличающиеся учетом стоимости возврата.

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

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

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

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

Реализация и внедрение результатов работы.

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на Всероссийской НТК «Актуальные проблемы информатики и информационных технологий» (Тамбов, 2004), II Международной НПК «Единое информационное пространство '2004» (Украина, Днепропетровск, 2004), Всероссийской НТК «Наука на рубеже тысячелетий» (Тамбов, 2004), X Международной НТК «Современные проблемы информатизации в непромышленной сфере и экономике» (Воронеж, 2005), Всероссийской НТК «Информационные технологии» (Воронеж, 2005), 3-й Всероссийской НПК «Актуальные проблемы профессионального образования: проблемы и перспективы» (Воронеж, 2005), Международной НПК «Составляющие научно-технического прогресса» (Тамбов, 2005), Всероссийской НТК «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2005, 2006), X Международной НТК «Современные проблемы информатизации в прикладных задачах» (Воронеж, 2006), а также на научных семинарах кафедры ABC ВГТУ в 2004-2006 гг.

Публикации. Основные результаты диссертации опубликованы в 17 научных работах, в том числе две [8, 34] - из списка изданий, рекомендованных ВАК. В работах, опубликованных в соавторстве и приведенных в списке использованных источников, лично соискателю принадлежит: в [8, 25] - способ формализованного описания процессов планирования транспортного обслуживания удаленных объектов; в [4, 26] - оптимизационная задача доставки газа с учетом временных особенностей; в [24, 27, 35] - модели и алгоритмы оптимизации доставки в условиях территории и города; в [29, 32, 33] - особенности программного проектирования информационно-управляющей системы базы сжиженного газа; в [23, 28, 31, 34] - методы и технологии создания компонент территориально распределенной информационной системы.

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

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

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

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

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

4. Создан общий алгоритм для нахождения циклического покрытия с минимальным числом поворотов в дискретном обходе на основе мультизвездного покрытия, выполняемый за линейное относительно длины границ время. Для мультипрямоугольного целочисленного покрытия показано существование алгоритма сложности 0(n*logn) для получения циклического покрытия с минимальным числом поворотов.

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

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

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

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

9. Основные теоретические и практические результаты внедрены в Воронежском филиале ОАО "СГ-Транс" с годовым экономическим эффектом 688 тыс. руб. (в ценах 2006 г.). Подсистема, предназначенная для оптимизации поставок в распределенной транспортно-складской системе, зарегистрирована в Государственном фонде алгоритмов и программ.

1. Анисимов П.А., Маринук М.Н. Системы оперативного управления дискретными производствами. Кишинев: Штиинца, 1984. 174 с.

2. Арчибальд Р. Управление высокотехнологичными программами и проектами. М.: ДМК Пресс, 2005. - 464 с.

3. АСУ ТП установки комплексной подготовки газа. "Ревдагазсервис",1998.

4. Байдаков В., Дранищев В., Краюшкин А., Кузнецов И., Лавров М., Моничев А. 1С Предприятие 8.0. Конфигурирование и администрирование. -М.:ЗАО «1С», 2005.-688 с.

5. Берж К. Теория графов и ее применения. М.: ИЛ, 1962. - 320 с.

6. Бурковский В.Л., Копылов Р.В. К постановке задачи оптимизации управления доставкой для многоуровневой древовидной сети с учетом сроков. -Системы управления и информационные технологии. 2006, №2.1(24). - С. 149-154.

7. Васильченко Н.Г. Современная система управления предприятием. Учебно-практическое пособие. М.: Интел-Синтез, 2003. - 320 с.

8. Виноградов В.И. Информационно-вычислительные системы: Распределенные модульные системы автоматизации. М.: Энергоатомиздат, 1986. 336 с.

9. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. - 360 с.

10. Гарсиа-Молина Г., Ульман Д., Уидом Д. Системы баз данных. Полный курс. -М.: «Вильяме», 2003. 1088 с.

11. Дейт К. Дж. Введение в системы баз данных. М.: «Вильяме», 2000 - 846 с.

12. Евстигнеев В.А. Применение теории графов в программировании. -М.: Наука, 1985.-352 с.

13. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. - 1104 с.

14. Киселев А.Г. Исследование контуров управления в интегрированной информационной системе промышленного предприятия // Машиностроитель. 2003. - № 9. - С.24-32.

15. Кнут Д. Искусство программирования для ЭВМ. Т.2: Получисленные алгоритмы. М.: Мир, 1977. - 724 с.

16. Кнут Д. Искусство программирования для ЭВМ. Т.З: Сортировка и поиск. М.: Мир, 1978. - 844 с.

17. Компьютерное управление реконфигурирующимися технологическими процессами автоматизированного производства изделий электромеханики/ О.Я.Кравец, В.Л.Бурковский, П.П.Махначев и др. Воронеж: Изд-во ВГУ, 1993. 160с.

18. Копылов Р.В. Обобщенный стоимостной критерий в задаче оптимизации доставки сжиженного углеводородного газа в регионе. Новые технологии в научных исследованиях, проектировании, управлении, производстве: Труды Всерос. конф. Воронеж: ВГТУ, 2005. С. 22-23.

19. Копылов Р.В. Оптимизационные задачи для управления распределением поставок сжиженного газа. Шаг в будущее, Центральная Россия. - Липецк: ЛГТУ, 2004. С. 23-24.

20. Копылов Р.В., Кравец О.Я. Исследование и оптимизация обслуживания потребности в сжиженном углеводородном газе в территориально распределенной системе. Информационные технологии моделирования и управления. - 2005, №2(20), с. 14-18.

21. Копылов Р.В., Кравец О.Я. Многоуровневая оптимизационная задача управления поставками сжиженного газа. Актуальные проблемы информатики и информационных технологий: Сб. тр. - Тамбов: Изд-во ТГУ, 2004.-С. 104.

22. Копылов Р.В., Кравец О.Я. Программный модуль «Оптимизация поставок в распределенной транспортно-складской системе». ФАП ВНТИЦ. Per. N50200600123 от 06.02.2006.

23. Копылов Р.В., Кравец О.Я. Разработка высокоэффективной региональной информационно-управляющей системы производства и снабжения сжиженным углеводородным газом. Наука на рубеже тысячелетий: Сб. науч. статей. - Тамбов: Изд-во БМА, 2004. - С. 166-167.

24. Копылов Р.В., Кравец О.Я. Технологии и методы создания информационной системы учета сжиженного газа. Новые технологии в научных исследованиях, проектировании, управлении и производстве: Тр. Всеросс. конф. - Воронеж: ВГТУ, 2006. - С. 51-53.

25. Копылов Р.В., Кравец О.Я., Солдатов Е.А. Особенности реализации корпоративной информационной системы учета сжиженного газа. Современные проблемы информатизации в прикладных задачах: Сб. трудов. Вып. 11. Воронеж: Научная книга, 2006. - С. 88-90.

26. Копылов Р.В., Поваляев А.Д. Оптимизация движения информации в телекоммуникационных подсистемах корпоративной вычислительной сети. -Вестник Воронежского государственного технического университета. Том 1, №5,2005. С.97-99.

27. Кук Д., Бейз Г. Компьютерная математика. М.: Наука, 1990. - 384 с.

28. Митичкин С.А. Разработка в системе 1С Предприятие 8.0. М.: ООО «1С-Паблишинг», 2003.-413 с.

29. Модернизация АСУТП магистральных трубопроводов/ Современные технологии автоматизации, 1997, N4.

30. Мониторинг газовых регуляторных пунктов/ С.Золин, В.Махов, И.Корниенко, А.Кошта//"Прософт-Е", "Ревдагазсервис", 1998.

31. Новоженов Ю.В. Объектно-ориентированные технологии разработки сложных программных систем. М.: Диалог-МИФИ, 1996. - 286 с.

32. Оре О. Теория графов. М.: Наука, 1980. - 336 с.

33. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики. М.: Энергоатомиздат, 1981. 319с.

34. Радченко М.Г. 1С .'Предприятие 8.0. Практическое пособие разработчика. Примеры и типовые приемы. М.: ООО «1С-Паблишинг», 2004. - 656 с.

35. Разумов О.С. Организация данных в вычислительных системах. М.: Статистика, 1978. - 184 с.

36. Растригин JI.A. Современные принципы управления сложными объектами. М.: Советское радио. 1980. 232 с.

37. Свами М., Тхуласираман К. Графы, сети и алгоритмы. -М.: Мир, 1984.-454 с.

38. Семенов М.И. и др. Автоматизированные информационные технологии в экономике. М.: Финансы и статистика, 2003. - 264 с.

39. Система учета расхода природного газа и смеси газов// ТЭТА "Поток", 1999.

40. Системы контроля распределения и хранения нефти и нефтепродуктов и управление ими/ Приборы и системы управления, 1998, N7.

41. Харари Ф. Теория графов. М.: Мир, 1973. - 300 с.

42. Чоговадзе Г.Г. Автоматизация проектирования систем оперативного управления технологическими процессами. М.: Энергия, 1980. - 288 с.

43. Aggarwal A., Coppersmith D., Khanna S., Motwani R., Schieber B. The angularmetric traveling salesman problem, in Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Jan. 1997, pp. 221-229.

44. Alsuwaiyel M.H., Lee D.T., Minimal link visibility paths inside a simple polygon, Comput. Geom. Theory Appl., 3 (1993), pp. 1-25.

45. Approximation algorithms for lawn mowing and milling, Comput. Geom. Theory Appl., 17 (2000), pp. 25-50.

46. Arc routing problems, part II: The rural postman problem, Operations Research, 43 (1995), pp. 399-414.

47. Arkin E.M., Bender M.A., Demaine E., et al. Optimal covering tours with turn costs, in Proc. 13th ACM-SIAM Sympos. Discrete Algorithms, 2001, pp. 138— 147.

48. Arkin E.M., Fekete S.P., Mitchell J.S.B. The lawnmower problem, in Proc. 5th Canad. Conf. Comput. Geom., 1993, pp. 461-466.

49. Arkin E.M., Held M., Smith C.L. Optimization problems related to zigzag pocket machining, Algorithmica, 26 (2000), pp. 197-236.

50. Arkin E.M., Mitchell J.S.B., Piatko C.D. Minimum-link watchman tours, Inform. Process. Lett., 86 (2003), pp. 203-207.

51. Arya S., Cheng S.-W., Mount D.M. Approximation algorithm for multiple-tool milling, Internat. J. Comput. Geom. Appl., 11 (2001), pp. 339-372.

52. Bard J.F., Huang L., Dror M., Jaillet P. «А Branch and Cut Algorithm for the VRP with Satellite Facilities», HE Transactions 30, pp 821-834

53. Benavent E., Soler D. The directed rural postman problem with turn penalties, Transporation Science, 33 (1999), pp. 408-418.

54. Bennet M., Heimes S. The Use of Hierarchical Networks of Computers in Totally Integrated FMS Systems// European advanced Manufacturing Systems (exhibitions and conference). Italy, 1988. P. 243-255.

55. Chazelle B. Triangulating a simple polygon in linear time, Discrete Comput. Geom., 6 (1991), pp. 485-524.

56. Clossey J., Laporte G., Soriano P. Solving arc routing problems with turn penalties, Technical Report G-2000-05, Le Groupe d'etudes et de recherche en analyse des decisions (GERAD), Montreal, Canada, March 2000.

57. Collins M.J., Moret B.M.E. Improved lower bounds for the link length of rectilinear spanning paths in grids, Inform. Process. Lett., 68 (1998), pp. 317-319.

58. Culberson J., Reckhow R.A. Orthogonally convex coverings of orthogonal polygons without holes, J. Comput. Syst. Sci., 39 (1989), pp. 166-204.

59. Dantzig G.B., Ramser R.H. «The Truck Dispatching Problem». Management Science 6, 80-91. 1959

60. David A. Aaker. Strategic market management. NY.: John Wiley & Sons, 1988.-364 p.

61. Demaine E.D., Demaine M.L., Mitchell J.S.B. Folding flat silhouettes and wrapping polyhedral packages: New results in computational origami, in Proc. 15th Annu. ACM Sympos. Comput. Geom., June 1999, pp. 105-114.

62. Demaine E.D., Mitchell J.S.B., O'Rourke J., The Open Problems Project. URL: http://maven.smith. edu/~orourke/TOPP/.

63. Dror M., Laporte G., Trudeau P., «Vehicle routing with split deliveries», Discrete Appl. Math. 50,239-254 (1994).

64. Edward A. Silver, Rein Peterson. Decision systems for inventory management and production planning. NY.: John Wiley & Sons, 1988. - 728 p.

65. Eiselt H.A., Gendreau M., Laporte G. Arc routing problems, part I: The Chinese postman problem, Operations Research, 43 (1995), pp. 231-242.

66. Fekete S.P. Geometry and the Travelling Salesman Problem, ph.D. thesis, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, 1992.

67. Fekete S.P., Woeginger G.J. Angle-restricted tours in the plane, Comput. Geom. Theory Appl., 8 (1997), pp. 195-218.

68. Fernandez D.S. Problemas de Rutas por Arcos con Giros Prohibidos, PhD thesis, Vniversitat de Valencia, 1995.

69. Finding an approximate minimum-link visibility path inside a simple polygon, Inform. Process. Lett., 55 (1995), pp. 75-79.

70. Gabow H., Taijan R. Faster scaling algorithms for network problems, SIAM J. Comput., 18 (1989), pp. 1013-1036.

71. Gabow H.N. Implementation of algorithms for maximum matching on nonbipartite graphs, PhD thesis, Department of Computer Science, Standford University, 1973.

72. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, NY, 1979.

73. Geometric shortest paths and network optimization, in Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds., Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000, pp. 633-701.

74. Gribkovskaia I., Halskau O., Bugge M., Kim N. «Models for Pick-up and Deliveries from Depots with Lasso Solutions».

75. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems, SIAM J. Comput., 28 (1999), pp. 1298-1309.

76. Hassin R., Megiddo N. Approximation algorithms for hitting objects by straight lines, Discrete Appl. Math., 30 (1991), pp. 29-42.

77. Held M. On the Computational Geometry of Pocket Machining, vol. 500 of Lecture Notes Comput. Sci., Springer-Verlag, June 1991.

78. Hjorring C. «The Vehicle Routing Problem and Local Search Metaheuristics», Chapter 2. PhD thesis, Department of Engineering Science, The University of Auckland, 1995.

79. Ibarra O.H., Moran S. Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication, Inform. Process. Lett., 13 (1981), pp. 12-15.

80. Itai A., Papadimitriou C.H., Szwarcfiter J.L. Hamilton paths in grid graphs, SIAM J. Comput, 11 (1982), pp. 676-686.

81. Iwano K., Raghavan P., Tamaki H. The traveling cameraman problem, with applications to automatic optical inspection, in Proc. 5th Annu. Internat. Sympos. Algorithms Comput., vol. 834 of Lecture Notes Comput. Sci., Springer-Verlag, 1994, pp. 29-37.

82. Johnson D.S., Papadimitriou C.H. Computational complexity and the traveling salesman problem, in The Traveling Salesman Problem, E. Lawler, J. Lenstra, A. R. Kan, and D. Shmoys, eds., John Wiley & Sons, New York, 1985, pp. 68-74.

83. Kapoor S., Maheshwari S.N. Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles, in Proc. 4th Annu. ACM Sympos. Comput. Geom., 1988, pp. 172-182.

84. Kapoor S., Maheshwari S.N., Mitchell J.S.B. An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane, Discrete Comput. Geom., 18 (1997), pp. 377-383.

85. Keil J.M. Polygon decomposition, in Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds., Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000, pp. 491-518.

86. Klein R., 2000. Personal Communication.

87. Kranakis E., Krizanc D., Meertens L. Link length of rectilinear Hamiltonian tours on grids, Ars Combinatorica, 38 (1994), p. 177.

88. Laporte G., Louveaux F.V. «Solving Stochastic Routing Problems with the Integer L- shaped Method». In Fleet Management and Logistics, T.G. Crainic and G. Laporte (eds.), 159-167, Kluwer Academic Publishers, Boston. 1998.

89. Mitchell J.S.B. LI shortest paths among polygonal obstacles in the plane, Algorithmica, 8 (1992), pp. 55-88.

90. Mitchell J.S.B., Suri S. Separation and approximation of polyhedral objects, Comput. Geom. Theory Appl., 5 (1995), pp. 95-114.

91. Molada E.M., Fernandez D.S. Exact solution of the Chinese postman problem with turn penalties, in XV Congress on Differential Equations and Applications/ V Congress on Applied Mathematics, vol. I, II (Spanish), Colecc. Congr.,9, 1998, pp. 1111-1115.

92. Ntafos S. Watchman routes under limited visibility, Comput. Geom. Theory Appl., 1 (1992), pp. 149-170.

93. Ralphs Т., Hartman J., Galati M. «Capacitated Vehicle Routing and Some Related Problems». Some CVRP Slides. Rutgers University. 2001.

94. Ralphs Т.К., Kopman L., Pulleyblank W.R., Trotter Jr. L.E. «On the Capacitated Vehicle Routing Problem». Accepted to Mathematical Programming, 2001.

95. Schrijver A. Combinatorial Optimization, Springer-Verlag, Berlin, 2003.

96. The VRP Web: http://neo.lcc.uma.es

97. Toth P., Vigo D. «The Vehicle Routing Problem». Monographs on Discrete Mathematics and Applications. SI AM, Philadelphia. 2001.

98. Umans C., Lenhart W. Hamiltonian cycles in solid grid graphs, in Proc. 38th Annu. IEEE Sympos. Found. Comput. Sci., 1997, pp. 496-507.

99. West D. An Introduction to Graph Theory, Prentice Hall, 1995.