Задача адресной перевозки с временными окнами | Статья в журнале «Молодой ученый»

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

Опубликовать статью в журнале

Библиографическое описание:

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



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

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

Введение. Темой данной работы является задача адресной перевозки (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).
Основные термины (генерируются автоматически): ANT-TIME, ACS, M-ACS, адресная перевозка, транспортное средство, TIME, ANT, муравьиная колония, алгоритм, лучшее время маршрута.


Ключевые слова

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

Похожие статьи

Организация системы транспортной логистики путем...

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

Для построения наиболее оптимального маршрута система пользуется алгоритмом муравьиной колонии.

Роевой интеллект и его наиболее распространённые методы...

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

Динамическая адаптация эвристического алгоритма для задачи...

Маршрут транспортного средства делится на два этапа.

Пусть A будет постоянное время для подготовки транспортного средства, а B — время для разгрузки

В среднем, маршрут для каждого транспортного средства, сгенерированный при помощи алгоритма Iterated Local...

Применение системы «ГЛОНАСС» на автомобильном транспорте...

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

Автоматизация проектирования маршрутов обхода...

В настоящее время не существует методов получения точного решения за время

2. Метод колонии муравьев. Идею метода, не используя бионические термины, можно представить

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

Применение бионических принципов в проектировании...

Необходимо построить маршрутов транспортных средств минимальной суммарной

Существует множество алгоритмов для решения задачи транспортной маршрутизации

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

Методы и алгоритмы эффективного решения задачи...

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

Выбор оптимального маршрута грузоперевозок автомобильным...

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

Задача теории расписаний с временем поступления и временем...

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

Реактивный алгоритм динамической маршрутизации...

Ткачев, Д. Ф. Реактивный алгоритм динамической маршрутизации в перспективной мобильной сети, построенной на

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

Похожие статьи

Организация системы транспортной логистики путем...

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

Для построения наиболее оптимального маршрута система пользуется алгоритмом муравьиной колонии.

Роевой интеллект и его наиболее распространённые методы...

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

Динамическая адаптация эвристического алгоритма для задачи...

Маршрут транспортного средства делится на два этапа.

Пусть A будет постоянное время для подготовки транспортного средства, а B — время для разгрузки

В среднем, маршрут для каждого транспортного средства, сгенерированный при помощи алгоритма Iterated Local...

Применение системы «ГЛОНАСС» на автомобильном транспорте...

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

Автоматизация проектирования маршрутов обхода...

В настоящее время не существует методов получения точного решения за время

2. Метод колонии муравьев. Идею метода, не используя бионические термины, можно представить

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

Применение бионических принципов в проектировании...

Необходимо построить маршрутов транспортных средств минимальной суммарной

Существует множество алгоритмов для решения задачи транспортной маршрутизации

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

Методы и алгоритмы эффективного решения задачи...

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

Выбор оптимального маршрута грузоперевозок автомобильным...

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

Задача теории расписаний с временем поступления и временем...

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

Реактивный алгоритм динамической маршрутизации...

Ткачев, Д. Ф. Реактивный алгоритм динамической маршрутизации в перспективной мобильной сети, построенной на

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

Задать вопрос