Оптимизация транспортных маршрутов: разберемся по понятиям

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

Исследование операций (operations research)
Научное направление, занимающееся разработкой и практическим применением методов наиболее оптимального принятия решений в организационном управлении.

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

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

Решаемые в рамках линейного программирования задачи описываются с помощью линейных функций, линейных уравнений и неравенств, т.е.:
- Целевая функция L(X) представляет собой линейную функцию от элементов решения
- Ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.

Модель
Материально или мысленно представляемый образ  объекта-оригинала, с помощью которого получают новые знания об этом объекте-оригинале. Из определения следует, что моделировать надо такие объекты, которые трудно или нельзя изучить другими методами.

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

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

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

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

Метод северо-западного угла
Эвристический метод нахождения решения, когда значения расставляются в матрице решений начиная с верхней левой ячейки начиная с ресурса с наименьшей ценой и далее по порядку (предварительное решение)

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

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

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

Алгоритм Свира (дворника-стеклоочистителя)
Один из эвристических (нематематических) вариантов построения маршрута при большом количестве точек. Заключается в нанесении на карту всех точек маршрута и воображаемом движении "дворника-стеклоочистителя" по карте из места отправления по кругу и стирании заказов (точек маршрута). Как только сумма заказов "стертых" магазинов достигнет вместимости транспортного средства, фиксируется сектор, обслуживаемый одним кольцевым маршрутом, и намечается путь объезда потребителей.