SchoolBus_TRA_DP2. Транспортное обслуживание, Кофман. Минимум затрат для доставки школьников в школу на автобусах. Планирование поставок, логистика, ритейл. 2 отрезка пути.

Постановка задачи

Кофман А., Анри-Лабордер А., Методы и модели исследования операций. Том 3. стр. 18-20

(Методы и модели исследования операций. Целочисленное программирование, 1977, стр. 18 — 20)

В небольшом населенном пункте А имеется школа, которую посещает некоторое число учеников; при этом место жительства некоторых учеников находится вне населенного пункта, что приводит к необходимости организовать их доставку к школе на автобусах. Имеются две основные автобусные остановки В и С (В находится между А и С)

Обслуживающее населенный пункт А транспортное агентство располагает двумя типами автобусов на разное число мест.

Транспортным агентством установлены цены проездных билетов для каждого из отрезков пути и в зависимости от типа автобуса.

Необходимо определить, какого типа автобусы следует использовать на каждом отрезке пути, так чтобы суммарные издержки были минимальными.

Дано:

•  Участки пути, образованными остановками и школой.

•  Число учеников для перевозки на каждом участке пути.

•  Цены проездного билета по участкам пути.

•  Типы автобусов для перевозки.

Требуется:

Определить число и типы автобусов для перевозки школьников на каждом участке пути

кратко

Установки описывают автобусы, которые могут привлекаться для перевозки школьников. Их максимальное возможное число, достаточное для перевозки всех школьников: 3 автобуса по 35-мест (105 человек), 2 автобуса 50 мест (100 человек).

Число школьников, которых требуется перевести по каждому из участков пути, представлено в таблице: C->B – 48; B->A – 72.

Отметим, что в отрезок пути B->A включаются не только школьники, проживающие на этом отрезке, но и все школьники, проживающие на отрезке C->B.

Операции установок отражают использование/неиспользование автобуса на данном отрезке пути

Интервалы времени описывают отрезки пути C->B и B->A, которые необходимо обслужить автобусами.

Потоки отражают максимальное число учеников, которых можно перевезти данным автобусом по данному отрезку пути.

Емкости отражают потребность в перевозке школьников на каждом отрезке пути. Ограничение на верхнюю границу емкости равное 0 означает требование перевезти всех школьников на каждом отрезке пути.

кратко

Рисунок. Общий вид потоковой схемы объекта «с именами»

кратко

Матрица переналадок отражает цену проездного билета по отрезкам пути:

Переход автобуса с простоя на перевозку по отрезку пути равен цене проездного билета для отрезка пути, приведенного к целым числам умножением на 10.

Фрагмент матрицы переналадок

Рисунок. Фрагмент формы – стадия, установка, операция, поток

Заданы фрагменты решения, которые запрещают осуществлять перевозку по неверному отрезку пути. Автобус в отрезке пути (интервале C->B) может либо не осуществлять перевозку, либо перевозить по отрезку пути C->B, для отрезка B->A аналогично.

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

Критерий – минимум суммарных затрат от перевозки всех школьников, который задается критерием «Переключение». Переход автобуса с отрезка C->B на B->A равен разнице отрезка C->A и отрезка C->B, т.е. фактически цена продолжения перевозки этим же автобусом и по второму отрезку пути.

кратко

Автобусы для перевозки детей

Рисунок. Фрагмент формы – стадия, установка, операция, поток

Примечание. Видна вместимость автобусов первого типа – 35 пассажиров.

Автобусы для перевозки детей

Рисунок. Фрагмент формы – стадия, установка, операция, поток

Примечание. Видна вместимость автобусов второго типа – 50 пассажиров.

Число школьников, которых нужно перевести по отрезкам пути:

Рисунок. Фрагменты формы – стадия, емкость

Примечание. Видно требование перевести всех школьников как по первому отрезку «C->B» и «B->Школа_A».

кратко

Фрагменты расписания

Рисунок. Фрагмент расписания выполнения операций

Примечание. Для перевозки школьников оптимально выделить автобус «Вольво» на весь путь, а автобус «Форд» – только на вторую часть пути.

Перевезенные школьники по отрезкам пути:

Рисунок. Гистограммы изменения состояния емкостей

Примечание. Отрицательные значения показывают оставшиеся свободные места в автобусах.

Объяснения решения

Рисунок. Фрагмент трассы объяснений хода рассуждений Решателя DP

кратко