Задача планирования распределения транспортных ресурсов в условиях нерегулярного поступления заказов на обслуживание

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

Таким образом, возникает необходимость частого решения специфических задач планирования загрузки транспортных ресурсов, причем в условиях дефицита времени, что затрудняет использование известных моделей и методов, которые обычно не учитывают новых условий и требуют значительного времени для вычислений [2].

Рассмотрим систему с и объектами х₁, х₂, .., х_и и т транспортными средствами.

Под маршрутомj'-го транспортного средства l k j j = 1, 2, .,т будем понимать последовательность к. элементов xvx ₂,..., x_k j в том порядке, в каком транспортное средство их обходит.

Под выполнимым маршрутом, в зависимости от решаемой задачи, может пониматься условие непрерывной работы всех объектов маршрута, это может быть условие ограничения среднего времени ожидания или требование обслуживания таким образом, чтобы объекты с высоким приоритетом не простаивали и другое. В общем случае, условие выполнимости маршрута можно записать в виде некотор ого ограничения на элементы маршрута ф ( l j ) >  0, j = 1, m .

Введем в рассмотрение множество L всех выполнимых маршрутов системы. Естественно потребовать, чтобы маршруты выбирались из L таким образом, чтобы все объекты системы были обслужены. Тогда распределение транспортных средств системы можно представить в виде задачи оптимизации: m ^ k j ^ max, j = 1

ф ( l k j .) >  0, j = 1,2,..., m ,                 С ¹ )

1 / . e L, j = 1,2,..., m .

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

Каждый объект х, i= 1,2, .., и в некоторый момент времени характеризуется двумя числами (t, i), где t. время достижения транспортным средством объекта х, i . доступное время ожидания. Для производства это время, в течение которого работа оборудования не прерывается благодаря имеющемуся запасу сырья и комплектующих. Для сети торговых точек это время бездефицитной работы объекта. Для скорой помощи это нормативное время, в течении которого пациент с его заболеванием может ожидать приезда машины.

Точки х₁, х₂, .,х_к (к <  и) образуют выполнимый маршрут 1_к длины к, если для всех i, i = 2,3, ., к выполняется условие

Т i >1л .                    (2)

5 = 1

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

Для выполнимого маршрута 1 = (х1, х2..., хк) введем k величину Ak = Тk -^tj, время, которое транспортное j=1

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

Выполнимый маршрут х_р х₂, ., х, х . ₊₁, ., х_к допускает расширение в точке х, если найдется такая точка y(t_y, i), что маршрутх₁, х₂, ., х . ,у, х . ₊₁, ., х_к будет выполнимым.

В этом случае точка y(t_y, i_y) должна удовлетворять условиям

^Т y >lL ts ⁺ t y , s = 1

p ty <Т Р -^ ^ ’ Р = j + 1’-’ k.

s = 1

Точку y(t_y, l_y) будем называть вписанной в маршрут 1_к в точке./.

Подмаршрутом выполнимого маршрута 1_к длины s называется такой выполнимый маршрут 1_s =y_py₂, .,y_s, s < к, который получается из него путем удаления (к - s)

точек.

Любой подмаршрут маршрута 1_к можно расширить до маршрута длины к, так как существует по крайней мере один маршрут длины к, это - 1_к.

Множество всех выполнимых маршрутов обозначим L. Lk множество выполнимых маршрутов длины к, q и Lk = L, q < n.

k = 1

Выполнимый маршрут 1_к+1, полученный расширением маршрута 1_к на одну точку, называется соседним маршрутом для 1_к. Множество соседних маршрутов для 1_к обозначим L_k+1, L_k+X с L_{k + 1}.

Множество точек, каждую из которых можно вписать в маршрут 1_к до образования соседнего маршрута, обозначим У_к, Y_k с ( X \ X_k ) , где Х_к - множество точек маршрута 1_к.

Выполнимый маршрут 1_k = x 1 , x ₂,..., x_k будем называть монотонным маршрутом порядка к, если для всех l k e L_k таких, что A _k < A _k , следует Y_k с Y_k .

Монотонный маршрут 1к является монотонным, если любой подмаршрут этого маршрута будет монотонным.

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

Рассмотрим простой случай, когда имеется только одно транспортное средство, т = 1. В этом случае задача сводится к поиску максимального выполнимого маршрута 1к, что приводит к решению следующей оптимизационной задачи:

k ^ max,

Т i > ^ к , i = 1,2,..., k .

5 = 1

Пусть решением задачи (4) является выполнимый маршрут максимальной длины /к Так как выполнимых маршрутов одинаковой длины может быть несколько, то и маршрутов с максимальной длиной может быть больше чем один. Обозначим множество маршрутов максимальной длины Q_p.

Выберем маршрут 1 ° = 1₂ (длиной к = 2), 1₂ = х,, х, для которого

A = max( T j - ( t i + t j )), i , j = 1,2,..., n i # j .

• i ,    j

Для маршрута 1_к (к > 2) рассмотрим соседние маршруты, образованные с помощью точек множества У_к. Из всех соседних маршрутов выберем маршрут 1_к+1, для которого А _к+1 = A * , где

А = max A y .                  (5)

y ∈ Y k

Теорема. Если множество Qp решений задачи (4) содержит хотя бы один монотонный маршрут любого по- рядка, то локальный поиск из точки 12 с выбором соседнего маршрута по системе окрестностей 2к, к = 3,..., p, по свойству (5) дает точное решение задачи (4).

Пусть маршрут l _p = x 1 , x ₂,..., x _p , l_p e Q_p , является монотонным маршрутом любого порядка. Покажем, что маршрут 1⁰ с величиной А = А ₂ последовательным расширением можно привести к длине_р. Выделим из оптимального маршрута 1* любой подмаршрут 1* длины к, к= 2, 3, .,р для которого вычислим величину А*. В этом случае выполнится А k < А _k , так как А _к максимальное для всех выполнимых маршрутов длины к. Так как маршрут 1* монотонный, то выполнится У k c Y_k , у Р , Y_k - множества точек, которые можно вписать в маршруты /_к * и 1_к. Расширение маршрута 1_к * существует, так как это подмаршрут маршрута длины/). И тогда У_к не пустое множество и, следовательно, существует расширение маршрута 1_к.

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

Пусть требуется на множестве объектов х₁,х₂, .., х_и, каждый из которых характеризуется двумя числами (7, т ), найти выполнимый маршрут максимальной длины. Введем в рассмотрение булевы переменные: 8„ = 1, если объект i обслуживается ранее объекта j, 8 = 0 в противном случае, i,j =1,2,..., и.

Для каждого объекта введем величину z, z_ = 1, если объект/' будет обслужен и z_ = 0в противном случае,/ = 1,2, ..., и. Тогда задачу (3) можно представить в следующем виде:

n

^ z_p ^ max, i = 1

z / ( ⁸ j + j = zp                ⁽⁶⁾

z j ^T j ^{- (} Х ⁸ iz^i + j z j .

Если z = 0, то ограничения нет, в правой части каждого ограничения суммируется время достижения объектов, уже обслуженных до/-го. Второе ограничение гарантирует выполнимость маршрута.

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

{ l k j }, ^j = 1, ²,..., m ,

X_k^ Xs = ® ,               ⁽⁷⁾

• i ,    s = 1,2,..., m , i ^ s .

Задача распределения транспортных средств (1) по выполнимым маршрутам сводится к следующей постановке. Найти такую систему маршрутов { l j }, j = 1,2,..., m , чтобы m ^ k j ^ max, j = 1

т i - ^ t S , i = 1,2,..., k j ,                (8)

s = 1

j = 1, 2,..., m .

Под системой маршрутов системы (7) будем понимать систему {lp.}, pj < kj, j = 1, 2,..., m . Из системы маршрутов (7) выберем такую подсистему маршрутов {Ipj}, pj < kj, j = 1, 2,..., m, чтобы из точек этой подсистемы можно было составить один выполнимый маршрут 1к, m k = ^ pj. Из оставшейся системы опять выберем такую j=1

подсистему. (Возможно на некоторых шагах для некото-р^Др)0).

Тогда окончательно получим, что систему маршру тов можно представить как совокупность нескольких не-пересекающихся одномерных выполнимых маршрутов qm

• l s . , l s ₂ ,..., l q , Z S i = £ k j . i = 1          j = 1

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

На множестве-^решим одномерную задачу, т. е. найдем максимальный маршрут 1_к. Все эти точки можно распределить по т маршрутам, так как всегда можно получить т подмаршрутов из исходного маршрута. На оставшемся множестве точек опять решим одномерную задачу и получим оптимальный маршрут 1_к1. Теперь можно распределить из этого маршрута) точек, причем) <  к₁. И так далее. В итоге либо получим, что все точки исходного множества распределены либо некоторый одномерный маршрут, точки которого уже нельзя будет распределить по маршрутам.

Решение задачи (1) сводится к следующему На каждом шаге 5, на множестве X_k , X_k c X находится оптимальный маршрут 1_к, точки которого принадлежат множеству X^s_k . Для каждого маршрута системы маршрутов (7) I p j , j = 1, 2,..., m из множества X^s_k ищем точки, расширяющие этот маршрут таким образом, чтобы полученная система маршрутов была максимальной. В итоге получим систему маршрутов I j ,/ = 1, 2,., т. Поиск осуществляем таким образом, чтобы выполнялось

m

^ k j ^ max, j = 1

X S c l k , j = 1,2,..., m ,                 (9)

l^J_k c L , j = 1, 2,..., m .

Для решения задачи (9) можно предложить следующее.

Маршрут 1_к является q соседним для маршрута 1, если точка x_q, q e {1, k } маршрута 1_k может быть вписанной в маршрут 1_р.

Маршрут 1_к может одновременно являться q соседним для нескольких маршрутов системы маршрутов.

Обозначим А q j максимальный запас времени для маршрута/, (/ = 1,2,..., т) при вписывании точкиx_q в этот маршрут.

А^ = тах{ А _q }, j = 1,2,..., m .           (10)

j j

Из условия (10) определим номер маршрута) для которого маршрут 1_к будет q соседним.

Просматривая все q, можно либо для каждого q определить маршрут, в который эта точка может быть вписа- на наилучшим образом, либо для нее не существует маршрута, в который она могла бы быть вписанной. Таким образом, для каждогоу-го маршрута найдется множество ф, q е {1, k} соседних маршрутов D, из которого определится наилучшая точка xq , которая и будет вписана в этот маршрут. Из lk удаляются вписанные в систему маршрутов точки и точки, которые никуда не вписались, и из полученного нового маршрута аналогичным образом формируются следующие соседние маршруты. Поиск осуществляется до тех пор, пока либо все точки маршрута 1к будут вписанными в систему, либо больше не удается выделить соседние маршруты. В этом случае получим расширение системы, которое будет наилучшим.

Таким образом, решение задачи с m транспортными средствами сводится к многократному решению задачи одномерного случая.