Вступ. 
Завдання маршрутизації транспортних засобів з обмеженнями замовників (Site-DependentVehicleRoutingProblem, SDVRP)

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

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

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

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

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

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

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

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

Задачи:

• · Разработать эвристический алгоритм решения SDVRP
• · Создать программу, использующую разработанный алгоритм
• · Протестировать программу на примерах с целью проверки качества найденного решения

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