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

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

005055822

Плотников Олег Александрович

РАЗРАБОТКА АЛГОРИТМОВ МНОГОАЛЬТЕРНАТИВНОЙ МАРШРУТИЗАЦИИ ГРУЗОПЕРЕВОЗОК В СИСТЕМАХ ТРАНСПОРТНОЙ ЛОГИСТИКИ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ

МЕТОДОВ

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

АВТОРЕФЕРАТ

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

2 9 НОЯ 2012

Воронеж - 2012

005055822

Работа выполнена в ФГБОУ ВПО «Воронежский государственный технический университет».

Научный руководитель Подвальный Евгений Семенович,

доктор технических наук, профессор, ФГБОУ ВПО «Воронежский государственный технический университет», профессор кафедры автоматизированных и

вычислительных систем

Официальные оппоненты: Матвеев Михаил Григорьевич,

доктор технических наук, профессор, ФГБОУ ВПО «Воронежский государственный университет», профессор кафедры программирования и информационных технологий

Васильев Олег Вячеславович,

кандидат технических наук,

ООО «АТ-Консалтинг», старший разработчик

Ведущая организация ФГБОУ ВПО «Липецкий государственный

технический университет»

Защита состоится «21» декабря 2012 г. в 11 час. 30 мин. в конференц-зале на заседании диссертационного совета Д 212.037.02 ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский пр., 14.

С диссертацией можно ознакомиться в научно-технической библиотеке ФГБОУ ВПО «Воронежский государственный технический университет».

Автореферат разослан «20» ноября 2012 г.

Ученый секретарь диссертационного СОВ;

мурнов Сергей Михайлович Л

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

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

Особенно актуально решение задач маршрутизации в условиях крупных городов и мегаполисов ввиду разветвленной транспортной сети и большого количества точек доставки. Основными задачами планирования доставки являются: задача нахождения оптимальных маршрутов (задача коммивояжера) и задача оптимальной загрузки транспортных средств (задача о ранце). Задача о коммивояжере и задача о ранце исследуются в теории комбинаторной оптимизации и относятся к классу КР-сложных задач. На практике данные задачи оказываются еще сложнее за счет выполнения доставки парком транспортных средств с ограниченной грузоподъемностью, нерегулярной средней скорости движения в течение дня, а также необходимости выполнения доставки «точно в срок». Данная задача является задачей маршрутизации транспорта. Исследованиями в данной области занимались М.И. Смирнов, Р.З. Хайруллин, А. О. Алексеев, И. И. Меламед, С. И. Сергеев, И. X. Сигал, .1. Ь. В!ап1оп, в. ,1еоп и др.

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

Решение задачи маршрутизации позволяет решить следующие задачи планирования доставки:

- распределение транспортных средств по маршрутам с учетом их грузоподъемности;

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

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

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

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

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

Тематика диссертационной работы соответствует одному из основных научных направлений ФГБОУ ВПО «Воронежский государственный технический университет»: «Вычислительные комплексы и проблемно-ориентированные системы управления».

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

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

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

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

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

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

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

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

Тематика работы соответствует п. 4 «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации», п. 5 «Разработка специального математического и программного обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации» и п. 9 «Разработка проблемно-ориентированных систем управления, принятия решений и оптимизации технических, экономических, биологических, медицинских и социальных объектов» паспорта специальности 05.13.01 - «Системный анализ,

управление и обработка информации».

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

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

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

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

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

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

Работа поддержана целевым грантом фонда содействия развитию малых форм предприятий в научно-технической сфере в рамках программы «УМНИК» (проект №14306) и грантом администрации городского округа город Воронеж на проведение НИОКР, направленной на решение проблем городского хозяйства (договор №33).

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

Полученные в диссертации результаты используются в учебном процессе Воронежского государственного технического университета при чтении спецкурсов. Интерактивная система маршрутизации используется в ООО Научно-производственном предприятии «Орт» и ООО «Альфа-Инжиниринг».

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

конференциях: Всероссийской конференции «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2009); VIII Всероссийской научно-практической конференции «Актуальные вопросы профессионального образования» (Воронеж, 2010); Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых, секция «Информационные технологии» (Воронеж, 2011); XII Международной научно-методической конференции «Информатика: проблемы, методология, технологии» (Воронеж, 2012); V Международной научно-производственной конференции «Новые технологии управления движением технических объектов» (Москва, 2012); а также на научных конференциях ФГБОУ ВПО «Воронежский государственный технический университет».

Публикации. По результатам диссертации опубликовано 12 научных работ, в том числе 4 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежат: [1] — алгоритм решения задачи поиска кратчайшего пути между вершинами графа с нерегулярным весом ребер, [2] — разработка геоинформационной компоненты в составе подсистемы маршрутизации, [5] — анализ использования геоинформационных подсистем в составе информационных систем транспортной логистики, [6] — методы решения задач маршрутизации транспортной логистики, [3, 4, 7] - алгоритм решения задачи маршрутизации для парка автотранспортных средств, [8] - разработка специального программного обеспечения, [9] - муравьиный алгоритм как алгоритм локального поиска при решении задач маршрутизации. Материалы диссертации отражены также в 3 научно-технических отчетах НИОКР.

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

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

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

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

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

Показано, что для решения задачи маршрутизации необходимо решение следующих задач:

- разработка алгоритма нахождения глобального плана доставки для парка транспортных средств;

- разработка алгоритма локального поиска в составе алгоритма глобального поиска;

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

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

многокритериальности выбора.

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

В конце главы сформулированы цели и задачи исследования.

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

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

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

Типичная формула эвристики выражается в виде

f(n) = g(n) + h(n), (1)

где f(n) - значение оценки, назначенное узлу n, g(n) - наименьшая стоимость прибытия в узел п из точки старта, h(n) - эвристическое приближение

стоимости пути к цели от узла п.

Также во второй главе проведена оптимизация алгоритма А* по времени выполнения (табл. 1). Оценка работы алгоритма рассмотрена для двух случаев: трудного и простого. Измерение проводилось в миллисекундах для каждого из случаев. Соотношения скорости работы алгоритма при оптимизации даны по отношению к предыдущим реализациям алгоритма.

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

Затем для организации поиска в глубину была произведена замена очереди по принципу FIFO на очередь по принципу LIFO.

Для поиска вершины в сортирующем дереве многие стандартные алгоритмы требуют времени 0(F). Для минимизации временных затрат были исследованы различные структуры данных, которые могут применяться в работе алгоритма А*. В результате анализа структур данных сделан вывод о том, что для поставленной задачи целесообразно использовать хэш-таблицы, так как выполнение операций с ними происходит за время 0(1), а количество узлов относительно небольшое.

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

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

На рис. 1 показан пример сокращения количества обрабатываемых узлов. На рисунке слева (до оптимизации) количество узлов равно 763, справа (после оптимизации) - 447.

Рис. 1. Пример сокращения количества обрабатываемых узлов (слева - до оптимизации, справа - после оптимизации)

Схема работы модифицированного алгоритма А* представлена на рис. 2.

Рис. 2. Схема работы модифицированного алгоритма А*

Таблица 1

Оценка результатов работы алгоритма А*

Реализация Простой случай Трудный случай

Время ЦП Изменение, MC Изменение, % Время ЦП Изменение, MC Измене -пие, %

Классический А* 315 - - 2876 - -

Оптимизация графа 288 27 8,57 2360 516 17,94

Очередь по принципу LIFO 243 45 15,63 2193 167 7,07

Использование структур HashMap 9,22 233,78 96,20 228 1965 89,60

Контроль оценки эвристического приближения 1,7 7,52 81,56 13,3 214,7 94,17

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

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

Доставка осуществляется парком автотранспортных средств в соответствии со списком заявок на доставку. Каждое транспортное средство имеет определенную грузоподъемность, что накладывает ограничения на суммарный вес перевозимых товаров. Товары также характеризуются определенным весом.

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

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

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

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

Пусть п — количество транспортных средств; ш — количество заявок; с,^ Рук - соответственно стоимость, время и вес, характеризующие затраты на перемещение из узла к-1 в узел к дорожного графа при выполнении заявки ] транспортным средством г, Рг грузоподъемность транспортного средства ¡. Кроме того, транспортное средство I = 1, п может участвовать в доставке или нет и выполнять или не выполнять заявку у = 1, т.

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

п т I

)кРцкУ]Х1 min, (2)

¡=i /=i fc=i n m l

^ ^T CijkPijkyjXi min, (3)

¡=1 j—1 k=l m l i n

^ ^ ^ VtjkyjXi /PiXi -> max, (4)

i—1 j=1 k=l I i=l

lk

(5)

cijk = Ujk * Vu (6)

r 0, если ТС не участвует в плане доставки, (.1, ( = 1, п, если ТС участвует в плане доставки, ^ ( 0, если ТС не выполняет заявку,

il, j = 1, m, если ТС выполняет заявку, ^

где li - длина дороги k, Ut(t) - средняя скорость движения по дороге к в зависимости от времени дня (задается исходя из статистики), V, - удельный расход топлива транспортного средства 1, х,, У) - булевы переменные. Должно выполняться условие баланса:

^ Pik = <*£

|£=1 z

(9)

9=1

л m

i=1

где а, - товары, перевозимые транспортным средством ¡; ^ - товары в заявке].

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

С т I

]Г Л РЦкУ! < Ри

;'=1 к=1 <

_ г

Г 0,_

(1,; = 1 ,т'

(10)

где 1:ц - время выполнения заявки ] транспортным средством ¡; [^..^г] -временной интервал, в который необходимо выполнить доставку по заявке].

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

п т I

/_,/_! стРа>сУ1х1 т1п> ]=1 к=1 п т I

(11)

1 = 1 у = 1 к = 1

п т I / п

¿=1 ;=1к=1 / ¡=1 771 I

X X рг^у/ - р°

1=1 к=1 < <

771

;=1 О,

> с,

(12)

_( 0. = [ 0'

И 11, У = 1,т'

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

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

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

А1 А2 АЗ .. Ап

VI 0 1 0 0

У2 1 0 1 0

УЗ 0 0 0 1

Уп 0 0 0 0

где А1..Ап - заявки, VI..Уп - транспортные средства, 1 - признак выполнения заявки А1 транспортным средством VI.

Отметим, что каждая заявка может быть выполнена только одним транспортным средством, причем за одно посещение.

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

Л1 А2 АЗ ... Ап

2 1 п ... 3

где А1..Ап - заявки, 1..п - приоритет выполнения соответствующей заявки.

Очередь приоритетов является единственной для всех маршрутов в списке маршрутов конкретного мема.

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

- минимальное время, необходимое на выполнение заявок;

- минимальная стоимость выполнения заявок;

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

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

интерфейса.

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

Размер популяции является фиксированным. Для оценки решения в текущем поколении популяции мы используем оценку приспособленности наиболее приспособленной особи.

Реализовано несколько операторов скрещивания:

- скрещивание в случайном соотношении (1-точечный кроссовер, рис.2);

- скрещивание в интервале (2-точечный кроссовер, рис. 3);

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

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

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

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

Рис. 3. Скрещивание в случайном соотношении

Рис. 4. Скрещивание интервалом от I до ]

Реализован метод использования «транспопуляций». Если оценка приспособленности не улучшается некоторое количество поколений, то на следующем поколении формируется заданное число новых популяций, которые характеризуются малым количеством поколений. Тем самым мы вносим в основную популяцию дополнительное разнообразие.

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

Модифицированный меметический алгоритм протестирован с различными настройками параметров. В табл. 2 приведены оценки значений работы алгоритма для 200 заявок при выполнении их парком из 30 транспортных средств различной грузоподъемности. Алгоритм имеет следующие настройки:

- размер популяции (количество особей) - 50;

- количество поколений популяции - 200;

- вероятность мутации - 50 %;

- количество поколений с равным значением приспособленности, после которого вводятся транспопуляции - 5;

- количество транспопуляций -3;

- количество поколений транспопуляций - 3;

- количество особей, переходящих в новое поколение - 1;

- вероятность смены метода селекции - 10 %;

- оптимизация выполняется по минимальной стоимости выполнения всех заявок.

Результаты работы алгоритма характеризуются:

- временем работы алгоритма;

- совокупным временем выполнения всех заявок на доставку;

- совокупной стоимостью выполнения всех заявок на доставку;

- средней загрузкой транспортных средств.

Таблица 2

Оценка результатов работы МА

Реализация Кол-во поколений Размер популя -ции Время выполнения, с Время, мин Стоимос ть, руб. Загрузка, %

Скрещивание в случайном соотношении 200 50 3 3721 33393 55,4

Скрещивание интервалом от 1 до ) 200 50 6 3742 32973 55,5

Скрещивание выбором случайных битов 200 50 7 3551 32882 55,9

Скрещивание выбором случайных битов (2) 200 50 10 3520 32868 55,4

Мутация 200 50 12 3505 31978 56.0

Использование транспопуляций 200 50 16 3125 29885 56,4

Исключение неиспользуемых ТС 200 50 14 3414 21078 66,8

Локальный поиск 200 50 18 3278 19991 78,1

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

Таким образом, модифицированный меметический алгоритм отвечает принципам многоальтернативных систем за счет того, что:

1. Использует многоальтернативность выбора:

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

-при попадании решения в локальный оптимум используются методы введения «транспопуляций» и метод исключения неиспользуемых транспортных средств;

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

включающего отбор наиболее приспособленных особей и турнирный отбор.

2. Использует многокритериальность выбора: оптимизация может выполняться по одному из трех критериев (по минимальной стоимости, по минимальному времени, по максимальной загрузке).

3. Использует параллельность выбора: генетические операторы выполняются параллельно с последующим объединением частных результатов.

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

Проанализированы входные и выходные данные для интерактивной системы оптимизации грузоперевозок, на основе данного анализа спроектирована база данных программного средства.

Разработана модульная структура программного средства с учетом архитектуры МУС (рис. 5). Основные классы программного обеспечения вынесены в отдельный модуль и могут быть использованы как АР1 для взаимодействия с разработанной системой маршрутизации. Кроме того, класс, взаимодействующий с БД, работает как служба и может быть доступен из любой точки программной системы.

Сплошными линиями показаны прямые зависимости модулей, пунктирными - связи модулей с использованием «слабых связей» и шаблона проектирования «наблюдатель».

Рис. 5. Модульная структура системы маршрутизации 15

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

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

Для повышения скорости работы меметического алгоритма в модуле оптимизации применяются методы параллельных вычислений. Тесты проводились на рабочей станции с двухъядерным процессором AMD Turion II Dual-Core. Из результатов тестов (рис. 6) видно, что оптимальное количество потоков равно количеству ядер процессора. Это также подтверждается и другими разработчиками программного обеспечения при решении различного рода задач. Применение параллельных вычислений позволило повысить скорость работы алгоритма в среднем в 2 раза.

120 100 SO к 60 £ 01 £ 40 20 0

\......._........................

. \..........._.................. .............................................................

\..............._........................................

1 2 3 44 4 5 6 7 8 ;

««««««800 поколений 104 44 44 44 44 45 44

«™»-»»400 поколений 38 20 22 ................. 11 21 22 21 22 21

..............200 поколений 19 11 11 11 11 11 12

Рис. 6. График зависимости времени выполнения алгоритма от количества потоков

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

Разработанная система оптимизации планирования грузоперевозок реализована на языке Java и содержит механизмы встраивания в промышленные системы, в том числе ERP-системы, такие как, например, Compiere и Openbravo. Визуальный интерфейс системы оптимизации грузоперевозок представлен на рис. 7.

Рис. 7. Визуальный интерфейс основного вида системы маршрутизации

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

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

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

2. Разработан алгоритм решения задачи поиска оптимального пути между вершинами дорожного графа с нерегулярным весом ребер. Данный алгоритм основан на алгоритме А*. Предложен метод контроля оценки эвристического приближения для ускорения поиска решения за счет направленного поиска (поиска в глубину).

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

4. В качестве локального поиска модифицированного меметического

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

5. На основе разработанных алгоритмов реализовано специальное программное обеспечение для решения задачи маршрутизации парка автотранспортных средств с ограничениями грузоподъемности при использовании дорожного графа с нерегулярным весом ребер с учетом выполнения доставки «точно в срок».

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

7. Зарегистрирован программный модуль «Подсистема создания интерактивной карты в системе маршрутизации автотранспорта» в ФАП ВНТИЦ, № 14353890.00440 и программный модуль «Интерактивная АИС комплексного решения задач транспортной логистики» в ФГНУ ЦИТИС, № госрегистрации 2012618764 от 26.09.2012.

Основные результаты диссертации опубликованы в следующих работах:

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

1. Плотников O.A. Решение задачи поиска оптимального пути между двумя точками на графе с нерегулярным весом ребер / O.A. Плотников, Е.С. Подвальный // Вестник Воронежского государственного технического университета. 2012. Т. 8. № 6. С. 22-27.

2. Подвальный Е.С. Разработка структуры и графического интерфейса интерактивной системы маршрутизации / Е.С. Подвальный, O.A. Плотников // Вестник Воронежского государственного технического университета. 2011. Т. 7. № 12.1. С. 96-101.

3. Плотников O.A. Разработка алгоритма для комплексного решения задач АСУ транспортной логистики / O.A. Плотников, Е.С. Подвальный // Вестник Воронежского государственного технического университета. 2011. Т. 7. № 11.1. С. 102-105.

4. Плотников O.A. Разработка меметического алгоритма для решения задач оптимального планирования грузоперевозок / O.A. Плотников, Е.С. Подвальный // Вестник Воронежского государственного технического университета. 2012. Т. 8. № 8.1. С. 93-98.

Статьи и материалы конференций

5. Плотников O.A. Использование геоинформационных систем: проблемы и перспективы развития / O.A. Плотников, Е.С. Подвальный // Новые технологии в научных исследованиях, проектировании, управлении, производстве, НТ-2009: сб. науч. тр. Всерос. конф. Воронеж: ВГТУ, 2009. С. 78.

6. Плотников O.A. Методы оптимизации, применяемые для решения задачи о коммивояжере при управлении муниципальным транспортом / O.A. Плотников, Е.С. Подвальный // Актуальные вопросы профессионального образования: материалы VIII Всерос. науч.-практ. конф. Воронеж: ВФ РАГС, 2010. С. 46-49.

7. Плотников O.A. Комплексное решение задач транспортной логистики с помощью интерактивной системы маршрутизации / O.A. Плотников, Е.С. Подвальный // Инновационные технологии и материалы (ИТМ-2011): Всерос. науч.-практ. конф. студентов, аспирантов и молодых ученых, секция «Информационные технологии». Воронеж: ЗАО «Воронежский инновационно-технологический центр», 2010. С. 11-12.

8. Плотников O.A. Разработка интерактивной системы маршрутизации для комплексного решения задач транспортной логистики в соответствии с архитектурой MVC / O.A. Плотников, Е.С. Подвальный // Информатика: проблемы, методология, технологии: материалы XII Междунар. науч.-метод. конф. Воронеж: ВГУ. 2012, Т. 1. С. 319-320.

9. Плотников O.A. Применение муравьиных алгоритмов для решения задачи коммивояжера при управлении движением парка транспортных средств / O.A. Плотников, Е.С. Подвальный // Новые технологии управления движением технических объектов: сб. тр. 5-ой Междунар. науч.-производ. конф. М., 2012. С. 31-36.

10. Плотников O.A., Подвальный Е.С. Программный модуль «Интерактивная АИС комплексного решения задач транспортной логистики». -М.: ФГНУ ЦИТИС, 2012. -№ госрегистрации 2012618764 от 26.09.2012.

11. Подвальный Е.С., Плотников O.A. Программный модуль «Подсистема создания интерактивной карты в системе маршрутизации автотранспорта». - М.: ФАП ВНТИЦ, 2009, - № 14353890.00440.

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

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

Введение.

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

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

1.2 Постановка задачи маршрутизации транспорта.

1.3 Методы решения задачи маршрутизации транспорта.

1.4 Алгоритмы нахождения оптимального пути между вершинами дорожного графа.

1.5 Использование геоинформационных компонент в составе информационных систем транспортной логистики.

1.6 Цели и задачи исследования.

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

2.1. Алгоритма А* для решения задачи поиска путей на графе.

2.2 Модификация алгоритма А* и оценка результатов работы.

Глава 3. Разработка алгоритма нахождения глобального плана доставки задачи маршрутизации транспорта.

3.1 Постановка задачи оптимизации глобального плана доставки.

3.2 Разработка модифицированного меметического алгоритма для решения задачи маршрутизации транспорта.

3.3 Алгоритма муравьиной колонии в качестве алгоритма локального поиска.

Глава 4 Разработка проблемно-ориентированного программного обеспечения многоальтернативной маршрутизации грузоперевозок.

4.1. Модульная структура системы маршрутизации.

4.2 Интерфейс программирования приложений.

4.3 База данных приложения и объектно-реляционное отображение.

4.4. Разработка геоинформационной компоненты в составе системы маршрутизации.

4.5. Модуль решения задач маршрутизации проблемноориентированного программного обеспечения.

4.6 Визуальный интерфейс программного средства.

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

Особенно актуально решение задач маршрутизации в условиях крупных городов и мегаполисов, в виду разветвленной транспортной сети и большого количества точек доставки. Основными задачами планирования доставки являются: задача нахождения оптимальных маршрутов (задача коммивояжера) и задача оптимальной загрузки транспортных средств (задача о ранце). Задача о коммивояжере и задача о ранце исследуются в теории комбинаторной оптимизации, и относятся к классу ЫР-сложных задач. На практике данные задачи оказываются еще сложнее, за счет выполнения доставки парком транспортных средств с ограниченной грузоподъемностью, нерегулярной средней скорости движения в течение дня, а также необходимости выполнения доставки «точно в срок». Данная задача является задачей маршрутизации транспорта. Исследованиями в данной области занимались М.И. Смирнов, Р.З. Хайруллин, А. О. Алексеев, И. И. Меламед, С. И. Сергеев, И. X. Сигал, 1 Ь. В1апк)п, в. .1еоп и др.

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

Решение задачи маршрутизации позволяет решить следующие задачи планирования доставки:

- распределение транспортных средств по маршрутам с учетом их грузоподъемности;

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

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

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

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

Тематика диссертационной работы соответствует одному из основных научных направлений ФГБОУ ВПО «Воронежский государственный технический университет»: «Вычислительные комплексы и проблемноориентированные системы управления». 5

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

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

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

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

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

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

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

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

Тематика работы соответствует п. 4 «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации», п. 5 «Разработка специального математического и программного обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации» и п. 9 «Разработка проблемно-ориентированных систем управления, принятия решений и оптимизации технических, экономических, биологических, медицинских и социальб пых объектов» паспорта специальности 05.13.01 - «Системный анализ, управление и обработка информации».

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

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

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

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

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

Работа поддержана целевым грантом фонда содействия развитию малых форм предприятий в научно-технической сфере, в рамках программы «УМНИК» (проект №14306), и грантом администрации городского округа город Воронеж на проведение НИОКР, направленной на решение проблем городского хозяйства (договор №33).

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

Полученные в диссертации результаты используются в учебном процессе Воронежского государственного технического университета при чтении спецкурсов. Интерактивная система маршрутизации используются в ООО Научно-производственном предприятии «Орт» и ООО «Альфа-Инжиниринг».

Апробация работы. Основные результаты, полученные в диссертационной работе, докладывались и обсуждались на международных и всероссийских конференциях: Всероссийской конференции «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2009.); VIII Всероссийской научно-практической конференции «Актуальные вопросы профессионального образования» (Воронеж, 2010.); Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых, секция «Информационные технологии» (Воронеж, 2011); XII Международной научно-методической конференции «Информатика: проблемы, методология, технологии.» (Воронеж, 2012); V Международной научно-производственной конференции «Новые технологии управления движением технических объектов» (Москва, 2012); а также на научных конференциях Воронежского государственного технического университета.

Публикации. Основные результаты диссертации опубликованы в 12 научных работах, в том числе 4 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве и приведенных а автореферате, лично соискателю принадлежат следующие результаты: [1] - алгоритм решения задачи поиска кратчайшего пути на карте между двух точек, [2] - разработка геоинформационной компоненты в составе подсистемы маршрутизации, [5] -анализ использования ГИС в составе АИС транспортной логистики, [6] - методы решения задач маршрутизации транспортной логистики, [3, 4, 7] - алгоритм решения задачи маршрутизации для парка автотранспортных средств, [8] - разработка специального программного обеспечения, [9] - муравьиный алгоритм как алгоритм локального поиска при решении задач маршрутизации. Материалы диссертации отражены также в 3 научно-технических отчетах НИОКР.

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 133 страницах, списка литературы из 164 наименований, содержит 33 рисунка и 3 таблицы.

Основные результаты работы состоят в следующем:

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

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

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

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

118 регулярной средней скоростью в течение дня и учитывающий необходимость доставки «точно в срок».

5. На основе разработанных алгоритмов реализовано специальное программное обеспечение для решения задачи маршрутизации парка автотранспортных средств с ограничениями грузоподъемности при использовании дорожного графа с нерегулярным весом ребер с учетом условия доставки «точно в срок».

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

7. Зарегистрирован программный модуль «Подсистема создания интерактивной карты в системе маршрутизации автотранспорта» в ФАП ВНТИЦ, № 14353890.00440 и программный модуль «Интерактивная АИС комплексного решения задач транспортной логистикой» в ФГНУ ЦИТИС, № госрегистрации 2012618764 от 26.09.2012.

ЗАКЛЮЧЕНИЕ

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

1. В.А. Гудков, Л.Б. Миротин A.B. Вельможин Теория организации и управления автомобильными перевозками: Логистический аспект формирования перевозочных процессов — Волгоград: Политехник, 2001.

2. М. А. Гайдес Общая теория систем (системы и системный анализ) //. — Винница, 2005. — с. 201.

3. К. И. Плужников С. В. Милославская Мультимодальные и интермодальные перевозки //, 2001.

4. Холопов К.В Экономика и организация внешнеторговых перевозок //. — Москва, 2000.

5. Тарабанько В.В. Левиков Г.А. Смешанные перевозки (состояние, проблемы, тенденции) //. — Москва, 2004.

6. Транспортное обеспечение внешнеторговых операций. Справочник. Кига 1 //. — Санкт-Петербург, 1998.

7. Е. Дрозд Интермодальные перевозки: мировой опыт // Гражданская авиация. — 2006

8. В. Никифоров Мультимодальные перевозки и транспортная логистика — Москва: РосКонсульт, 2007. — 272 с.

9. Николашин В.М. Сервис на транспорте: Учебное пособие — Москва: Academia, 2004.

10. Т. И. Семенович Автомобильные перевозки — s.l.: ИНФРА-М, 2009. — 224 с.

11. Л.Б. Миротин Учебник для транспортных вузов / Под общей редакцией Л.Б. Миротина //. — Москва, 2003. — с. 512.

12. В. В. Беднарский М. Е. Майборода Грузовые автомобильные перевозки — s.l.: Феникс, 2008. — 448 с.

13. Седюкевич В.Н Ванчукевич В.Ф. Автомобильные перевозки — s.l.: Дизайн ПРО, 1999.

14. Акулиничев В.М. Организация перевозок на промышленном транспорте — s.l.: Высшая школа, 1983.

15. Горев А.Э. Грузовые автомобильные перевозки — Москва: ИД Академия, 2008.

16. С. И. Коновалов, Ф. П. Касаткин Э. Ф. Касаткина Организация перевозочных услуг и безопасность транспортного процесса — Москва: Академический проект, 2005. — 352 с.

17. Гудков В.А, Миротин Л.Б., Куликов А.В. Вельможин А.В. Грузовые автомобильные перевозки — s.l.: Горячая линия Телеком, 2006. — 560 с.

18. Гаджинский А.М. Логистика: Учебник для высших и средних специальных учебных заведений.- 2-е изд. — Москва: Информационно-внедренческий центр "Маркетинг", 1999. — 228 с.

19. Логистический подход к управлению материальными потоками // сайт. URL: http://www.mybntu.com/techno/production/logisticheskij-podxod-k-upravleniyu-materialnymi-potokami.html (дата обращения: 05/11/2010).

20. Кузнецов В.Г. Николайчук В.Е. Теория и практика управления материальными потоками (логистическая концепция). Монография — Донецк: «КИТИС», 1999. — 413 с.

21. Т.В. Алесинская Основы логистики. Функциональные области логистического управления — Таганрог: Издательство ТТИ ЮФУ, 2010. — 116 с.

22. В.Г. Дегтяренко Основы логистики и маркетинга — Москва: Гардарика, 1996, —120 с.

23. Автоматизированная информационная система // Seopedia. URL: http://www.seobuilding.ru/wiki/aвтoмaтизиpoвaннaяинфopмaциoннaяcиcтeмa (дата обращения: 06/11/2010).

24. A Guide to Understanding Data Remanence in Automated Information Systems // The Rainbow Books. URL: http://www.fas.org/irp/nsa/rainbow/tg025-2.htm (дата обращения: 06/11/2010).

25. Ы.Э. Ташбаев Л.Б. Миротин Логистика для предпринимателя —- Москва: Инфра-М, 2002.

26. Маглинец Ю.А. Анализ требований к автоматизированным информационным системам: Учебное пособие — s.l.: s.n., 2008.

27. Раджив Мотвани, Джеффри Ульман Джон Хопкрофт Введение в теорию автоматов, языков и вычислений — Москва: Вильяме, 2002.

28. Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Томас X. Кормен Алгоритмы: построение и анализ. — 2-е изд. — Москва: Вильяме, 2006. — 1296 с.

29. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы.3.е изд. — Москва: Вильяме, 2006. — 720 с.

30. Колмогоров А. Н. Теория информации и теория алгоритмов — Москва: Наука, 1987. —304 с.

31. Нагорный Н. М. Марков А. А. Теория алгоритмов, изд. 2 — Москва: ФАЗИС, 1996.

32. Подвальный С.Л. Обзор и классификация многоальтернативных систем // Информационные технологии моделирования и управления. — №74., Выпуск 2. — 2012. — с. 104-121

33. Подвальный С.Л. Многоальтернативные системы: обзор и классификация // Системы управления и информационные технологии. — №48., Выпуск 2.2012. —с. 4-13

34. Динамическое программирование // Яндекс словари. URL: Ьйр://з1оуап.уапс1ех.ги/Динамическоепрограммирование (дата обращения: 10/11/2011).

35. Динамическое программирование // Википедия. URL: http://ru.wikipedia.0rg/wiki^HHaMH4ecK0enp0rpaMMHp0BaHHe (дата обращения: 10/11/2011).

36. Christos Н. Papadimitriou, Umesh Vazirani Sanjoy Dasgupta Algorithms — 1e изд. — s.l.: McGraw-Hill Science/Engineering/Math, 2006. — 336 c.

37. Стенли P. Перечислительная комбинаторика — M: Мир, 1990. — 440 с.

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

39. Рыбников К. А. Введение в комбинаторный анализ. — 2-е изд. —М: Изд-воМГУ, 1985,—309 с.

40. А. Н. Land and A. G. Doig An automatic method of solving discrete programming problems — s.l.: s.n. — 497-520 c.

41. Murty K.G., Sweeney D.W., and Karel C. Little J.D.C. An algorithm for the traveling salesman problem // Operations Research. — 1963. — c. 972-989

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

43. Jens Clausen Branch and Bound Algorithms Principles and Examples — s.l.: s.n., 1999.

44. R. E. Moore Global optimization to prescribed accuracy // Computers and Mathematics with Applications. — 1991. — c. 25-39

45. Stephen Boyd and Jacob Mattingley Branch and Bound Methods. Notes for EE364b, Stanford University //. — 2007

46. Michael A. Trick. Branch and Bound // Michael Trick's Operations Research Page. URL: http://mat.gsia.cmu.edu/classes/integer/nodel3.html (дата обращения: 15/11/2011).

47. B.J. Lageweg, Jan K. Lenstra, James B. Orlin, Leen Stougie Koen M.J. De Bontridder Branch-and-Bound Algorithms for the Test Cover Problem //.

48. D. S. Johnson M. R. Garey Computers and Intractability: A Guide to the Theoryof NP-completeness — San Francisco: Freeman, 1979.

49. J. K. Lenstra A. W. J. Kolen Combinatorics in operations research — Amsterdam: Elsevier, 1995.

50. Дикин И. И. 747-748. Итеративное решение задач линейного и квадратичного программирования //. —№174., Выпуск 4. — 1967

51. Акулич И.Л. Математическое программирование в примерах и задачах — М: Высшая школа, 1986. — 319 с.

52. J. Е. Beasley Advances in Linear and Integer Programming — Oxford: Oxford Science, 1996.

53. Katta G. Murty Linear programming — New York: John Wiley & Sons, Inc., 1983.

54. Evar D. Nering and Albert W. Tucker Linear Programs and Related Problems — s.l.: Academic Press, 1993.

55. Голыитейн Е.Г. Юдин Д.Б. Линейное программирование. Теория, методы и приложения — s.l.: s.n., 1969.

56. Д.Э.Хопкрофт, Д.Д.Ульман А.В.Ахо Структуры данных и алгоритмы — М: Вильяме, 2001.

57. Эвристический алгоритм // Википедия. URL: http://ru.wikipedia.org/wiki/Эвpиcтичecкийaлгopитм (дата обращения: 17/11/2011).

58. A. Yeo and A. Zverovich G. Gutin Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP // Discrete Applied Mathematics. — 2002. — c. 81-86

59. G. Bendall and F. Margot Greedy Type Resistance of Combinatorial Problems // Discrete Optimization. — №3. — 2006. — c. 288-298

60. Greedy algorithm // Wikipedia. URL: http://en.wikipedia.org/wiki/Greedyalgorithm (дата обращения: 18/11/2011).

61. Алфёрова З.В. Теория алгоритмов — М: Статистика, 1973.

62. Jon L. Bentley Experiments on traveling salesman heuristics // Proc. 1st ACM-SIAM Symp. Discrete Algorithms (SODA). — 1990. — c. 91-99

63. A. B. Kahng and S. Reda Match Twice and Stitch: A New TSP Tour Construction Heuristic // Operations Research Letters. — №6., Выпуск 32. — 2004. —с. 499-509

64. Shen Lin,В- W. Kernighan An Effective Heuristic Algorithm for the Traveling-Salesman Problem I I Operations Research. — №2., Выпуск 21. — 1973. — с. 498-516

65. К. Helsgaun An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic // European Journal of Operational Research. — №1., Выпуск 126. —2000,—с. 106-130

66. David S. Johnson,Lyle A. McGeoch The Traveling Salesman Problem: A Case Study in Local Optimization // Local Search in Combinatorial Optimization. — 1997. —c. 215-310

67. H.H. and Stutzle T. Hoos Stochastic Local Search: Foundations and Applications //. — 2005

68. Vijay Arya and Naveen Garg and Rohit Khandekar and Adam Meyerson and Kamesh Munagala and Vinayaka Pandit Local Search Heuristics for k-Median and Facility Location Problems // Siam Journal of Computing. —№3., Выпуск 33. — 2004

69. IO. А. Кочетов, А. В. Плясунов H. И. Глебов Методы оптимизации. Учебное пособие //. — 2000. — с. 105

70. The TSP package for R // The TSP package for R. URL: http://tsp.r-forge.r-project.org/ (дата обращения: 23/11/2011).

71. Gilbert Babin, Stéphanie Deneault, Gilbert Laportey Improvements to the Or-opt Heuristic for the Symmetric Traveling Salesman Problem — Montreal: Cahiers du GERAD, 2005.

72. D. L. Applegate и др. The Traveling Salesman Problem: A Computational Study — s.l.: Princeton University Press, 2006.

73. D. E. Goldberg Genetic Algorithms in Search, Optimization & Machine Learning — New York: Addison-Wesley, 1989.

74. E. L. Lawler и др. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization — s.l.: John Wiley & Sons, 1985.

75. Fogel David B. Evolutionary Computation: The Fossil Record — New York: IEEE Press, 1998.

76. Курейчик В. В., Курейчик В. М. Емельянов В. В. Теория и практика эволюционного моделирования —М: Физматлит, 2003. —432 с.

77. Лебедев Б. К., Лебедев О. К. Курейчик В. М. Поисковая адаптация: теория и практика — М: Физматлит, 2006. — 272 с.

78. Курейчик В. В., Курейчик В. М. Гладков Л. А. Генетические алгоритмы: Учебное пособие. — 2-е изд. — М: Физматлит, 2006. — 320 с.

79. Курейчик В. В, Курейчик В. М. и др. Гладков Л. А. Биоинспирированные методы в оптимизации: монография — М: Физматлит, 2009. — 384 с.

80. Пилиньский М., Рутковский Л. Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы. — 2-е изд. — М: Горячая линия-Телеком, 2008. — 452 с.

81. Wolfgang Banzhaf и др. Genetic Programming An Introduction — San Francisco: Morgan Kaufmann, 1998.

82. Robert R Bies и др. A Genetic Algorithm-Based, Hybrid Machine Learning Approach to Model Selection // Journal of Pharmacokinetics and Pharmacodynamics. — 2006. — c. 196-221

83. David В Fogel Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. Third Edition — Piscataway: IEEE Press, 2006.

84. John Koza Genetic Programming: On the Programming of Computers by Means of Natural Selection — s.l.: MIT Press, 1992.

85. X. S. Chen и др. A Multi-Facet Survey on Memetic Computation // IEEE Transactions on Evolutionary Computation. — №5., Выпуск 15. — 2011. — с. 591-607

86. X. S. Chen, Y. S. Ong, M. H. Lim Research Frontier: Memetic Computation -Past, Present & Future // IEEE Computational Intelligence Magazine. — №2., Выпуск 5. — 2010. — с. 24-36

87. Kendall G. and Soubeiga E. and Cowling P. Choice function and random hyperheuristics // 4th Asia-Pacific Conference on Simulated Evolution and Learning SEAL. — 2002. — c. 667-671

88. Ong Y. S. and Keane A. J. 99-110 Meta-Lamarckian learning in memetic algorithms // IEEE Transactions on Evolutionary Computation. — №2., Выпуск 8. — 2004

89. Ong Y. S. and Lim M. H. and Zhu N. and Wong K. W. Classification of Adaptive Memetic Algorithms: A Comparative Study // IEEE Transactions on Systems Man and Cybernetics. —№1., Выпуск 36. — 2006. — с. 141-156

90. E. Ozcan Memes, Self-generation and Nurse Rostering // Lecture Notes in Computer Science. — 2007. — c. 85-104

91. E. Ozcan,C. Basaran "A Case Study of Memetic Algorithms for Constraint Optimization // Soft Computing: A Fusion of Foundations, Methodologies and Applications. — №8., Выпуск 13. —2009.— с. 871-882

92. S., Yang, Z. Areibi Effective memetic algorithms for VLSI design automation = genetic algorithms + local search + multi-level clustering //, Evolutionary Computation. — №3., Выпуск 12. — 2004. — с. 327-353

93. Chi-Keong Goh, Yew-Soon Ong, Kay Chen Tan Multi-Objective Memetic Algorithms — s.l.: Springer, 2009. — 416 c.

94. Ананий В. Левитин Алгоритмы: введение в разработку и анализ — М: Вильяме, 2006.

95. Е. W. Dijkstra A note on two problems in connexion with graphs // Numerische Mathematik. — 1959. — c. 269-271

96. F. Benjamin Zhan,Charles E. Noon Shortest Path Algorithms: An Evaluation Using Real Road Networks // Transportation Science. — №1., Выпуск 32. — 1998. —с. 65-73

97. Лорьер Ж.-Л. Системы искусственного интеллекта / Пер. с фр. и ред. В. Л. Стефанюка //. — 1991

98. Норвиг, П. Рассел С. Дж. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach / Пер. с англ. и ред. К. А. Птицына. — 2-е изд. — М: Вильяме, 1973.

99. R., Pearl, J Dechter Generalized best-first search strategies and the optimalityof A* //Journal of the ACM. —№32., Выпуск 3. — 1985.-е. 505 — 536127

100. Sven Koenig,Yaxin Liu, David Furcy Maxim Likhachev Incremental heuristic search in AI // AI Magazine. — №2., Выпуск 25. — 2004. — с. 99-112

101. Judea Pearl Heuristics: intelligent search strategies for computer problem solving//. — 1984

102. Patrick Lester. A* Pathfinding for Beginners // Policy Almanac. URL: http://www.policyalmanac.org/games/aStarTutorial.htm (дата обращения: 23/12/2011).

103. A* ALGORITHM TUTORIAL // I-Ieyes-Jones.com. URL: http://www.heyes-jones.com/astar.html (дата обращения: 15/12/2011).

104. S. Ghose, A. Acharya and S.C. de Sarkar P.P. Chakrabarti Heuristic search in restricted memory // Art. Intell. — 1989. — c. 197-221

105. R.E. Korf Depth-first iterative-deepening: An optimal admissible tree search //Art. Intell. —№1., Выпуск 27. — 1985. —с. 97

106. S. Ghosh, D.S. Nau, A.K. Pal and L. Kanal A. Mahanti Performance of IDA* on trees and graphs // 10th Nat. Conf. on Art. Int. — 1992. — c. 539-544

107. B.G. Patrick Binary iterative-deepening A*: An admissible generalization of IDA* search // Procs. 9th Canadian Conf. on Art. Intell. — 1992. — c. 54

108. S. Russell Effcient memory-bounded search methods", // Procs. European AI Conf. — 1992.—c. 1-5

109. Recursive Best First Search // Artifical Intelligence. URL: http://intelligence.worldofcomputing.net/ai-search/recursive-best-first-search.html (дата обращения: 17/11/2011).

110. Weixiong Zhang State Space Search: Algorithms, Complexity, Extensions, and Applications — s.l.: Springer, 1999.

111. Rong Zhou and Eric A. Hansen Memory-Bounded A* Graph Search // 15th International FLAIRS Conference Pensacola. — 2002

112. S. Russell Efficient memory-bounded search methods // In Proceedings of the 10th European Conference on Artificial intelligence. — 1992. — c. 1-5

113. SMA* // Wikipedia. URL: http://en.wikipedia.org/wiki/SMA* (дата обращения: 06/12/2011).

114. Шайтура С. В. Журкин И. Г. Геоинформационные системы — Москва: КУДИЦ-ПРЕСС, 2009. — 272 с.

115. Самардак А. С. Электронный учебник "Геоинформационные системы" //Электронный ресурс.

116. Подвальный Е.С. Плотников О.А. Использование геоинформационных систем: проблемы и перспективы развития // Новые технологии в научных исследованиях, проектировании, управлении, производстве, НТ-2009: Труды Всероссийской конференции. — с. 7-8

117. В. С. Тикунов Моделирование в картографии: Учебник — М: Изд-во МГУ, 1997.

118. Кулагин В.П., Тихонов А.Н., Цветков В.Я. Иванников А. Д. Геоинформатика — М: МАКС Пресс, 2001. — 349 с.

119. Кошкарев А.В., Тикунов B.C. и др. Капралов Е.Г. Основы геоинформатики —М: Издательский центр «Академия», 2004. —352 с.

120. Amit Patel. Implementation notes // Stanford Theory Group. URL: http://theory.stanford.edU/~amitp/GameProgramming/ImplementationNotes.html#s et-representation (дата обращения: 11/12/2011).

121. Kingsley Sage. Data Structures // University of Sussex. URL: http://www.informatics.susx.ac.ukycourses/dats/dats.html (дата обращения: 11/12/2011).

122. Robert Ronngren Rassul Acm A Comparative Study of Parallel and Sequential Priority Queue Algorithms //. — №7., Выпуск 2. — 1997. — с. 157— 209

123. Data Structures in С++ Case Study: Priority Queues // University of Minnesota Duluth. URL: http://www.d.umn.edu/~tcolburn/cs251 l/lectures/pqueue/pq0.htm (дата обращения: 11/12/2011).

124. Ricardo Baeza-Yates Gaston H. Gonnet. Handbook of Algorithms and Data Structures // Universidad de Chile. URL:http://users.dcc.uchile.cl/~rbaeza/handbook/hbook.html (дата обращения: 12/12/2011).

125. Class HashMap // Oracle. URL: http://docs.oracle.eom/javase/6/docs/api/java/util/HashMap.html (дата обращения: 12/02/2012).

126. Class Hashtable // Oracle. URL: http://d0cs.0racle.c0m/javase/6/d0cs/api/java/util/Hashtable.html (дата обращения: 12/02/2012).

127. Подвальный Е.С. Плотников O.A. Решение задачи поиска оптимального пути между двумя точками на графе с нерегулярным весом ребер // Вестник ВГТУ. — №8., Выпуск 6. — 2012. — с. 22-27

128. Андерсон Джеймс Дискретная математика и комбинаторика — Москва: Вильяме, 2006. — 960 с.

129. Hans Kellerer, Ulrich Pferschy, David Pisinger Knapsack Problems — s.l.: Springer, 2004.

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

131. Dan Graur,Wen-Hsiung Li Fundamentals of Molecular Evolution: Second Edition — Sunderland, Massachusetts: Sinauer Associates, Inc, 2000.

132. Thomas Stützle Marco Dorigo Ant colony optimization — s.l.: A Bradford book, 2004.

133. Штовба С.Д. Муравьиные алгоритмы // Математика в приложениях. — 2003. —с. 70-75

134. Батищев Д.И. Решение дискретных задач с помощью эволюционно-генетических алгоритмов — Н-Новгород: ННГУ, 2011. — 199 стр с.

135. Карл И. Вигерс Разработка требований к программному обеспечению — s.l.: Русская редакция, 2004.

136. Р. Хелм, Р. Джонсон, Дж. Влиссидес Э. Гамма Приемы объектно-ориентированного проектирования. Паттерны проектирования — Спб.: Питер, 2011.—368 с.

137. Сергей Рогачев. Обобщенный Model-View-Controller // RSDN. URL: http://rsdn.ru/article/patterns/generic-mvc.xml (дата обращения: 12/02/2012).

138. Мартин Фаулер Шаблоны корпоративных приложений — Москва: Вильяме, 2009. — 544 с.

139. Грег Уилсон Энди Орам Идеальный код — Спб: Питер, 2011. — 624 с.

140. Documentation // Oracle. URL: http://docs.oracle.com/ (дата обращения: 12/02/2012).

141. Netbeans // Netbeans. URL: http://netbeans.org/ (дата обращения: 12/02/2012).

142. Heiko Bock The Definitive Guide to NetBeans Platform 7 — s.l.: Apress, 2011.

143. Joshua Bloch Effective Java (2nd edition) — s.l.: Addison-Wesley, 2008. — 259-312 с.

144. С. J. Date Date on Database: Writings 2000-2006 — s.l.: Apress, 2006. — 566 c.

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

146. Дейт К. Дж. Введение в системы баз данных. — 8-е изд. — Москва: Вильяме, 2005. — 1328 с.

147. Когаловский М.Р. Энциклопедия технологий баз данных — Москва: Финансы и статистика, 2002. — 800 с.

148. Бегг К. Коннолли Т. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. — 3-е изд. — Москва: Вильяме, 2003. — 1436 с.

149. Кузнецов С. Д. Основы баз данных. — 2-е изд. — Москва: Интернет-университет информационных технологий БИНОМ. Лаборатория знаний, 2007. —484 с.

150. Ерош И. Л. Дискретная математика. Комбинаторика — СПб: СПбГУАП, 2001.

151. Оре О. Теория графов — М: Наука, 1968. — 336 с.

152. A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs // Math. Program. — 2005. — c. 251-282

153. Melanie Mitchell An Introduction to Genetic Algorithms — Cambridge: MIT Press, 1996.

154. R., Langdon, W. В., McPhee, N. F. Poli A Field Guide to Genetic Programming — s.l.: Lulu.com, freely available from the internet, 2008.

155. Lothar M Schmitt Theory of Genetic Algorithms // Theoretical Computer Science. —2001. — c. 1-61

156. Michael D Vose The Simple Genetic Algorithm: Foundations and Theory — Cambridge: MIT Press, 1999.

157. Роберт Седжвик Фундаментальные алгоритмы на С++. — 3-е изд. — Санкт-Петербург: ДиаСофт, 2002. — 688 с.

158. Silvano Martello,Paolo. Toth Knapsack problems: Algorithms and computer interpretations — s.l.: Wiley-Interscience, 1990.

159. A. Kulanoot, 47 (2001) L. Caccetta Computational Aspects of Hard Knapsack Problems // Nonlinear Analysis. — 2001. — c. 5547-5558

160. Подвальный E.C. Плотников О. А. Разработка алгоритма для комплексного решения задач АСУ транспортной логистики // Вестник ВГТУ. — №7., Выпуск П. —2011. —с. 102-105

161. Неравенство треугольника // Wikipedia. URL: http://ru.wikipedia.org/wiki/Hepaвeнcтвoтpeyгoльникa (дата обращения: 02/10/11).

162. Первый проректор ФГБОУ ВПО "ВГТУ"1. В. Сафонов 2012 г.м.п.1. АКТо внедрении результатов диссертационной работы в учебный процесс Воронежского государственного технического университета

163. Результаты диссертационной работы:

164. Вид внедрения результатов зарегистрированная программа для ЭВМкомплекс, машина, система, прибор, инструмент, технология,

165. Интерактивная АИС комплексного решения задач транспортной логистики»методика, зарегистрированные программы для ЭВМ, базы данных, и т.д.)

166. Область внедрения лабораторный практикум и лекционные курсы по дисциплине «Нелинейное программирование»; специальность «Вычислительные машины, комплексы, системы и сети»специальност!., дисциплина, вид учебной нагрузки)

167. Форма внедрения описание лабораторной работы, материалы лекционного курсаучебник, учебное пособие, курс лекций, м.у. и т.д., с указанием выходных данных)

168. Технический уровень НИР свидетельствоподаны заявки на объекты промышленной собственности, получены

169. ФГБУ ФИПСрег. №2012618764 от 26.09.2012г.положительные решения, патенты России, дипломы, медали и др. их № и дата)

170. Публикации по материалам НИР: 11 публикаций, из них 4 в изданиях из списка ВАКколичество, где опубликованы)

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

172. При наличии годового экономического эффекта прилагается рассчет утвержденный Ректором и гл. Бухгалтером.1. Согласовано:

173. Руководитель основного научного направления Ш4?/Л »oq1. D9 2012 г.

174. Отдел методического обеспечения учебношдроцесса УМУ

175. ООО Научно-производственное предприятие1. Орт»394026, г. Воронеж, Московский пр. 22, тел/факс (4732) 21-45-26 e-mail: info@ort-vrn.ru, www.ort-vrn.ru

176. Председатель комиссии Члены комиссии:

177. В настоящее время программная система «Интерактивная АИС комплексного решения задач транспортной логистики» находится на опытной эксплуатации.'1. Главный инженер1. Дорофеев А.Н.