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

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

Оглавление

• Введение
• Описание задачи
• Математическая модель задачи
• Описание алгоритма
• Библиографическийсписок


Введение

Проблема маршрутизации автотранспорта (VehicleRoutingProblems, VRP) является фундаментальной в области задач комбинаторной оптимизации с широким спектром применения в практике. Впервые задачу сформулировали Джордж Данциг и Джон Рамсер в 1959 году, но наибольшее развитие она получила в последние 10 лет. Сейчас уже доказано, что задача маршрутизации транспорта и различные её вариации относятся к классу NP-сложных задач, кроме того,были показаны вычислительные сложностинекоторых из этих задач ^[6].

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

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

Одной из первых работ, посвящённых задаче маршрутизации транспортных средств с ограничениями заказчиков, является подход, предложенный Ай-МингЧао в 1998 ^[1]. Автор разделилзадачу на два шага: решить задачу о назначениях и улучшить полученное начальное решениепутем перемещения вершин из разных маршрутов. В своей статье автор также представил математические модели для обоих шагов.

Основываясь на математических моделях, Дэвид Писинджер и СтэфанРобке смогли перевести задачу маршрутизации в другие задачи линейной оптимизации, и испытали на них уже известные алгоритмы [5].

В 2002 году Гилберт Лапорте^[3]показал, что метаэвристика под названием табу поиск может быть эффективно применена для различных вариаций задачи маршрутизации транспорта. В своей работе автор предложил две стратегии для улучшения решения в табу поиске: менять местами две вершины в разных маршрутах и запрещать изменять определенный маршрут полностью.

Примерно в это же время Ай-МингЧао предложил свой алгоритм с использованием табу поиска^[2]. Кроме вышеописанных стратегий автор разрешил совершать недопустимые шаги, т.е. назначать машинам заказчиков, которых данные транспортные средства обслуживать не могут.

Целью настоящей работы является рассмотрение задачи маршрутизации транспортных средств с ограничениями заказчиков (Site-DependentVehicleRoutingProblem, SDVRP) и разработка алгоритма поиска наилучшего решения с помощью мета-эвристики поиска с запретами (tabu-search).

Задачи:

· Разработать эвристический алгоритм решения SDVRP

· Создать программу, использующую разработанный алгоритм

· Протестировать программу на примерах с целью проверки качества найденного решения

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

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

маршрутизация автотранспорт поиск

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

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

Рис.1. Различные представление задачиVRPв виде графа

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

Математическая модель задачи

Пусть - множество всех вершин; - вершина-склад, в которой построенные маршруты должны начинаться и заканчиваться; - множество из n целевых вершин для посещения;- множество вершин, которые могут быть обслужены k-м ТС; - множество вершин, которых запрещено обслуживать k-му ТС; - стоимость переезда между вершинами ; K - количество транспортных средств(ТС); - грузоподъёмность k-го ТС; - величина потребности узла (= 0); - переменная, представляющая собой загрузку k-готранспортногосредства после посещения узла i,

,

.

Тогда можно построить следующую систему ограничений:

Ограничения (1)-(3) задают следующие условия: каждая вершина обслуживается только одним транспортным средством; используется ровно Kтранспортных средств; если ТС посетило вершину, оно должно её покинуть. Условие (4) не дает вершинам, запрещенным к обслуживанию k-ой ТС, быть обслуженными. Условие (5) задает ограничения по грузоподъёмности различных транспортных средств, условие (6) - загрузку k-го ТС после посещения вершины i.

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

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

Данный алгоритм использует принципы мета-эвристики, называемой табу поиском (tabu-search). Процедуру построения пути можно разделить на две части: 1) Используя жадный алгоритм, построить начальное решение; 2) Улучшить начальное решения, используя табу поиск.

Обозначения, используемые в процедуре построения начального решения:

Routes - список путей, для всех транспортных средств, v₀ - начальная вершина(склад), V' - множество всех вершин, исключая склад.

Процедура построения начального решения:

1)Routes =Ш

2)route = Ш

3)Для каждой машины выполнять:

4)V_k = V'

5)route =v₀

6)Найти самую удаленную вершину v_kиз V_kот v₀

7)V_k = V_k \ v_k

8) Если данное ТС сможет вместить груз v_k то:

9)route < v_k

10) Иначе перейти к шагу 6.

11)Повторять пока V_k != Шили пока машина не заполнится полностью:

12)Найти вершиныv_i1, v_i2,v_i3, v_i4из V_k -наиболее близкиекv_k

13) Из этих четырех вершин равновероятно выбирается одна v_i.

14) V_k = V_k \ v_i

15)Если данное ТС сможет вместить груз v_i,то:

16)route < v_i

17)v_k = v_i

18) добавить груз вершины к текущему грузу машины

19)route < v₀

20)Routes < route

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

Стоит заметить, что полученное решение может быть недопустимым, так как некоторые вершины могут не попасть ни в один из построенных маршрутов, либо оказаться в маршрутах транспортных средств, которые не могут обслуживать данных заказчиков, поэтому вводится дополнительное обозначение: penalty = штраф*(количество незадействованных вершин). Значение штрафа выбирается достаточно большим. Если начальное решение является допустимым, то penalty = 0.

Результирующее значение F считается как длина всех маршрутов плюс значение переменной penalty.

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

Обозначения:

Duration - длительность запрета; tabu_list - список запрещенных изменений, в котором хранятся пары (вершина, сосед). Наличие в списке запретов пары (v_i, -1) означает, что вершина v_i не может быть исключена из всех маршрутов на данной итерации.

Для улучшения найденного пути есть 4 стратегии:

I. Swap - поменять местами две вершины из разных путей

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

III. Insert - убрать одну вершину из своего пути и добавить ее в более выгодное, не запрещенное место в другом пути

IV. badInsert- добавить одну незадействованную вершину в наиболее

маршрутизация автотранспорт поиск

Рис.2 Операция Insert

Процедура локального поиска:

Повторять, пока изменения происходили хотя бы один раз за итерацию:

1) Выбрать ту стратегию (2,7,11,15), которая имеет лучше всех остальных изменяет значение функции F

2) Если существует «незанятая» вершина v_i, которую можно добавить в маршрут k

3) Выполнить операцию badInsertдля вершины v_i в путьk

4) Добавить в tabu_list пару (v_i, -1)

5)penalty = penalty - штраф;

6) Пересчитать F

7) Если существует вершина i в маршруте k, которую можно переместить в маршрут m, причем F уменьшится:

8) Выполнить операцию Insertдля вершиныi в m

9) Добавить в tabu_listнужные пары

10) Пересчитать F

11) Если существует вершина i в маршруте k и вершина j в маршрутеm, причем при их обмене маршрутами значениеF уменьшается:

12)Поменять местами вершины i и j

13) Добавить в tabu_listнужные пары

14) Пересчитать F

15) Если существует вершина i в маршруте k и «незанятая» вершина j, причем при их обмене положением значение F уменьшается:

16) Поменять местами вершины i и j

17) Добавить в tabu_listсоответствующие пары запретов

18) Пересчитать F

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

Проводимые эксперименты.

Для проверки полученной программы использовались модулируемые данные, основу для которых составили входные данные для задачи Capacitated Vehicle Routing Problem. Для проверки, использовались данные, для которых уже найдено точное решение. Исходные данные изменялись в соответствии с условиями задачи, т.е. к ним для каждого заказчика добавлялись новые ограничения на типы машин, которые могут его обслуживать, но делалось это с учетом, что найденное точное решение так останется верным и при условии новых ограничений.

Заключение

В данной работе мною были рассмотрены задачи маршрутизации транспортных средств с ограничениями заказчиков (Site-Dependent Vehicle Routing Problem, SDVRP). Кроме того, я разработал эвристический алгоритм на основе табу поиска для поиска решения подобных задач. Мною были предложены несколько операций улучшения решения, а также в этом подходе были разрешены как недопустимые перемещения вершин из путей в пути, так и исключение заказчика из всех путей на время, и способ выхода из недопустимого решения. Полученный алгоритм был реализован на языке С++(11) и протестирован на известных примерах.

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

[1] I-Ming Chao: A New Algorithm For The Site-Dependent Vehicle Problem. Kluwer Academic Publisher, 301-312,1998

[2] I-Ming Chao, Tian-Shy Liou: A New Tabu Search Heuristic For The Site-Dependent Vehicle Routing Problem. Springer US puplisher, 107-119,2005

[3] Jean-FranёcoisCordeau, Gilbert Laporte: Tabu Search Heuristics for the Vehicle Routing Problem. Springer US publisher, 145-163, 2005.

[4] Gilbert Laporte,Moccia L.,Cordeau J.-F.: An Incremental Tabu-Search Heuristic for the Generalized Vehicle Routing Problem. Journal of Operational Research Society, 232-244,2012

[5] David Pisinger and Stefan Ropke: A General Heuristic for Vehicle Routing Problems. Journal Computers and Operations Research 2403-2435,2007

[6] C. Archetti, D. Feillet, M. Gendreau, and M. Speranza, “Complexity of the VRP and SDVRP,” Transportation Part C, pp. 1-10, 2010.

Размещено на Allbest.ru