Построить оптимальный маршрут для транспортного средства – эта одна из самых распространенных задач в транспортной логистике, но за всей простотой ее формулировки скрывается целое направление в прикладной математике — комбинаторная оптимизация. В общем случае определение оптимальной последовательности объезда заданных точек сводится к нахождению баланса между тремя минимумами: расстоянием, временем и затратами на перевозку. Точно неизвестно кто и когда впервые сформулировал эту задачу. Первым письменным источником, в котором упоминается эта проблема, считается книга 1832 года «Коммивояжер. Как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах. Советы старого курьера». Поэтому сегодня задачу поиска оптимального маршрута часто называют задачей коммивояжера. Задача коммивояжера является очень трудоемкой с точки зрения перебора всех возможных вариантов посещения промежуточных точек, а для более чем 66 городов ее считают трансвычислительной. Поэтому для сложной маршрутной сети используются специальные алгоритмы анализа вариантов, самым известным из которых является метод ветвей и границ. Суть его заключается в отсеивании подмножеств допустимых решений, заведомо не содержащих оптимальных решений.
Веб-сервис Google maps, который мы будем использовать для решения задачи, позволяет вводить до 10 точек для одного маршрута.
Теперь рассмотрим пример программы в Excel для определения оптимальной последовательности посещения точек маршрута. Начальный, а также конечный пункт должен быть известен заранее по условию задачи. Для примера определим наилучший маршрут путешествия из Минска в Минск с посещением всех областных центров Беларуси и еще нескольких городов по периметру страны: Брест, Витебск, Гомель, Гродно, Могилев, Пинск, Полоцк, Поставы.
После нажатия на кнопку «Рассчитать» получим оптимальную последовательность посещения промежуточных точек.
