Размещено на http://www.allbest.ru/

Правительство Российской Федерации

Нижегородский филиал

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Национальный исследовательский университет

«Высшая школа экономики»

Факультет информатики, математики и компьютерных наук

Кафедра прикладной математики и информатики

ДИПЛОМНАЯ РАБОТА

На тему: «Алгоритмы для решения прикладной задачи маршрутизации транспорта»

Студента группы 14 ПМИ

Гревцова Сергея Валерьевича

Научный руководитель

к.ф-м.н. Бацын Михаил Владимирович

Нижний Новгород, 2018

Введение

Объект исследования.

Задача взвешенной маршрутизации транспорта (Capacitated Vehicle Routing Problem, CVRP) является классической задачей логистики, которая решается на графах. Задача определяется следующим образом. Есть транспортная сеть(дорог) со складом, набор вершин (магазинов или чего-то подобного), куда нужно что-либо доставить со склада, а также некоторое количество транспорта чтобы обслужить магазины. Необходимо вычислить набор маршрутов, начинающихся и заканчивающихся на складе, так чтобы:(1) спрос вершины был удовлетворён одним единственным транспортом, (2) общий спрос, которые обслуживает транспортное средство, не превышал его вместимости, (3) сумма расстояний, пройденных всеми транспортами была минимальна.

Практическая значимость и актуальность

На транспортировку товаров во все времена тратилось много сил, времени и иных человечески и материальных ресурсов. В цену товара всегда заложена в том числе его транспортировка, т.е. минимизируя цену и потери от транспортировки мы тем самым влияем на конечную цену товара, которая влияет на материальное состояние и качество жизни потребителя. Данная проблема одним из первых была исследована Labbeetal.1 Ими было показано что проблема TCVRPявляется NP-сложной. Этим и обусловлена сложность и значимость исследований в данном направлении.

Цель и задачи исследования

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

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

Для достижения цели были сформулированы следующие задачи.

· Ознакомление с ранее разработанными алгоритмами для решения данной задачи

· Разработка собственного эвристического алгоритма, отличного от ранее представленных

· Реализация алгоритма средствами программирования

· Получение репрезентативных результатов работы алгоритма

транспортный дерево маршрут граф

Обзор литературы

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

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

Rennie2(1995) улучшил предыдущий описанный алгоритм. Вместо прекращения слияние при превышении вместимости он поднимается вверх по дереву к корню пока наконец не найдёт (или не найдёт) подходящую для слияние вершину.

Basnetetal.3 (1999) разработал две эвристики для TCVRP. Первая, именуемая H1, основана на эвристике, разработанной Clarkeand Wright4(1964a). Метод сначала строит по отдельному маршруту для каждой точки, после чего комбинирует те маршруты, которые в данный момент дадут наибольший выигрыш по сокращению дистанции. Вторая, H2, начинает с создания одного маршрута сразу по всем вершинам, после чего разбивает маршрут для соблюдения условия вместимости. Также Basnetetal.3 (1999) сравнили свои алгоритмы с другими, представленными выше, выяснилось, что H1 работает значительно дольше других, но и конечный результат даёт лучше.

Hamaguchiand Katoh 4 (1998) разработали 1.5-приближенный алгоритм для TCVRP. Принимается что спрос в каждой вершине меньше единицы. Используется концепция D-feasibleи D-minimal вершин. В дополнение утверждается что любое поддерево может быть разбито на такие поддеревья, что общий спрос без одной вершины меньше единицы, а с этой вершиной больше или равен единице. После нахождения D-minimalиспользуются отношения, представленные в первоисточнике, для выбора одной из двух стратегий. Первая использует два транспорта для облуживания двух поддеревьев D-minimalподдерева. Вторая разбивает один маршрут так, что сумма спроса одной из его частей и неразбитого дерева была равна ровно единице, после чего также использует два транспорта.

Asanoatal.5(2001) разработали 1.35078-приближенный алгоритм для TCVRP. В нём используются те же концепты D-feasibilityи D-minimality, однако D-feasibilityподвергся изменению. Также в алгоритме используется семь перестраивающих дерево операций, которые не уменьшают лучший возможный результат. После чего используются методы из предыдущей рассмотренной работы. В конце применяется ещё одна новая стратегия.

Представленный в данной работе алгоритм заимствует некоторые идеи из представленных выше, однако лишь малую их часть. За основу был взят начальных подход эвристики H1, представленной Basnetetal.3 (1999). Однако маршруты строятся не для всех вершин, а только для листов, после чего используются слияния смежных маршрутов и добавления вершин выше по дереву. Алгоритм является видом жадной эвристики. В алгоритме также используется «параллельная» обработка маршрутов, каждый раз берётся маршрут, у которого кратчайшая дистанция до ближайшей точки маршрута максимальна среди прочих маршрутов, так как при обработке именно таких маршрутов достигается наибольшей выигрыш по общей пройденной дистанции. Под выигрышем здесь и далее будет подразумеваться сокращение общей пройденной транспортами дистанцией, если не указано что-то иное. Так как простейшие вычисления позволяют понять, что слияние двух удалённых маршрутов даёт весомый выигрыш, в случае успеха, а добавление предыдущей точки в маршрут лишь не увеличивает общей дистанции, то было решено сперва пытаться сливать маршруты с наиболее смежными маршрутами (под смежными понимаются маршруты, имеющие общие точки на пути следования с текущим). После чего обрабатываются отдельно незадействованные ни одним маршрутом вершины и применяется локальный поиск. Подробнее будет описано далее в работе.

Описание задачи

Мат модель

T={N,E) - связныйграф

|N| = n - мощностьN

|E| = m - мощность E

m = n - 1

Tне содержит циклов, является деревом

N - набор вершин

E = {(v1,v2)} - набор двунаправленных рёбер

c{i,j} = длина ребра {i,j}

di = вес(спрос) вершины

Cap - вместимость каждого транспорта (одно значение для всех)

vrx= [] - маршрут (vehicleroute) транспортаx

VR = [vr1,…,vrn] - все наборымаршрутов

Distx= дистанция, проходимая при обслуживании маршрута x

VR

· Спрос одной вершины обслуживается лишь одним транспортом

· Общая сумма дистанций всех транспортных средств минимальна

Описание алгоритма

Инициализация.

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

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

Веса рёбер берутся по эвклидовой метрике между точками. Спрос по аналогии с координатами и в последствии с весами рёбер, задаётся случайно.

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

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

Итерация

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

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

Было проверено два подхода. Первый: независимо от успеха или неудачи маршруты вновь сортируются для выявления наиболее отдалённого, после чего уже работа ведётся с ним и так далее. Второй: работа с текущим маршрутом ведётся до его изменения или невозможности любых изменений.

Завершение работы

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

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

Пример

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

Пусть Cap = 10

id, путь, полный путь, общая дистанция, взятые вершины, общий товар, проверенные и не подошедшие вершины, проверенные и не подошедшие маршруты, filled state, дистанция до самой дальней от депо непроверенной точки

-id : маршрут, с которым работает

Этап 0.

1, [1,2,3,4,5], [1,2,3,4,5,4,3,2,1], 2*(5+4+2+8)=38, [5], 3, [], [], false, 11

2, [1,2,6,7], [1,2,6,7,6,2,1], 2*(5+3+6)=28, [7], 8, [], [], false, 8

3, [1,8,9], [1,8,9,8,1], 2*(7+9)=32, [9], 9, [], [], false, 7

taken by tree: [1,5,7,9]

Этап 1.

-1, [1,2,3,4,5], [1,2,3,4,5,4,3,2,1], 2*(5+4+2+8)=38, [5], 3, [], [2], false, 11

2, [1,2,6,7], [1,2,6,7,6,2,1], 2*(5+3+6)=28, [7], 8, [], [1], false, 8

3, [1,8,9], [1,8,9,8,1], 2*(7+9)=32, [9], 9, [], [], false, 7

taken by tree: [1,5,7,9]

Этап 2.

-1, [1,2,3,4,5], [1,2,3,4,5,4,3,2,1], 2*(5+4+2+8)=38, [5,4], 3+4=7, [], [2], false, 9

2, [1,2,6,7], [1,2,6,7,6,2,1], 2*(5+3+6)=28, [7], 8, [], [1], false, 8

3, [1,8,9], [1,8,9,8,1], 2*(7+9)=32, [9], 9, [], [], false, 7

taken by tree: [1,5,7,9,4]

Этап 3.

-1, [1,2,3,4,5], [1,2,3,4,5,4,3,2,1], 2*(5+4+2+8)=38, [5,4], 3+4=7, [3], [2], false, 5

2, [1,2,6,7], [1,2,6,7,6,2,1], 2*(5+3+6)=28, [7], 8, [], [1], false, 8

3, [1,8,9], [1,8,9,8,1], 2*(7+9)=32, [9], 9, [], [], false, 7

taken by tree: [1,5,7,9,4]

Этап 4.

1, [1,2,3,4,5], [1,2,3,4,5,4,3,2,1], 2*(5+4+2+8)=38, [5,4], 3+4=7, [3], [2], false, 5

-2, [1,2,6,7], [1,2,6,7,6,2,1], 2*(5+3+6)=28, [7,6], 8+1=9, [], [1], false, 5

3, [1,8,9], [1,8,9,8,1], 2*(7+9)=32, [9], 9, [], [], false, 7

taken by tree: [1,5,7,9,4,6]

Этап 5.

1, [1,2,3,4,5], [1,2,3,4,5,4,3,2,1], 2*(5+4+2+8)=38, [5,4], 3+4=7, [3], [2], false, 5

2, [1,2,6,7], [1,2,6,7,6,2,1], 2*(5+3+6)=28, [7,6], 8+1=9, [], [1], false, 5

-3, [1,8,9], [1,8,9,8,1], 2*(7+9)=32, [9], 9, [8], [], true, 0

taken by tree: [1,5,7,9,4,6]

Этап 6.

-1, [1,2,3,4,5], [1,2,3,4,5,4,3,2,1], 2*(5+4+2+8)=38, [5,4,2], 3+4+3=10, [3], [2], true, 0

2, [1,2,6,7], [1,2,6,7,6,2,1], 2*(5+3+6)=28, [7,6], 8+1=9, [], [1], false, 5

3, [1,8,9], [1,8,9,8,1], 2*(7+9)=32, [9], 9, [8], [], true, 0

taken by tree: [1,5,7,9,4,6,2]

Этап 7.

1, [1,2,3,4,5], [1,2,3,4,5,4,3,2,1], 2*(5+4+2+8)=38, [5,4,2], 3+4+3=10, [3], [2], true, 0

-2, [1,2,6,7], [1,2,6,7,6,2,1], 2*(5+3+6)=28, [7,6], 8+1=9, [], [1], true, 0

3, [1,8,9], [1,8,9,8,1], 2*(7+9)=32, [9], 9, [8], [], true, 0

tree taken: [1,5,7,9,4,6,2]

Этап 8.

1, [1,2,3,4,5], [1,2,3,4,5,4,3,2,1], 2*(5+4+2+8)=38, [5,4,2], 3+4+3=10, [3], [2], true, 0

2, [1,2,6,7], [1,2,6,7,6,2,1], 2*(5+3+6)=28, [7,6], 8+1=9, [], [1], true, 0

3, [1,8,9], [1,8,9,8,1], 2*(7+9)=32, [9], 9, [8], [], true, 0

-4, [1,2,3], [1,2,3,2,1], 2*(5+4)=18, [3], 6, [], [1], true, 0

-5, [1,8], [1,8,1], 2*(7)=14, [8], 4, [], [3], true, 0

taken by tree: [1,5,7,9,4,6,2,3,8]

total dist = 38+28+32+18+14=70+28+18+14=70+30+20+10=100+30=130

Результаты

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

1) С пересортировкой

По времени работы 1

Число вершин	min	max	average
10	0.009459495544433594	0.01850724220275879	0.012527024745941162
20	0.07102417945861816	0.15105009078979492	0.09845775365829468
30	0.23407697677612305	0.5381796360015869	0.3563802599906921
40	0.6287097930908203	2.4089138507843018	1.113991379737854
50	1.3164699077606201	14.221323013305664	3.5877544403076174
60	2.5849196910858154	12.929954290390015	5.94044439792633
70	5.868994235992432	17.215938091278076	9.78295921087265
80	8.387910604476929	41.85054922103882	19.637101793289183
90	11.57103967666626	87.51419043540955	27.610056936740875
100	21.078017950057983	137.05416750907898	46.019426989555356

По дистанции 1

Число вершин	min	max	average
10	1.0	2.288135593220339	1.2661432155450723
20	1.0844099913867356	1.6837606837606838	1.4092784640569185
30	1.0618489583333333	1.8469635627530365	1.339779290150432
40	1.061398521887436	2.081525804038893	1.3758490198581264
50	1.026121521862578	2.5638297872340425	1.4486457950231615
60	1.0159310524941239	2.144995322731525	1.4615469847831062
70	1.14679186228482	1.8755401901469317	1.433251880070896
80	1.0879199428162973	2.0103950103950106	1.435896552132356
90	1.0144410768407917	2.2674563591022445	1.4320375276026591
100	1.0853715350570696	1.6771004942339374	1.3744082555504884

По времени работы 2

Числе вершин	min	max	average
10	0.010001182556152344	0.01700592041015625	0.012527978420257569
20	0.0610203742980957	0.18257617950439453	0.09743616580963135
30	0.21408557891845703	1.0814344882965088	0.358159601688385
40	0.5632257461547852	3.946850538253784	0.9992257833480835
50	1.4631168842315674	5.48567795753479	2.778642737865448
60	2.861859083175659	11.800071716308594	5.347563099861145
70	4.200141429901123	28.335801362991333	9.980088984966278
80	7.592424392700195	23.969468116760254	14.040029859542846
90	14.511544227600098	117.107351064682	39.09848688840866
100	16.447499990463257	287.7070150375366	58.85284916162491

По дистанции 2

Число вершин	min	max	average
10	1.0	1.8571428571428572	1.3017813651726189
20	1.0	1.5442875481386393	1.3048135619607073
30	1.0268551236749117	2.041988003427592	1.3204424653069182
40	1.0460691036554832	1.8007915567282322	1.381729685542873
50	1.1304717382065448	1.7868357487922706	1.4230139099833505
60	1.082687338501292	2.08018154311649	1.3712705935111353
70	1.0854936569222284	2.837748344370861	1.416456039209249
80	1.094824016563147	1.7326279668287103	1.3290694464402837
90	1.1058909891723252	2.1752854264607118	1.527212868339603
100	1.0305628028326501	2.598151848151848	1.4436994279536506

2) Без пересортировки

По времени работы 1

Число вершин	min	max	average
10	0.008500814437866211	0.016505956649780273	0.01177884340286255
20	0.06001996994018555	0.14005327224731445	0.0913077712059021
30	0.22907614707946777	0.4136364459991455	0.29980993270874023
40	0.5896956920623779	0.9488162994384766	0.6704939246177674
50	1.230909824371338	2.1042017936706543	1.5078877329826355
60	2.4648470878601074	4.299524307250977	2.9617971062660216
70	4.210960149765015	10.401612281799316	5.51760311126709
80	6.73482346534729	17.250618934631348	8.95126485824585
90	10.133190155029297	18.163665533065796	12.694964849948883
100	16.126083374023438	23.298141479492188	18.97441495656967

По дистанции 1

Число вершин	min	max	average
10	1.0	2.183381088825215	1.3279369578862057
20	1.047872340425532	1.6788617886178863	1.3969801208872707
30	1.0323668240053945	2.2489795918367346	1.3944796072558003
40	1.0839398350315381	1.8524464831804281	1.3255087353389388
50	1.0446175637393769	2.098684210526316	1.357674003994062
60	1.0800902425267906	1.830547818012999	1.3409041383582416
70	1.0605125771238728	2.420309050772627	1.4940627260699368
80	1.0140782122905028	2.605474561142517	1.505143977823913
90	1.031456953642384	1.7456949569495694	1.3429484506309701
100	1.018016581632653	1.6433816607041989	1.3016721795847064

По времени работы 2

Число вершин	min	max	average
10	0.009503841400146484	0.023007631301879883	0.012979340553283692
20	0.06602263450622559	0.11603760719299316	0.08355629444122314
30	0.23908114433288574	0.5301761627197266	0.3060801148414612
40	0.5961987972259521	1.003889560699463	0.7519622683525086
50	1.268423080444336	2.0961992740631104	1.549552059173584
60	2.4432411193847656	5.672220468521118	2.983863055706024
70	4.126861333847046	7.503121614456177	5.404492390155792
80	7.040019750595093	13.927533864974976	8.77237137556076
90	10.36286211013794	19.798405170440674	13.192953670024872
100	15.76520824432373	24.103680849075317	19.002488481998444

По дистанции 2

Число вершин	min	max	average
10	1.0	1.9285714285714286	1.3107680555501298
20	1.0	1.9458333333333333	1.3683374950479859
30	1.0275562001450327	2.122593718338399	1.404998291144715
40	1.0023866348448687	2.3088109495295126	1.400724565112434
50	1.0568720379146919	1.8181818181818181	1.3773227251779652
60	1.0082401412595645	3.048293963254593	1.3676754642953528
70	1.0566254670882438	2.072363636363636	1.5009255220900488
80	1.1174232817651535	1.673954829408938	1.299842784088064
90	1.0977506580521657	2.034592304977056	1.3974318783486193
100	1.067625458996328	1.8589206505667817	1.3876536855697494

Выводы

Оригинальный алгоритм был разработан и реализован средствами программирования на языке Python(3.6.2), его работоспособность была проверена и подтверждена экспериментами. Поставленные задачи были выполнены, результаты работы и программный код представлены в данной работе.

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

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

1. Labbe M, Laporte G and Mercure H. (1991). Capacitated vehicle routing on trees. Opns Res 39: 616-622.

2. Rennie, S., 1995. Optimal Dispatching and Routing of Milk Tanker for Northland Dairy Board. In: 30th Annual Conference of the Operational Research Society of New Zealand. ORSNZ: Wellington, New Zealand, pp. 95-102.

3. Basnet, C., Foulds, L., Wilson, J., 1999. Heuristics for Vehicle Routing onTree-like Networks. Journal of the Operational Research Society 50, 627-635.

4. Hamaguchi, S., Katoh, N., 1998. A Capacitated Vehicle Routing Problem on a Tree. Algorithms and Computation 1533, 399-407.

5. Asano, T., Katoh, N., Kawashima, K., 2001. A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree. Journal of Combinatorial Optimization 5 (2), 213-231.

6. Turner WG, Ghare PM and Foulds LR. (1974). Transportation routing problem: a survey. AIIE Trans 6: 288-301.

7. Watson-Gandy CDC and Foulds LR. (1981). Vehicle scheduling: a survey. New Zealand Opl Res 9: 73-92.

8. Basnet C, Clark DN and Foulds LR. (1993). A decision support system approach to vehicle routing. Control and Cybernetics22: 131-144.

9. Laporte G and Norbert Y. (1987). Exact algorithms for the vehicle routing problem. In: Martello S, Laporte G, Minoux M and Ribeiro C (eds). Surveys in Combinatorial Optimization.North-Holland: Amsterdam, 147-184.

10. Golden BL and Assad AA. (1988) Vehicle Routing: Methods and Studies. North-Holland: Amsterdam.

11. Foulds LR. (1998). Graph Theory Applications, 3rd Printing. Springer-Verlag: New York.

12. Clarke G and Wright JW. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Opns Res 12: 568-581.

Приложение

Листинг кода

importoperator

import copy

import random

import time

global debug

debug = False

class Node: # done

def __init__(self, n_id=1, n_demand=0, n_lvl=0):

self.id = int(n_id)

self.demand = int(n_demand)

self.lvl = n_lvl

class Veh_route: # done

def __init__(self, id=0, way=[]):

self.id = id

self.way = way

self.way_with_way_back = way

self.cap = 10

self.goods = 0

self.distance = 0

self.nodes_to_take = []

self.counted_nodes = []

self.failed_to_merge_routs_id = set()

self.failed_to_add_vertexes_id = set()

self.filled = False

def add_way_back_to_root(self, tree):

global debug

new_way = self.way.copy()

way_back = go_for_BFS(tree, self.way[-1], 1)[0][1:] # to exclude last node counts twice

if debug: print("way back in way back func: ", way_back)

for n in way_back:

new_way.append(n)

self.way_with_way_back = new_way

def valuate_route(self, tree):

global debug

if debug: print("** [veluate route]->start")

if debug: print("way before valuate: ", self.way)

self.add_way_back_to_root(tree)

if debug: print("way with way back: ", self.way_with_way_back)

counted_dist = 0

counted_goods = 0

f_f = True

n_from = 0

n_to = 0

for n in self.way_with_way_back:

if n in self.nodes_to_take:

if n not in self.counted_nodes:

counted_goods += get_node_by_id(tree.nodes, n).demand

self.counted_nodes.append(n)

if n_from == 0:

n_from = n

if f_f:

f_f = False

continue

if debug: print("node from: ", n_from)

n_to = n

if debug: print("node to: ", n_to)

arc_weight = get_arc_weight(tree, n_from, n_to)

if arc_weight == None: arc_weight = 0

if debug: print("arc weight: ", arc_weight)

counted_dist += arc_weight

n_from = n_to

self.distance = counted_dist

self.goods += counted_goods

if debug: print("** [veluate route]->finish")

def take_node(self, node_id):

global debug

if node_id in self.way:

if node_id in self.counted_nodes:

if debug: print("node already taken and counted")

else:

if node_id in self.nodes_to_take:

if debug: print("already taken")

else:

self.nodes_to_take.append(node_id)

return True

else:

if debug: print("no such node id in way, can't add")

return False

def sort_way(self, nodes):

self.way = self.__sort_by_lvl(nodes)

def __sort_by_lvl(self, nodes):

way_with_lvls = {}

for id in self.way:

node = get_node_by_id(nodes, id)

way_with_lvls[id] = node.lvl

sorted_way = (sorted(way_with_lvls.items(), key=operator.itemgetter(1)))

new_way = []

for elem in sorted_way:

new_way.append(elem[0])

# print (new_way)

return new_way

# print ("sort by lvl tbd")

def get_commons(way_one, way_two):

global debug

taken_n_id = None

f_f = True

commons = []

for n_id in way_one:

if f_f:

if n_id in way_two:

taken_n_id = n_id

else:

if debug: print("no common vertices at all. error")

return commons

f_f = False

continue # skip roote vertex

if n_id not in way_two:

return commons

else:

commons.append(n_id)

return commons

# not need for now

def take_last_common(way_one, way_two):

global debug

taken_n_id = None

f_f = True

for n_id in way_one:

if f_f:

if n_id in way_two:

taken_n_id = n_id

else:

if debug: print("no common vertices at all. error")

return taken_n_id

f_f = False

continue

if n_id not in way_two:

return taken_n_id

else:

taken_n_id = n_id

return taken_n_id

def get_max_or_min_route_lvl_node(way, nodes, max=True):

f_f = True

taken_lvl = None

taken_node_id = None

for n_id in way:

cur_lvl = get_node_by_id(nodes, n_id).lvl

if f_f:

taken_node_id = n_id

taken_lvl = cur_lvl

f_f = False

continue

if max and cur_lvl > taken_lvl:

taken_lvl = cur_lvl

taken_node_id = n_id

if not max and cur_lvl < taken_lvl:

taken_lvl = cur_lvl

taken_node_id = n_id

return taken_node_id

def shuffle_route(tree, route):

global debug

nodes_to_take = set()

min_node = get_max_or_min_route_lvl_node(route.way, tree.nodes, max=False)

max_node = get_max_or_min_route_lvl_node(route.way, tree.nodes, max=True)

one_way = go_for_BFS(tree, min_node, max_node)[0]

for n_id in route.way:

if n_id not in one_way:

nodes_to_take.add(n_id)

if debug:

print(one_way)

print(nodes_to_take)

print(len(nodes_to_take))

while len(nodes_to_take) > 0:

another_max_node = get_max_or_min_route_lvl_node(nodes_to_take, tree.nodes, max=True)

another_way = go_for_BFS(tree, max_node, another_max_node)[0][1:]

max_node = another_max_node

if debug: print(one_way)

for n_id in another_way:

one_way.append(n_id)

if n_id in nodes_to_take:

nodes_to_take.remove(n_id)

if debug:

print(another_way)

print(one_way)

def get_most_far_not_checked(route, tree):

global debug

if debug: print("**[get_most_far_not_check]->start")

if debug: print("route.id: ", route.id, "route.way: ", route.way, "route.nodes_to_take: ", route.nodes_to_take,

"route.failed_to_add_vertexes_id: ", route.failed_to_add_vertexes_id, "tree.served_nodes_id: ",

tree.served_nodes_id)

not_checked = list_minus_list(

list_minus_list(list_minus_list(route.way, route.nodes_to_take), route.failed_to_add_vertexes_id),

tree.served_nodes_id)

if debug: print("not checked: ", not_checked)

for_sorting = {}

for n_id in not_checked:

cur_way = go_for_BFS(tree, 1, n_id)[0]

for_sorting[n_id] = count_one_dir_distance(cur_way, tree)

for_sorting = sorted(for_sorting.items(), key=operator.itemgetter(1), reverse=True)

if debug: print("**[get_most_far_not_check]->finish")

if len(for_sorting) > 0:

if debug:

print("print (for_sorting[0][0]): ", for_sorting[0][0])

return for_sorting[0][0]

else:

return None

# updated

def try_to_add_new_node(route, tree, n_id):

global debug

if debug: print("**[try_to_add_new_node]->start")

if debug: print("before add: ", route.way)

if n_id in route.counted_nodes:

if debug: print('already counted, no need to go twice')

if debug: print("**[try_to_add_new_node]->finish")

return route

copied_route = copy.deepcopy(route)

if not n_id in route.way:

new_part_way = go_for_BFS(tree, route.way[-1], n_id)[0]

if debug: print("want to add: ", new_part_way)

new_part_way = new_part_way[1:] # cut first cos it's counter already

if debug: print("cutted: ", new_part_way)

for n in new_part_way:

route.way.append(n)

route.take_node(n_id)

if debug: print("new way:", route.way)

if debug: print("goods before", route.goods)

route.valuate_route(tree)

if debug: print("goods after", route.goods)

if route.cap < route.goods:

route = copied_route

route.failed_to_add_vertexes_id.add(n_id)

if debug: print("overcap")

else:

tree.served_nodes_id.add(n_id)

if debug: print("**[try_to_add_new_node]->finish")

return route

# refacted 2

def add_most_far_single(route, tree):

global debug

changed_route = copy.deepcopy(route)

changed_tree = copy.deepcopy(tree)

most_far_id = get_most_far_not_checked(changed_route, tree)

if debug: print("most far id: ", most_far_id)

if most_far_id == None or most_far_id == 1:

if debug: print("cant add prev vertex")

return route, tree, most_far_id, False

if changed_route.goods + get_node_by_id(tree.nodes, most_far_id).demand <= changed_route.cap:

route = try_to_add_new_node(changed_route, changed_tree, most_far_id)

tree = changed_tree

if debug: print(" ")

return route, tree, most_far_id, True

else:

if debug: print("cant add cos of violating capacity restrictions. taking old one")

if debug: print("goods for now: ", changed_route.goods, "demand of new vertex: ",

get_node_by_id(tree.nodes, most_far_id).demand, "capacity: ", changed_route.cap)

if debug: print("cant add prev vertex")

return route, tree, most_far_id, False

def count_one_dir_distance(way, tree):

counted_dist = 0

f_f = True

n_from = 0

n_to = 0

for n in way:

if n_from == 0:

n_from = n

if f_f:

f_f = False

continue

n_to = n

arc_weight = get_arc_weight(tree, n_from, n_to)

counted_dist += arc_weight

n_from = n_to

return counted_dist

def get_truly_most_near_distance_from_depot(route, tree):

global debug

new_way = []

ways = {}

if debug: print("route id: ", route.id)

for n in route.nodes_to_take:

new_way = go_for_BFS(tree, 1, n)[0]

ways[count_one_dir_distance(new_way, tree)] = new_way

if debug:

print('way before sorting')

print(ways)

ways = (sorted(ways.items(), key=operator.itemgetter(0)))

if debug:

print("way after sorting")

print(ways)

return ways[0][0]

def get_route_by_id(routes, id):

global debug

if debug: print("routes: ", routes)

for r in routes:

if r.id == id:

return r

if debug: print("can't find route with that id")

return None

def sort_routes_in_decrease_order_of_distance_from_depot(routes, tree):

global debug

routes_with_dist = {}

for route in routes:

if debug: print("print (vars(route)): ", vars(route))

routes_with_dist[route.id] = get_truly_most_near_distance_from_depot(route, tree)

ways = (sorted(routes_with_dist.items(), key=operator.itemgetter(1), reverse=True))

return ways

class Arc: # done

def __init__(self, node_from, node_to, a_weight=0):

self.from_id = node_from

self.to_id = node_to

self.weight = a_weight

class Tree: # done

def __init__(self):

self.arcs = []

self.nodes = []

self.matr = None

self.served_nodes_id = set()

def get_node_by_id(nodes, id):

for n in nodes:

if n.id == id:

return n

return None

def check_leaf(the_tree, node_id): # done

for arc in the_tree.arcs:

if node_id == arc.from_id:

return False

return True

def get_all_leafs(the_tree): # done

leafs = []

for node in the_tree.nodes:

if check_leaf(the_tree, node.id):

leafs.append(node.id)

return leafs

def get_parent(the_tree, node_id): # done

for arc in the_tree.arcs:

if node_id == arc.to_id:

return arc.from_id

return 0

def get_childs(the_tree, node_id): # done

childs_id = []

for arc in the_tree.arcs:

if node_id == arc.from_id:

childs_id.append(arc.to_id)

return childs_id

def get_arc_weight(the_tree, from_node, to_node): # done

for arc in the_tree.arcs:

if (arc.from_id == from_node and arc.to_id == to_node) or (arc.to_id == from_node and arc.from_id == to_node):

return arc.weight

# for BFS

def get_nearest_nodes(the_tree, node_id):

nearest_nodes = []

parent = get_parent(the_tree, node_id)

if not parent == 0:

nearest_nodes.append(parent)

if not check_leaf(the_tree, node_id):

childs = get_childs(the_tree, node_id)

for c in childs:

nearest_nodes.append(c)

return nearest_nodes

# for BFS

def get_nearest_for_all(the_tree):

nearests = {}

for node in the_tree.nodes:

nearests[node.id] = get_nearest_nodes(the_tree, node.id)

return nearests

def go_for_BFS(the_tree, from_node, to_node):

nearests_for_all = get_nearest_for_all(the_tree)

if the_tree.matr == None:

graph = make_graph(the_tree)

else:

graph = the_tree.matr

p = BFS(from_node, to_node, nearests_for_all, graph)

return p

def BFS(from_node, to_node, nearests, matr=[[]]):

queue = []

checked = {}

d = {}

p = {}

path = []

queue.append(from_node)

checked[from_node] = True

p[from_node] = -1

while (not len(queue) == 0):

v = queue.pop()

for to in nearests[v]:

if not to in checked:

checked[to] = True

queue.append(to)

try:

d[to] = d[v] + 1

except:

d[v] = 0

d[to] = d[v] + 1

p[to] = v

if to_node == None or not checked[to_node]:

print("no path")

else:

v = to_node

while not v == -1:

path.append(v)

v = p[v]

path = reverse_list(path)

return path, p, checked

# don't need for now

def make_way_to_every_node_from_root(the_tree):

routes = {}

id = 0

for node in the_tree.nodes:

node_id = node.id

if node_id == 1:

continue

new_route = Veh_route(id)

way = [node_id]

distance = 0

goods = node.demand

while 1:

new_node_id = get_parent(the_tree, node_id)

distance += get_arc_weight(the_tree, node_id, new_node_id)

if new_node_id == 1:

way = reverse_list(way)

break

goods += get_node_by_id(the_tree, new_node_id).demand

way.append(new_node_id)

node_id = new_node_id

new_route.way = way

new_route.distance = distance

new_route.goods = goods

id += 1

routes[id] = new_route

return routes

def make_way_to_every_leaf_from_root(the_tree): # done

global debug

if the_tree.matr == None:

make_graph(the_tree)

routes = {}

id = 0

for node in the_tree.nodes:

if not check_leaf(the_tree, node.id):

continue

node_id = node.id

the_tree.served_nodes_id.add(node_id)

if debug: print("node id: ", node_id)

if node_id == 1:

continue

way = go_for_BFS(the_tree, 1, node_id)

if debug: print("way: ", way)

routes[id] = way

id += 1

if debug: print("routes:", routes)

return routes

def reverse_list(list): # done

result = []

for l in reversed(list):

result.append(l)

return result

def make_graph(the_tree):

graph = {}

for arc in the_tree.arcs:

graph[(arc.from_id, arc.to_id)] = True

graph[(arc.to_id, arc.from_id)] = True

return graph

def valuate_after_route_to_leafs(routes, tree):

global debug

Veh_routes = []

for r_id in routes:

if debug: print("route id: ", r_id, " route: ", routes[r_id][0])

route_to_add = Veh_route(r_id, routes[r_id][0])

route_to_add.take_node(route_to_add.way[-1])

tree.served_nodes_id.add(route_to_add.way[-1]) # ?

Veh_routes.append(route_to_add)

for r in Veh_routes:

if debug: print("_____________")

r.sort_way(tree.nodes)

if debug: print("r id:", r.id, "way", r.way)

r.valuate_route(tree)

if debug:

print("distance: ", r.distance)

print("goods: ", r.goods)

return Veh_routes

# POINT BLOCK START

class Point:

def __init__(self, x=0, y=0, id=0, taken=False):

self.id = id

self.x = x

self.y = y

self.taken = taken

def evklid_dist(self, point2):

return (pow(self.x - point2.x, 2) + pow(self.y - point2.y, 2)) ** (0.5)

def generate_points(amount=1):

global debug

points = {}

for i in range(2, amount + 2):

new_point = Point(x=random.randint(0, 100), y=random.randint(0, 100), id=i)

points[i] = new_point

if debug: print("i:", i, "new_point.x: ", new_point.x, "new_point.y: ", new_point.y)

if debug: print("len(points): ", len(points))

return points

def sort_points_by_evklid_from_depot(points):

dict_for_sorting = {}

for p_id in points:

if p_id == 1:

continue

dict_for_sorting[p_id] = points[p_id].evklid_dist(points[1])

dict_for_sorting = (sorted(dict_for_sorting.items(), key=operator.itemgetter(1)))

result = []

for elem in dict_for_sorting:

result.append(elem[0])

return result

def get_closest_point(point, points, if_taken=False):

closest_id = None

closest_dist = None

f_f = True

for p_id in points:

p = points[p_id]

if if_taken and not p.taken:

continue

cur_dist = point.evklid_dist(p)

if f_f:

f_f = False

closest_id = p.id

closest_dist = cur_dist

continue

if cur_dist < closest_dist:

cur_dist = closest_dist

closest_id = p.id

return closest_id, closest_dist

def get_medium_point(points):

global debug

med_x = None

med_y = None

for p_id in points:

p = points[p_id]

if not med_x and not med_y:

med_x = p.x

med_y = p.y

continue

med_x += p.x

med_y += p.y

med_x /= len(points)

med_y /= len(points)

if debug: print("med_x: ", med_x, "med_y: ", med_y)

med_point_id = get_closest_point(Point(med_x, med_y), points)[0]

med_point = points[med_point_id]

if debug: print("med_point.x", med_point.x, "med_point.y", med_point.y)

med_point.taken = True

old_id = med_point.id

med_point.id = 1

points[1] = med_point

points.pop(old_id)

return med_point

def validate_lvls(tree):

global debug

depot_id = 1

for node in tree.nodes:

node_id = node.id

if node_id == 1:

continue

way = go_for_BFS(tree, node_id, depot_id)[0]

node.lvl = len(way) - 1

if debug: print("node id: ", node.id, "way: ", way, "lvl: ", node.lvl)

def make_tree(amount_of_nodes, Cap):

global debug

generated_points = generate_points(amount_of_nodes)

get_medium_point(generated_points)

sorted_by_dist = sort_points_by_evklid_from_depot(generated_points)

the_Tree = Tree()

the_Tree.nodes.append(Node(1, 0, 0))

for p_id in sorted_by_dist:

p = generated_points[p_id]

if p.id == 1:

continue

the_Tree.nodes.append(Node(p.id, random.randint(1, Cap)))

closest_point_id, dist_to_closest_taken = get_closest_point(p, generated_points, if_taken=True)

if debug: print("cur id: ", p.id, "closest point id: ", closest_point_id)

generated_points[closest_point_id].taken = True

the_Tree.arcs.append(Arc(p.id, closest_point_id, int(dist_to_closest_taken)))

p.taken = True

the_Tree.matr = make_graph(the_Tree)

if debug: print("get_node_by_id(the_Tree.nodes,1): ", vars(get_node_by_id(the_Tree.nodes, 1)))

validate_lvls(the_Tree)

normalize_arcs(the_Tree)

return the_Tree

def normalize_arcs(the_tree):

global debug

for arc in the_tree.arcs:

from_id = arc.from_id

to_id = arc.to_id

if get_node_by_id(the_tree.nodes, from_id).lvl > get_node_by_id(the_tree.nodes, to_id).lvl:

if debug: print("before change: ", vars(arc))

from_id = from_id + to_id

to_id = from_id - to_id

from_id = from_id - to_id

arc.to_id = to_id

arc.from_id = from_id

if debug: print("after change: ", vars(arc))

# POINT BLOCK FINISH

def check_demand_before_merge(rout_1, rout_2, tree):

global debug

full_demand = 0

for n_id in rout_1.nodes_to_take:

full_demand += get_node_by_id(tree.nodes, n_id).demand

for n_id in rout_2.nodes_to_take:

if n_id not in rout_1.nodes_to_take:

full_demand += get_node_by_id(tree.nodes, n_id).demand

if full_demand > rout_1.cap: # comment for check

if debug: print("overcap, can't merge two routs. full demand: %s, max demand: %s" % (full_demand, rout_1.cap))

return False

return True

def merge_two_routs(rout_1, rout_2, routes, tree):

global debug

if not check_demand_before_merge(rout_1, rout_2, tree):

return False, rout_1

if rout_1.id <= rout_2.id:

new_id = rout_1.id

else:

new_id = rout_2.id

new_way = copy.deepcopy(rout_1.way)

commons = get_commons(rout_1.way, rout_2.way)

if debug: print("way1: ", rout_1.way, "way2: ", rout_2.way)

f_f = True

for n in rout_2.way:

if n == 1:

continue

if n not in commons:

if f_f:

new_part_way = go_for_BFS(tree, new_way[-1], n)[0][1:]

f_f = False

if debug: print("new_part_way: ", new_part_way)

for n_id in new_part_way:

new_way.append(n_id)

continue

new_way.append(n)

new_rout = Veh_route(new_id, new_way)

for n_id in rout_2.nodes_to_take:

new_rout.take_node(n_id)

for n_id in rout_1.nodes_to_take:

new_rout.take_node(n_id)

new_rout.valuate_route(tree)

for smth in rout_2.failed_to_merge_routs_id:

new_rout.failed_to_merge_routs_id.add(smth)

for smth in rout_2.failed_to_add_vertexes_id:

new_rout.failed_to_add_vertexes_id.add(smth)

for r in routes:

add_flag = False

if rout_1.id in r.failed_to_merge_routs_id:

r.failed_to_merge_routs_id.remove(rout_1.id)

add_flag = True

if rout_2.id in r.failed_to_merge_routs_id:

r.failed_to_merge_routs_id.remove(rout_2.id)

add_flag = True

if add_flag:

r.failed_to_merge_routs_id.add(new_id)

if debug:

for r in routes:

print("id: ", r.id)

if debug:

print("len before pop: ", len(routes))

print(vars(routes[0]))

print(vars(routes[1]))

print(vars(routes[2]))

routes.pop(routes.index(rout_1))

routes.pop(routes.index(rout_2))

if debug: print("len after pop: ", len(routes))

routes.append(new_rout)

for n_id in new_rout.nodes_to_take:

tree.served_nodes_id.add(n_id)

if debug:

print("len after append: ", len(routes))

for r in routes:

print("id: ", r.id)

print(vars(routes[0]))

print(vars(routes[1]))

return True, new_rout

def take_first_not_failed(route, routes_id_to_check):

for r_id in routes_id_to_check:

if r_id not in route.failed_to_merge_routs_id:

return r_id

return None

# not need

def for_debug_of_generated_tree(the_Tree):

global debug

print(vars(the_Tree))

for node in the_Tree.nodes:

print(vars(node))

to_id_count_check = {}

from_id_count_check = {}

for arc in the_Tree.arcs:

try:

to_id_count_check[arc.to_id]

except:

to_id_count_check[arc.to_id] = 0

try:

from_id_count_check[arc.from_id]

except:

from_id_count_check[arc.from_id] = 0

to_id_count_check[arc.to_id] += 1

from_id_count_check[arc.from_id] += 1

print(vars(arc))

if debug: print("print (to_id_count_check): ", to_id_count_check)

if debug: print("print (from_id_count_check): ", from_id_count_check)

if debug:

for smth in from_id_count_check:

if from_id_count_check[smth] > 1:

print(from_id_count_check[smth])

if debug:

for node in the_Tree.nodes:

if not (node.id in to_id_count_check or node.id in from_id_count_check):

print("print (arc.id): ", node.id)

arcs = []

for arc in the_Tree.arcs:

arcs.append((arc.from_id, arc.to_id))

print("len(arcs)", len(arcs))

print("print (arcs): ", arcs)

for arc in arcs:

mirror = (arc[1], arc[0])

if mirror in arcs:

print("HYA SEBE")

print("NODES")

for node in the_Tree.nodes:

print(vars(node))

print("ARCS")

for arc in the_Tree.arcs:

print(vars(arc))

# new one

def step2(cur_route, Veh_routes, the_Tree):

global debug

if debug: print("**[step]->start")

route_id = cur_route.id

if debug: print("cur route id: ", route_id, "cur route way: ", cur_route.way)

most_common_routes_id = get_most_common_routes_id(cur_route, Veh_routes)

if most_common_routes_id == []:

f_1 = True

else:

f_1 = False

res = False

f_2 = False

if len(most_common_rou...