Коротко и по делу — на примере задачи оптимизации маршрутов (TSP/VRP).
1) Точные методы
- Что: гарантированно находят оптимум и (в случае branch-and-bound / MIP) могут дать доказательство оптимальности.
- Примеры: полный перебор (пермутации), динамическое программирование (Held–Karp для TSP), ветвление и границы / MIP‑решение.
- Сложность: полный перебор $O(n!)$; Held–Karp $O(n^2{2}^n)$; ветвление и границы в худшем случае экспоненциально, но часто эффективно при сильных ограничениях и хороших оценках.
- Плюсы: оптимум или гарантия близости к нему; полезно для маленьких задач и для верификации.
- Минусы: быстро становится вычислительно неосуществимым при росте $n$.
- Когда использовать: когда $n$ мало ($n\le 20$–$30$) или когда требуется доказательство оптимальности/строгие SLA и есть время/ресурсы.
2) Эвристические методы
- Что: быстрые приближённые алгоритмы без гарантий оптимальности, часто специализированы под структуру задачи.
- Примеры: nearest neighbor, savings (Clarke–Wright), insertion, локальный поиск (2‑opt, 3‑opt), конструктивные правила + улучшения.
- Сложность: обычно полиномиальная, напр. nearest neighbor $O(n^2)$, 2‑opt за итерацию $O(n^2)$.
- Плюсы: очень быстрые, просты в реализации, хороши для оперативных решений при больших $n$.
- Минусы: могут застревать в локальных минимумах; качество зависит от эвристики и инициализации; нет гарантий.
- Когда использовать: когда нужна быстрая эвристика для большого потока запросов, ограниченное время ответа (миллисекунды‑секунды), либо как начальное решение для метаэвристик/мип.
3) Метаэвристики
- Что: общие стохастические схемы поиска глобума, используют эвристики как операторы; хороши для сложных ограничений и больших задач.
- Примеры: генетические алгоритмы, simulated annealing, tabu search, ant colony optimization, GRASP.
- Сложность: зависит от параметров: примерно $O(\text{pop\_size}\cdot n\cdot \text{generations})$ для GA; выражается в практике, не в жёсткой формуле.
- Плюсы: находят хорошие решения для средних и больших задач; гибкие при наличии ограничений (временные окна, ёмкость); часто дают близкие к оптимальным решения.
- Минусы: долгое время настройки, стохастичность (разные запуски дают разные решения), без строгих гарантий оптимальности.
- Когда использовать: средние и большие задачи ($20<n\le 200$ и выше) когда нужна хорошая (но не обязательно оптимальная) маршрутная схема и есть больше времени чем на чистую эвристику.
4) Практические рекомендации по выбору
- Очень маленькие задачи ($n\le 20$): используйте точные методы (DP, MIP).
- Малые–средние ($20<n\le 100$): попробуйте MIP/branch‑and‑bound с ограничением времени; если время жёстко, используйте улучшенные эвристики (2‑opt/3‑opt) или метаэвристику.
- Средние–большие ($100<n\le 500$): метаэвристики или гибрид эвристика+локальный поиск; возможно декомпозиция (кластеризация клиентов и локальные решения).
- Очень большие ($n>500$): эвристики, кластеризация, online/streaming подходы; применяйте правило «route‑first, cluster‑second» или иерархическое разбиение.
- Если требуемая гарантия качества критична → MIP с тайм‑лимитом, сравнение нижней/верхней оценок; если главное время ответа — выбирайте быстрые эвристики.
- Для VRP с дополнительными ограничениями (ёмкость, окна) чаще нужны метаэвристики или специализированные эвристики; можно комбинировать: эвристика для инициализации + метаэвристика для улучшения + MIP на подзадачах для контроля качества.
5) Практические приёмы гибридизации
- Эвристика для быстрого начального решения, затем локальный поиск (2‑opt/3‑opt).
- Методы разделения по географии (к‑means, sweep) + оптимизация внутри кластеров.
- Использовать MIP/branch‑and‑bound с тайм‑лимитом, чтобы получить бенчмарк и доказательство близости к оптимуму при необходимости.
Краткая шпаргалка:
- Нужен точный оптимум и маленькая задача → точный метод.
- Нужно быстрый результат в реальном времени и большая задача → эвристика.
- Нужно хорошее качество для средних/больших задач и есть время на вычисления → метаэвристика или гибрид.
Если нужно, могу привести конкретную схему выборa/порогов под вашу службу доставки (число заказов, окна, ёмкость, допустимое время ответа).