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

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

Характеристики

Автор	ЧЕРНЫШЕВ СЕРГЕЙ ВЛАДЛЕНОВИЧ
Тип	Кандидатская диссертация
Специальность	математическое моделирование, чис¬ленные методы и комплексы программ

Оглавление

Введение.....................................................................5

1 Обзор существующих алгоритмов решения ЗМТ................................11

1.1 Классификация ЗМТ ....................................................................11

1.2 Методы оптимизации ................................................................. 13

1.2.1 Метод ветвей и границ................................................... 13

1.2.2 Методы линейной оптимизации.................................. 14

1.2.3 Генетические алгоритмы............................................... 16

1.2.4 Метод имитации отжига................................................ 17

1.2.5 Поиск с запретами........................................................... 19

1.3 Классификация Фишера............................................................. 19

1.4 Классификация Кордо................................................................. 21

1.4.1 Построение начального приближения......................... 22

1.4.2 Локальная оптимизация приближения........................ 23

1.4.3 Глобальная оптимизация .............................................. 25

1.4.4 Машинное обучение....................................................... 27

1.5 Выводы.......................................................................................... 30

2 Многофазный алгоритм...............................................................32

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

2.2 Общая схема работы алгоритма ............................................... 34

2.3 Построение редуцированного графа........................................... 35

2.3.1 Одномерный случай........................................................... 36

2.3.2 Двумерный случай............................................................. 36

2.3.3 Многомерный случай ....................................................... 39

2.4 Метод фиктивных клиентов.......................................................... 52

2.5 Построение начального приближения....................................... 54

2.6 Обмен сегментов маршрутов........................................................ 55

2.6.1 Ускорение операции обмена сегментов......................... 55

2.6.2 Поиск оптимального обмена сегментов.......................... 59

2.7 Разгрузка агентов............................................................................ 62

2.8 Постобработка................................................................................ 63

2.9 Выводы............................................................................................. 64

3 Аспекты реализации...............................................................................66

3.1 Система PlanVidia............................................................................ 66

3.2 Архитектура PlanVidia........................................ ,..................... 68

3.2.1 Эксплуатация системы..................................................... 68

3.2.2 Основные части системы ................................................. 69

3.2.3 Назначение системы......................................................... 70

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

3.2.5 Внутренняя структура системы...................................... 71

3.2.6 Расчетный модуль............................................................. 73

3.2.7 Потоки данных................................................................... 74

3.3 Формирование исходных данных............................................... 76

3.3.1 Построение графа дорог................................................... 76

3.3.2 Геокодирование.................................................................. 78

4 Практические результаты........................................................................80

4.1 Процедура тестирования ................................................................. 80

4.1.1 Открытое тестирование....................................................... 80

4.1.2 Внешнее тестирование......................................................... 81

4.2 Примеры проектов............................................................................ 81

4.2.1 Антверпен.............................................................................. 81

4.2.2 Бельгия................................................................................... 84

4.3 Визуальное тестирование................................................................. 85

4.3.1 Обслуживание изолированных клиентов......................... 85

4.3.2 Распределение кластеров между агентами...................... 85

4.3.3 Привязка клиентов к ребрам графа................................... 87

4.4 Результаты экспериментов .............................................................. 88

4.4.1 Алгоритм начального построения .................................... 88

4.4.2 Зависимость результатов от размеров групп ... 88

4.4.3 Тестовые наборы Геринга и Хомбергера......................... 89

4.4.4 Задачи большой размерности............................................ 90

4.4.5 Вариация параметров оптимизации ................................. 91

4.4.6 Эффективность оптимизации............................................. 92

4.4.7 Сравнение расчетных данных с экспериментальными 93

4.4.8 Проекты компании CapVidia............................................. 95

4.4.9 Параллельные вычисления................................................. 96

4.5 Выводы................................................................................................ 97

Литература.......................................................................................................112

Задать вопрос

Введение

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

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

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

Рассматриваемый класс задач представляет интерес с научной точки зрения. В данном направлении на протяжении последних сорока лет ведутся интенсивные исследования [7,28,30,33-36,39,44,46,47,49, 50,52-57,59-61,67,69-74,77,80,83,85-88,90-93,95,96,99,100,103-107, 109,111]. Огромное количество входных параметров, с одной стороны, делают задачу настолько сложной, что многие существующие алгоритмы либо не применимы, либо плохо адаптируемы к практике. С другой стороны, эта же особенность предоставляет простор для новых исследований.

Первые приближенные алгоритмы были получены в 1970-х годах (Clarke G. [39], Wright J.W. [61]). В 1980-е годы были заложены основные подходы к приближенному решению задач маршрутизации транспорта (Cook Т., Russel R.A., Christofides N., Mingozzi A., Toth P. [44, 107]). С середины 1990-х годов исследования сосредоточились на построении метаэвристик, в основе которых лежат такие методы как поиск с исключениями, метод отжига, генетические алгоритмы, метод муравьиных колоний, нейросети и другие (Gendreau М., Osman I.H., Matsuyama Y. [7,28,34,35,86,90,100]). В последние десять лет исследования склонились в основном в сторону обработки сложных видов ограничений (Frazzoli Е., Bullo F. [30,50,56]).

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

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

Задачами исследования являются:

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

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

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

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

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

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

3. Предложен метод фиктивных клиентов для снижения размерности задачи.

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

5. Построена новая структура данных для выполнения операции обмена сегментов маршрутов и доказано, что применение этой структуры позволяет сократить время выполнения таких операций с 0(п) до 0(log²n), где п — общее количество клиентов в маршрутах.

6. С помощью введенного в диссертации понятия «разрез» сформулировано часто выполняющееся на практике условие фильтрации и доказано, что выполнение данного условия позволяет сократить количество разрезов с 0(п²) до 0(п).

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

Практическая ценность. Алгоритмы, опубликованные в данной работе, реализованы на языке C++ и протестированы в операционных системах Windows, Linux. Для практического использования создана динамическая библиотека, которая в настоящее время внедрена в программном комплексе PlanVidia.

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

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

1. Всероссийская научная конференция «Высокопроизводительные вычисления и их приложения», Черноголовка, 2000

2. Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 2001

3. Научная конференция «Ломоносовские чтения», Москва, 2003

4. Всероссийская конференция студентов, аспирантов, молодых ученых «Технологии Microsoft в теории и практике», Москва, 2005

5. Международный семинар по компьютерной алгебре и информатике, Москва, 2005

6. Шестая международная конференция памяти академика А. П. Ершова «Перспективы систем информатики», Новосибирск, 2006

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

Публикации. Основные результаты работы изложены в 10 научных статьях, среди которых б — в тезисах докладов [2,9,14,19,25,27],

3 — в рецензируемых российских периодических изданиях [18,24,26], из которых 2 статьи [24,26] опубликованы в журналах из списка ВАК и 1 статья в международном рецензируемом журнале [38].

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

Структура и объем диссертации Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 115 страницах, содержит 39 иллюстраций. Библиография включает 113 наименований.

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

Литература

1. Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: Вильямс, 2000. 384 с.

2. Бабенко М.А., Панкратьев Е.В., Чеповский А.М., Чернышев С.В. Оптимизационные задачи на графах, возникающие в транспортной логистике // Перспективы систем информатики: шестая международная конференция памяти академика А. П. Ершова. Рабочий семинар «Наукоемкое программное обеспечение» (Новосибирск, Академгородок, 28-29 июня 2006 г.). Новосибирск: изд-во института систем информатики СО РАН, 2006. С. 31-32.

3. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. 336 с.

4. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 2008. 330 с.

5. Вирт Н. Алгоритмы и структуры данных. СПб: Невский Диалект, 2008. 352 с.

6. Глебов Н.И., Кочетов Ю.А., Плясунов А.В. Методы оптимизации. Новосибирск: изд-во Новосиб. гос. ун-та, 2006. 105 с.

7. Емельянова Т.С., Курейчик В.М. Решение транспортных задач с использованием комбинированного генетического алгоритма // Искусственный интеллект: Одиннадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2008 (Дубна, 28 сентября - 3 октября 2008 г.). М.: Физматлит, 2008. С. 158-164.

8. Еремеев А.В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации: дисс.... канд. физ.-мат. наук. Омск, 2000. 119 с.

9. Инюхин А.В., Панкратьев Е.В., Чеповский А.М., Чернышев С.В. Использование Т-системы для преобразования графа дорог в задаче оптимизации маршрутов движения // Высокопроизводительные вычисления и их приложения: труды Всерос. науч. конф. (Черноголовка, 30 октября - 2 ноября 2000 г.). М.: изд-во МГУ, 2000. С. 220-223.

10. Кнут Д.Э. Искусство программирования для ЭВМ. М.: Мир, 1978. 2303 с.

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

12. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Вильямс, 2005. 1296 с.

13. Краснов М.В. Многокритериальная задача о кратчайших путях для всех пар узлов графа // Современные проблемы математики и информатики: сб. науч. тр. Вып. 3. Ярославль: изд-во ЯрГу, 2000. С. 62-66.

14. Лахно А.П., Чернышев С.В. Модификация метода Османа в задачах маршрутизации автотранспорта с временными окнами // Технологии Microsoft в теории и практике программирования: труды V Всерос. конф. студентов, аспирантов и молодых ученых (Москва, 1-2 апр. 2008 г.). М.: Вузовская книга, 2008. С. 229-230.

15. Лебедев С.С., Ковалевская М.И. Множители Лагранжа в простейшей задаче размещения. Исследования по дискретной оптимизации. М.: Наука, 1976. С. 170-180.

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

17. Лопатин А.С. Методы отжига. [Электронный ресурс]. Спб, 2005. URL: http://www.cs-seminar.spb.ru/reports/52.pdf (дата обращения: 12.11.2010).

18. Панкратьев Е.В., Чеповский А.М., Черепанов Е.А., Чернышев С.В. Алгоритмы и методы решения задач составления расписаний и других экстремальных задач на графах больших размерностей // Фундаментальная и прикладная математика. 2003. Т. 9, № 1. С. 235-251.

19. Панкратьев Е.В., Чеповский А.М., Черепанов Е.А., Чернышев С.В. Нахождение наборов оптимальных маршрутов на больших сетках дорог геоинформационных систем // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: материалы 10 междунар. науч.-техн. конф. (Рязань, 14-16 ноября 2001 г.). Рязань: изд-во Рязанской гос. радиотехн. акад., 2001. С. 240-241.

20. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1984. 512 с.

21. Растригин Л.А. Случайный поиск — специфика, этапы истории и предрассудки // Вопросы кибернетики. 1978. Вып. 33. С. 3-16.

22. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977. 352 с.

23. Ульянов М.В. Ресурсно-эффективные компьютерные алгоритмы. Разработка и анализ. М.: Физматлит, 2008. 303 с.

24. Чернышев С.В. Локальная оптимизация путей в задачах маршрутизации автотранспорта с временными окнами // УМН. 2009. Т. 64, № 1. С. 165-166.

25. Чернышев С.В. Обобщение задачи нахождения кратчайших путей в ориентированном графе // Технологии Microsoft в теории и практике программирования: труды Всерос. конф. студентов, аспирантов и молодых ученых (Москва, 17-18 февр. 2005 г.). М.: изд-во МГТУ им. Н. Э. Баумана, 2005. С. 138.

26. Чернышев С.В. Обобщение многокритериальной задачи о нахождении кратчайших путей в ориентированном графе // Вестник МГУ. Сер. 1, Математика. Механика. 2007. № 6. С. 1-8.

27. Чернышев С.В. Построение начального приближения в задаче маршрутизации с ограничениями по времени и другими вспомогательными условиями // Технологии Microsoft в теории и практике программирования: труды Всерос. конф. студентов, аспирантов и молодых ученых (Москва, 2-3 марта 2006 г.). М.: изд-во МГТУ им. Н. Э. Баумана, 2006. С. 139.

28. A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows / E. Taillard [et al.] // Transportation Science. 1997. Vol. 31. P. 170-186.

29. An algorithm for the traveling salesman problem / J. D.Little [et ah] // Operations Research. 1963. Vol. 11. P. 972-989.

30. An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows / 0. Braysy [et ah] // Transportation Science. 2008. Vol. 42, № 3. P. 371-386.

31. ArcLogistics Route: A Complete Routing and Scheduling Solution: An ESRI White Paper. October, 2004. NY: ESRI, 2004. 12 p.

32. Atserias A., Bonet M.L., Levy J. On Chvatal Rank and Cutting Plane Proofs // Electrnic Colloquium on Computational Complexity: Report. № 40. 2003. 12 p.

33. Baker E., Schaffer J. Computational experience with branch exchange heuristics for vehicle routing problem with time window constraints // American Journal of Mathematical and Management Sciences. 1987. Vol. 6, № 3,4. P. 261-300.

34. Braysy O., Gendreau M. Vehicle Routing Problem with Time Windows, Part II: Metaheuristics // Transportation Science. 2005. Vol. 39, № 1. P. 119-139.

35. Braysy O. Genetic Algorithms for the Vehicle Routing Problem with Time Windows // Arpakannus. 2001. Vol. 1 (special issue on Bioinformatics and Genetic Algorithms). P. 33-38.

36. Bramel J.B., Simchi-Levi D. A location based heuristic for general routing problems // Operations Research. 1995. Vol. 43, № 4. R 649.

37. Brumbaugh-Smith J., Shier D. An empirical investigation of some bicriterion shortest path algorithms. // European Journal of Operational Research. 1989. Vol. 43, № 2. P. 216-224.

38. Chepovskii A.M., Cherepanov E.A., Chernyshev S.V. Pankratiev E.V., Algorithms and methods for solving scheduling problems and other extremum problems on large-scale graphs // Journal of Mathematical Sciences. 2005. Vol. 128, № 6. P. 3487-3495.

39. Clarke G., Wright J.W. Scheduling of vehicles from a central depot to a number of delivery points // Operations Research. 1964. Vol. 12, № 4. P. 568-581.

40. Climaco J.C.N., Pascoal M.M.B. Finding non-dominated bicriteria shortest pairs of disjoint simple paths // Computers and Operations Research. 2009. Vol. 36, № 11. P. 2892-2898.

41. Colorni A. Ant system for job-shop scheduling // Belgrian Journal of Operation Research, Statistics and Computer Science. 1994. Vol. 34. P. 39-53.

42. Colorni A. Distributed optimization by ant colonies // Proceedings of the European Conference on Artificial Life. Paris: Elsevier, 1991. P. 134-142.

43.Computing many-to-many shortest paths using highway hierarchies / S. Knopp [et ah] // Proceedings of Workshop on Algorithm Engineering and Experiments (ALENEX 2007). New Orleans: ALENEX, 2007. P. 36-45.

44. Cook T.M., Russell R.A. A simulation and statistical analysis of stochastic vehicle routing with timing constraints // Decision Sciences. 1978. Vol. 9, № 4. R 673-687.

45. Costa D. Ants can colur graphs // Journal of the Operational Research Society. 1997. Vol. 48. R 275-305.

46. Csiszar S. Route Elimination Heuristic for Vehicle Routing Problem with Time Windows // Acta Polytechnica Hungarica. 2005. Vol. 2, № 2. P. 77-89.

47. Desaulniers G., Lessard F., Hadjar A. Tabu Search, Partial Elementarity, and Generalized k-Path Inequalities for the Vehicle Routing Problem with Time Windows // Transportation Science. 2008. Vol. 42, № 3. P. 387-404.

48. Durbin R., Willshaw D. An analogue approach to the travelling salesman problem using an elastic net method // Nature. 1987. Vol. 326, № 6114. P. 689-691.

49. Effective Local Search Algorithms for Routing and Scheduling Problems with General Time-Window Constraints / T. Ibaraki [et al.] // Transportation Science. 2005. Vol. 39, № 2. P. 206-232.

50. Favaretto D., Moretti E., Pellegrini P. Ant colony system for a VRP with multiple time windows and multiple visits // Journal of Interdisciplinary Mathematics. 2007. Vol. 10, № 2. P. 263-284.

51. Finding cuts in the TSP: A preliminary report / Center for Discrete Mathematics к Theoretical Computer Science / D. Appletgate [et al.] Piscataway, USA: DIMACS, Rutgers University, 1995. 64 p.

60. Ghaziri H. Supervision in the self-organizing feature map: Applicaiton to the vehicle routing problem // Meta-Hueristics: Theory and Applications. Boston: Kluwer Academic Publishers, 1996. P. 651-660.

61. Gillett B.E., Miller L.R. A heuristic algorithm for the vehicle dispatch problem // Operations Research. 1974. Vol. 22, № 2. P. 340-349.

62. Glover F. Tabu Search — Part I. // ORSA Journal on Computing. 1989. Vol. 1, № 3. P. 190-206.

63. Glover F. Tabu Search — Part II. // ORSA Journal on Computing. 1989. Vol. 2, № 1. P. 4-32.

64. Goldberg A., Kaplan H., Werneck R. Reach for A: Efficient point-to- point shortest path algorithms. Technical Report MSR-TR-2005-132. Silicon Valley: Microsoft Research, 2005. 41 p.

65. Hamacher H.W., Ruzika S., Tjandra S.A. Algorithms for time dependent bicriteria shortest path problem // Discrete Optimization. 2006. Vol. 3, № 3. P. 238-254.

66. Hansen P. Bicriterion path problems // Lectures Notes in Economics and Mathematical Systems. 1979. Vol. 177. P. 109-127.

67. Heuristic Method for Vehicle Routing Problem with Time Window / K. C.Tan [et ah] // Artifical Intelligence in Engineering. 2000. Vol. 15. P. 281-285.

68. Holland J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Ann-Arbor: University of Michigan Press, 1975. 183 p.

69. Irnich S. A Unified Modeling and Solution Framework for Vehicle Routing and Local Search-Based Metaheuristics // INFORMS Journal on Computing. 2008. Vol. 20, № 2. P. 270-287.

70. AT-Path Cuts for the Vehicle Routing Problem with Time Windows / N. Kohl [et al.] // Proceedengs of NOAS’97. Copenhagen: Copenhagen University, 1997. P. 307-340.

71. Kallehaug B. Larsen J. Madsen O.B., Lagrangean Duality Applied On Vehicle Routing With Time Windows // Informatics and Mathematical modelling: Technical Report. Kgs. Lyngby: Technical University of Denmark, 2001. 34 c.

72. Kawamura H. Cooperative search based on pheromone communication for vehicle routing problems // IEEE Transactions on Fundmentals of Electronics, Communications and Computer Sciences. 1998. Vol. E81- A, № 6. P. 1089-1096.

73. Kim K., Kim S., Sahoo S. Waste collection vehicle routing problem with time windows // Transportation Science. 2005. Vol. 39, № 1. P. 119-139.

74. Kindervater G., Savelsbergh M.W. Vehicle routing: Handling edge exchanges // Local Search in Combinatorial Oprimization. Chichester: Wiley, 1997. P. 337-360.

75. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by Simulated Annealing // Science. 1983. Vol. 20, A® P. .-671.680

76. Kohonen T. Self-Jrganization and Associative Memory. Berlin: Springer-Verlag, 1988. 312 p.

77. Kolen A.W., Ran A.H., Trienekens H.W. Vehicle Routing with Time windows // Operations Research. 1987. Vol. 35, № 2. P. 266-273.

78. Land A.H., Doig A.G. An autmatic method of solving discrete programming problems // Econometrica. 1960. Vol. 28. P. 497-520.

79. Levine M.S. Finding the Right Cutting Planes for the TSP // Proceedings of Algorithm Engineering and Experimentation, International Workshop (ALENEX’99). Baltimore: Springer, 1999. P. 266-281.

80. Lim A., Zhang X. A Two-Stage Heuristic with Ejection Pools and Generalized Ejection Chains for the Vehicle Routing Problem with Time Windows // INFORMS Journal on Computing. 2007. Vol. 19, №3. P.443-457.

81. Martins E.Q. On a multicriteria shortest path problem // European Journal of Operational Research. 1984. Vol. 16, № 2. P. 236-245.

82. Martins E.Q.V., Santos J.L.E. The labelling algorithm for the multiobjective shortest path problem: Internal Technical Report. / CISUC, Departamento de Matematica, Universidade de Coimbra, Portugal. 1999. 24 p.

83. Matsuyama Y. Self-organization via competition, cooperation and categorization applied to extended vehicle routing problem // Proceedings of the International Joint Conference on Neural Network. Seattle: WA, 1991. P. 385-390.

84. Mote J., Murthy I., Olson D.L. A parametric approach to solving bicriterion shortest path problems // European Journal of Operational Research. 1991. Vol. 53, № 1. P. 81-92.

85. Mukai N., Feng J., Watanabe T. Heuristic Approach Based on Lambda-Interchange for VRTPR-Tree on Specific Vehicle Routing Problem with Time Windows . // LNAI. 2004. Vol. 3029. P. 229- 238.

86. New heuristics for the vehicle routing problem / J. F.Cordeau [et al.] // Logistics Systems: Design and Optimization. New York: Springer, 2005. P. 279-297.

87. Ohlmann J.W., Fry M.J., Thomas B.W. Route Design for Lean Production Systems // Transportation Science. 2008. Vol. 42, № 3. P. 352-370.

88. Ombuki-Berman B.M., Runka A., Hanshar F.T. Waste Collection Vehicle Routing Problem with Time Windows Using Multi- Objective Genetic Algorithms // Proceedings of the Third IASTED International Conference on Computational Intelligence. Anaheim, USA: ACTA Press, 2007. P. 91-97.

89. Oliver I.M., Smith D.J., Holland J.R. A Study of Permutation Crossover Operations on the Traveling Salesman Problem // Proc. 2nd Int. Conf. on Genetic Algorithm. Hillsdale, NJ: Lawrence Erlbaum Associates, 1987. P. 224-230.

90. Ombuki B., Ross B.J., Hanshar F. Multi-objective Genetic Algorithms for Vehicle Routing Problem with Time Windows // Applied Intelligence. 2006. Vol. 24, Ml. P. 17-30.

91. Osman I.H. Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem // Annals of Operations Research. 1993. Vol. 41, № 4. P. 421-452.

92. Potvin J.Y., Rousseau J.M. An exchange heuristic for routing problems with time windows // Journal of Operational Research Society. 1995. Vol. 46. P. 1433-1446.

93. Renaud J., Bostor F.F., Laporte G. An improved petal heuristic for the vehicle routing problem // Journal of Operational Research. 1995. Vol. 47. P.329-336.

94. Russel R.A. An effective heuristics for the m-tour travelling salesman problem with some side conditions. // Operations Research. 1977. Vol. 25. P. 517-524.

95. Savelsbergh M.W. An efficient implementation of local search algorithms for constrained routing problem // European Journal of Operational Research. Vol. 47, Ш 1. 1990. P. 75-85.

96. Savelsbergh M.W.P. Local search in routing problems with time windows // Annals of Operations Research. 1985. Vol. 4, № 1. P. 285- 305.

97. Schwefel H.P. Numerical optimization of computer models. New York: John Wiley к Sons, Inc., 1981. P. 389.

98. Schultes D. Fast and exact shortest path queries using highway hierarchies: Master’s thesis. Universitat des Saarlandes, 2005. 68 p.

99. Shaw P. Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems // Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming. London: Springer-Verlag, 1998. P. 417-431.

100. Sigauke C., Talukder H.M. A Modified Osman’s Simulated Annealing and Tabu Search Algorithm for the Vehicle Routing Problem // Asor bulletin. 2003. Vol. 22, № 3. P. 9-14.

101. Skriver A.J.V. A classifications of bicriterion shortest path (bsp) algorithms // Asia-Pacific Journal of Operational Research. 2000. Vol. 17, № 2. P. 199-212.

102. Skriver A.J.V., Andersen K.A. A label correcting approach for solving bicriterion shortest-path problems // Computers and Operations Research. 2000. Vol. 27, № 6. P. 507-524.

103. Solomon M.M. Algorithm for Vehicle Routing and Scheduling Problem with Time Window Constraints // Operations Research. Vol. 35, № 2. 1987. P. 254-265.

104. Solomon M.M., Baker E., Schaffer J. Vehicle routing and scheduling problems with time window constraints: Efficient implementations of solution improvement procedures // Vehicle routing: Methods and srudies. Amsterdam: North-Holland, 1988. P. 85-106.

105. Thangiah S.R. An Adaptive Clustering Method using a Geometric Shape for Vehicle Routing Problems with Time Windows // Proceedings of the Sixth International Conference on Genetic Algorithms. San Francisco: Morgan Kaufmann Publishers Inc., 1995. P. 536-545.

106. The VRP with Time Windows / J. F.Cordeau [et al.] // SIAM Monographs on Discrete Mathematics and Applications. Philadelphia: SIAM, 2001. P. 157-193.

Вернуться к списку