Модели, методы и алгоритмы эффективного решения задачи маршрутизации транспорта на графах больших размерностей тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Чернышев, Сергей Владленович

• Чернышев, Сергей Владленович
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Чернышев, Сергей Владленович

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.5 Выводы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.9 Выводы.

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

3.1 Система Р1апУ1сНа.

3.2 Архитектура РкпУМа.4.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2.1 Антверпен.

4.2.2 Бельгия.

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

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

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

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

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

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

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

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

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

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

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

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

4.4.8 Проекты компании СарУ1(На.

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

4.5 Выводы.

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

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

В работе рассматриваются задачи оптимизации на графах больших размерностей, возникающие в транспортной логистике, не имеющие эффективных алгоритмов нахождения точного решения. Исследуемый класс задач является вариацией задач маршрутизации транспорта с временными окнами и дополнительными ограничениями [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 Т., Rüssel R.A., Christofides N., Mingozzi A., Toth P. [44, 107]). С середины 1990-х годов исследования сосредоточились на построении метаэвристик, в основе которых лежат такие методы как поиск с исключениями, метод отжига, генетические алгоритмы, метод муравьиных колоний, нейросети и другие (Gendreau M., Osman I.H., Matsuyama Y. [7,28,34,35,86,90,100]). В последние десять лет исследования склонились в основном в сторону обработки сложных видов ограничений (Frazzoli Е., Bullo F. [30,50,56]).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическая ценность. Алгоритмы, опубликованные в данной работе, реализованы на языке С++ и протестированы в операционных системах 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. Приближенный алгоритм решения бикритериальной задачи о поиске кратчайших путей.

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

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

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

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

Улучшены существующие результаты:

6. Разработана структура данных для быстрого выполнения обменов сегментов маршрутов. Скорость работы возросла с 0(п) до О (log2 тг).

7. При помощи разрезов и условия фильтрации ускорена процедура поиска оптимальных обменов сегментов маршрутов с 0(пъ) до 0(п log2 п).

Разработаны программные продукты:

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

В работе рассмотрены задачи маршрутизации транспорта с временными окнами и дополнительными ограничениями, приведен обзор научных публикаций за последние 40 лет. Опубликованы научные работы [2,9,14,18,19,24-27,38].

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

Список литературы диссертационного исследования кандидат физико-математических наук Чернышев, Сергей Владленович, 2011 год

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21. 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.

22. An algorithm for the traveling salesman problem / J. D.Little et al. // Operations Research. 1963. Vol. 11. P. 972-989.

23. An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows / O. Bráysy et al. // Transportation Science. 2008. Vol. 42, № 3. P. 371-386.

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

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

26. 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.

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

28. Bráysy 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.

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

30. 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.

31. 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.

32. 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.

33. 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.

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

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

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

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

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

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

40. 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.

41. 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.

42. 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.

43. 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.

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

45. Fisher M.L., Jaikumar R. A generalized assignment heuristic for vehicle routing // Networks. 1981. Vol. 11, № 2. P. 109-124.

46. Fisher M.L., Jôrnsten K.O., Madsen O.B. Vehicle Routing with Time Windows: Two Optimization Algorithms // Operations Research. 1997. Vol. 45, № 3. P. 488-492.

47. Fisher M.L. Optimal Solution of Vehicle Routing Problems Using Minimum K-trees // Operations Research. 1994. Vol. 42, № 4. P. 626642.

48. Fisher M.L. Vehicle Routing // Handbooks in Operations Research And Management Science. Amsterdam: NorthHolland, 1995. P. 1-33.

49. Frazzoli E., Bullo F. Decentralized algorithms for vehicle routing in a stochastic time-varying environment // Decision and Control. 2004. Vol.4. P. 3357-3363.

50. Geoffrion A.M., McBride R. Lagrangian Relaxation Applied to Facility Location Problems // AIIE Transactions. 1978. Vol. 10. P. 40-48.

51. Ghaziri H. Solving routing problems by a self-organizing map // Artificial Neural Networks. Amsterdam: North-Holland, 1991. P. 829834.

52. 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.

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

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

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

56. 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.

57. 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.

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

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

60. 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.

61. 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.

62. K-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.

63. 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.

64. 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.

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

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

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

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

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

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

71. 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.

72. 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.

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

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

75. 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.

76. 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.

77. 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. 229238.

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

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

80. 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.

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

82. 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.

83. 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.

84. 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.

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

86. 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.

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

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

89. Schultes D. Fast and exact shortest path queries using highway hierarchies: Master's thesis. Universität des Saarlandes, 2005. 68 p.

90. 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.

91. 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.

92. 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.

93. 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.

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

95. 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.

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

97. The vehicle routing problem / N. Christofïdes et al. // Combinatorial Optimization. 1979. P. 315-338.

98. Thorup M. Undirected single-source shortest paths with positive integer weights in linear time // Journal of the ACM. Vol. 46, № 3. 1999. P. 362-394.

99. Toth P., Vigo D. An overview of vehicle routing problems // The Vehicle Routing Problem: SIAM Monographs on Discrete Mathematics and Applications. Philadelphia: SIAM, 2002. P. 1-24.

100. TSP cuts which do not conform to the template paradigm / D. Appletgate et al. // Computational Combinatorial Optimization, LNCS. 2001. Vol. 2241. P. 261-303.

101. Vacic V., Sobh T.M. Vehicle Routing Problem with Time Windows // International Scientific Journal of Computing. 2004. Vol. 3, JVfi 2. P. 72-80.

102. Vincke P. Problèmes multicritères // Cahiers du Centre d'Etudes de Recherche Opérationelle. 1974. Vol. 16. P. 425-439.

103. Williams J.W. Heapsort // Communications of the ACM. 1964. Vol. 7, № 6. P. 347-348.