Теоретическое обоснование. 
Задача поиска оптимального плана доставки продукции торгового предприятия

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

Начнем с подробного описания и изучения классической задачи коммивояжера — КЗК («задача странствующего торговца»), поскольку не проанализировав данную задачу, понять более сложную ее модификацию не представляется возможным (Макконнелл, 2004). Отметим, что КЗК представляет собой одну из самых известных математических задач XX века. С экономической точки зрения решением задачи является самый выгодный маршрут, проходящий через указанные города (точки на карте) по одному разу, с возвращением в исходный. В условиях данной задачи традиционно указываются какие-либо критерии оптимальности (наименьшее расстояние или время). Говоря об актуальности исследования задачи, которая появилась в середине ХVIII века, подчеркнем, что с 1959 по 2008 годы около 1 000 научных журналов публиковали статьи про задачу коммивояжера на первых страницах. Более того, научная литература на тему КЗК растет экспоненциально каждый год со скоростью 6% (Baldacci, et al., 2012).

Представим классическую задачу коммивояжера в виде модели на графе. Пусть имеется ориентированный конечный граф в котором N — множество вершин, А — множество ребер (Хайруллин, 2014). Тогда длина ребра будет являться его весом и будет связывать вершины. Граф должен быть полным, поскольку необходимо учесть все возможные ребра. Таким образом, решение задачи коммивояжера — это такой маршрут, который является ориентированным полным остовным циклом (проходит через все вершины) минимального веса (сумма всех расстояний между вершинами) в графовой модели. Предполагается, что переменная является бинарной, то есть принимает значение 1, если ребро графа включено в оптимальный маршрут, проделанный коммивояжером, и 0, если не включено.

Математическая постановка классической задачи коммивояжера выглядит следующим образом:

Подробно постановка задачи будет описана в следующем разделе. КЗК относится к числу трансвычислительных (Irnich, 2008): уже при относительно небольшом числе вершин графа (> 67) ее невозможно решить методом полного перебора маршрутов современным компьютером менее чем за несколько миллиардов лет. Задача имеет экспоненциальную алгоритмическую сложность: коммивояжер в каждом городе встает перед выбором следующего из еще не посещенных, а значит, существует.

маршрутов для асимметричной (расстояние из города i в город j, не равно обратному) задачи, где n — число городов. В настоящем исследовании будут использоваться именно асимметричные матрицы расстояний и времени, что существенно увеличит алгоритмическую сложность. Классическая задача коммивояжера является NP-полной (Костюк, 2013), что означает невозможность решения каким-либо алгоритмом за полиномиальное время. За нахождение такого метода, американское математическое сообщество предлагает приз в миллион долларов, что говорит об огромном интересе к задаче как с теоретической, так и практической точки зрения.

Приведем наиболее значимые работы о КЗК расположив их в хронологическом порядке. Первым упоминанием о классической задаче коммивояжера (traveling salesman problem — TSP) стали труды английских математиков У. Гамильтона и Т. Киркмана в середине ХIХ века.

(Laporte, 1992). В то время авторы не имели необходимых методов для решения задачи и могли сформулировать только вид предполагаемого решения — маршрут коммивояжера, проходящий через каждый город только один раз (необходимо объехать все города без исключения). Описываемый путь торговца получил название гамильтонов цикл. С развитием такого направления науки как комбинаторная оптимизация, исследователи стали придавать задаче коммивояжера теоретический смысл. На основе КЗК были разработаны такие известные методы дискретной оптимизации, как «жадный» алгоритм, метод ветвей и границ, а также ряд современных эвристик (Moon, et al., 2012). Спустя столетие после постановки классической задачи коммивояжера, ее решением занялись американские сотрудники RAND Corporation, в том числе, Д. Фалкерсон. Применив метод ветвей и границ, ученый нашел маршрут для 21 города США и доказал его оптимальность (Toth, Vigo, 2002). В середине 70-х годов ХХ века КЗК активно применялась в биологии, информатике и медицине. Через два десятилетия Д. Апплегейт и У. Кук создали «библиотеку» стандартизированных постановок и модификаций классической задачи коммивояжера — TSPLIB, куда вошли экземпляры, содержащие более 10 000 точек на карте (Applegate, Cook, 1993). В середине 2010 года европейские математики решили КЗК, включающую тысячу вершин. Используя методы кластеризации, удалось доказать, что полученное решение всего на 1% отличается от оптимального (Schneider, et al., 2010).

По данным электронных библиотек, в научной литературе существует более 6 000 исследований, связанных с задачей коммивояжера. Рассмотрим наиболее значимые из них. Кроуз в 1958 году в своей работе продемонстрировал несколько возможных способов упрощения вычислительной сложности задачи (Croes, 1958). Один из них — использование неориентированного графа при построении модели (матрица расстояний — симметрична). Математик обосновал, что симметричную КЗК решать значительно легче по сравнению с асимметричной. Автор показал на практике, что задача с неориентированными дугами графа на практике становится менее реалистичной. Более того, ученый считал, что для упрощения процедуры нахождения оптимального решения, необходимо использовать только линейные условия, добавляя в постановку ограничение элиминирующее подциклы в маршруте коммивояжера (Croes, 1958). Заметим, что преследуя цель нахождения оптимального решения КЗК, на первой итерации необходимо получить допустимое решение. Впоследствии, итеративное улучшение решения, путем ряда перестановок в исходной последовательности городов, приведет к образованию наилучшего решения задачи. Рассмотрим другую немаловажную работу, посвященную решению классической задачи коммивояжера. Лин в 1973 году впервые проанализировал простейший эвристический алгоритм нахождения решения КЗК — «жадный» метод. Автор исследовал вычислительное время задачи и продемонстрировал, что «жадный» алгоритм способен его существенно сократить (Lin, Kernighan, 1973). Подчеркнем, что решение, получаемое в ходе использования «жадного» алгоритма не всегда будет оптимальным, а значит, необходимы дополнительные перестановки в полученной последовательности городов. Переходя к современным статьям о КЗК, отметим, что несмотря на развитие эвристических алгоритмов, многие ученые на протяжении XX века продолжали решать задачу точными методами. Многие ученые были убеждены, что задачу коммивояжера необходимо решать методом ветвей и границ. Заметим, что описываемый алгоритм был популярен в научном сообществе и положил начало большому количеству статей, реализующих его на разном количестве городов (вершин на графе). Метод заключался в разделении множества маршрутов на подмножества, в каждом из которых производился поиск «нижней границы" — кратчайшего маршрута в подмножестве. Наилучший маршрут соединялся из всех «нижних границ» подмножеств (Toth, Vigo, 2002). Осознав необходимость применения задачи на практике, только к концу ХХ века ученые стали решать классическую задачу коммивояжера при помощи приближенных алгоритмов, таких как: алгоритм минимального остовного дерева, локального поиска и др.

Классическая задача коммивояжера решается в логистической практике редко, поскольку ее ограничения не включают, например, моделирование дорожных пробок, маршрутизацию нескольких машин в автопарке и, конечно, временные интервалы доставки покупателям. Поэтому Данциг и Рамсер предложили разновидность КЗК, дополнив задачу ограничением на количество автомобилей и назвав ее задачей маршрутизации транспорта (ЗМТ). В своей статье исследователи поставили вопрос оптимального развоза бензина на автозаправочные станции в городе N, предложив математическую постановку задачи и решив ее эвристическим алгоритмом. Данциг и Рамсер придали ЗМТ следующую форму задачи математического программирования, которая будет анализироваться в следующем разделе работы (Danzig, Ramser, 1959):

Отметим, что с математической точки зрения ЗМТ (6) — (11) отличается от классической задачи коммивояжера (1) — (6), наличием индекса k над переменной, который отвечает за номер транспортного средства в задаче. Несмотря на незначительное нововведение в математическую постановку, алгоритмическая сложность задачи существенно увеличивается.

Через несколько лет после публикации статьи Данцига и Рамсера (1959), Кларк и Райт (1964) улучшили подход американских исследователей, предоставив вниманию математического сообщества алгоритм «сбережений», который был легко применим к решению задачи маршрутизации транспорта и на тот момент являлся одним из передовых, поскольку находил оптимальные маршруты за кратчайшее время. Метод «сбережений» начинает поиск оптимального маршрута с первоначального решения задачи, когда каждому транспортному средству ставится в соответствие единственная случайная точка на карте (количество автомобилей равно количеству вершин графа). На каждой последующей итерации алгоритм пытается так уменьшить количество машин (путем объединения двух случайных маршрутов), что «сбережения» (сокращение общей длины или времени маршрута) были максимальными. Кларк и Райт (1964) впервые предложили проводить оптимизацию маршрутов, решая ЗМТ как последовательно, так и параллельно, доказав, что одновременный выезд автомобилей из начальной точки приводит к более эффективному решению задачи (Clarke, Wright, 1964). Вышеупомянутая статья имела огромный успех, что и привлекло ученых из разных стран к анализу как постановок, так и алгоритмов касающихся стандартной задачи маршрутизации транспорта (обобщение задачи коммивояжера без усложнений и дополнительных ограничений).

Существенное внимание в первых работах о ЗМТ уделялось вычислительной сложности задачи. Так, Кан и Ленстра (1975) определили масштаб и характер задачи маршрутизации транспорта с математической точки зрения, описав новые алгоритмы решения ЗМТ, связывающие точные и эвристические методы. Авторы доказали, что задача маршрутизации транспорта является NP-сложной (как и задача коммивояжера), что говорит о ее неразрешимости за полиномиальное время (Kan, Lenstra, 1975). Тем не менее, многие исследователи конца ХХ века продолжали решать задачу маршрутизации транспорта точными методами.

В своей обзорной статье Лапорт (1992) детально проанализировал ряд работ, связанных с точными алгоритмами решения ЗМТ (полный перебор, метод ветвей и границ и др.) (Laporte, 1992). Ученый выяснил, что огромное количество задач остались нерешенными из-за длительности обработки данных описываемыми методами. Более того, в большинстве статей рассматривались задачи малых размерностей. Таким образом, необходимость углубленного исследования эвристических алгоритмов и новых модифицированных постановок задачи росла с каждым годом.

Отметим, что одной из первых и основных разновидностей классической задачи маршрутизации транспорта стало добавление в математическую постановку ограничения на грузоподъемность автомобилей, которое позволило оптимально распределять грузы между машинами, не превышая суммарную нагрузку на каждое транспортное средство. Как и стандартная ЗМТ, ее модификация с грузоподъемностью в литературе в основном решается классическими методами оптимизации (методом имитации отжига, жадным алгоритмом, и др.). Важно заметить, что задача маршрутизации транспорта с ограничением только на грузоподъемность редко используется на практике, поскольку оптимизация реальных бизнес процессов подразумевает введение и анализ таких ограничений как: временные интервалы поставки, пробки на дорогах в конкретном городе в определенное время дня и др. Такие ограничения неизбежно возникают, когда задача решается для конкретных организаций, которые занимаются транспортировкой людей или доставкой товаров (продукции). К примеру, Дерошье в своей статье ввел понятие «жестких» и «мягких» временных интервалов доставки грузов, что существенно изменило взгляд на ЗМТ, образовав новую математическую постановку задачи — с временными окнами и ограничением на грузоподъемность (capacitated vehicle routing problem with time windows — CVRPTW) (Desrochers, et al., 1992). Основным отличием «жестких» временных окон от «мягких» является возможность отгрузки продукции покупателю в случае нарушения временного интервала: если водитель опаздывает к покупателю с «жесткими» временными окнами — продукция будет непринята в полном размере (в случае с «мягкими» интервалами водитель получит штраф, но сможет произвести отгрузку). Более того, Дерошье в 1992 году обосновал, что решение задачи будет оптимальным, если автомобиль не имеет возможности приехать к покупателю позже заданной правой границы «жесткого» временного окна, в отличие от случая с «мягкими» временными интервалами.

В конце ХХ века большинство научных работ посвящались именно задаче маршрутизации транспорта с «жесткими» временными окнами, поскольку она в большей степени применяется на практике, начиная от деятельности инкассаторов и почтовых работников до маршрутизации школьных автобусов (Irnich, 2008). Математик выяснил, что на современных компьютерах, точные методы решают вышеописанную задачу с 50 — 60 точками на карте более чем за 50 часов, что недопустимо для оптимизации реальных логистических процессов. Так, Соломон в 1987 году рассмотрел первый эвристический алгоритм, позволяющий решить ЗМТ с временными интервалами и грузоподъемностью транспортных средств за существенно меньшее время, по сравнению с точными методами (Solomon, 1987). Эвристика была основана на алгоритме сбережений Кларка и Райта (1964) для классической задачи маршрутизации транспорта и улучшала текущее решение на каждой итерации, позволяя решать задачу на ориентированном графе (матрица расстояний между каждой точкой на карте асимметрична). Более того, Соломону удалось ускорить процесс решения задачи почти в 2 раза (Solomon, 1987).

Помимо эвристических методов, в современных статьях появилась новая категория алгоритмов — метаэвристики (обобщенные способы решения задачи коммивояжера) (Пантелеев, Метлицкая, Алешина, 2013). Одним из наиболее популярных метаэвристических методов является алгоритм муравьиной колонии, который будет использоваться в настоящем исследовании в разделе Данные и методология. Рассмотрим его подробно. Впервые в литературе М. Дориго сформулировал и реализовал алгоритм муравьиной колонии, который эмпирически решает ЗМТ быстрее, в сравнении с другими существовавшими и доступными алгоритмами конца ХХ века (Dorigo, 1999). В работах отмечается, что муравьиный алгоритм эффективен для количества вершин больше 20, то есть позволяет учесть временные ограничения в маршруте у наибольшего количества покупателей, в отличие от других методов оптимизации (гнездовой метод Монте-Карло, модифицированный генетический алгоритм и др.) (Курейчик, Мартынов, 2014). Более того, алгоритм муравьиной колонии меньше подвержен неоптимальным начальным решениям по сравнению с обычными эвристическими алгоритмами. Маршрут строится случайным образом и колония при выборе каждой следующей вершины опирается на память всех предшествующих муравьев, а не нескольких, в отличие от алгоритмов, построенных по принципу марковских процессов (текущее состояние системы зависит только от предыдущего). Итак, алгоритм муравьиной колонии основан на поведении множества искусственных муравьев, которые кооперируются для нахождения решения задачи путем обмена феромонами, находящимися на дугах графа (дороги в городе). Как известно, муравьи способны находить наилучший маршрут от источника еды до муравейника, оставляя след из феромона, по которому будут двигаться муравьи-последователи. Поскольку на самом выгодном маршруте феромона будет скапливаться больше, чем на других, через определенный момент времени, вся колония предпочтет его. Данный процесс получил название коллективное обучение (Dorigo, 1999). Необходимо отметить, что алгоритм муравьиной колонии учитывает как пространственные, так и временные характеристики задачи. С его помощью планируется найти решение, близкое к оптимальному.

Говоря о работах, связанных с подробным рассмотрением получаемых решений ЗМТ, отметим, что многие авторы считают недостаточным одного лишь решения задачи без последующего анализа. Экономисты утверждают, что для оптимизации логистики также необходимо обращать внимание на сам процесс формирования заказов, который может быть не оптимальным. Описываемая ситуация моделируется в виде задачи о ранце 0−1 (0−1 knapsack problem) (Toth, Vigo, 2002), которая имеет следующую математическую постановку:

где: — цена j-го заказа;

— вес j-го заказа;

— переменная, отвечающая за нахождение j-го заказа в автомобиле;

— суммарная грузоподъемность транспортного средства.

Таким образом, ограничение (12) является целевой функцией классической задачи о ранце и представляет собой дневную выручку компании, которую необходимо максимизировать. Ограничение (13) показывает, что вес всех заявок в автомобиле не должен превышать его грузоподъемность. Последнее ограничение (14) — говорит о том, что переменная принимает только два значения — 1, если заказ загружен в машину, 0 — в противном случае.

В научных статьях существует огромное количество модификаций и алгоритмов решения данной задачи (Иглин, 2003). Существуют задачи о многомерном ранце, целочисленная задача о рюкзаке, задача о рюкзаке с мультивыбором и др. Заметим, что задача о ранце (как и задача коммивояжера) является NP-сложной и не решается ни одним полиномиальным алгоритмом за мыслимое время (Макконнелл, 2004). В выпускной квалификационной работе частично затрагивается процесс фильтрации покупателей в случае возникновения излишнего спроса на продукцию фирмы. Подчеркнем, что решение задачи о рюкзаке не является целью настоящего исследования и будет рассмотрено в дополнение к анализу решения задачи маршрутизации транспорта с ограничением на грузоподъемность и временными окнами покупателей в разделе Описание результатов.

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