Разработка и исследование алгоритмов решения транспортных задач с использованием генетических методов тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Емельянова, Татьяна Сергеевна

• Емельянова, Татьяна Сергеевна
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Емельянова, Татьяна Сергеевна

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

ГЛАВА 1 СОСТОЯНИЕ ПРОБЛЕМЫ И АНАЛИЗ МЕТОДОВ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ.

1.1 Классификация транспортных задач. Транспортные задачи с ограничением по времени.

1.2 Динамическая транспортная задача. Проблема оценки динамической составляющей транспортной задачи.

1.3 Анализ методов решения транспортных задач с ограничением по времени.

1.4 Выводы.

ГЛАВА 2 РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА РЕШЕНИЯ ЛИНЕЙНЫХ ТРАНСПОРТНЫХ ЗАДАЧ БОЛЬШОЙ РАЗМЕРНОСТИ.

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

2.2 Определение и основные свойства генетических алгоритмов.

2.3 Структура генетического алгоритма.

2.4 Конструирование начальной популяции.

2.5 Операторы селекции.

2.6 Оператор кроссинговера.

2.7 Оператор мутации.

2.8 Выводы.

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

3.1 Математическая постановка транспортной задачи с ограничением по времени.

3.2 Структура разработанного генетического алгоритма.

3.3 Кодирование решения.

3.4 Оператор инициализации.

3.5 Оператор кроссинговера.

3.6 Операторы мутации.

3.7 Фундаментальная теорема ГА.

3.8 Оценка временной сложности алгоритма.

3.9 Распараллеливание алгоритма для многоядерных систем.

3.10 Применение разработанного ГА для решения динамической транспортной задачи с ограничением по времени.

3.11 Выводы.

ГЛАВА 4 ТЕСТИРОВАНИЕ И ЭКСПЕРИМЕНТАЛЬНОЕ ОБОСНОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ.

4.1 Описание тестовых моделей транспортных задач.

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

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

4.4 Исследование влияния динамической составляющей на решение транспортных задач с ограничением по времени.

4.5 Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование алгоритмов решения транспортных задач с использованием генетических методов»

Актуальность работы

Транспортировка важная область жизнедеятельности человека. Перевозка людей и грузов (от пищевых до промышленных) — это неотъемлемая часть жизни современного человека. Так расходы на транспортировку различных видов грузов составляют в Великобритании -15%, во Франции — 9%, в Дании - 15% от общих национальных расходов [1]. Необходимость решения таких транспортных задач, с минимизацией издержек на перевозку, определяется большим экономическим эффектом при нахождении лучшего решения, т.к. это явно увеличивает прибыль предприятия. Применение компьютерных методов решения задач позволяет увеличить скорость принятия решений и повысить эффективность найденных решений. Поэтому требуются алгоритмы способные исполняться на массово доступных вычислительных средствах (персональных компьютерах и малых серверах). Разработка новых алгоритмов должна учитывать структуру вычислительных средств, на которых будут исполняться программы (реализующие данные алгоритмы). В настоящее время основные тенденции развития компьютерной техники таковы: за последние несколько лет резко снизился рост частоты процессоров, появилась возможность хранить в памяти огромные объемы информации. Снижение роста быстродействия процессоров произошло из-за достижения технологического предела нанометровых технологий, однако появилась возможность разместить на одном кристалле большее количество вычислительных элементов (процессорных ядер). Польза от использования этих ядер будет только в том случае, если исполняемая программа (и её алгоритм) является параллельным, в противном случае будет использоваться (работать) только одно ядро, а остальные будут простаивать. Известно, что классические алгоритмы не имеют возможности распараллеливания и имеют экспоненциальный рост времени выполнения от размерности задачи. Т.е. количество математических действий (команд) растет экспоненциально, а развитие процессорных элементов (увеличение тактовой частоты, уменьшение количества тактов выполнения команд, задержка на выборку данных из памяти) не компенсируют растущие (с увеличением размерности задачи) потребности классических алгоритмов. Точные методы решения транспортных задач (ТЗ), позволяют найти решение только для задач с малым количеством клиентов (т.е. до 50-ти клиентов [2]). Для решения задач большой размерности точные методы являются не эффективными в связи с их большими временными затратами. Однако, именно сейчас, требуется эффективные алгоритмы решения задач большой размерности, т.к. в настоящее время наблюдается процессы глобализации в экономике. В частности, это приводит к слиянию множества мелких и средних компаний в крупные корпорации, которые пытаются уменьшить издержки путем сокращения количества однотипных объектов инфраструктуры (складов, ремонтных мастерских и пр.) преобразовывая их в крупные объекты регионального значения. Что приводит к необходимости планирования транспортных операций с большим количеством клиентов, т.е. к ТЗ большой размерности. Таким образом, решение ТЗ большой размерности является актуальной задачей. Одним из классов ТЗ является ТЗ с ограничением по времени. Данный класс задач является сложным для решения, но необходимым и широко применяемым на практике. Моделью ТЗ с ограничением по времени описываются: банковские и почтовые доставки, перевозка людей, сбор промышленных и бытовых отходов, доставка продуктов, доставка топлива и материалов на предприятия. На настоящий момент в иностранной литературе предложено множество алгоритмов решения данного класса задач, к сожалению, в нашей стране методы транспортной логистики только начинают свое развитие. Практическим алгоритмам по решению ТЗ с ограничением посвящено множество работ следующих ученых: Solomon, Tompson, Psaraflis, Russell, Antes, Derigs, Cordone, Wolfer-Calv, Caseau, Laburthe, Braysy, Rochat, Taillard, Chiang,

Cordeau, Thangiah, Homberger, Gehring, Mester, Barkaoui, Csiszar, Van Henlenryck и др.

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

Цель диссертации

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

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

1. Проведение сравнительного анализа эффективности существующих методов решения ТЗ.

2. Построение генетических операторов отражающих специфику решаемой ТЗ (линейной или с ограничением по времени).

3. Разработка специального комбинированного генетического алгоритма (ГА) для решения статической ТЗ с ограничением по времени.

4. Разработка модифицированного ГА для решения динамической ТЗ.

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

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

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

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

3. Предложен метод распараллеливания ГА для применения его в многоядерных системах, что позволило получить увеличение быстродействия.

Результаты выносимые на защиту

1. Генетические операторы для решения линейной транспортной задачи большой размерности (порядка 100x100).

2. Новый ГА и генетические операторы для решения транспортных задач с ограничением по времени.

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

4. Метод распараллеливания ГА ориентированный на выполнение разработанных алгоритмов на многоядерной вычислительной базе.

Практическая значимость

На основе разработанных алгоритмов создан программно-алгоритмический комплекс для решения транспортных задач с ограничением по времени. При построении программного комплекса использовался объектно-ориентированный язык С++ и среда разработки Microsoft Visual

С++ 6.0. Отладка и тестирование проводилось на ЭВМ типа IBM PC, с процессором AMD Athlon 64 Х2 5400+, 2.8 ГГц, ОЗУ 3ГБ. Отличительная особенность разработанного программного комплекса — это эффективное использование многоядерной вычислительной системы, что позволило сократить время решения транспортных задач в два раза.

Внедрение результатов работы

Основные результаты диссертационной работы использованы в госбюджетных и хоздоговорных работах, проводимых в Таганрогском технологическом институте Южного федерального университета: в госбюджетной работе «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», в гранте РФФИ «Разработка теории и принципов эволюционной оптимизации и принятия решений на основе бионического моделирования». Материалы диссертации также использованы в учебном процессе на кафедре САПР в Таганрогском технологическом институте Южного федерального университета в цикле лекций и практических занятий по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Прикладная информатика».

Методы исследования

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

Апробация работы

Основные результаты, полученные в ходе работы, докладывались и обсуждались на:

1. Всероссийских научных школах-семинарах молодых ученых, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки», Таганрог, 2007 и 2008 годы.

2. Международной научно-технической конференции «Интеллектуальные системы» (AIS'08) и «Интеллектуальные САПР» (CAD02008), Геленжик, 2008.

3. IX Всероссийской научной конференции «Техническая кибернетика, радиоэлектроника и системы управления», Таганрог, 2008.

4. Второй Всероссийской научной конференции с международным участием «Нечеткие системы и мягкие вычисления» (НСМВ-2008), Ульяновск, 2008.

5. XI Национальной конференции по искусственному интеллекту с международным участием (КИИ-08), Дубна 2008.

Публикации

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

Объем и структура диссертации

Диссертация состоит из введения, 4 глав, заключения, списка литературы, включающего 102 наименования и 6 приложений. Основной текст диссертации изложен на 150 страницах, включая 41 рисунок и 6 таблиц.

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

В результате проведенной работы можно сделать следующие выводы:

1. Написан программный модуль, реализующий разработанный ГА для решения линейных задач, позволяет решать линейные ТЗ представленные в матричном виде порядка 100x100 за достаточно малое время (время работы пропорционально размерности задачи).2. Результаты решения тестовых задач размера от 5x5 до 18x18 показали, что решение, полученное разработанным алгоритмом, при подборе параметров ГА, совпадает с оптимальным решением. При решении тестовых задач порядка 100x100 решение улучшалось в среднем на 35% от начального решения, при этом время решения задачи увеличивалось пропорционально размерности задачи.3. Написан программный модуль реализующий, разработанный ГА для решения ТЗ с ограничением по времени программный. Программный модуль был разработан для решения, как тестовых задач Соломона, так и для решения расширенных задач Соломона описанных в текстовом виде. Набор тестовых задач отражал различное расположение клиентов (равномерное, кластерное и смешанное) относительно депо и различную жесткость временных ограничений, накладываемых на время прибытия транспортного средства к клиенту.4. Результаты тестов по задачам всех видов показали, что данный алгоритм в отличие от других известных алгоритмов дает решение, в котором количество транспортных средств и общее пройденное расстояние сбалансировано. Это приводит к тому, что на практике добавляя несколько транспортных средств получаем значительное уменьшение общего пройденного расстояния, что приводит к уменьшению затрат на топливо, амортизацию транспортных средств, уменьшению нагрузки на водителя, также можно отметить, что уменьшается вероятность аварии, т.к. эта вероятность тем выше чем больше пройденное расстояние.5. Адаптация разработанного алгоритма для решения динамической ТЗ позволило решать задачи, в которых некоторое количество запросов клиентов известно заранее, а другие запросы появляются по мере выполнения решения (т.е. в течение дня по мере обслуживания

клиентов). Причем, информация о новых запросах клиентов не может быть предопределена. В данном случае каждый раз при поступлении нового запроса решается задача с учетом уже обслуженных и новых клиентов и текущего положения транспортных средств.6. Результаты решения динамических ТЗ с ограничением по времени при имитации появления запросов в процессе выполнения решения показали, что общее пройденное расстояние получаемого решения увеличивается незначительно (на 15%), даже при большом количестве динамических запросов (90%).Следовательно, тестирование и экспериментальное обоснование разработанного комплекса ГА для ТЗ доказали практическую эффективность разработанных ГА и целесообразность применимости теоретических разработок на практике.ЗАКЛЮЧЕНИЕ Проблема транспортировки груза от производителей к потребителям с наименьшими издержками будет актуальна всегда, с развитием человечества понятие издержек меняется, но желание снизить затраты - остается неизменным. Поэтому основой данной работы явилась разработка комплекса алгоритмов для решения ТЗ адаптированных для выполнения на распространенных и широкодоступных многоядерных процессорах. ГА явились удобной основой для разработки такого комплекса алгоритмов.Результатом работы стал комплекс ГА для решения ТЗ с ограничением по времени. В результате проведенной работы были получены следующие результаты:

1. Разработан ГА для решения транспортной задачи с ограничением по времени. Разработаны и модифицированы ГО. Анализ оценки времени работы нового ГА для решения транспортной задачи с ограничением по времени показал, что зависимость времени работы алгоритма от размерности задачи составляет 0(n J).2. Разработаны новые ГО отражающие специфику матричного представления линейной ТЗ. Оценка времени работы ГА для решения линейных транспортных задач показала пропорциональную зависимость от размерности задачи О(п).3. Разработана процедура распараллеливания ГА с учетом применения данного алгоритма на многоядерных системах, которая позволяет значительно сократить время выполнения алгоритма.4. На основе предложенных алгоритмов разработаны программно алгоритмические модули решения транспортных задач, отличающиеся тем, что позволяют эффективно использовать многоядерную вычислительную систему.5. Анализ результатов экспериментов показал, что разработанный ГА дает наилучшие решения с точки зрения баланса между количеством транспортных средств и общим пройденным расстоянием.6. Предложена модификация ГА для решения ТЗ с ограничением по времени с динамическими запросами клиентов. Для задач с количеством динамических запросов 90% общее пройденное расстояние увеличивается на 15% по сравнению со статическими задачами.Полученные теоретические результаты, подтвержденные практическими экспериментами, продемонстрировали эффективность разработанного комплекса ГА, предназначенного для решения ТЗ и ориентированного на выполнение на распространенных и доступных вычислительных системах.

Список литературы диссертационного исследования кандидат технических наук Емельянова, Татьяна Сергеевна, 2009 год

1.Csiszar S. Optimization Approaches for Logistic Problems -Vehicle Routing Problem with Time Windows // PhD Dissertation. - Budapest, Hungary, submitted: August 2006.

2. Cordeau J.-F, Desaulniers G., Gesrosiers J., Solomon M., Soumis F. The VRP with Time Windows. Chapter 7 // Paolo Toth and Daniel Vigo (eds), SIAM, Monographs on Discrete Mathematics and Applications. 2001.

3. Babb T. Pickup and Delivery Problem with Time Windows, CoordinatedTransportation Systems: The State of the Art // Department of Computer Science University of Central Florida Orlando, Florida. 2005.

4. B.H. Иванченко, C.M. Ковалев, A.H. Шабельников. Новыеинформационные технологии: интегрированная информационно-управляющая система автоматизации процесса расформирования-формирования поездов: Учебник. Ростов-на-Дону, РГУПС, 2002.

5. Laporte G. The Vehicle Routing Problem: An overview of exact and approximate algorithms // European Journal of Operation Research. -1992.-Vol. 59-p. 345 -358.

6. Pisinger D., Roplce S. A general heuristic for vehicle routing problems //Computers and Operations Research. 2007. - Vol. 34. - p. 2403-2435.

7. Braysy O., Gendreau M. Route Construction and Local Search Algorithmsfor the Vehicle Routing Problem with Time Windows // Internal Report STF42 AO 1024, SINTEF Applied Mathematics 2001.

8. Kim В., Kim S, Sahoo S. Waste collection vehicle routing problem withtime windows // Computers & Operations Research. 2006. - Vol. 33. -pp. 3624-3642.

9. Flatberg Т., Halse G., Kloster O., Nilssen J., Riise A. Dinamic andStochastic Aspects in Vehicle Routing A Literature Survey // STF90 A05413, SINTEF Applied Mathematics. - 2005.

10. Potvin J.-Y., Xu Y., Benyahia I. Vehicle routing and scheduling whith dynamic trave times // Computer & Operations Research. 2006. - Vol. 33,p. 1129- 1137.

11. Malandraki C., Daskin M.S. Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms // Transportation Science 1992 - 26(3) - p. 185-200.

12. Haghani A., Jung S. A dynamic vehicle routing problem with time-dependent travel times // Computers & Operations Research 2005 - 32 -p.959-2986, 2005.

13. Ichoua S., Gendreau M., Potvin J.-Y. Vehicle Dispatching with Time-Dependent Travel Times // European Journal of Operational Research -2003- 144(2)-p.379-396.

14. Fleischmann В., Gietz M., Gnutzmann S. Time-Varying Travel Times in Vehicle Routing // Transportation Science 2004 - 38(2) - p. 160-173.

15. Ichoua S., Gendreau M., Potvin J. Y. Vehicle dispatching with time-dependent travel times // European Journal of Operational Research 2003 - 144-p.379-396.

16. Montemanni R., Gambardella L.M. An exact algorithm for the robust shortest path problem with interval data // Computers & Operations Research 2004 - 31(10) - p. 1667-1680.

17. Hall R.W. The fastest path through a network with random time-dependent travel times // Transportation Science 1986 -20(3) - p. 182188.

18. Fu, L. and L.R. Rilett, Expected shortest paths in dynamic and stochastic traffic networks. Transportation Research part B, 32(7): 499-516, 1998.

19. Fu L. Scheduling dial-a-ride paratransit under time-varying, stochastic congestion // Transportation Research 2002 - part B, 36 - p.485-506.

20. Kim S, Lewis M.E., White C.C. Optimal vehicle routing with real-time traffic information. Working paper, College of Engineering, University of Michigan, 2004

21. Larsen A. The dynamic vehicle routing problem // Ph.D. dissertation, Technical University of Denmark, Lyngby, Denmark. — 2000.

22. Montemanni R., Gambardella L.M., Rizzoli A.E., Donati A.V. A new algorithm for a Dynamic Vehicle Routing Problem based on Ant Colony System // Technical Report: 1DSIA-23-02, 2002.

23. Russell W., Bent R., Hentenryck P.V. Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers. // Operation Research 2004 - Vol. 52, No. 6 - pp. 977-987.

24. Zhu K., Ong K. L. A reactive method for real time dynamic vehicle routing problem // 12th ICTAT 2000, Vancouver, Canada 2000.

25. Zhao X., Goncalves G., Dupas R. A genetic approach to solving the vehicle routing problem with time-dependent travel times // 16th Mediterranean Conference on Control and Automation Congress Centre Ajaccio, France June 25-27 2008 - pp.413-418.

26. Blasum U., Hochstattler W. Application of the Branch and Cut Method to the Vehicle Routing Problem // Technical Report zaik2000-386, Centre of Applied Computer Science, University of Cologne, Germany. 2000.

27. Емельянова Т.С. Анализ методов решения нелинейных транспортных задач. // Перспективные информационные технологии и интеллектуальные системы. 2007. №1(29). - С. 38-49,

28. Solomon М. М. Algorithms for the Vehicle Routing and Scheduling Problems with Time Windows Constraints // Operation Research. 1987. -Vol 35-pp. 254-265.35. http://web.cba.neu.edu/-msolomon/problems.htm.

29. Braysy O., endreau M. Genetic Algorithms for the Vehicle Routing Problem with Time Windows // STF42 AO 1021, SINTEF Applied Mathematics, Research Council of Norway. 2001.

30. Gendreau M., Braysy O. Metaheuristic Approaches for the Vehicle Routing Problem with Time Windows: A Survey // MIC2003: The Fifth Metaheuristics International Conference, Kyoto, Japan. August 25-28, 2003.

31. Braysy O., Gendreau M. Tabu Search Heuristics for the Vehicle Routing Problem with Time Windows // Internal Report STF42 AO 1022, SINTEF Applied Mathematics, Department of Optimisation, Oslo, Norway. 2001.

32. Tan К. C., Lee L. H., Zhu Q. L., Ou. K. Heuristic methods for vehicle routing problem with time windows // Artificial Intelligent in Engineering. -2001.-Vol. 15-pp. 281-295.

33. Potvin J.-Y., Rousseau J.-M. A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows // European Journal of Operational Research. 1993. -Vol. 66. - P. 331-340.

34. Ioannou G., Kritikos M., Prastacos G. A Greedy Look-Ahead Heuristic for the Vehicle Routing Problem with Time Windows // Journal of Operational Research Society. 2001. -Vol. 52. - P. 523-537.

35. Potvin J.-Y., Rousseau J.-M. An Exchange Heuristic for Routeing Problems with Time Windows // Journal of the Operational Research Society 1995 - 46 - p.1433-1446.

36. Thompson P. M., Psaraftis H.N. Cyclic Transfer Algorithms for Multivehicle Routing and Scheduling Problems // Operations Research -1993 —41 p.935-946.

37. Laporte G., Gendreau M., Potvin J.-Y., Semet, F. Classical and modern heuristic for the vehicle routing problem // International Transaction in Operational Research. 2000. - Vol. 7. - pp. 285-300.

38. Russell R.A. Hybrid Heuristics for the Vehicle Routing Problem with Time Windows // Transportation Science 1995 - 29 - p. 156-166.

39. Antes J., Derigs U. A New Parallel Tour Construction Algorithm for the Vehicle Routing Problem with Time Windows // Working Paper, Department of Economics and Computer Science, University of Koln, Germany, 1995.

40. Antes J., Derigs U. A new parallel tour construction algorithm for the vehicle routing problem with time window // University of Koln, Germany, Department of Economics and Computer Science. Working paper 1995.

41. Cordone R., Wolfler-Calvo R. A Note on Time Windows Constraints in Routing Problems // Internal Report, Department of Electronics and Information, Polytechnic of Milan, Milan, Italy, 1997.

42. Caseau Y., Laburthe F. Heuristics for Large Constrained Vehicle Routing Problems // Journal of Heuristics 1999 - 5 - p.281-303.

43. Braysy О., Gendreau M. Metaheuristics for the Vehicle Routing Problem with Time Windows // Internal Report STF42 AO 1025, SINTEF Applied Mathematics, Department of Optimisation, Norway, 2001.

44. Braysy O, Gendreau M. Metaheuristics for the Vehicle Routing Problem with Time Windows // Internal Report STF42 AO 1025, SINTEF Applied Mathematics, Department of Optimisation, Oslo, Norway. -2001.

45. Taillard E., Badeau P., Gendreau M, Guertin F., Potvin J.-Y. A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windos //Transportation Science. 1997 - Vol. 31. - pp. 170 - 186.

46. Taillard E., Badeau P., Gendreau M, Guertin F., Potvin J.-Y. A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows //Transportation Research C. 1997. - Vol. 5. - pp. 109 - 122.

47. Rochat Y., Taillard E. Probabilistic Diversification and Intensification in Local Search for Vehicle Routing // Journal of Heuristics 1995 - 1 — pl47—167.

48. Chiang W.C., Russell R.A. A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows // INFORMS Journal on Computing 1997 - 9 - p.417-430.

49. Cordeau J.-F., Laporte G., Mercier A. A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows // Journal of the Operational Research Society 2001 - 52 - p. 928-936.

50. Thangiah S. R. Vehicle Routing with Time Windows using Genetic Algorithms // Technical Report SRU-CpSc-TR-93-23, Computer Science. 1993.

51. Chang Y., Chen L. Solve the vehicle routing problem with time windows via a genetic algorithm // Discrete and continuous dynamical systems supplement. 2007. - pp. 240-249.

52. Bjarnadottir A.S. Solving the Vehicle Routing Problem with Genetic Algorithms. Printed by Informatics and Mathematical Modelling, 1MM Technical University of Denmark, DTU. 2004.

53. Jung S., Moon. B.R. A Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows. // In Proceedings of Genetic and Evolutionary Computation Conference. San Francisco: MorganKaufmann Publishers-2002-p. 1309-1316.

54. Braysy O., Gendreau M., Dullaert W. Evolutionary Algorithms for the Vehicle Routing Problem with Time Windows // Journal of Heuristics. -2004.-Vol. 10.-pp. 587-611.

55. Mester D., Braysy O. Active guided evolution strategies for the large scale vehicle routing problem with time windows // Computers & Operations Research. 2005. - Vol.32. - pp. 1593-1614.

56. Berger J., Barkaoui M. A Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows // Computer and Operation Research. 2004. - Vol. 31. - pp. 2037-2053.

57. Bent R., Hentenryck PV. A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows // Transportation Science -2004. Vol. 38 - pp. 515-530.

58. Csiszar S. Two-Phase Heuristic for the Vehicle Routing Problem with Time Windows // Acta Polytechnica Hungarica. 2007. - Vol. 4 - pp. 143-156.

59. Вентцель E. С. Исследование операций: задачи, принципы, методология. М.: Наука. 1988.

60. Вентцель Е. С. Исследование операций. М., «Советское радио», 1972.

61. Таха X. А. Введение в исследование операций. 6-е издание.: Пер. с англ. — М.: Издательский дом «Вильяме», 2001.

62. Емельянова Т.С. Генетические алгоритмы решения транспортных задач. // Тезисы докладов IX Всероссийской научной конференции «Техническая кибернетика, радиоэлектроника и системы управления». Таганрог: Изд-во ЮФУ - 2008. С. 150-151.

63. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы построение и анализ Пер. с англ.- М 2004.

64. Емельянов В. В., Курейчик В. В, Курейчик В. М. Теория и практика эволюционного моделирования. М. : ФИЗМАТ ЛИТ, 2003

65. Генетические алгоритмы: Учебное пособие. Под ред. В.М. Курейчика. Ростов-на-Дону: ООО «Ростиздат», 2004.

66. Курейчик В.М. Генетические алгоритмы и их применение. -Таганрог: Изд-во ТРТУ, 2002.

67. Michalewicz Z. Genetic Algorithms + data structures = evolution programs. Springer-Verlay, New York, 1992.

68. Емельянова Т. С. Применение генетических алгоритмов для решения транспортной задачи линейного программирования. // Перспективные информационные технологии и интеллектуальные системы 2006 -Таганрог, №3(27) - 15-29.

69. Емельянова Т. С. Об одном генетическом алгоритме решения транспортной задачи. // Известия ТРТУ. 2007 - Таганрог, №1(73), 65-70.

70. Емельянова Т.С. Об одном генетическом алгоритме решения транспортной задачи с ограничением по времени. // Известия ЮФУ. Тематический выпуск «Интеллектуальные САПР». 2008. №4(81). -С. 45-50.

71. Емельянова Т.С. Генетический алгоритм решения транспортной задачи с ограничением по времени. // Перспективные информационные технологии и интеллектуальные системы. 2007. №4(32).-С. 43-59.

72. Королюк В.С.,Портенко Н.И., Скороход А.В., Турбин А.Ф. Справочник по теории вероятностей и математической статистике. — М.: Наука, 1985.

73. Glover A., Kochenberger Gary A. Handbook of Metaheuristics. Springer, 2002.

74. Курейчик B.M., Гладков JI.A. Основные положеия теории генетического поиска. Конспект лекций. Таганрог: Изд-во ТРТУ, 2001.

75. Holland J.H. Adaptation in Natural and Artificial System. An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan. 1975.

76. David A. Coley. An Introduction to Genetic Algorithms for Scientists and Engineers, World Scientific Publishing Co., Inc., River Edge, NJ, 1998.

77. Melanie M. An Introduction to Genetic Algorithms. A Bradford Book The MIT Press Cambridge, Massachusetts • London, England., 1999.

78. Шилд Г. Полный справочник по С++, 4-е издание.: Пер. с англ. М. Издательский дом «Вильяме», 2007.

79. Страуструп Б. Язык программирования С++. Специальное издание.: Пер. с англ. М. ООО «Бином-Пресс», 2006.

80. Емельянова Т. С. Использование библиотеки Direct Draw в MS Visual С++ для улучшения визуализации решений математических задач. // Технологии Microsoft в теории и практике программирования. 2008 - Таганрог - 5-8.

81. Genderau М., Guertin F., Potvin J. Y., Taillard E.Tabu Search for RealTime Vehicle Routing and Dispatching // Technical report CRT-96-47, Centre de recherchesur les transports, Universite' de Montre'al,Montre'al, Canada-1996.

82. Ichoua S., Genderau M, Potvin J. Y. Diversion Issues in Real-Time Vehicle // Dispatching Transportation Science 2000 - Vol. 34, No. 4, November. - pp.427-438.