Моделирование транспортных процессов и систем

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

  Из всех вышеуказанных  факторов от качества сменно-суточного  планирования на автотранспортном предприятии  в наибольшей степени зависит  коэффициент использования пробега.

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

  Эта задача маршрутизации  состоит в следующем.

   Разнородный груз сосредоточен в пунктах отправления  А₁, А₂…А_i…А_m в количествах соответственно а₁, a₂…a_i…a_m единиц. Его необходимо доставить в пункты назначения В₁, В₂…В_j…В_n в количествах в₁, в₂…в_j…в_n соответственно.

         Объём перевозок  из i-го пункта отправления в j-й  пункт назначения составляет q_ij единиц  и известен для всех пунктов.

        Расстояние от i-го пункта отправления до j-го пункта назначения равно l_ij и известно для всех комбинаций ij.

        В процессе выполнения перевозок  в пунктах назначения В₁, В₂…В_j…В_n после разгрузки автомобилей будет образовываться порожняк в количествах   в₁¹,  в₂¹…в_j¹…в_n¹ единиц.

        Этот порожняк необходимо подать  под очередную загрузку в пункты  отправления А₁, А₂…А_i…А_m в количестве   а₁¹, а₂¹…а_i¹…а_m¹.

        Величины а_i, в_j, q_ij, a_i¹, в_j¹ могут выражаться либо в тоннах, либо в ездках автомобиля. Для существа задачи это безразлично, тем более что тонны всегда можно перевести в ездки. Однако с методической точки зрения удобнее пользоваться ездкой автомобиля с грузом и без груза.

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

      По  смыслу рассматриваемой задачи  всегда имеет место условие

  в_j¹ = в_j= ,   где   j=1, 2…n;

  a_i¹ = a_i = ,   где   i=1,2…m.

        Расстояние от В_j до А_i, равное l_ji=l_ji, известно для всех сочетаний i, j.

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

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

       Таким образом, требуется составить  такой план перевозок (маршруты  движения автомобилей и сменные  задания водителям), который обеспечит  выполнение заданных объёмов  перевозок с наименьшим холостым  пробегом автомобилей.

 
 

  5. Методы определения  кратчайших расстояний  перевозок 
 

1. Табличный метод  определения кратчайших расстояний.

 

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

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

  G = (x, y). 

   Каждому ребру графа  приписано некоторое число (длина  ребра) lij ≥ 0. Тогда любая цепь μ, составленная из нескольких ребер, характеризуется длиной l_μ. Требуется для двух произвольных вершин найти такой путь, чтобы его длина была наименьшей:

  

  Рассмотрим  решение задачи с нахождением  кратчайшего пути на конкретном примере. 

  Пример. Дана модель участка транспортной сети экономического региона (рис. 6.1). Требуется табличным методом определить кратчайшее расстояние между пунктами К₁ и К₁₄.  

  Решение:

  Аналитическая модель решаемой задачи имеет вид 

  

.

  Составляем  матрицу (табл. 6.1) решения (исходный вариант) и заносим в нее расстояние от каждой вершины отсчета К_i (i=1,2,3,…14) до всех вершин К_i , соседних с ней.

  После занесения в рабочую часть  матрицы величин  видно, что имеется , но нет величины . Тем самым учитывается, что на ребре К₄К₅ наложено ограничение – одностороннее движение и передвижение возможно только со стороны К₄ (см. рис. 6.1).

  При дальнейших расчетах пользуются следующим правилом.

  Каждой  вершине К_i соответствует некоторое число , характеризующее расстояние  от вершиныК₁  до вершины К_j.

  Вершине К_j = К_i, т.е. точке, от которой измеряются расстояния, соответствует . Соответственно и Получаем  в строке К₁ и в столбце К₁ величины расстояний

  Затем, начиная с первого столбца (К_i) i=1, рассматриваем клетки с записанными расстояниями (в данном примере клетки К₁К₂ и клетки К₁К₄), для которых известно и равно нулю. 
 

  

    

  Для определения  (для строк К₂ и К₄) используют правило                              

  

.

    Согласно для строки К₂ имеем ; для строки К₄ имеем =0+3=3, что и заносится в клетки столбца , а в силу связанности транспортной сети для рассмотренных соседних вершин имеем , поэтому можно заполнить две клетки в верхней строке (К₂ и К₄).

  Получив значения в столбцах К₂ и К₄, по клеткам К₂ , К₃ и К₄ , К₆, где записаны  величины , аналогично находим для строк К₃ и К₆.

   Для ; .

   И опять в силу связанности  сети заполняем две клетки в верхней  строке (К₃ и К₆).

  Аналогично  находим  для строк К₅ , К₇, К₈ и столбцов К₅ , К₇ и К₈, но после нахождения столбцов К₇ и К₈ в строке К₉ оказались две клетки  с заполненными  (К₇, К₉ и К₈, К₉), для которых уже известно. Поэтому для того, чтобы найти для строки К₉, используется другое правило: если в j-й строке имеются несколько клеток с указанными величинами и для этих клеток уже известно, то определяется меньшей суммой значений ( + ) для всех известных , т. е.

  

.

   Применяя  данное правило для строки  К₉, получаем 

  

         

  Минимальная величина Это и будет  строки К₉, и опять .

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

  Определив все значения и , рассматриваем заполненные клетки матрицы. Начиная со столбца К₁, находим для них разности ( - ) и сравниваем эти разности  с расстоянием , записанным в клетке.

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

  

  Затем исправляется величина в соответствующем столбце матрицы.

  Для столбца  К₁:

   

  

   Расчеты показывают, что в столбце  К₁ соблюдается условие оптимальности и изменять величины и нет надобности. Если выполнить расчеты для всех столбцов, то окажется, что условие оптимальности нарушено только в столбце К₁₁, где для клетки К₁₁ и К₁₀ имеем Поэтому внести изменение согласно формуле (6.2):

  

                                                            

  Вместо  прежнего значения  в матрице записываем В результате внесенного изменения получаем матрицу "Улучшенный  вариант" (табл. 6.2).

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

  В соответствии с высказанным положением в рассматриваемом  примере необходимо проверить условие  оптимальности только для клеток столбца К₁₀ (К₁₀К₉, К₁₀К₁₁ и К₁₀К₁₄), для которых   стало 25, а было 33, используя правило, что значения и не меняются, если - £ , проводим вычисления и получаем

   

;

   

   

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

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

  

  Задача  решена. Получена матрица оптимального варианта расстояний (табл. 6.2).  Кратчайший   путь  между пунктами К₁…К₄ определен, составляет 31 км и проходит через пункты К₁-К₄-К₆-К₇-К₁₁-К₁₂-К₁₃-К₁₄. 

2.  Определение  кратчайших расстояний по транспортной  сети  методом потенциалов.

 

  Пусть задана транспортная сеть, состоящая из пунктов А₁, А_2…, А_i…, А_m и дорог, соединяющих эти пункты между собой. Длины участков дороги между каждой парой соседних пунктов А_i Аj известны и равны l_jj. Если два соседних пункта  А_i и Аj непосредственно не соединены между собой участком дороги, то принимаем l_jj= ∞. Из начального пункта А₁ в конечный пункт А_m можно попасть по большому числу маршрутов, проходящих через разные промежуточные пункты. Требуется найти среди этих маршрутов путь наименьшей протяженности [13].