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

РАСПРЕДЕЛЕНИЕ ТРАНСПОРТНЫХ СРЕДСТВ В УСЛОВИЯХ ВНУТРИГОРОДСКИХ ПАССАЖИРСКИХ ПЕРЕВОЗОК

Рассматриваемые в этой главе динамические транспортные модели во многом имеют сходство с предложенными в предыдущей главе конвейерными моделями распределения ограниченных ресурсов.

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

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

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

Рассмотрим задачу распределения п автобусов по т городским маршрутам (п> т). Обозначим интенсивность поступления пассажиров на остановку ос, следующих до остановки (3 на маршруте ? через

где т( число остановок на маршруте.

Через gea(t) обозначим интенсивность обслуживания пассажиров на остановке а маршрута ? в момент времени t.

Здесь и далее под интенсивностью транспортного обслуживания будем понимать интенсивность поступления пассажиров в транспортное средство в заданный момент времени 7.

Определим ql{t) следующим образом:

Здесь ^ — момент прибытия автобуса j на остановку ос маршрута ?; ff^ — момент отправления автобуса j от остановки ос маршрута ?; М — число автобусов, проходящих через остановку а маршрута ?.

Для введенных обозначений очереди на автобусных остановках вычисляются исходя из уравнения

где U(a(t) — интенсивность поступления пассажиров на остановку а маршрута ?, вычисляемая из соотношения

V4J) — очередь пассажиров на остановке а маршрута ? в момент t количество свободных мест в автобусе j маршрута ?, прибывшего на остановку а, после выхода пассажиров на этой остановке.

Здесь V^?(tj}?) — объем очереди пассажиров на остановке К маршрута ?, маршрут которых заканчивается за остановкой а, в момент прибытия автобуса j на эту остановку; — объем пассажиров на остановке К маршрута ? в момент прибытия автобуса j на эту остановку; 1Vam вместимость автобуса; — соответственно моменты прибытия и отправления автобуса j с остановки К маршрута ?.

Будем обозначать время, которое пассажир, поступивший на остановку а маршрута ? в момент t, тратит на ожидание транспортного средства, через T4j).

Вычисляется T„(t) исходя из следующего соотношения:

где т( число остановок на маршруте ?.

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

при ограничениях:

Здесь Т^(а(, t) потери времени пассажиров, прибывших на остановку а маршрута ? в момент t, при условии, что на маршрут ? выделено а1 автобусов; А — число всех возможных вариантов распределения автобусов; q^(а(, t) — интенсивность транспортного обслуживания пассажиров на остановке а маршрута ?, если на маршрут ? выделено я, автобусов. Интервал времени (tQ, Т) — это интервал, в течение которого планируется распределение транспортных средств для перевозки пассажиров.

Рассмотрим алгоритм решения полученной нелинейной задачи дискретной оптимизации, используя схему метода ветвей и границ.

1. Выбирается начальное допустимое распределение автобусов, заданное вектором а = (я,,..., ат), задающее распределение автобусов

по маршрутам и вычисляется значение функционала (6.1)

при заданном распределении автобусов по маршрутам. Получена верхняя оценка оптимального решения. Значение функционала (6.1) при начальном распределении транспортных средств далее будем называть «рекордом».

2. Вычисление нижней оценки конструируемого решения для любого момента f производится по формуле

Первое слагаемое правой части формулы (6.4) задает фактические потери времени пассажиров на ожидание транспортного средства до момента времени t'.

Второе слагаемое задает предполагаемые потери времени пассажиров на ожидание транспортного средства, перевозка которых будет осуществлена в период времени (t', Т), при условии неограниченной вместимости транспортных средств. Уточнение нижней оценки производится через интервалы времени, кратные периоду следования автобусов на маршрутах, и сравнивается с «рекордом», пока не будет реализована одна из альтернатив:

  • а) получено решение, у которого значение функционала (6.1) меньше, чем у «рекорда». В этом случае значение функционала (6.1) для нового решения назначается «рекордом» и осуществляется переход к пункту 2, если не все варианты распределения транспортных средств по маршрутам исследованы, и выход из алгоритма, если исследованы все варианты распределения транспортных средств;
  • б) нижняя оценка исследуемого решения на момент времени /' оказалась выше значения «рекорда». В этом случае осуществляется выбор нового варианта распределения транспортных средств и переход к пункту 2.

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

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

Введем следующие обозначения:

— объем пассажиров, прибывших на остановку а маршрута ?; объем пассажиров, прибывших на остановку а маршрута ?, следующих до остановки (3.

Очевидно, выполняется соотношение

Обозначим через и соответственно нижнюю и верхнюю границы величины U^; Bfa — объем выхода пассажиров из транспортного средства на остановке ос маршрута L

Ниже приводятся формулы вычисления верхних и нижних оценок величины на основе информации о входе-выходе пассажиров:

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

Определение 6.1. Задача (6.1)—(6.3) устойчива при изменении корреспонденции пассажиропотоков на маршруте I, если существует такое е > 0, что при уменьшении Uia не более чем на ? для всех а, 3, за исключением

и сохранении соотношения (т.е. увеличении

l/щ на величину z(mf - а + 1)) сохраняется вектор а = аа*т, задающий оптимальное распределение автобусов по маршрутам и значение функционала (6.1).

Определение 6.2. Задача (6.1)—(6.3) устойчива по структуре решения при изменении корреспонденции пассажиропотоков на маршруте ?, если существует такое ?, что при уменьшении не более чем на ? для всех ос, 3, за исключением , сохраняется вектор а = = a*v ..., а*т, задающий оптимальное решение задачи. Очевидно, что для устойчивости решения на маршруте ? необходимо и достаточно выполнения следующего соотношения:

где В^ — количество свободных мест в транспортном средстве для рейса j на остановке а маршрута ?; L — число рейсов; т( число остановок.

Величину еинт далее будем называть интервалом устойчивости задачи (6.1)—(6.3).

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

Здесь М — число всех возможных вариантов распределения транспортных средств по маршрутам; W(a, ?ст) — значение функционала (6.1) для оптимального распределения транспортных средств по маршрутам при уменьшении CAL на всех остановках, за исключением последней, на величину ?ст при сохранении соотношения

W(ap ?ст) — значение функционала (6.1) для варианта а( (/=1, 2, ..., т) распределения автобусов по маршрутам.

Очевидно, что если задача (6.1)—(6.3) устойчива, то она устойчива и по структуре решения.

Учитывая монотонное неубывание функционала (6.1) при возрастании ?ст, легко видеть, что достаточным условием того, чтобы ?ст > 0, является единственность решения а*, минимизирующего значение функционала (6.1). Отсюда, в частности, следует, что необходимым условием того, чтобы ?ст = 0, в задаче (6.5)—(6.7) будет неединственность решения задачи (6.1)—(6.3). Легко понять, что решение задачи (6.5)—(6.7) при изменении корреспонденции пассажиропотоков в смысле определения 6.2 не может быть больше

Исходя из определения необходимым условием того, чтобы

является совпадение решения задачи (6.1)—(6.3) для корреспонденции Uia с решением для корреспонденции, у которого

для всех

Учитывая конечное число всех вариантов распределения автобусов по маршрутам и монотонное возрастание функционала (6.1) при изменении корреспонденции пассажиров, получим следующее утверждение.

При изменении корреспонденции пассажиров от 0 до minUea интервал изменения корреспонденции может быть разбит на конечное число отрезков так, что каждому отрезку, в котором изменяется ?ст, будет соответствовать один и тот же вектор а., задающий оптимальное распределение автобусов по маршрутам.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >