Автоматика и телемеханика, № 7, 2014
© 2014 г. Е.М. БРОНШТЕЙН, д-р физ.-мат. наук (bro-eflm@yandex.ru), Д.М. ВАГАПОВА (lisichka8706@mail.ru), А.В. НАЗМУТДИНОВА (morissetten@gmail.com) (Уфимский государственный авиационный технический университет)
О ПОСТРОЕНИИ СЕМЕЙСТВА МАРШРУТОВ ДОСТАВКИ ШКОЛЬНИКОВ ЗА МИНИМАЛЬНОЕ ВРЕМЯ1
Рассматривается задача о школьном автобусе, заключающаяся в формировании маршрутов доставки учеников по домам после окончания занятий несколькими автобусами за минимальное время. Приведена соответствующая линейная частично целочисленная модель. Наряду с точным применяется простой эвристический алгоритм. Проведен вычислительный эксперимент.
1. Введение
Задача о школьном автобусе (School Bus Routing Problem, SBRP) впервые была сформулирована в [1]. За последние десятилетия опубликовано множество работ, посвященных этому классу задач, в них приводятся модификации, отражаются различные аспекты проблематики, анализируются как точные, так и эвристические алгоритмы решения (подробный обзор см. в [2]). Большое число работ посвящено применению метаэвристик. Часто рассматриваются задачи минимизации числа автобусов при тех или иных ограничениях, в частности, на топологию сети дорог (например, недавняя работа [3]). Отметим актуальность задачи для современной России, когда закрывается множество сельских школ и учащихся доставляют транспортом по домам из учебных заведений, расположенных достаточно далеко от пунктов проживания. Класс SBRP естественным образом входит в общее семейство оптимизационных задач транспортной логистики (Vehicle Routing Problem, VRP), постановка которых восходит к работе [4]. На сайте http://neo.lcc.uma.es/vrp/ аккумулируется информация по этой тематике. В данной работе рассматривается одна из задач класса SBRP. В этой задаче в отличие от ранее рассматривавшихся целевой функцией является максимальное время доставки школьников. В работе описан новый метод приведения задачи к линейной частично целочисленной форме, также предложен простой эвристический алгоритм. Для сравнительного анализа эффективности различных алгоритмов решения задачи проведен вычислительный эксперимент. Рассмотренная задача близка к теории расписаний, существенный вклад в развитие которой внес академик НАН Беларуси В.С. Танаев (см, например, [5, 6]). Если автобус
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 13-01-00005).
один, то сформулированная задача равносильна КР-трудной задаче построения минимальной гамильтоновой цепи. Тем самым сформулированная задача относится к тому же классу сложности.
2. Постановка задачи
По окончании занятий требуется развезти школьников по их остановкам на нескольких автобусах. При этом школьников следует доставить за минимально возможное время.
Для построения математической модели введем соответствующие величины.
1. Для каждой из N остановок задана величина Оп (п = 1,..., N) - число школьников, которых надо доставить на эту остановку. Для единообразия школу считаем 0-й остановкой.
2. Каждый из К автобусов характеризуется числом Тк (к = 1,...,К) посадочных мест.
3. Между некоторыми парами остановок есть дороги, время проезда по которым равно К^ (от г-й остановки до ^-й). Граф, вершинами которого являются остановки, а дугами - дороги, считаем сильно связным. Следует отметить, что время проезда определяется не только расстоянием, но и качеством дороги, рельефом местности и т.д. В этой связи величины К^ не обязаны удовлетворять неравенству треугольника. По величинам К^ строится квадратная матрица С = || с^- || порядка N + 1, элементами которой являются минимальные времена проезда между остановками. Для этого применялся алгоритм Флойда-Уоршелла [7]. Элементы матрицы С удовлетворяют неравенству треугольника.
4. Необходимо найти величины хП (п = 0,..., N; к = 1,..., К) - число школьников, которых необходимо доставить к-м автобусом на п-ю остановку.
Запишем соответствующие ограничения.
(1) хП ^ 0 (п = 0, ...^; к = 1,...,К), целые, хк = 0.
На каждую остановку необходимо доставить всех школьников, для которых это необходимо:
к
(2) ^ хП = (п = 0,..., N), полагаем Б0 = 0. к= 1
Ограничения на вместимость автобусов:
N
(3) ]ТхП<Тк (к = 1,...,К).
П=1
Добавлением виртуальных школьников в количестве ^к=1 Тк — Хт=1 (в случае положительности этой величины), для которых пунктом доставки
является школа, можно добиться того, что ограничения (3) выполняются в форме равенств. Это существенно для п. 3. Таким образом, полагаем, что общее число школьников равно числу мест в автобусах: y^—i
Пусть Hк = {i : хк > 0} - множество остановок, на которых должен высадить пассажиров k-й автобус. Следует отметить, что величинами хП маршруты автобусов однозначно не определяются. Пусть P(Hk) - минимальное время проезда по маршруту, проходящему через все остановки из Hк, у которого начальный пункт - школа.
Целевая функция:
(4) max{P (H к)} — min.
к
Результатом решения задачи (1)-(4) является график доставки, при котором школьник, который покинет автобус на своей остановке последним по времени, будет доставлен за минимально возможное время. Очевидно, что задача (1)-(4) имеет решение (вообще говоря, не единственное).
3. Линейная частично целочисленная модель 1
Ценой существенного повышения размерности задачу (1)—(4) удается привести к линейной частично целочисленной форме. Разумеется, условия (1)—(3) остаются без изменений.
Определим булевы переменные У, (п = ; к = 1,...,К) - инди-
каторы того, что к-й автобус высадит школьников на п-й остановке, т.е. У,^ = = 1 тогда и только тогда, когда х, ^ 1 при п > 0; естественно, полагаем У0к = 0. Поскольку х, ^ Тк, то
(5) Угак Тк ^ х, (п = 0,...,Ж; к = 1,...,К).
Выполнение этого неравенства обеспечит справедливость равенства У,/к = = 1 при х, ^ 1, выполнение равенств Ук = 0 при х, = 0 можно обеспечить ограничениями вида У,к ^ х, (п = 0,..., N; к = 1,..., К). Для сокращения числа ограничений обеспечиваем выполнение этих условий специальной конструкцией целевой функции.
Введем булевы переменные Z!kv (и, V = 0,..., N; к = 1,..., К) - индикаторы того, что к-й автобус высаживает школьников последовательно на и-й и v-й остановках (если и > 0).
Поскольку 0-я остановка (школа) в любом маршруте является начальной и не является конечной, справедливы равенства
N N
(6) Y,zkv = 1, 5>ио = 0 (к = 1,...,К).
v=0 м=0
Всякая остановка (пусть v-я), на которой к-й автобус высаживает пассажиров, является конечной для некоторого отрезка пути, на котором Z!kv = 1,
поэтому
N
(7) = ^ (к = 1,...,К; V =
м=0
В то же время все остановки маршрута кроме последней являются начальными для соответствующих дуг. Отсюда,
N
(8) < ^ (к = 1,..., К; и = 1,...,Ж).
^=0
Введем целочисленные переменные АЦ (к = 1,..., K; и = 1,... , N), удовлетворяющие условиям
(9) 0 < АЦ < N1^ (к = 1,...,К; и = 1,...,Ж),
N
(10) Гк < АЦ ^ Гк (к = 1,..., К; и = 1,...,Ж),
П=1
(11) АЦ - Ак + N2^ < N - 1 (к = 1,...,К; и, V = 1,...,Ж).
Легко проверить, что переменные АЦ равны 0, если к-й автобус не высаживает школьников на и-й остановке, и равны последовательным номерам остановок на маршруте в порядке высадки школьников к-м автобусом (после школы). Тем самым исключается существование циклов. Перейдем к построению целевой функции.
Введем переменную 1 - максимальную из продолжительностей проезда по всем маршрутам. Справедливы неравенства
N N
(12) < t (к = 1,...,К).
^=0 ц=0
Величину Ь необходимо минимизировать. Кроме того, необходимо обеспечить обнуление булевых переменных
Определим величину Д(С) - минимальную из положительных алгебраических сумм различных элементов матрицы C, т.е. положим
{N N NN
Е Е СУ : Е Е > 0 > ,
¿=0 3=0 ¿=0 3=0 )
где минимум берется по всевозможным наборам величин е^ € {—1, 0,1}. Величина Д(С) существует и положительная в силу конечности рассматриваемого множества, она является оценкой снизу положительных разностей времен прохождения путей, соединяющих какие-нибудь пары остановок. Тем
самым A(C) является и оценкой снизу положительных разностей времен прохождения самых продолжительных маршрутов для любых способов организации доставки школьников.
Пусть a € (0, A(C)]. Зададим целевую функцию следующим образом:
N K
(13) t + a^^Yk/(2NK) — min.
г—0 k—1
Проверим, что в точке минимума такой целевой функции достигает минимума и переменная t.
Пусть в решении задачи значения t, Yk соответственно равны t*, Yk*. Рассмотрим величины t', Yk' для любого другого допустимого решения, при котором t' — t* > 0. Тогда t' — t* ^ A(C) ^ a по определению A(C). Справедливо неравенство
NK
NK
eeyk — ее yk*
г—0 k—1
г—0 k—1 NK
NK
ЕЕ — Yk*
^eef — y
г—0 k—1
г—0 k—1
k*
<
^ NK.
Последнее неравенство следует из булевости переменных Yk. Отсюда
NK
NK
t' + /(2NK) — t* + ^]TYk*/(2NK)
—0 k—1
г—0 k—1
= (t' — t*) +
a
NK
2NK
г—0 k—1
ЕЕ — Yk*l ^
^ a —
a
NK
2NK
ee|yk' — y
k*
aNK a
г=0 к=1
что и требовалось.
Естественно, yk* = 0 при хк* = 0.
Если элементы матрицы расстояний целые, то можно принять а = 1. Оценим размерность полученной задачи (1)-(3), (5)-(13). Переменных х,, У^, А по NK, число переменных Zkv равно K^ + 1)2, переменная £ единственная. Таким образом, число переменных имеет порядок О^2К). Тот же порядок имеет и число ограничений.
4. Линейная частично целочисленная модель 2. (Релаксированная задача)
Ослабим ограничения задачи (1)-(3), (5)-(13), исключив условие целочис-ленности базовых переменных х,. Структура задачи несколько упрощается, но в процессе решения могут получиться дробные значения х,.
Опишем метод приведения величин жП к целым с сохранением (или даже с сокращением) маршрутов автобусов.
Выделим остановки, для которых в полученном решении задачи хотя бы одна из величин жП не является целой. Пусть Un - множество автобусов, для которых это так и аП - дробные части величин жП. Характеристикой решения будем считать величину n Card (Un). Поскольку сумма дробных частей величин жП для всякой выделенной остановки (пусть n-й) является целой, из условия (2) следует, что не менее двух значений аП полож
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.