Отправьте статью сегодня! Журнал выйдет 12 июля, печатный экземпляр отправим 16 июля
Опубликовать статью

Молодой учёный

Задача адресной перевозки с временными окнами

Математика
05.07.2020
162
Поделиться
Библиографическое описание
Кулагина, С. А. Задача адресной перевозки с временными окнами / С. А. Кулагина, Ю. В. Скородумова, А. А. Иванова. — Текст : непосредственный // Молодой ученый. — 2020. — № 27 (317). — С. 12-16. — URL: https://moluch.ru/archive/317/72389/.


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

Ключевые слова: задача адресной перевозки, муравьиный алгоритм.

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

Постановка задачи. В данной работе рассматривается задача с одним транспортным средством, которое начинает и заканчивает свой маршрут в депо. Транспортное средство не может выполнять несколько заказов одновременно, то есть забирать людей “по дороге”. Перевозка осуществляется по заранее известным запросам, включающим следующие данные: 1) координаты отправления и прибытия, 2) временные окна на вывоз или доставку (то есть максимальное и минимальное время начала и окончания поездки), 3) время на обслуживание клиента до и после поездки (если клиенту требуется дополнительное время, чтобы сесть в машину или загрузить багаж).

Математическая постановка. Задачу адресной перевозки можно задать на графе G=(N, A) , где N — множество вершин: P={ 1 ,…,n} и D={n+ 1 ,…, 2 n} — вершины отправления и прибытия соответственно, {0} — вершина, обозначающая депо, в котором изначально находятся все транспортные средства, а A — множество ребер. Каждый маршрут клиента i начинается в вершине и заканчивается в вершине . Кроме того, для каждой вершины известно время c i на обслуживание клиента перед или после поездки и временное окно [ e i , l i ]. Для каждой дуги известно время t ij пути по ней.

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

Целевая функция (1) минимизирует общую стоимость маршрута, которая в данном случае является временем. Ограничения (2), (3) и (4) гарантируют, что все маршруты транспортного средства начинаются и заканчиваются в депо. Условия (5) и (6) устанавливают, что каждый заказ будет выполнен один раз, и транспортное средство переместится из вершины отправления в соответствующую ей вершину доставки. Ограничения на время прибытия в следующую вершину маршрута B i задано в неравенстве (7). Условие (8) ограничивает время прибытия минимальным и максимальным временем начала обслуживания вершины. Наконец, в условии (9) полагаем, что x ij =1, если транспортное средство переместилось из вершины i в вершину j , и x ij =0 в ином случае.

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

  1. Инициализация параметров.
  2. Расстановка муравьев по вершинам в случайном порядке.
  3. for t = 1 to t_max do
  4. for k = 1 to m do
  5. for i = 1 to n — 1 do
  6. применение стратегии выбора пути;
  7. обновление феромонов;
  8. поиск лучшего маршрута;
  9. Вывод глобально лучшего маршрута.

Здесь t_max — заранее заданное число повторов основной части алгоритма (или жизненный цикл муравьиной колонии), m — количество муравьев в колонии, n — количество вершин в графе.

Есть несколько стратегий выбора пути ─ Ant System (AS) [1], Ant Colony System (ACS) [2] и Modified Ant Colony System (M — ACS). Применяя данные стратегии, муравьи опираются на следующую информацию — количество феромона ij на ребре ( i, j ), видимость ij вершины j и список посещенных вершин tabu_list.

AS : ,

ACS :

M - ACS :

Также существуют различные способы вычисления видимости вершины. В данной работе рассмотрены несколько подходов, учитывающих временные окна. Для удобства обозначим их как ANT_TIME 1 [3], ANT_TIME 2 [4] и ANT_TIME 3 [5].

ANT-TIME 1

ANT-TIME 2

,

ANT-TIME 3

Для решения поставленной задачи использовались алгоритмы ANT_TIME 1, ANT_TIME 2 и ANT_TIME 3 в связке с каждой из стратегий выбора пути AS, ACS и M-ACS. Стоит отметить, что подходы ANT_TIME 2 и ANT_TIME 3 впервые использовались для решения задачи адресной перевозки.

Алгоритмы были реализованы на языке Python. Данные о вершинах и разметка вершин на точки отправления и доставки брались из тестовых примеров, размещенных в сети Интернет [6]. Временные окна генерировались случайным образом.

Алгоритмы были реализованы с использованием следующих значений параметров: n = 41 - количество вершин графа, m = 20 — количество муравьев в колонии, α = 1, β = 1, γ = 1 — параметры, отвечающие за влияние концентрации феромона и видимости на вероятность перехода, Q = 1 — количество феромонов, ω = 0.5 — параметр локального испарения феромона, ρ = 0.6 - параметр глобального испарения, σ = 0.01, λ = 0.01 — параметры для вычисления эвристик, q0 = 0.7 — параметр для выбора правила для перехода в следующую вершину в стратегиях ACS и M-ACS, ν = 60 — скорость, t max = 20 — жизненный цикл муравьиной колонии.

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

Таблица 1

Результаты работы алгоритмов на графе с 41 вершиной

Алгоритм

Стратегия

Лучшее время маршрута

Среднее время маршрута

Среднее время вычислений

Среднее кол-во заказов

Кол-во успешных туров

ANT — TIME 1

AS

27.36762871

30.00670987

0.05981349

11.64

0

ACS

24.33553884

27.66034498

0.08169099

13.6

0

M-ACS

24.66516612

27.85776373

0.05200895

12.79

0

ANT — TIME 2

AS

24.58951634

25.70720050

0.32875761

15.8556

1

ACS

23.86681285

24.98715482

0.35313985

15.15

3

M-ACS

25.77217115

25.35720826

0.20443104

14.55

1

ANT — TIME 3

AS

26.23591265

26.89348178

0.43719965

10.54

0

ACS

24.65265292

27.00833381

0.48515794

14.18

5

M-ACS

23.92085032

27.54231113

0.44881124

17.57

39

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

С помощью алгоритмов ANT-TIME 2 и ANT-TIME 3 удалось построить маршруты, удовлетворяющие всем ограничениям. Лучшее время маршрута, построенного алгоритмом ANT-TIME 2, было найдено с использованием стратегии ACS. То же можно сказать и о количестве успешных туров.

В алгоритме ANT-TIME 3 использовались эвристики, направленные на строгое соблюдение временных окон, этим объясняется достаточно большое количество успешных туров. При этом использование стратегии M-ACS позволило достичь лучших результатов как по времени лучшего маршрута, так и по количеству успешных маршрутов. В то же время ANT-TIME 3 требует наибольшего времени вычисления.

Таким образом, наилучшие результаты по значению целевой функции и времени работы показал алгоритм ANT-TIME 2 с использованием стратегии ACS, а количество успешных туров — алгоритм ANT-TIME 3 в связке со стратегиями M-ACS.

Алгоритмы ANT-TIME 2 ACS и ANT-TIME 3 M-ACS, показавшие наилучшие результаты, были дополнительно рассмотрены на графе со 101 вершиной (50 запросов на перевозку). Результаты представлены в таблице 2.

Таблица 2

Результаты работы алгоритмов на графе со 101 вершиной

Имя файла данных

Алгоритм

Лучшее время маршрута

Макс. кол-во заказов

Среднее время маршрута

Среднее кол-во заказов

Среднее время вычислений

1P1

ANT-TIME 2

52.29623731

49

52.29623731

33.43

4.81587873

ANT-TIME 3

61.00058275

50

67.09935076

14.18

11.08235990

2P1

ANT-TIME 2

49.90624517

49

52.12220228

35.02

5.99185033

ANT-TIME 3

64.44667793

50

67.22705415

32.74

10.53928622

3P1

ANT-TIME 2

52.03960973

49

52.61987721

34.46

7.99570506

ANT-TIME 3

58.85601463

50

67.25229198

31.1

10.55909965

4P1

ANT-TIME 2

50.46140168

50

51.57021183

38.78

4.52485980

ANT-TIME 3

59.75183647

50

63.02709233

28.88

7.97703070

5P1

ANT-TIME 2

52.82012369

50

51.76323587

38.79

4.57656121

ANT-TIME 3

58.03609214

50

62.79899191

28.49

7.01111531

Для трех тестовых наборов ANT-TIME 2 ACS не смог построить маршруты с соблюдением всех ограничений, в то время как ANT-TIME 3

M-ACS построил 1–3 успешных тура для каждого из пяти наборов данных. Однако, для наборов 4P1 и 5P1, в которых удалось обслужить всех клиентов, ANT-TIME 2 ACS показал лучшее время маршрута. Кроме того, ANT-TIME 2 ACS позволил включить в маршрут в среднем большее количество клиентов. Стоит также отметить, что время работы алгоритма ANT-TIME 2 ACS на используемых данных в среднем в 1.7 раз меньше времени работы ANT-TIME 3 M-ACS.

Заключение. В данной работе была рассмотрена статическая задача адресной перевозки с временными окнами и одним транспортным средством. В качестве основного метода решения был выбран алгоритм муравьиной колонии. По результатам исследования выявлены алгоритмы, строящие маршрут с наибольшим количеством обслуженных заказов — ANT-TIME 2 и ANT-TIME 3. Кроме того, для каждого из алгоритмов найдена стратегия перехода, с помощью которой можно получить наилучшее значение целевой функции. Сравнение этих алгоритмов на тестовых данных большей размерности позволило определить метод, позволяющий получить лучшее время маршрута. Таким алгоритмом является ANT-TIME 2 со стратегией ACS.

Литература:

  1. Colorni A., Dorigo M., Maniezzo V. Distributed optimization by ant colonies // European Conference on Artificial Life, 1991.
  2. Dorigo M. Gambardella L. M. Ant colony system: a cooperative learning approach to the traveling salesman problem // IEEE Transactions on Evolutionary Computation, 1997. Vol. 1, No 1, P. 53─66.
  3. Tripathy T., Nagavarapu S. C., Azizian K., Pandi R. R., Dauwels J. Solving dial-a-ride problems using multiple ant colony system with fleet size minimisation // Advances in Computational Intelligence Systems, 2017. P. 325─336.
  4. Baran B. and Schaerer M. A multiobjective ant colony system for vehicle routing problem with time windows // The 21st IASTED International Multi-Conference on Applied Informatics, 2003. P. 97─102.
  5. Cheng C. B., Mao C. P. A modified ant colony system for solving the traveling salesman problem with time windows // Mathematical and Computer Modeling, 2007. Vol. 46. P. 1225─1235.
  6. The VRP Web [Электронный ресурс]. URL: http://www.bernabe.dorronsoro.es/vrp/ (дата обращения: 10.01.2020).
Можно быстро и просто опубликовать свою научную статью в журнале «Молодой Ученый». Сразу предоставляем препринт и справку о публикации.
Опубликовать статью
Ключевые слова
задача адресной перевозки
муравьиный алгоритм
Молодой учёный №27 (317) июль 2020 г.
Скачать часть журнала с этой статьей(стр. 12-16):
Часть 1 (стр. 1-79)
Расположение в файле:
стр. 1стр. 12-16стр. 79

Молодой учёный