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 означает требование перевезти всех школьников на каждом отрезке пути.

кратко

Схема Объекта

подробнее…

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

кратко

Особенности Решения S.SchoolBus_TRA_DP2.

Особенности Задачи

подробнее…

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

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

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

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

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

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

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

кратко

Исходные данные

подробнее…

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

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

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

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

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

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

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

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

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

кратко

Результаты решения

подробнее…

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

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

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

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

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

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

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

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

кратко