Оптимизация маршрута доставки однородного груза от множества производителей множеству потребителей тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Гиндуллин, Рамиз Вилевич

• Гиндуллин, Рамиз Вилевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Гиндуллин, Рамиз Вилевич

ОГЛАВЛЕНИЕ

С.

Введение

1 ОБЗОР ЗАДАЧ ТРАНСПОРТНОЙ МАРШРУТИЗАЦИИ

1.1 Задачи транспортной маршрутизации

1.2 Методы решения задач транспортной маршрутизации

1.3 Задача коммивояжера (TSP, Traveling salesman problem)

1.4 Выводы

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

2.1 Задача 1

2.2 Задача 2

2.3 Задача 3

2.4 Задача 4

3 ПОСТАНОВКА ЧИСЛЕННЫХ ЭКСПЕРИМЕНТОВ, ИССЛЕДОВАНИЕ РЕЗУЛЬТАТОВ

3.1 Точные решения задачи 2

3.2 Зависимость длины оптимального маршрута от вместимости транспортного средства

3.3 Сравнение эффективности эвристик для решения задачи 2

3.4 Сравнение эффективности эвристик для решения задачи 3

3.5 Сравнение эффективности жадных алгоритмов для решения

задачи 3

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЕ А

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

ВВЕДЕНИЕ

Актуальность темы работы. Транспортная промышленность необходима для обеспечения производства сырьем и доставки готового товара потребителям. Особое внимание уделяется задачам, связанным с планированием маршрутов. По разным оценкам от 30% до 50 % всех затрат на логистику связано с транспортными издержками.

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

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

Степень разработанности темы исследования. В работе

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

средств при перевозке грузов - VRP (Vehicle Routing Problem) - SVRPPD -

задача транспортной маршрутизации с вывозом и доставкой одним

транспортным средством. Первая задача транспортной маршрутизации была

сформулирована Г. Данцигом и Дж. Рамсером в 1959 году, ее постановка

инициировала важный класс задач оптимизации. Наиболее часто

встречающиеся постановки задач данного класса предполагают доставку

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

Предполагается, что целью является минимизация стоимости

транспортировки. Встречаются задачи и с другой целевой функцией

3

(например, временем доставки грузов), но их, как правило, можно переформулировать таким образом, что целевая функция будет носить экономический смысл Как правило, задачи данного класса относятся к NP-трудным, точное решение которых при сколько-нибудь значительной размерности требует огромного количества времени. На сегодняшний день сформулировано множество вариантов данной задачи, в которых учитываются различные реальные ограничения, разработан ряд алгоритмов приближенного поиска оптимальных решений. Это связано с тем, что развитие логистических процессов и потребность в учете новых факторов ведут к постановке новых задач, требующих, в свою очередь, применения новых методов решения. Создана европейская рабочая группа VeRoLog (Vehicle Routing and Logistics), которая активно занимается задачами транспортной маршрутизации.

Необходимо указать на отличие задачи в рассматриваемой постановке от классической задачи маршрутизации транспортных средств. Особенностями рассматриваемой задачи являются наличие множественных пунктов-производителей, из которых производится вывоз груза. Поставленная задача может быть сформулирована, как целочисленная линейная оптимизационная задача, и является обобщением двух известных задач: задачи коммивояжера и задачи о загрузке рюкзака. Менее 10% работ, посвященных задачам транспортной маршрутизации, рассматривают данный вариант задачи. Результаты по близким задачам получены Cordeau J.-F. [51], Laporte G. [61, 173], Renaud J. [173], Desrosiers J. [67], Mingozzi A. [41], Pankratz G. [163], Ченцовым А.Г. [16], Гимади Э.Х. [11] и другими учёными. Также, создана европейская рабочая группа VeRoLog (Vehicle Routing and Logistics), которая активно занимается задачами транспортной маршрутизации.

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

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

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

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

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

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

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

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

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

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

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

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

3. Сравнение эффективности предложенных алгоритмов.

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

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

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

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

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

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

значимость заключается в формализации и решении монономенклатурной

оптимизационной задачи маршрутизации транспортных средств с одним

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

6

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

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

Степень достоверности и апробация результатов.

-Теоретические положения работы подтверждаются математическими доказательствами.

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

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

1. Всероссийская зимняя школа Всероссийская зимняя школа-семинар аспирантов и молодых ученых семинар аспирантов и молодых ученых семинар аспирантов и молодых ученых «Актуальные проблемы науки и техники», Уфа, 2010.

2. Всероссийская конференция «Математическое программирование и приложения», Екатеринбург, ИММ УрО РАН, 2011.

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

4. Международная конференция «Дискретная оптимизация и исследование операций», Новосибирск, 2013.

5. Вторая ежегодная конференция Европейской рабочей группы УеЯоЬо§, Саутгемптон, 2013.

6. Научные семинары в Уфимском государственном авиационном техническом университете, в Башкирском государственном университете и Институте математики Уфимского научного центра РАН.

Работа выполнена при поддержке РФФИ (проекты № 10-06-00001 и № 13-01-00005).

1. ОБЗОР ЗАДАЧ ТРАНСПОРТНОЙ МАРШРУТИЗАЦИИ

1.1 Задачи транспортной маршрутизации

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

История задач маршрутизации насчитывает более полувека. Первая работа, посвященная данному типу задач, появилась в 1959 году, когда была опубликована статья Г. Данцига и Дж. Рамсера [65], в которой была сформулирована группа задач, впоследствии названная VRP - Vehicle Routing Problem. В данной работе рассматривалась задача нахождения оптимального маршрута доставки парком бензовозов продукта от конечной станции магистрального трубопровода до большого количества обслуживающих терминалов (задача диспетчеризации грузовиков). Используя методы, опирающиеся на формулировки линейного программирования, предложенные ручные вычисления давали решение, близкое к оптимальному, для задач с количеством маршрутов 4 и количеством станции 12. Типичная постановка задачи приведена на рисунке 1.1.

Рисунок 1.1 Типичная постановка задачи транспортной маршрутизации и ее

решение.

Задачи транспортной маршрутизации являются обобщением задачи коммивояжера, поэтому, как правило, относятся к классу ИР-сложных задач (однако, некоторые частные варианты задачи могут решаться за полиномиальное время, например, [21]).

На текущий момент, имеется множество вариантов задач маршрутизации [38, 164, 165, 8]. В целом, задачи маршрутизации можно разделить по следующим характеристикам [8]:

1. Пункты производства

а) Пункт производства один. Это характерно для ситуации, когда имеется склад (база) с которого осуществляются поставки различным потребителям.

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

таксопарка) В этом случае пункт посадки каждого пассажира можно считать пунктом производства.

2. Пункты потребления.

а) Пункт один. В частности это так, если продукция из разных мест должна доставляться на склад или в пункт сертификации.

б) пунктов несколько Эта ситуация наиболее распространенная. Содержательная интерпретация аналогична 16.

3) Сеть дорог.

а) Дорога характеризуется одним параметром.

б) Дорога характеризуется несколькими параметрами перевозки, расстояние, пропускная способность по весу, ограничения по скорости и др.).

-Все учитываемые характеристики аддитивно пути.

-Среди характеристик есть неаддитивные пропускная способность).

4) Количество груза.

а) Количество груза характеризуется вещественным числом (непрерывная задача).

-Одним. -Несколькими.

б) Количество груза характеризуется целым числом (дискретная

задача).

-Одним. -Несколькими.

5) Базы ТС (депо).

а) База одна.

б) Баз несколько.

в) Базы совпадают с пунктами производства.

6) Вид груза.

(стоимость габариты,

зависят от

(например,

а) Задачи с однородным грузом.

б) Многопродуктовые задачи.

7) Характер ТС.

а) ТС единственное.

б) Все ТС одинаковые.

в) ТС различны.

8) Ограничения на вместимость ТС.

а) Предусмотрены ограничения только по одному параметру.

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

9) Ограничения по видам перевозимых грузов.

а) Есть грузы, запрещенные к перевозке тем или иным ТС.

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

в) Существуют запреты на совместную перевозку грузов некоторых видов одним ТС.

10) Условия перевозки.

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

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

в) В каждый пункт потребления грузы из разных пунктов производства доставляет одно ТС.

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

д) Возможность совпадения пунктов производства и потребления.

-Некоторые пункты могут быть одновременно пунктами производства и потребления. -Все пункты разные.

11) Ограничения по времени.

а) Грузы из пунктов производства должны забираться в указанные временные окна.

б) Грузы в пункты потребления должны доставляться в указанные временные окна.

в) Максимальная длительность маршрута перевозок ограничена.

г) Время непрерывного пребывания ТС в пути ограничено.

д) Имеются те или иные ограничения на последовательность

перевозок.

12) Особые условия перевозки.

а) Каждый вид груза должен быть доставлен из некоторого пункта производства в некоторый пункт потребления (такси).

б) Не допускается порожний пробег (кроме начального и конечного отрезков маршрута).

13) Факторы, определяющие стоимость перевозки.

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

б) Зависимость стоимости перевозки от загрузки ТС.

-Пропорциональность зависимости стоимости от загрузки.

14) Условие возврата.

а) ТС должны возвращаться на исходную базу.

б) ТС должны завершать маршрут на какой-нибудь базе.

в) ТС могут завершать маршрут в любом месте.

15) Учет упаковки в транспортное средство (для дискретного случая постановки задачи). При этом условии в задачу вводятся ограничения

на размещение ящиков внутри транспортного средства, а также ограничение на последовательность погрузки-выгрузки груза / стековый принцип (LIFO).

16) Определенность.

а) Статическая задача, т.е. заказы в процессе доставки не изменяются.

б) Динамическая задача, т.е. заказы после планирования могут

13

добавляться или отменяться.

Наиболее исследованными вариантами задач маршрутизации являются:

Capacitated VRP (CVRP, задача маршрутизации транспортных средств с учетом грузоподъемности). Базовый вариант задач транспортной маршрутизации, который и был описан в работе Данцига и Рамсера. Парк транспортных средств одинаковой вместимости находятся в одном депо. Задача состоит в нахождении минимальных по затратам (денежным, времени или расстоянию) замкнутых маршрутов, которые полностью обслужат всех клиентов, таких чтобы выполнялось условие не превышения вместимости ТС на каждом из маршрутов. При этом, каждый потребитель обсуживается ТС только один раз, поэтому вместимость ТС должна превышать потребность любого из клиентов. Кристофидесом в 1979 году была дана формализация в виде задачи линейного программирования [58].

Multi Depot VRP (задача транспортной маршрутизации с множеством депо). У компании может быть несколько депо, через которые можно обслуживать потребителей. Если клиенты сгруппированы около депо, то данная задача маршрутизации может быть решена как, множество независимых задач маршрутизации. Однако, если клиенты и депо смешаны между собой, то в данном случае решается задача MDVRP. Одним из ранних упоминаний задачи с несколькими депо является [204].

Periodic VRP (периодическая задача маршрутизации). Обобщение классической задачи маршрутизации, в которой период планирования составляет более одного дня. У каждого клиента возникает ежедневная потребность, которая должна быть удовлетворена как минимум одним визитом ТС. Впервые рассмотрена в [56].

VRP with Backhauls (задача транспортной маршрутизации с обратным транзитом). В данной задаче надо учитывать возможность того, что потребители могут вернуть часть ранее завезенного груза, который транспортное средство должно будет отвезти на склад. Главным допущением в данной задаче считается то, что перед тем как с пункта можно будет забрать груз, в него уже был завезен груз на предыдущих шагах данного маршрута или предыдущих развозках. При этом, заранее известны количества груза, которые надо будет завезти и забрать. Данная постановка задачи означает, что в отличие от предыдущих задач, полная или почти полная загрузка транспортных средств грузом в депо не является экономически выгодной или, более того, осуществимым. Впервые термин VRPB был представлен в [98]. Существует 3 группы задач с обратным транзитом [45]:

- транспортное средство может забирать груз на маршруте до того как полностью развезет свои доставки;

- транспортное средство может забирать груз на маршруте до того как полностью развезет свои доставки и один и тот же клиент может как принимать груз, так и отправлять;

- транспортное средство на маршруте вначале доставляет груз до клиентов, и только потом забирает его; маршрут может состоять только из доставок, но не может состоять только из забора груза.

Первые два класса задач впервые поставлены и рассмотрены в [52] и [102]. Однако эти типы задач в литературе рассматривались реже в связи с тем, что на практике сложно переставлять товары в частично заполненном транспортном средстве. Третий тип задач в литературе встречается чаще. Ранними работами, посвященными ему, являются [66], [98] и [99].

VRP with Pick-Up and Delivering (задача транспортной маршрутизации

с вывозом и доставками, VRPPD). Задача является обобщением предыдущего

класса задач. Главная особенность заключается в том, что отсутствует

15

необходимость посещения клиента с целью передать ему груз, чтобы впоследствии вернуться и осуществить обратный транзит. То есть, у клиента изначально имеется груз, который необходимо забрать. В результате, клиент у которого имеется груз для вывоза и который должен принять груз может быть посещен транспортным средством дважды. Возможность передачи груза от одного клиента к другому допускается, но этот случай мало исследован [103]. Согласно [93] менее 10% работ, посвященных задачам транспортной маршрутизации, рассматривают варианты задач с вывозом и доставками. Вариант задачи с одним ТС имеет несколько названий [106]: SVRPPD, 1-VRPPD [67, 143], SVPDP [61], SPDP [166], TSPPD [51]. Подобного типа задачи появляются при перевозках однородных грузов, таких как газ, почва, песок, деньги.

Для VRPPD с множеством ТС в [159] рассмотрено использование раздельных доставок и загрузок (то есть, с возможностью неоднократного посещения пунктов). Было показано, что использование раздельных доставок позволяет сократить расстояние перевозок, по сравнению с однократным посещением клиентов. Размер экономии сильно зависит от вместимости ТС по сравнению с запросами пунктов.

Вариантом данной задачи можно считать VRP with Satellite Facilities (задача транспортной маршрутизации с сопутствующими складами), в которой у транспортного средства есть возможность пополнить груз в сопутствующих складах, без возврата в депо [118].

VRP with Time Windows (задача транспортной маршрутизации с временными окнами). К задаче транспортной маршрутизации добавляются ограничения на время посещения каждого из клиентов. Клиент может быть обслужен только в пределах заданного временного окна. [187]

Stochastic VRP (стохастическая задача транспортной маршрутизации). Это задача маршрутизации у которой не менее одного параметра заданы случайным образом. Возможно три варианта задачи:

- стохастические потребители (потребитель может присутствовать с заданной вероятностью);

- стохастические потребности клиентов;

- стохастическое время обслуживания.

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

Первый случай известен, как Chance Costrained Programming (ССР, программирование с вероятностными ограничениями) и он сравнительно легко решается, когда его сводят к детерминированному варианту задачи маршрутизации. [55, 128, 129].

Второй вариант SVRP может решаться как Stochastic program with Recource (SPR, стохастическое программирование с рекурсией). Начальное решение определяется до получения значений случайных величин. На следующем этапе уже могут приниматься корректирующие действия. [40, 115, 189].

Split Deliveries VRP (SDVRP, задача транспортной маршрутизации с

раздельными доставками). В данной задаче, парк однотипных транспортных

средств с ограниченной вместимостью должен обслужить некоторое

множество потребителей. Каждый потребитель может быть посещен более

одного раза, в отличие от задачи VRP, в связи с этим потребность отдельного

потребителя может быть выше вместимости транспортного средства. Каждое

ТС должно начинать и заканчивать свой маршрут в депо. Задача состоит в

нахождении множества маршрутов транспортных средств, которые обслужат

17

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

Задача была представлена в литературе 20 лет назад в [74] и [75], в которых было показано, что использование раздельных доставок в некоторых случаях позволяет получить маршрут короче, чем в случае однократного посещения клиентов. В [24], анализируется максимально возможный выигрыш, получаемый при использовании раздельных доставок, а в [23] те же авторы представили результаты вычислительных экспериментов, в которых показано, как данный выигрыш зависит от характеристик задачи. В [21] они анализируют вычислительную сложность SDVRP. Было выявлено, что в случае целочисленного варианта с вместимостью транспортных средств не более 2, задачу можно свести к задаче b-согласования вершин графа (Ь-matching problem), постановки которой приведены в [91], и для которой имеется полиномиальный алгоритм решения [91, 107]. В остальных случаях, SDVRP относится к классу NP-полных задач.

Dror, Laporte и Trudeau [73] предложили метод ветвей и границ, основанный на целочисленной линейной постановке SDVRP, куда помимо прочих неравенств были включены неравенства связности, которые обеспечивали то, что каждый клиент будет обслужен хотя бы одним транспортным средством. Метод был опробован на трех небольших примерах до 20 пунктов с различным спросом со стороны потребителей.

Belenguer, Martinez и Mota рассматривали SDVRP как полиэдр [35]. На основании частичного описания SDVRP-полиэдра, авторы использовали метод ветвей и отсечений, который позволял решать задачи средних размеров с количеством потребителей до 51. Усиленная линейная релаксация позволяет получить хорошую нижнюю границу для значения оптимального решения.

Точные способы решения задачи также были предложены Li et al [132],

Джин, Лиу и Боуден [117, 136]. Оба подхода работают только при очень

18

маленьких размерностях. Лучший результат получен для SDVRP с временными окнами (SDVRPTW) в работе Gueguen [90, 105]. В последней работе предложены точные методы, способные решать задачу с сотней потребителей.

Первым эвристическим алгоритмом для SDVRP стал локальный поиск, который был предложен в работах Dror и Trudeau [74, 75]. Предлагалось использование двухэтапной процедуры, по которой вначале получали допустимое решение задачи VRP, а затем его улучшали, используя добавление путей и обмен пунктами между ними. Добавление путей означает, что создавался новый путь, который обслуживал клиента раздельной доставкой, если это позволяло уменьшить общую длину перемещений. Обмен пунктами состоял в том, что рассматривался клиент i с потребностью di и его убирали со всех путей, которые его обслуживают. Далее, рассматриваются все пути, в которых транспортное средство нагружено не полностью и данное транспортное средство имеет возможность обслужить еще и пункт /. Производится расчет того, насколько длиннее станет общая дистанция, если клиента i поместить в каждый из данных путей. Выбирается то подмножество вставок, общая дистанция при котором является минимальной. Данные простые подходы успешно использовались в эвристических и метаэвристических методах в будущем.

Позднее, предложено использование табуированного поиска [20, 22]. В [55] предложен эвристический частично целочисленный алгоритм пути "между записями", который оказался эффективным в задачах с большими потребностями со стороны пунктов-потребителей. Вычислительные эксперименты, сравнивающие эффективность этих методов приведены в [202]. Frizzel и Giffin в [84] представили формализацию задачи SDVRP с сеткой и временными окнами (SDVRP with grid network and time windows).

Список литературы диссертационного исследования кандидат наук Гиндуллин, Рамиз Вилевич, 2013 год

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

1. Айзенштат B.C., Кравчук Д.Н. О минимуме линейной формы на множестве всех полных циклов симметрической группы S. Кибернетика. 1968. 2:64-66.

2. Бронштейн Е.М., Гиндуллин Р.В. Об одном классе задач маршрутизации. Математическое Моделирование. 2010. Том 23. №6. С. 123-132.

3. Бронштейн Е.М., Гиндуллин Р.В. Об одной целочисленной задаче маршрутизации. Логистика и управление цепями поставок. 2013. №6. С. 85-90.

4. Бронштейн Е.М., Гиндуллин Р.В. Об одном классе задач маршрутизации. Информационный бюллетень «XIV Всероссийская конференция «Математическое программирование и приложения» (тезисы докладов)». Екатеринбург. ИММ УрО РАН. 2011. С. 156157.

5. Бронштейн Е.М., Гиндуллин Р.В. Об одном классе оптимизационных задач маршрутизации. Материалы международной конференции «Дискретная оптимизация и исследование операций». Новосибирск. 2013. С. 127.

6. Бронштейн Е.М., Гиндуллин Р.В. Об одном классе задач маршрутизации. Научно-технические ведомости СПбГПУ. Информатика, телекоммуникации, управление. 2013. №1(164). С. 63-67.

7. Бронштейн Е.М., Гиндуллин Р.В. Оптимизационные задачи транспортной логистики. Материалы международной научной конференции "Математическое моделирование, оптимизация и информационные технологии". Кишинеу. Академия транспорта и коммуникации. 2012. С. 214-219.

8. Бронштейн Е.М., Гиндуллнн P.B. Точные решения некоторых оптимизационных задач транспортной логистики. Математическое моделирование. 2013. Том 25. №11. С. 121-127.

9. Бронштейн Е.М., Заико Т.А. Детерминированные оптимизационные задачи транспортной логистики. Автоматика и телемеханика. 2010. 10: 133-147.

10. Гайков Н.Е. О минимуме линейной формы на циклах. // Известия АН БССР. Серия физико-математических наук. 1980. 4:128.

11. Гимади Э.Х. , Шахшнейдер А. В. Приближенные алгоритмы с оценками для задач маршрутизации на случайных входах с ограниченным числом клиентов в каждом маршруте. // Автоматика и телемеханика. 2012. № 2. 126-140.

12. Гиндуллин Р.В. Об одной задаче транспортной логистики. 5-ая Всероссийская зимняя школа-семинар аспирантов и молодых ученых «Актуальные проблемы науки и техники». Уфа. 2010. С. 8184.

13. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир. 1978. 432 с.

14. Мудров В.И. Один способ решения задачи коммивояжера с помощью целочисленного линейного программирования. Журнал вычислительной математики и математической физикию 1963. 6: 1137-1139.

15. Свидетельство о государственной регистрации программы для ЭВМ № 2011615572 «Решение задач транспортной маршрутизации различными методами» в Реестре программ для ЭВМ от 15 июля 2011 г.

16. Ченцов A.A., Ченцов А.Г., Ченцов П. А. Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями. Известия высших учебных заведений. Математика. 2010. 6: 64-81.

17. Aarts E., Korst J. Simulated Annealing and Boltzmann Machines. A stochastic Approach to Combinatorial Optimization and Neural Computing // Chichester: John Wiley and Sons. 1989. 272 pages.

18. Ansari N., Hou E. Computational Intelligence for Optimization. Boston: Kluwer Academic. 1996. 225 pages.

19. Applegate D., Bixby R., Chvatal M., Cook W., Helsgaun K. Optimal Tour of Sweden // The Traveling Salesman. 2010. URL: http://www.tsp.gatech.edu/sweden/index.html (дата обращения 29.10.2013).

20. Archetti С., Hertz A., Speranza M.G. A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science. 2006. 40:64-73.

21. Archetti C., Mansini R., Speranza M.G.. Complexity and reducibility of the skip delivery problem. Transportation Science. 2005. 39: 182-187.

22. Archetti C., Savelsbergh M.W.P., Speranza M.G. An optimization-based heuristic for the split delivery vehicle routing problem. Transportation Science. 2008. 42:22-31.

23. Archetti C., Savelsbergh M.W.P., Speranza M.G. To split or not to split: That is the question. // Transportation Research E. 2008. 44:114-123.

24. Archetti C., Savelsbergh M.W.P., Speranza M.G. Worst-case analysis for split delivery vehicle routing problems.Transportation Science. 2006. 40: 226-234.

25. Archetti C., Speranza M.G. Vehicle routing in the 1-skip collection problem. Journal of the Operational Research Society. 2004. 55:717-727.

26. Baker B.M., Carreto C.A.C. A visual interactive approach to vehicle routing. Computers and Operations Research. 2003. 30:321-337.

27. Baker E.K. An exact algorithm for the time-constrained traveling salesman problem. Operations Research. 1983. 31: 65-73.

28. Baldacci R., Hadjiconstantinou E., Mingozzi A. An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation. Operations Research. 2004. 52: 723-738.

29. Ball M., Bodin L., Baldacci R., Mingozzi A. The rollon-rolloff vehicle routing problem. Transportation Science. 2000. 34: 271-288.

30. Baptiste S., Oliviera R. C., Zuquete E. A period vehicle routing case study. European Journal of Operational Research. 2002. 139:220-229.

31. Barachet L.L. Graphic solution to the traveling-salesman problem. Operations Research. 1957. 5: 841-845.

32. Baralia R., Hildago J.I., Perego R. A Hybrid Heuristic for the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation. 2001. 5(6): 1—41.

33. Beardwood J., Halton J. H., Hammersley J. M. The shortest path through many points. Proceedings of the Cambridge Philosophical Society. 1959. 55: 299-327.

34. Beckmann M., Koopmans T.C. A Note on the Optimal Assignment Problem // Cowles Commission Discussion Paper: Economics 2053. Chicago: Cowles Commission for Researchin Economics. 1952. 12 pages.

35. Belenguer J.M., Mart'inez M.C., Mota E. A lower bound for the split delivery vehicle routing problem. Operations Research. 2000. 48, 801810.

36. Bellman R. Combinatorial processes and dynamic programming. Combinatorial Analysis. Providence: American Mathematical Society. 1960. Pages 217-249.

37. Beltrami E. J., L. D. Bodin. Networks and vehicle routing for municipal waste collection. Networks. 1974. 4:65-94.

38. Berbeglia G., Cordeau J.F. Gribkovskaia I., Laporte G. Static pickup and delivery problems: A classication scheme and survey // TOP. 2007. 15:131.

39. Bertsimas D.J., Chervi P., Peterson M. Computational Approaches to Stochastic Vehicle Routing Problems. Transportation Science. 1995. 29:342-352.

40. Bertsimas D.J., Jaillet P., Odoni A.R. A priori optimization. Operation Research. 1990. 38:1019-1033.

41. Bianco L., Mingozzi A., Ricciardelli S. Exact and heuristic procedures for the traveling salesman problem with precedence constraints, based on dynamic programming. INFOR. 1994. 32:19-31.

42. Birkhoff G. Tres observaciones sobre el algebra lineal. Revista Facultad de Ciencias Exactas // Puras y Aplicadas Universidad Nacional de Tucuman, Serie A (Matematicasy Fisica Teorica). 1946. 5: 147-151.

43. Bock F. An algorithm for solving "travelling-salesman" and related network optimization problems [abstract]. Operations Research. 1958; 6: 897.

44. Bock F. Mathematical programming solution of traveling salesman examples. Recent Advances in Mathematical Programming. New York: McGraw-Hill. 1963. 347 pages.

45. Brandao J. A new tabu search algorithm for the vehicle routing problem with backhauls. European Journal of Operational Research. 2006. 173: 540-555.

46. Bronstein E., Gindullin R. On one class of routing optimization problem. Second Annual Conference of the EURO Working Group of Vehicle Routing and Logistics Optimization (7-10 July 2013, Southhampton, UK). Southhampton. P. 19.

47. Bullnheimer B., Hartl R. F. Strauss C. Applying the Ant System to the Vehicle Routing Problem. Paper presented at 2nd International Conference on Metaheuristics // Sophia-Antipolis. 1997. July 21-24.

48. Burkard R.E., Deineko V.G., van Dal R., van der Veen J.A.A., Woeginger G.J. Well-solvable special cases of the TSP: a survey, SI AM Review. 1998. 40: 496-546.

49. Burkard R.E., Klinz B., Rudolf R. Perspectives of Monge Properties in Optimization. Discrete Applied Mathematics. 1996. 70: 95-161.

50. Campos V., Corberan A., Mota E. A Scatter Search Algorithm for the Split Delivery Vehicle Routing Problem. Studies in Computational Intelligence. 2008. 144: 137-152.

51. Carrabs F., Cordeau J.-F., Laporte G. Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading. INFORMS Journal on Computing. 2007. 19: 618-632.

52. Casco D., Golden B., Wasil E.. Vehicle routing with backhauls: Models, algorithms and case studies. Vehicle Routing: Methods and Studies. Amsterdam: Elsevier Science Publishers. 1988. 127- 147.

53. £elaa E., Deinekob V., Woegingerc G.J. The x-and-y-axes travelling salesman problem. European Journal of Operational Research. 2012. 223: 333-345.

54. Charon I., Hudry O. Applications of the Noising Method to the Traveling Salesman Problem. European Journal of Operational Research. 2000. 125:266-277.

55. Chen S., Golden B., Wasil E. The split delivery vehicle routing problem: Applications, test problems, and computational results // Networks. 2007.49:318-329.

56. Christofides N., Beasley J.E. The period routing problem. Networks. 1984. 14:237-56.

57. Christofides N., Mingozzi A., Toth P. Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxation. Mathematical Programming. 1981. 10:255-280.

58. Christofides N., Mingozzi A., Toth P. The vehicle routing problem. Combinatorial Optimization. Chichester: Wiley. 1979. pp315-338.

59. Clarke G., Wright J. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research. 1964. 12: 568-581.

60. Cordeau J.-F., Gendreàu M., Laporte G. A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks. 1997. 30: 105-119.

61. Cordeau J.-F., Laporte G., Ropke S. Recent models and algorithms for one-to-one pickup and delivery problems // The Vehicle Routing Problem: Latest Advances and New Challenges. Springer. 2008. Pages 327-357.

62. Croes G.A. A method for solving traveling-salesman problems. Operations Research. 1958. 6: 791-812.

63. Cutler M. Efficient special case algorithms for the N-line planar traveling salesman problem. 1980. Networks. 10: 183-195.

64. Dantzig G., Fulkerson R., Johnson S. Solution of a Large Scale Traveling Salesman Problem. Paper P-510. Santa Monica: The RAND Corporation, 1954.

65. Dantzig G.B., Ramser J.H. The Truck Dispatching Problem. Management Science. 1959. 6: 80-91.

66. Deif I., Bodin L. Extension of the Clarke and Wright algorithm for solving the vehicle routing with backhauling. Proceedings of the Babson Conference on Software Uses in Transportation and Logistics Management. 1984. pp. 75-96.

67. Desaulniers G., Desrosiers J., Erdmann A., Solomon M.M., Soumis F. VRP with pickup and delivery. SI AM Monographs on Discrete Mathematics and Applications. 2002. 9: 225-242.

68. Desrochers M., Verhoog T. W. A Matching Based Savings Algorithm for the Vehicle Routing Problem. Les Cahiers du GERAD G-89-04.

r r

Montréal: Ecole des Hautes Etudes Commerciales de Montréal. 1989. 19 pages.

69. Desrosiers J., Dumas Y., Soumis F. A dynamic programming solution of the large-scale single-vehicle dial-a-ride problem with time windows.

American Journal of Mathematical and Management Sciences, 1986. 6:301-325.

70. Diaby M. The salesman traveling problem: a linear programming formulation // WSEAS Transactions on Mathematics 2007. 6: 745-754.

71. Dorigo M. Ant Colonies for the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation. 1997. 1:53-66.

72. Dorigo M. Optimization, Learning and Natural Algorithms. Ph.D. Thesis. Milano: Politécnico di Milano. 1992.

73. Dror M., Laporte G., Trudeau P. Vehicle routing with split deliveries. Discrete Applied Mathematics. 1994. 50: 239-254.

74. Dror M., Trudeau P. Savings by split delivery routing. Transportation Science. 1989. 23: 141-145.

75. Dror M., Trudeau P. Split delivery routing. Naval Research Logistics. 1990. 37: 383-402.

76. Dror M., Trudeau P. Stochastic Vehicle Routing With Modified Savings Algorithm. European Journal of Operational Reserach. 1986. 23:228235.

77. Dueck G., Scheurer T. Threshold Accepting: A General Purpose Optimization Algorithm // Journal of Computational Physics. 1990. 90:161-175.

78. Eastman W.L. Linear programming with pattern constraints. Ph.D. Dissertation. Harvard: Harvard University. 1958.

79. Fejes L. Uber einen geometrischen Satz. Mathematische Zeitschrift. 1940. 46: 83-85.

80. Few L. The shortest path and the shortest road through n points. Mathematika. 1955. 2: 141-144.

81. Fischetti M., Gonzalez J.J.S., Toth P. A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research. 1997. 45: 378-394.

82. Fischetti M., Toth P. An additive bounding procedure for combinatorial optimization problems. Operations Research. 1989. 37:319-328.

83. Fisher M. L., Jaikumar R. A Generalized Assignment Heuristic for Vehicle Routing. Networks. 1981. 11:109-124.

84. Frizzell P.W., Giffin J.W. The split delivery vehicle scheduling problem with time windows and grid network distances. Computers & Operations Research. 1995. 22: 655-667.

85. Fukasawa R., de Aragao M.P., Reis M., Uchoa E. Robust Branch-and-Cut-and-Price for the Vehicle Routing Problem. Relatorios de Pesquisa em Engenharia de Producao RPEP. 2003. 8.

86. Gamboa D., Rego C., Glover F. Data Structures and Ejection Chains for Solving Large-Scale Traveling Salesman Problems. European Journal of Operational Research. 2005. 160:154-171.

87. Gamboa D., Rego C., Glover F. Implementation Analysis of Efficient Heuristic Algorithms for the Traveling Salesman Problem. Computers & Operations Research. 2006. 33:1154-1172.

88. Gavish B. A note on. the formulation of the m-salesman traveling salesman problem. Management Science. 1976. 22: 704-705.

89. Gelinas S., Fabrication de Tournees avec Rechargement. Unpublished Master's Thesis. Montreal: Ecole Polytechnique. 1991.

90. Gendreau M., Dejax P., Feillet D., Gueguen C. Vehicle routing with time windows and split deliveries. Technical Report 851. Avignon: Laboratoire d'Informatique d'Avignon. 2006.

91. Gerards A.M.H. Matching in Network Models. In Handbooks in Operations Research and Management Science. Amsterdam: North-Holland. 1995. Vol. 7. pp. 135-224.

92. Ghosh M. N. Expected travel among random points in a region. Calcutta Statistical Association Bulletin. 1949. 2: 83-87.

93. Giaglis G. M., Minis I., Tatarakis A., Zeimpekis V. Minimizing logistics

risk through real-time vehicle routing and mobile technologies: research

82

to date and future trends. International Journal of Physical Distribution & Logistics Management, 2004. 34:749-764.

94. Gillett B. E., Miller L. R. A Heuristic Algorithm for the Vehicle Dispatch Problem. Operations Research. 1974. 22:340-349.

95. Gillett B.E., Johnson J.G. Multi-terminal vehicle-dispatch algorithm. Omega. 1976.4:711-718.

96. Glover F. A Template for Scatter Search and Path Relinking. Lecture Notes in Computer Science. 1997. 1363: 13-54.

97. Glover F. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research. 1986. 13:533-549.

98. Goetschalckx M., Jacobs-Blecha C. The vehicle routing problem with backhauls. European Journal of Operational Research. 1989. 42: 39-51.

99. Goetschalckx, M., Jacobs-Blecha, C. The vehicle routing problem with backhauls: Properties and solution algorithms. Technical Report MHRC-TR-88-13 // Athlanta: Georgia Institute of Technology. 1993.

100. Goldbarg E.F.G., Souza G.R., Goldbarg M.C. Particle Swarm Optimization for the Traveling Salesman Problem. EVOCOP. 2006. 3906:99-110.

101. Goldberg D. Genetic Algorithms in Search, Optimization, and Machine Learning. New York: Addison Wesley Publishing Company Inc. 1989. 432 pages.

102. Golden B., Baker E., Alfaro J., Schaffer J. The vehicle routing problem with backhauling: Two approaches // Proceedings of the Twenty-first Annual Meeting of S.E. TIMS. Myrtle Beach: S.E. TIMS. 1985. pp. 9092.

103. Golden B.L. and Assad A.A., Vehicle routing: Methods and studies // Studies in Management Science and Systems. Volume 16. Amsterdam: North-Holland. 1988. 7-45.

104. Grotschel M. On the symmetric travelling salesman problem: solution of

a 120-city problem. Mathematical Programming Study. 1980. 12: 61-77.

83

105. Gueguen C. M'ethodes de resolution exacte pour les probr ernes de tourn'ees dev'ehicules. Ph.D. thesis. Paris:'Ecole Centrale. 1999.

106. Hanne L., Decision Support for Planning of Multimodal Transportation with Multiple Objectives, Kongens Lyngby: DTU Transport. 2009. 225 pages.

107. Hannemann M.M., Schwartz A. Implementing weighted b-matching algorithms: Towards a flexible software design // ACM Journal of Experimental Algorithmics. 1999. 4:7.

108. Heller I. Geometric characterization of cyclic permutations. Bulletin of the American Mathematical Society. 1955. 61: 227.

109. Heller I. Neighbor relations on the convex of cyclic permutations. Bulletin of the American Mathematical Society. 1955. 61: 440.

110. Heller I. Neighbor relations on the convex of cyclic permutations. Pacific Journal of Mathematics. 1956. 6: 467-477.

111. Heller I. On the problem of shortest path between points. I // Bulletin of the American Mathematical Society. 1953. 59: 551.

112. Heller I. On the problem of shortest path between points. II // Bulletin of the American Mathematical Society, 1953. 59: 551-552.

113. Heller I. On the travelling salesman's problem. Proceedings of the Second Symposium in Linear Programming. Washington, D.C.: National Bureau of Standards, U.S.Department of Commerce. 1956. Pp.643-665.

114. Hong S. A linear programming approach for the traveling salesman problem. Ph.D. Thesis. Baltimore: The Johns Hopkins University. 1972.

115. Jaillet P. A priori solution of a travelling salesman problem in which a random subset of customers are visited. Operations Research. 1988. 36: 929-936.

116. Jessen R. J. Statistical Investigation of a Sample Survey for Obtaining Farm. Facts Research Bulletin 304. Ames: Iowa State College of Agriculture and Mechanic Arts. 1942.

117. Jin M., Liu K., Bowden R.O. A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem. International Journal of Production Economics. 2007. 105: 228-242.

118. Jonathan F. Bard, Liu Huang, Patrick J., Moshe Dror, A Decomposition Approach to the Inventory Routing Problem with Satellite Facilities. Transportation Science. 1998 . 32: 189-203.

119. Kalantari B., Hill A.V., Arora S.R. An algorithm for the traveling salesman problem with pickup and delivery customers. European Journal of Operational Research. 1985. 22:377-386.

120. Karg R.L., Thompson G.L. A heuristic approach to solving travelling salesman problems. Management Science. 1964. 10: 225-248.

121. Kuhn H.W. On certain convex polyhedra. Bulletin of the American Mathematical Society. 1955. 61: 557-558.

122. Kytojoki J., Nuortio T.; Braysy O., Gendreau M. An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Computers & Operations Research, 2007. 34:2743-2757.

123. Lambert F. The traveling-salesman problem. Cahiers du Centre de Recherche Operationelle. 1960. 2: 180-191.

124. Land A. The solution of some 100-city travelling salesman problems. Technical Report // London: London School of Economics. 1979

125. Landrieu A., Mati Y., and Binder Z. A tabu search heuristic for the single vehicle pickup and delivery problem with time windows. Journal of Intelligent Manufacturing. 2001. 12:497-508

126. Laporte G., Louveau F.' Formulations and Bounds for the Stochastic Capacicated Vehicle Routing Problem With Uncertain Supplies. Report G-87-23, Montreal: Ecole Hautes Etudes Commerciale. 1987.

127. Laporte G., Louveau F., Mercure H. Models and Exact Solutions for a Class of Stochastic Location-Routing Problems. Report G-87-23, Montreal: Ecole Hautes Etudes Commerciale. 1987.

128. Laporte G., Louveaux F.V., Mercure H. Models and exact solutions for a class of stochastic location-routing problems. European Journal of Operational Research. 1989. 39:71-78.

129. Laporte G., Louveaux .F.V., Mercure H. The vehicle routing problem with stochastic travel times. Transportation Science. 1992. 26:161-170.

130. Laporte G., Mercure H., Nobert Y. An exact algorithm for the asymmetrical capacitated vehicle routing problem. Networks. 1986. 16: 33-46.

131. Lawler E.L., Wood D.E. Branch-and-bound methods: a survey // Operations Research. 1966. 14: 699-719.

132. Lee C.G., Epelman M.A., White III C.C., Bozer Y.A. A shortest path approach to the multiple-vehicle routing problem with split pick-ups. Transportation Research B. 2006. 40: 265-284.

133. Li X, Tian P., Hua J., Zhong N. A Hybrid Discrete Particle Swarm Optimization for the Traveling Salesman Problem. SEAL. 2006. 4247:181-188.

134. Lin S. Computer solutions of the traveling salesman problem. The Bell System Technical Journal. 1965. 44: 2245-2269.

135. Little J.D.C., Murty K.G., Sweeney D.W., Karel C. An algorithm for the traveling salesman problem. Operations Research. 1964. 11: 972-989.

136. Liu K. A study on the split delivery vehicle routing problem. PhD thesis, Starkville: Mississippi State University. 2005.

137. M.M. Flood, The traveling-salesman problem, Operations Research 4 61-75

138. Mahalanobis P. C. A sample survey of the acreage under jute in Bengal. Sankhya. 1940.4: 511-530.

139. Malek M., Huruswamy M., Owens H., Pandya M. Serial and parallel search techniques for the traveling salesman problem. Annual Operation Research. 1989.21:59-84.

140.

141,

142.

143,

144,

145,

146,

147

148

149

150

151

152

Marinakis Y., Migdalas A., Pardalos P.M. Expanding Neighborhood GRASP for the Traveling Salesman Problem. Computational Optimization and Applications. 2005. 32:231-257. Marks E. S. A lower bound for the expected travel among m random points. The Annals of Mathematical Statistics. 1948. 19: 419-422. Martin G.T., Solving the traveling salesman problem by integer linear programming. Technical report. //New York: C-E-I-R. 1966. Martinovic G., Aleksi I., Baumgartner A. Single-Commodity Vehicle Routing Problem with Pickup and Delivery Service. Mathematical Problems in Engineering, 2008. 2008: 17 pages.

Matthus F. Tourenplanung - Verfahren zur Einsatzdisposition von Fuhrparks//Darmstadt: S.Toeche-Mittler Verlag. 1978. 244 Seiten. Menger K. Das botenproblem. Ergebnisse eines Mathematischen Kolloquiums. 1932. 2: 11-12.

Menger K. Ein Theorem über die Bogenlänge. Mathematischnaturwissenschaftliche. 1928. 65: 264-266.

Menger K. On shortest polygonal approximations to a curve. Reports of a Mathematical Colloquium. 1940. 2: 33-38.

Menger K. Uber die neue Defnition der Bogenlänge. Mathematischnaturwissenschaftliche. 1929. 66: 23-24.

Meulemeester L. De, Laporte G., Louveaux F.V., Semet F. Optimal sequencing of skip collections and deliveries. Journal of the Operational Research Society. 1997. 48: 57-64.

Milgram A.N. On shortest paths through a set. Reports of a Mathematical Colloquium. 1940. 2:39-44.

Miller C.E., Tucker A.W., Zemlin R.A. Integer programming formulation of traveling salesman problems. Journal of the Association for Computing Machinery. 1960. 7:326-329.

Mladenovic N., Hansen P. Variable Neighborhood Search. Computers & Operations Research. 1997. 24:1097-1100.

153. Morton G., Land A., A contribution to the "travelling-salesman1 problem. Journal of the Royal Statistical Society Series B. 1955. 17: 185-194.

154. Mueller-Merbach H. Drei neue methoden zur losung des travelling salesman problems, teil 1 // Ablauf und Planungsforschung. 1966. 7: 3246.

155. Mueller-Merbach H. Drei neue methoden zur losung des travelling salesman problems, teil 2 // Ablauf und Planungsforschung 1966. 7: 7891.

156. Mueller-Merbach H. Zweimal travelling Salesman. DGOR-Bulletin. 1983. 25:12-13.

157. Mullaseril P.A., Dror M., Leung J. Split-delivery routing in livestock feed distribution. Journal of the Operational Research Society. 1997. 48: 107-116.

158. Norman R.Z. On the convex polyhedra of the symmetric traveling salesman problem. Bulletin of the American Mathematical Society. 1955. 61:559.

159. Nowak M., Ergun O., White C.C. Pickup and delivery with split loads. Submitted for publication. Transportation Science. 2008. 42: 32-43.

160. Nowak M.A. The pickup and delivery problem with split loads. PhDthesis. Atlanta:Georgia Institute of Technology. 2005.

161. Ombuki B., Hanshar F. An effective genetic algorithm for the multidepot vehicle routing problem. Technical report // Ontario: Brock University. 2004.

162. Osman I.H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research. 1993.41:421-451.

163. Pankratz G. A grouping genetic algorithm for the pickup and delivery problem with time windows. Operations Research Spectrum. 2005. 27:21-41.

164. Parragh S., Doerner K., Hartl R. A survey on pickup and delivery problems. Part I: Transportations between customers and depot // Journal fur Betriebswirtschaft. 2008. 58: 21-51.

165. Parragh S., Doerner K., Hartl R. A survey on pickup and delivery problems. Part II: Transportations between customers and depot // Journal fur Betriebswirtschaft. 2008. 58: 21-51.

166. Parragh S.N., Doerner K.F., Hartl R.F. A survey on pickup and delivery models, part I // Journal fur Betriebswirtschaft. 2008. 58: 21-51.

167. Picard J. C., Queyranne M. The time-dependent travelling salesman problem and its application to the tardiness in one-machine scheduling. Operations Research. 1978, V.26, P.86-110.

168. Potvin J.Y. Genetic Algorithms for the Traveling Salesman Problem. Annual Operation Research. 1995. 63:339-370.

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

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

171. Raymond T.C. Heuristic algorithm for the traveling-salesman problem. IBM Journal of Research and Development. 1969. 13:400-407.

172. Reiter S., Sherman G. Discrete optimizing. SIAM Journal on Applied Mathematics. 1965. 13:864-889.

173. Renaud J., Boctor F.F., Laporte G. Perturbation heuristics for the pickup and delivery traveling salesman problem. Computers & Operations Research. 2002. 29:1129-1141.

174. Renaud J., Laporte G., Boctor F. F. A tabu search heuristic for the multidepot vehicle routing problem. Computers & Operations Research. 1996. 23:229-235.

175. Robacker J.T. Some Experiments on the Traveling-Salesman Problem. Research Memorandum RM-1521. Santa Monica: The RAND Corporation. 1955.

176. Roberts S.M., Flores B. An engineering approach to the traveling salesman problem. Management Science. 1966. 13: 269-288.

177. Robinson J. On the Hamiltonian Game (A Traveling Salesman Problem). Research Memorandum RM-303. Santa Monica: The RAND Corporation. 1949. 10 pages.

178. Ronald S. Routing and Scheduling Problems. Practical Handbook of Genetic Algorithms. New York: CRC Press. 1995. Pages 367-430.

179. Rossman M. J., Twery R. J. A solution to the travelling salesman problem by combinatorial programming. Operations Research. 1958. 6:897.

180. Russell R.A., Igo W. An assignment routing problem. Network. 1979. 9: 1-17.

181. Ryan D. M., Hjorring C. and Glover F. Extensions of the Petal Method for Vehicle Routing. Journal of the Operational Research Society. 1993. 44:289-296.

182. Sanders D. On Extreme Circuits, Ph.D. thesis, New York: City University of New York. 1968.

183. Scheuerer S. Neue Tabusuche-Heuristiken fur die logistische Tourenplanung bei restringierendem Anhangereinsatz, mehreren Depots und Planungsperioden // PhD thesis. Regensburg: Universität Regensburg. 2004.

184. Schrijver A. On the History of Combinatorial Optimization (till 1960). Handbooks in Operations Research and Management Science: Discrete Optimization. Amsterdam: Elsevier. 2005. pp. 1-68

185. Shapiro D. Algorithms for the solution of the optimal cost traveling salesman problem. Sc.D. Thesis, St. Louis: Washington University. 1966.

186. Sierksma G., Tijssen G.A. Routing helicopters for crew exchanges on off-shore locations. Annals of Operations Research. 1998. 76: 261-286.

187. Solomon M.M. Algorithms for the Vehicle Routing Problem with Time Windows. Transportation Science. 1995. 29:156-166.

188. Solomon M.M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research. 1987. 35: 254-265.

189. Stewart W.RJr., Golden B.L. Stochastic vehicle routing: A comprehensive approach // European Journal of Operational Research. 1983. 14:371-385.

190. Taillard E.D. Parallel iterative search methods for vehicle routing problems. Networks. 1993. 23:661-673.

191. Tan C.C.R., Beasley J. E. A heuristic algorithm for the period vehicle routing problem. Omega. 1984. 12:497-504.

192. Teodorovic D., Pavkovic G. A simulated annealing technique approach to the vehicle routing problem in the case of stochastic demand. Transportation Planning and Technology. 1992. 16:261-273.

193. Thanghia S.R., Salhi S. Genetic clustering: An adaptive heuristic for the multidepot vehicle routing problem // Applied Artificial Intelligence. 2001. 15:361-383.

194. Thangiah S. R., Nygard K. E., Juell P. L. Gideon: A genetic algorithm system for vehicle routing with time windows // Proceedings of the Seventh Conference on Artificial Intelligence Applications. Miami: IEEE Computer Society Press. 1991. Pages 322-325.

195. Thangiah S.R. Vehicle Routing with Time Windows using Genetic Algorithms. Technical Report SRU-CpSc-TR-93-23. Slippery Rock: Computer Science Department, Slippery Rock University. 1993.

196. Thompson P. M., Psaraftis H. N. Cyclic Transfer Algorithms for the Multivehicle Routing and Scheduling Problems. Operations Research. 1993.41:935-946.

197. Tillman F.A. The multiple terminal delivery problem with probabilistic demands. Transportation Science. 1969. 3:192-204.

198. Van Breedam A. An Analysis of the Behavior of Heuristics for the Vehicle Routing Problem for a Selection of Problems with Vehicle-Related, Customer-Related, and Time-Related Constraints. Ph.D. dissertation // Antwerp:University of Antwerp. 1994

199. Van der Brüggen L.J.J., Lenstra J.K., Schuur P.C. Variable-depth search for the single-vehicle pickup and delivery problem with time windows. Transportation Science. 1993. 27:298-311.

200. Verblunsky S. On the shortest path through a number of points. Proceedings of the American Mathematical Society. 1951. 2: 904-913.

201. Weuthen H.-K. Tourenplanung - Losungsverfahren fur Mehrdepot -Probleme // PhD thesis. Universität Karlsruhe TH. 1983.

202. Wilck IV J., Cavalier T. A Construction Heuristic for the Split Delivery Vehicle Routing Problem. American Journal of Operations Research. 2012. 2: 153-162.

203. Willard J.A.G. Vehicle routing using r-optimal tabu search. MSc thesis. London: Management School, Imperial College. 1989.

204. Wren A. and Holliday A. Computer scheduling of vehicles from one or more depots to a number of delivery points. Journal of the Operational Research Society. 1972. 23:333-344.

205. Xie M., Miyawaki T., De Jong K.A. Solving the Multi-Depot Vehicle Routing Problem using Ant Colony Optimization and Re-Assignment // Applied Simulation and Modelling / 777: Artificial Intelligence and Soft Computing, June 25 - 27, 2012, Napoli. Calgary: ACTA Press. 2012. 777-007.

206. Yano C.A., Chan T.J., Richter L., Culter T., Murty K.G., McGettigan D. Vehicle Routing at Quality Stores. Interfaces. 1987. 17: 52-63.