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

• Яковлева, Таисия Александровна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Яковлева, Таисия Александровна

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

Глава 1. Анализ оптимизационных задач транспортной логистики

1.1. Актуальность задач транспортной логистики для промышленности

1.2. Характеристики задач организации транспортных перевозок

1.3. Некоторые задачи организации транспортных перевозок

1.4 Мультиноменклатурная оптимизационная задача маршрутизации транспортных средств с ограничениями на перевозку

Выводы по главе:

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

2.1. Концептуальная постановка задачи

2.2. Линейная постановка задачи

2.3. Трехэтапный алгоритм решения задачи

2.4. Целочисленный вариант мультиноменклатурной оптимизационной задачи

2.5. Эвристический метод решения задачи

Выводы по главе:

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

3.1. Организация функционирования, архитектура и реализация программного обеспечения

3.2. Экранные формы программного обеспечения

Выводы по главе:

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

4.1. Анализ эффективности разработанных методов решения

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

4.3. Определение управляющих параметров (способов упорядочения) при прикреплении ТС к ПП

4.4. Анализ эффективности эвристических алгоритмов на примерах псевдослучайных исходных данных и задач из TSPLib

Выводы по главе:

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

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

ВВЕДЕНИЕ

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

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

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

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

Планирование грузоперевозок затрагивает еще один важный аспект -маршрутизацию транспортных средств. Повышенное внимание к задачам этой области объясняется тем, что по разным оценкам от 30% до 50 % всех затрат на логистику связано с транспортными издержками. При этом наиболее сложными и дорогостоящими являются международные перевозки, затраты на которые в 2,5-3 раза выше, чем перевозки на внутреннем рынке. Определение и эксплуатация рациональных маршрутов при строгом соблюдении сроков поставок помогают добиться не только минимизации эксплуатационных затрат или тонно-километрового пробега, но и сократить товарно-производственные запасы на складах в 1,5-2 раза.

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

Поставленная задача относится к классу задач маршрутизации транспортных средств при перевозке грузов - VRP (Vehicle Routing Problem).

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

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

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

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

Задачи исследования. Для достижения цели работы были поставлены и решены следующие задачи:

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

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

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

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

5. Реализация предложенных методов на ЭВМ, экспериментальная проверка эффективности работы предложенных алгоритмов.

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

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

этом принимаются равными евклидовым расстояниям; 2) примеры из библиотеки задачи коммивояжера (Т8РНЬ).

На защиту выносятся следующие результаты исследований:

1. Математическая модель мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку (п.2 Паспорта специальности 05.13.01).

2. Алгоритм построения локально оптимального решения мультиноменклатурной оптимизационной задачи маршрутизации транспортных средств с ограничениями на перевозку в случае целочисленности исходных данных (п.4 Паспорта специальности 05.13.01).

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

4. Сравнительный анализ эффективности предложенных методов (п.9 Паспорта специальности 05.13.01).

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

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

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

3. Доказательство существования для любого допустимого способа

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

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

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

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

Апробация работы. Работа была поддержана стипендией Президента Республики Башкортостан (2010-2011 учебный год), Российским фондом

фундаментальных исследований (проект 10-06-00001) и грантом Президента Российской Федерации для государственной поддержки ведущих научных школ Российской Федерации № НШ-65497.2010.9.

Основные результаты диссертационной работы докладывались и обсуждались на:

• четвертой Всероссийской зимней школе-семинаре аспирантов и молодых ученых "Актуальные проблемы науки и техники" (Уфа, 19-21 февраля 2009 г.)

• пятой Всероссийской зимней школе-семинаре аспирантов и молодых ученых "Актуальные проблемы науки и техники" (Уфа, 17-20 февраля 2010 г.)

• XII международной конференции "Компьютерные науки и информационные технологии" (Москва-СПб., 13-19 сентября 2010 г.)

• 33-й международной научной школе-семинаре имени академика С.С. Шаталина "Системное моделирование социально-экономических процессов" (Звенигород, 1-5 октября 2010 г.)

• 14-й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 28 февраля - 4 марта 2011 г.)

• шестой Всероссийской зимней школе-семинаре аспирантов и молодых ученых "Актуальные проблемы науки и техники" (Уфа, 15-18 февраля 2011 г.)

• VII международной научно-практической конференции "Актуальные задачи математического моделирования и информационных технологий" (Сочи, 18-25 мая 2011 г.)

• VI Специальном симпозиуме по исследованию операций, безопасности информации и технической кибернетики (Баден-Баден, 3-7 августа 2011г.)

• научных семинарах в Башкирском государственном университете, Омском филиале института математики им. C.JI. Соболева СО РАН, институте математики с вычислительным центром УНЦ РАН.

Публикации. Список публикаций автора по теме диссертации включает 13 научных трудов, в том числе 4 статьи в рецензируемых научных журналах из списка ВАК, свидетельство об официальной регистрации программного продукта, 4 публикации в трудах международных конференций. Шесть публикаций выполнено без соавторов.

Структура и объем диссертации. Диссертационная работа состоит из введения, 4 глав, разбитых на параграфы, основных результатов работы, библиографического списка литературы, включающего 109 источников, 1 приложения, содержит 7 таблиц, 24 рисунка. Общий объем работы составляет 125 страниц.

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

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

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

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

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

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

5. Разработан программный продукт в среде МАТЬАВ, проведен вычислительный эксперимент, подтвердивший эффективность работы предложенных алгоритмов.

Список литературы диссертационного исследования кандидат физико-математических наук Яковлева, Таисия Александровна, 2012 год

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Ельдештейн Ю.М. Логистика : электрон, учеб.-метод. комплекс. Красноярск, 2006.

2. Дрожжин А.И. Логистика. Учебный курс (учебно-методический комплекс). М., 2007.

3. Скоробогатова Т.Н. Логистика. Учебное пособие. 2-е изд. Симферополь: ООО «ДиАйПи», 2005, 116 с.

4. Проблемы логистики: [сайт]. URL: http://problema-logistic.ru

5. Parragh S., Doerner К., Hartl R. A survey on pickup and delivery problems. Part I: Transportations between customers and depot // Journal of Betriebswirtschaft. 2008. V. 58. P. 21-51.

6. Parragh S., Doerner K., Hartl R. A survey on pickup and delivery problems. Part II: Transportations between customers and depot // J. Betriebswirtschaft. 2008. V. 58. No 2. P. 81-117.

7. Berbeglia G., Cordeau J.F., Gribkovskaia I., Laporte G. Static pickup and delivery problems: A classification scheme and survey // TOP. 2007. V. 15. №1. P. 1-31.

8. The VRP Web: [сайт]. URL: http://neo.lcc.uma.es/radi-aeb/WebVRP/

9. About Vehicle Routing Problems: [сайт]. URL: http://www.idsia.ch/monaldo/vrp.html

10. Vehicle Routing and Travelling Salesman Problems: [сайт]. URL: http://www.sintef.no/static/am/opti/projects/top/vrp/index.html

П.Трофимов Д., Федуков А. Задача маршрутизации транспорта: [сайт].

URL: http://rain.ifmo.ru/cat/view.php/theory/insorted/vф-2006#cvrp 12.Бронштейн Е.М., Заико (Яковлева) Т. А. Детерминированные оптимизационные задачи транспортной логистики // Автоматика и телемеханика. 2010. №6. С. 133-147.

13.Усенко И.В. Обзор проблем принятия решений в неопределенных и расплывчатых условиях при решении транспортных задач // Перспект. информ. технологии и интел. системы. 2008. Т. 34. № 2. С. 37-44.

14.Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. Новосибирск: Наука. Сиб. отделение, 1987.

15.Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976.

16.Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998.

17.Dantzig G.B., Ramser J.H. The Truck Dispatching Problem // Management Sci. 1959, V. 6. No l.P. 80-91.

18.Гэри M, Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

19.Laporte G. The Traveling Salesman Problem: An overview of exact and approximate algorithms // Eur. J. Oper. Res. 1992. V. 59. P. 231-248.

20.Ralphs Т.К., Kopman L., Pulleyblank W.R., Trotter L.E., Jr. On the Capacitated Vehicle Routing Problem // Math. Progr., 2003, V. 94. P. 343359

21.Toth P., Vigo D. Branch-and-bound algorithms for the capacitated VRP // Vehicle Routing Problem. 2001. SIAM, P. 29-51.

22.Handbook of discrete and combinatorial mathematics. CRC Press LLC, 2000

23.Clarke G., Right J.W. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points // Oper. Res., 1963. V. 11. P. 568-581.

24.Desaulniers G. Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows// Oper. Res., 2010. V. 58. P. 179-192.

25.Dominique Feillet, Pierre Dejax, Michel Gendreau, and Cyrille Gueguen. Vehicle routing with time windows and split deliveries. Technical Paper 2006-851, Laboratoire d'lnformatique d'Avignon, 2006.

26.Spasovic L., Chien S., Kelnhofer-Feeley C. A Methodology for Evaluating of School Bus Routing A Case Study of Riverdale // Jersey Transport. Res. Board 80th Annual Meeting January 7-11, 2001 Washington, D.C. TRB Paper No. 01-2088.

27.Танаев B.C., Шкурба B.B. Введение в теорию расписаний. М.: Наука, 1975.

28.Сотсков Ю.Н., Струсевич В.А., Танаев B.C. Математические модели и методы календарного планирования. Минск: Университетское, 1994.

29.3аико (Яковлева) Т.А. Об одной задаче транспортной логистики // «Информатика, управление и компьютерные науки»: Труды 4-ой Всерос. зимней школы-семинара аспирантов и молодых ученых. Уфа: Изд. «Диалог», 2009. Т.1. С. 207-210.

ЗО.Заико (Яковлева) Т.А. Мультиноменклатурная задача транспортной логистики // "Актуальные проблемы науки и техники": Труды 5-ой Всерос. зимней школы-семинара аспирантов и молодых ученых. Уфа: Изд. "УГАТУ", 2010. Т. 3, С. 134-138.

31.Бронштейн Е.М., Заико (Яковлева) Т.А. О мультиноменклатурной задаче маршрутизации транспортных средств // "Системное моделирование социально-экономических процессов": Труды 33-й международной научной школы-семинара имени С.С. Шаталина. Звенигород: Изд. ВГУ, 2010. С. 78-79.

32.Muyldermans L., Pang G. On the benefits of co-collection: Experiments with a multi-compartment vehicle routing problem // European Journal of Operational Research No. 206. 2010. P. 93-103.

33.Бронштейн E.M., Заико (Яковлева) Т.А. Задача маршрутизации с запретами // Информационные технологии. М.: Изд-во "Новые технологии", 2011. №6. С. 42-44.

34.Tolga Bektas. The multiple traveling salesman problem: an overview of formulations and solution procedures // The International Journal of Management Science Omega. No. 34. 2006. P. 209 - 219.

35.Pei-Fang Tsai. Tight Flow-Based Formulations for the Asymmetric Traveling Salesman Problem and Their Applications to some Scheduling Problems, PhD thesis, Virginia Polytechnic Institute, 2006

36.Сесекин A.H., Ченцов А.Г. Метод динамического программирования в задаче коммивояжера. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2006, 60 с.

37.Laporte G., Metaheuristics for the Vehicle Routing Problem: Fifteen Years of Research, Canada Research Chair in Distribution Management НЕС Montreal, 2007

38.Laporte G., The Vehicle Routing Problem: An overview of exact and approximate algorithms // European Journal of Operational Research. No. 59. 1992. P. 345-358.

39.P. Toth and D. Vigo. The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002.

40.Christofides, N., Mingozzi, A., and Toth, P. Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations // Mathematical Programming. No. 20. 1981. P. 255-282.

41.Fisher M. L., Optimal Solution of Vehicle Routing Problems Using Minimum K-trees, Operations Research. No. 42. 1994. P. 626-642.

42.Laporte, G., Nobert, Y., and Desrochers, M. "Optimal routing under capacity and distance restrictions", Operations Research No. 33. 1985. P. 1050-1073.

43.Bard J.F., Huang L.,Dror M., Jaillet P. A branch and cut algorithm for the VRP with satellite facilities // HE Transactions. No. 30. 1998. P. 821-834.

44.P. Augerat. Approche Polyedrale du Probleme de Tournees de Vehicules. PhD thesis, Institut National Polytechnique de Grenoble. 1995.

45.R. Fukasawa H. Longo J. Lysgaard M. Poggi de Aragao M. Reis E. Uchoa and R.F. Werneck. Robust branch-and-cut-and-price for the capacitated vehicle routing problem // Math. Program. No. 106. 2006. P. 491-511.

46.Clarke, G., and Wright, J.W. Scheduling of vehicles from a central depot to a number of delivery points, Operations Research. No. 12. 1964. P. 568-581.

47.M. Desrochers and T.W Verhoog. A matching based savings algorithm for the vehicle routing problem. Technical Report Cahiers du GERAD G-89-04, Ecole des Hautes Etudes Commerciales de Montreal, Canada, 1989.

48.K. Altinkemer and B. Gavish. Parallel savings based heuristic for the delivery problem. Operations Research. No. 39. 1991. P. 456-469.

49.R.H. Mole and S.R. Jameson. A sequential route-building algorithm employing a generalized savings criterion. Operational Research Quarterly. No. 27. 1976. P. 503-511.

50.N. Christofides, A. Mingozzi, and P. Toth. The vehicle routing problem. In N. Christofides, A. Mingozzi, P. Toth, and C. Sandi, editors, Combinatorial Optimization,Wiley, Chichester, UK. 1979. P 315-338.

51 .Renaud, J. & Boctor, F. A Sweep Based Algorithm for the Fleet Size and Mix Vehicle Routing Problem. European Journal of Operational Research. No. 140. 2002. P. 618-628.

52.Gillett B. & Miller L. A Heuristic for the Vehicle Dispatching Problem. Operations Research. No. 22. 1974. P. 340-349.

53.Fisher M.L., and Jaikumar R. "A generalized assignment heuristic for vehicle routing", Networks. No. 11. 1981. P. 109-124.

54.Ryan D., Hjorring C. & Glover F. Extension of the Petal Method for Vehicle Routing. Journal of the Operational Research Society. N.44. 1993. P.289-296.

55.J.E. Beasley. Route-first cluster-second methods for vehicle routing. Omega. No. 11. 1983. P. 403-408.

56.J. Renaud F.F. Boctor and G. Laporte. An improved petal heuristic for the vehicle routing problem. Journal of Operational Research Society. No. 47. 1996. P. 329-336.

57.É. D. Taillard. Parallel Iterative Search Methods for Vehicle Routing Problems. Networks. No. 23. 1993. P. 661-673.

58.P.M. Thompson and H.N. Psaraftis. Cyclic transfer algorithms for multi-vehicle routing and scheduling problems. Operations Research. No. 41. 1993. P. 935-946.

59.A. Van Breedam. An analysis of the behavior of heuristics for the vehicle routing problem for a selection of problems with vehicle-related, customer-related, and timerelated constraints. Ph.D. dissertation, University of Antwerp, 1994.

60.F. Robuste C.F. Daganzo and R. Souleyrette. Implementing vehicle routing models.Transportation Research B. 24. 1990. P. 263-286.

61.I.H. Osman. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41. 1993. P. 421451.

62.G. Dueck and T. Scheurer. Threshold accepting: A general purpose optimization algorithm. Journal of Computational Physics, 90. 1990. P. 161185.

63.G. Dueck. New optimization heuristics: The great deluge algorithm and the record to-record travel. Journal of Computational Physics, 104. 1993. P.86-92.

64.M. Gendreau, A. Hertz, and G. Laporte. A tabu search heuristic for the vehicle routing problem. Management Science, 40. 1994. P. 1276-1290.

65.J. Xu and J.P. Kelly. A network flow-based tabu search heuristic for the vehicle routing problem. Transportation Science, 30. 1996. P. 379-393.

66.J.H. Holland. Adaptation in Natural and Artificial Systems. The University of Michiga Press, Ann Arbor, MI, 1975.

67.I.M. Oliver, D.J. Smith, and J.R.C. Holland. A study of permutation crossover operators on the traveling salesman problem. In J.J. Grefenstette, editor, Proceedings of the Second International Conference on Genetic Algorithms, Lawrence Erlbaum, Hillsdale, NJ, 1987. P. 224-230.

68.J.-Y. Potvin. Genetic algorithms for the traveling salesman problem. Annals of Operations Research, 63. 1996. P.339-370.

69.Y. Rochat and E.D. Taillard. Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1. 1995. P. 147-167.

70.A. Colorni, M. Dorigo, and V. Maniezzo. Distributed optimization by ant colonies. In F. Varela and P. Bourgine, editors, Proceedings of the European Conference on Artificial Life, Elsevier, Amsterdam, 1991.

71. J. J. Hopfield and D.W. Tank. Neural computation of decisions in optimization prob lems. Biological Cybernetics, 52. 1985. P. 141-152.

72.M. Gendreau, G. Laporte, and J.-Y. Potvin. Vehicle routing: Modern heuristics. In E.H.L. Aarts and J.K. Lenstra, editors, Local Search in Combinatorial Optimization,Wiley, Chichester, UK, 1997. P. 311-336.

73.B.L. Golden, E.A. Wasil, J.P. Kelly, and I.M. Chao. Metaheuristics in vehicle routing. In T.G Crainic and G. Laporte. Fleet Management and Logistics, Kluwer, Boston, MA, 1998. P. 33-56.

74.Т.А. Заико (Яковлева). Мультиноменклатурная задача маршрутизации транспортных средств с ограничениями на перевозку (на англ. языке) // "Компьютерные науки и информационные технологии": Труды 12-ой междунар. конф. Москва-СПб.: Россия, 2010. Т. 2. С. 72-74.

75.Е.М. Бронштейн, Т.А. Яковлева. Трехэтапный эвристический алгоритм решения мультиноменклатурной задачи маршрутизации // "Математическое программирование и приложения": Труды 14-ой Всероссийской конференции. Екатеринбург: 2011. С. 158-159.

76. Т. А. Яковлева. Решение задачи коммивояжера как подзадачи маршрутизации транспортных средств // "Актуальные проблемы науки и

техники": Труды 6-ой Всерос. зимней школы-семинара аспирантов и молодых ученых. Уфа: Изд. "УГАТУ", 2011. Т. 1. С. 282-284.

77.Е.М. Бронштейн, Т.А. Яковлева. Сравнительный анализ эвристических алгоритмов решения мультиноменклатурной задачи маршрутизации с запретами // Логистика и управление цепями поставок. 2011. №4. С. 45

78.Яковлева Т.А. Целочисленная мультиноменклатурная оптимизационная задача маршрутизации транспортных средств с ограничениями на перевозку // Современные проблемы науки и образования. 2011. № 5. [сайт]: URL: www.science-education.ru/99-4830

79.Ковалев М.М. Дискретная оптимизация (целочисленное программирование). Москва: Едиториал УРСС. 2003. 192 с.

80.М. Маркус, X. Минк. Обзор по теории матриц и матричных неравенств; пер. с англ. под ред. В. Б. Лидского. М.: Наука, 1972. 232 с.

81.Е.М. Бронштейн, Т.А. Яковлева. Мультиноменклатурная задача маршрутизации с ограничениями как предмет исследования (на англ. языке) // Труды "6-го Специального Симпозиума по исследованию операций, безопасности информации и технической кибернетики". Баден-Баден: ФРГ, 2011. С. 89-92.

82.Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. : Пер. с англ. : Уч. пос. М.: Издательский дом «Вильяме». 2000. 384 с.

83.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999. 960 е., 263 ил.

84.Johnson D.S., McGeoch L.A. The Traveling Salesman Problem: A Case Study in Local Optimization, 1995.

85.Ravindra K. Ahuja, Ozlem Ergun, James B. Orlin, Abraham P. Punnen A survey of very large-scale neighborhood search techniques // Discrete Applied Mathematics 123, 2002, P. 75-102

86.Lin Shen, Kernighan B. W. An Effective Heuristic Algorithm for the Traveling-Salesman Problem // Operations Research 21, 1973, P. 498-516.

87.Fischer Т., Merz P., Embedding a chained Lin-Kernighan algorithm into a distributed algorithm, In Karl F. Doerner, M. Gendreau, P. Greistorfer, W. J. Gutjahr, R. F. Hartl, M. Reimann, editors, Metaheuristics - Progress in Complex Systems Optimization, volume 39 of Operations Research/Computer Science Interfaces, pages 277-295. Springer, October 2007

88.Helsgaun K., An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic // European Journal of Operational Research 126(1), 2000, P. 106-130.

89.Helsgaun K., General k-opt submoves for the Lin-Kernighan TSP heuristic // Math. Prog. Сотр. 2009. P. 119-163.

90.Nguyen H.D., Yoshihara I., Yamamori K., Yasunaga M. A New Data Structure for Lin-Kernighan Traveling Salesman Heuristic // available at [сайт]: URL: http://ir.lib.miyazaki-u.ac.jp/dspace/bitstream/l 0458/282/3/ KJ00002426422.pdf

91.Martin O., Otto S. W., Felten E. W. Large-step Markov chains for the TSP incorporating local search heuristics // Operations Res. Lett. 11, 1992, P. 219224.

92.Т.А. Яковлева. Генетический алгоритм с эвристикой Лина-Кернигана как подэтап решения мультиноменклатурной задачи маршрутизации // Труды междунар. Научно-практ. конф. "Актуальные задачи математического моделирования и информационных технологий".-Сочи: Изд. "European resercher", 2011. №5-1(7). С.660-661.

93.Boese К. D., Kahng А. В., Muddu S. A new adaptive multi-start technique for combinatorial global optimizations // Operations Res. Lett. 16, 1994, P. 101113.

j

94.Sherwani N.A. Algorithms for VLSI physical design automation, 3 ed, Kluwer academic publishers, 1999, P. 573.

95.ГОСТ 19.701-90 ЕСПД. Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения

96.ГОСТ 19.002-80 ЕСПД. Схемы алгоритмов и программ. Правила выполнения

97.ГОСТ 19.003-80 ЕСПД. Схемы алгоритмов и программ. Обозначения условные графические

98.Госстандарт России - Р50.1.028 - 2001. Рекомендации по стандартизации. Информационные технологии поддержки жизненного цикла продукции. Методология функционального моделирования

99.С.В.Маклаков. Создание информационных систем с AllFusion Modeling Suite. Москва. "ДИАЛОГ- МИФИ". 2005

100. Matlab Central, [сайт]: URL: http://www.mathworks.com/matlabcentral/

101. Консультационный центр MATLAB компании SoftLine. [сайт]: URL: http://matlab.exponenta.ru

102. Потемкин В.Г. Система MATLAB. Справочное пособие. - М..-ДИАЛОГ МИФИ, 1997. 350 с.

103. Иглин С.П. Математические расчеты на базе MATLAB. - СПб.: БХВ -Петербург, 2005. 640 с.

104. H.H. Мартынов. Matlab 7. Элементарное введение. М: Кудиц-Образ, 2005.416 с.

105. Иглин С. П. Решение некоторых задач теории графов в MATLAB // Exponenta Pro. Математика в приложениях № 4 (4), 2003.

106. ArcGIS 10 полнофункциональная геоинформационная система, [сайт]: URL: http ://www.dataplus .ru/networkanalyst

107. Пакет решения мультиноменклатурной задачи транспортной логистики / Т.А. Яковлева. Свид. №2011613654 о гос. регистрации программы для ЭВМ. 2011.

108. The Traveling Salesman Problem, [сайт]: URL: http://www.tsp.gatech.edu

109. TSPLIB: Symmetrie traveling salesman problem (TSP). [сайт]: URL: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html