Сущность проблемы маршрутизации автотранспорта. Разработка алгоритма поиска наилучшего решения задач маршрутизации с ограничениями заказчиков с помощью мета-эвристики поиска с запретами. Различные представление задачи Vehicle Routing Problem в виде графа.
Аннотация к работе
Сейчас уже доказано, что задача маршрутизации транспорта и различные ее вариации относятся к классу NP-сложных задач, кроме того,были показаны вычислительные сложностинекоторых из этих задач [6]. Автор разделилзадачу на два шага: решить задачу о назначениях и улучшить полученное начальное решениепутем перемещения вершин из разных маршрутов. В данной работе мною предложены несколько стратегий улучшения решения в табу поиске, например, перемещение одного заказчика в другой маршрут и «обмен» двумя заказчиками маршрутами. Пусть - множество всех вершин; - вершина-склад, в которой построенные маршруты должны начинаться и заканчиваться; - множество из n целевых вершин для посещения; - множество вершин, которые могут быть обслужены k-м ТС; - множество вершин, которых запрещено обслуживать k-му ТС; - стоимость переезда между вершинами ; K - количество транспортных средств(ТС); - грузоподъемность k-го ТС; - величина потребности узла (= 0); - переменная, представляющая собой загрузку k-готранспортногосредства после посещения узла i, , . Тогда можно построить следующую систему ограничений: Ограничения (1)-(3) задают следующие условия: каждая вершина обслуживается только одним транспортным средством; используется ровно Ктранспортных средств; если ТС посетило вершину, оно должно ее покинуть.В данной работе мною были рассмотрены задачи маршрутизации транспортных средств с ограничениями заказчиков (Site-Dependent Vehicle Routing Problem, SDVRP).
План
Оглавление
Введение
Описание задачи
Математическая модель задачи
Описание алгоритма
Библиографическийсписок
Введение
Вывод
В данной работе мною были рассмотрены задачи маршрутизации транспортных средств с ограничениями заказчиков (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.