Краткая сущность необъясненности: эвристическая машина, то есть электронно-механическое устройство для решения инженерных, научных, социологических и иных проблем.
Основное практическое предназначение ОТМ — это решение задачи маршрутизации. Она давно уже имеет как научную постановку, так и общепризнанные методы решения — более или менее точные. Этому посвящено немало публикаций, и поскольку я в этом вопросе далеко не теоретик, то не стану портить выверенные и стройные труды своим безграмотным изложением. Зато могу посоветовать хороший ресурс, где собраны наиболее понятные и полные описания модификаций задачи маршрутизации транспорта и подходы к их решению.
Нам очень повезло, потому что у нас под рукой есть реальный инструмент, включающий наиболее зарекомендовавшие себя математические алгоритмы решения задачи маршрутизации с различными ограничениями. Главное этот инструмент можно проверить на практике и разобрать что именно происходит на простых примерах. Этим я и предлагаю заняться.
— Вот, изволите видеть, так называемая эвристическая машина, — сказал старичок. — Точный электронно-механический прибор для отвечания на любые вопросы, а именно — на научные и хозяйственные. Как она у меня работает? Не имея достаточных средств и будучи отфутболиваем различными бюрократами, она у меня пока не полностью автоматизирована. Вопросы задаются устным образом, и я их печатаю и ввожу таким образом к ей внутрь, довожу, так сказать, до ейного сведения. Отвечание ейное, опять через неполную автоматизацию, печатаю снова я. В некотором роде посредник, хе-хе! Так что, ежели угодно, прошу.
Если говорить только об алгоритмах поиска оптимальной последовательности объезда точек, то они обозначены в ОТМ специальным параметром (MULTISTOP SEQUENCING ALGORITHM), который может иметь всего четыре значения (привожу описание на английском из документации к ОТМ с моим переводом):
- Insertion: Each stop for the second shipment is inserted into the first shipment at different points to form a combined shipment. This is simplistic with minimal evaluations. May be advisable for a large number of stops. // Каждая остановка для следующей перевозки вставляется в предыдущий вариант перевозки на разных позициях чтобы создать объединенную перевозку. Это простейший подход с минимальными оценками. Рекомендуется для большого числа остановок в рейсе.
- 2-Opt: Looks to find a sequence with a lower cost by replacing any 2 of the links (say first after step 1 and second after step 2, in essence, there are 3 sub-sequences) in a 2-Opt sequence by a set of 2 other links that would form a new sequence. For example, you have 8 stops and you know the cost of the initial sequence. By making a swap, there is a new sequence (i.e. 1,3,4,5,6,7,8,2). If this sequence results in a lower cost, the initial sequence is replaces with this one and 2-Opt runs again until there is no improvement after running all swaps. // Ищет последовательность с меньшей стоимостью (меньшим пробегом) путем замены двух отрезков в последовательности вставки двух других отрезков, которые сформируют новую последовательность. Например, у вас есть 8 остановок и вы знаете стоимость (пробег) по изначальной последовательности (1,2,3,4,5,6,7,8). Делая перестановку (например, двух отрезков между точками 1-2 и 2-3) вы получаете новую последовательность (1,3,4,5,6,7,8,2). Если эта последовательность дает более низкую стоимость (пробег), то изначальная последовательность заменяется ей и алгоритм запускается снова до тех пор пока результат не перестанет улучшаться после перестановок.
- 3-Opt: Similar to 2-Opt except 3 links are chosen (4 sub-sequences) // Аналогично алгоритму 2-Opt, за исключением того, что делает перестановку трех отрезков в первоначальной последовательности.
- Enumeration: Oracle Transportation Management goes through all possible sequences by enumerating in a proper order and chooses the sequence that is feasible and minimizes the total cost. Best when number of stops is low for performance reasons. // ОТМ проходит все возможные варианты последовательностей путем их перечисления и выбирает допустимую последовательность с минимальной стоимостью (пробегом). Лучший вариант для небольшого числа остановок с точки зрения производительности системы.
Описание первых трех из этих методов можно найти в Википедии в статье Обобщённая задача коммивояжёра. Они являются эвристическими, то есть неточными, но зато быстрыми и дающими хороший результат с достаточно большой вероятностью чтобы их можно было смело использовать. А вот последний метод — это полный перебор, который призван гарантировать действительно лучшее решение путем перебора и сравнения абсолютно всех вариантов сочетаний точек. Звучит отлично, но нас тут же предупреждают, что на большом числе точек эта задача может оказаться неподъемной даже для ОТМ. Большое число точек имеется в виду на один рейс. Далее видим рекомендуемое максимальное количество точек на рейс допустимое для полного перебора — это пять. Не так уж и плохо.
Надо сказать, что в реальных задачах результат маршрутизации — это результат работы далеко не только этих алгоритмов, но тут мы пренебрегаем возможными ограничениями и рассматриваем только задачу оптимальной последовательности точек.
— Внутре! — прошелестел старичок. — Внутре смотрите, где у нее анализатор и думатель…
Предлагаю рассмотреть очень простой пример, который легко можно посчитать и вручную. Возьмем одну точку отгрузки и три точки доставки для того, чтобы подсмотреть что же станет с этим делать ОТМ. По традиции для примера берем прекрасные сибирские города: Новосибирск — точка отгрузки; Томск, Кемерово и Новокузнецк — точки доставки, которые необходимо объехать одной машиной самым оптимальным образом. Для проведения опыта создаем три заказа, общий объем которых как раз входит в одну машину, и запускаем планирование по очереди используя имеющиеся алгоритмы маршрутизации.
Дальше я провела доскональный анализ системных логов чтобы точно установить пошаговые действия ОТМ при решении данной задачи. Оговорюсь, что для такого простого примера разницы в решении при использовании всех четырех алгоритмов не было. Но уже на пяти точках было установлено, что Insertion и 2-opt немного хуже, чем 3-opt и Enumeration, которым удалось уменьшить общий пробег. А вот улучшения результата при переходе с 3-opt на Enumeration не было замечено ни разу даже для больших массивов заказов. Поэтому, учитывая значительную разницу в скорости обработки, для оптимального результата вполне достаточно 3-opt.
Логика поиска решения строится на понятии «выигрыша» — каждое следующее решение по объединению точек в один маршрут оценивается в сравнении с вариантом без этого объединения по общему пробегу. Решение с наибольшим выигрышем переходит на следующую итерацию. Этот способ известен как «Механизм сбережений» (Savings, Clark and Wright, 1964).
Итак пошаговое решение задачи в ОТМ:
- Определяем расстояния от точки отгрузки до каждой точки доставки и строим прямые перевозки по каждому заказу. Это отправная точка, суммарный пробег по этим трем перевозкам мы и будем далее оптимизировать.
- Перебираем парные комбинации точек доставки и оцениваем выигрыш по расстоянию для каждой из комбинаций. Для пары Томск->Новокузнецк сразу натыкаемся на отрицательный выигрыш, поэтому обратный вариант Новокузнецк->Томск даже не рассматриваем (если проверить, то этот вариант еще хуже). Отсюда можно сделать вывод, что полный перебор не такой уж и полный, либо ОТМ что-то в логах не договаривает, а иначе не понятно как он этот вариант сразу выкинул без рассмотрения. Итого просчитано пять парных комбинаций.
- Среди парных комбинаций было несколько положительных выигрышей, но лучшим оказалось сочетание Кемерово->Новокузнецк. Для следующих итераций берем их объединенный результат для оценки выигрыша при добавлении третьей точки.
- Перебираем комбинации отрезка Кемерово->Новокузнецк с третьей точкой — Томск. В первом случае ставим точку в конце отрезка и получаем Новосибирск->Новокузнецк->Кемерово->Томск с отрицательным выигрышем. Во втором случае ставим Томск в начале отрезка и получаем Новосибирск->Томск->Кемерово->Новокузнецк с положительным выигрышем.
- Среди комбинаций из трех точек лучшее сочетание Новосибирск->Томск->Кемерово->Новокузнецк и оно берется как окончательное решение.
Для тех, кто лучше понимает в табличной форме — привожу таблицу выигрышей:
| До объединения | После объединения | Выигрыш | |
| Новосибирск->Новокузнецк | 371 | 371 | 0 |
| Новосибирск->Томск | 256 | 256 | 0 |
| Новосибирск->Кемерово | 257 | 257 | 0 |
| Новосибирск->Томск->Новокузнецк | 627 | 643 | -16 |
| Новосибирск->Кемерово->Новокузнецк | 628 | 465 | 163 |
| Новосибирск->Новокузнецк->Кемерово | 628 | 579 | 49 |
| Новосибирск->Томск->Кемерово | 513 | 442 | 71 |
| Новосибирск->Кемерово->Томск | 513 | 443 | 70 |
| Новосибирск->Новокузнецк->Кемерово->Томск | 721 | 765 | -44 |
| Новосибирск->Томск->Кемерово->Новокузнецк | 721 | 650 | 71 |
А для тех, кто предпочитает наглядное представление — серия картинок:
При этом анализатор агрегата будет анализировать, думатель… — у ей внутре ведь есть, кажется, думатель? — …думатель будет думать, и таким образом агрегат станет у вас обучаться. Вы и ахнуть не успеете, как он у вас начнет сам печатать.
Повторюсь, что в данном случае мы рассматривали работу алгоритма маршрутизации в совершенно чистом, изолированном виде. То есть мы совершенно не задействовали алгоритмы для оптимизации загрузки транспорта, когда стоит задача распределения грузов по машинам с целью максимальной утилизации их объема и грузоподъемности. Для этого может производиться не только консолидация, но и разбивка заказов на части. Также тут не учитывались ограничения по временным окнам доставки как самих заказов, так и точек доставки. А это может внести существенные коррективы и, например, разбить оптимальный до этого маршрут на два, чтобы везде успеть вовремя. Наконец, могут быть ограничения по совместимости грузов или по возможности приема тех или иных типов транспортных средств на точках доставки. Но об этих новшествах в следующих сериях.
Надеюсь хоть немного удалось приоткрыть завесу тайны маршрутизации и показать что же там делается внутри. К счастью, ОТМ вовсе не черный ящик — при желании всегда можно прочитать и разобраться что именно он делает. А чем больше понимания принципов работы, тем больше доверия к результату.
P.S. Цитаты из повести Аркадия и Бориса Стругацких «Сказка о тройке». Всем советую.