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

• Копылов, Роман Васильевич
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Копылов, Роман Васильевич

Введение.

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

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

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

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

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

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

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

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

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

2.4. Выводы.

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

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

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

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

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

3.5. Выводы.

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

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

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

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

4.4. Выводы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Копылов, Роман Васильевич

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Копылов, Роман Васильевич, 2006 год

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

86. Klein R., 2000. Personal Communication.

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

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

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

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

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

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

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

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

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

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

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

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

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