ОБЗОР МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА ДЛЯ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОГО МАРШРУТА ШКОЛЬНОГО ТРАНСПОРТА

В настоящее время в России существует проблема транспортного обеспечения обучающихся. Согласно 40 Федеральному закону № 273-ФЗ установлены следующие правила транспортного обеспечения: предоставление в соответствии с законодательством Российской Федерации мер социальной поддержки при проезде на общественном транспорте, а также организацию бесплатной перевозки до образовательных организаций и обратно.

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

В городе Набережные Челны отсутствует специализированный транспорт для школьников. Большое количество школьников проживает слишком далеко от школы. Это приводит к тому, что школьники опаздывают на уроки, следовательно, ухудшается качество образовательных услуг. Возникает необходимость в создании транспортной системы для школ.

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

В целом, проблема состоит из подзадач: выбор автобусных остановок, маршруты, расписание и корректировка времени начала учебы в школе. Выбор автобусной остановки относится к процессам выбора подмножества из множества доступных остановок, которые в дальнейшем обслуживаются автобусами. Этот шаг может также включать назначение учеников на автобусные остановки. Как правило, автобусные маршруты должны учитывать ограничения пропускной способности, а также ограничения по длине и длительности маршрута. Автобусное расписание представляет собой расчет возможного графика для автобусов. Он определяет, какой автобусный маршрут обслуживается в каждой точке времени. Регулировка времени начала обучения позволяет автобусам обслуживать несколько школ и, следовательно, сокращает количество необходимых автобусов. Все эти вопросы тесно взаимосвязаны, и их следует решать комплексно.

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

Сущность задачи маршрутизации школьных автобусов (SBRP – Student Bus Routing Problem) состоит в построении модели для нахождения оптимального маршрута автобуса, который будет удовлетворять различным ограничениям: максимальная вместимость автобуса, максимальная стоимость транспортировки, оптимальное время транспортировки школьников в автобусах, а также достаточное количество времени, чтобы добраться до школы. Также проблема маршрутизации школьных автобусов (SBRP) может быть определена как проблема нахождения оптимальных маршрутов транспортировки школьников с одной или нескольких остановок с минимальными затратами времени [1, с. 2-3].

Для решения задачи должны быть рассмотрены некоторые факторы, такие как экономические проблемы, вопросы, время, маршрут, эффективность и другие.

Одной из самых известных и наиболее часто используемых задач в транспортной логистике является задача коммивояжера или так называемая «задача о бродячем торговце». Ее сущность сводится к поиску наиболее короткого,  оптимального пути, проходящего через определенные пункты по одному разу с последующим возвратом в исходную точку. Задачу коммивояжера используют для нахождения самого выгодного маршрута, который позволит коммивояжеру объезжать определенные города со своим товаром по одному разу и вернуться в исходную точку. Наилучший маршрут будет определен минимальным временем, проведенным в пути, а также минимальными расходами на дорогу либо, в простейшем случае, минимальной длиной пути.

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

Задача коммивояжера формулируется следующим образом:

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

Алгоритм относится к «жадным» алгоритмам. Он достаточно прост в реализации, быстро выполняется. Недостатком алгоритма является выдача неоптимальные решения.

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

Следующий метод решения задачи коммивояжера - метод ветвей и границ. Метод основан на последовательном разбиении множества допустимых решений на некоторые подмножества. На каждом шаге метода элементы разбиения подвергаются проверке, тем самым выясняется, содержит данное подмножество оптимальное решение или нет. Проверка осуществляется с помощью вычисления оценки снизу для целевой функции на данном подмножестве. Если оценка снизу не меньше наилучшего из найденных решений (так называемого рекорда), то подмножество может быть отброшено. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы [2].

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

Частным случаем применения метода "ветвей и границ" для конкретной задачи является алгоритм Литтла. При применении данного метода маршрут коммивояжера представлен в виде построения двоичного корневого дерева решений, при этом каждой вершине x соответствует некоторое подмножество M(x) множества всех маршрутов коммивояжера [3].

Преимуществом данного метода является то, что активными объявляются только те вершины, в которых может содержаться оптимальный маршрут. Для этого существует правило активации вершин, сводимое к правилу подсчета границ.

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

Список литературы:

1. Denis M. Manumbu, Egbert Mujuni, Dmitry Kuznetsov. Mathematical Formulation Model for a School Bus Routing Problem with Small Instance Data. Mathematical Theory and Modeling. Vol.4, No.8, 2014.
2. Галяутдинов Р.Р. Задача коммивояжера - метод ветвей и границ // Сайт преподавателя экономики. [2013]. URL: http://galyautdinov.ru/post/zadacha-kommivoyazhera (дата обращения: 17.12.2017).
3. Гараба И.В. Сравнительный анализ методов решения задачи коммивояжера для выбора маршрута прокладки кабеля сети кольцевой архитектуры // Молодежный научно-технический вестник. – М. - 2013г. - №11.