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

  Переведём задачу на формальный язык. Обозначим каждый участок сети между двумя соседними  пунктами А_i и Аj числом x_ij= 1, если он является звеном выбранного маршрута движения из А_i в А_m, и x_ij=0, если он не входит в этот маршрут. Тогда задача отыскания кратчайшего пути из А_i в А_m сводится к выбору чисел x_ij (i, j = 1, 2, …, m), при которых достигает минимума линейная форма

  

,                                                

  при условии

  

   i=2, 3, …, m-1;

  

;

   ;

  

  0 ≤ x_ij ≤1, i, j =1,2………….m 

  Линейная  форма определяет длину маршрута между начальным и конечным пунктами. Условия означают, что для любого 0≤пункта маршрута А_i, исключая начальный и конечный, число дорог, входящих в этот пункт, равно числу дорог, выходящих из него. Поскольку l_ji>0 для всех I и j, условия вместе с требованием минимизации линейной формы означают, что из каждого пункта Аi (i=2, 3, …, m -1) выходит не более одной дороги. Условия фиксируют тот факт, что количество дорог, выходящих из начального пункта маршрута, Аi превышает на единицу число дорог, входящих в этот пункт. Аналогично условия указывает на то, что в последний пункт А_m входит на одну дорогу больше, чем выходит. Условия вместе с условиями и требованием минимизации линейной формы означают, что в каждый пункт маршрута входит ровно одна дорога и из каждого пункта маршрута исходит ровно одна дорога. Наконец, условия требуют, чтобы все  x_ij были равны нулю или единице. В целом, соотношения представляют собой определение кратчайшего пути на сети дорог между двумя заданными пунктами, т.е. аналитическую модель рассматриваемой задачи.

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

    Процесс определения кратчайших расстояний между пунктами модели транспортной сети рассмотрим также на конкретном примере. 

  6. Методы планирования  перевозок по сборно-развозочным  маршрутам 

1. Проектирование  развозочных маршрутов методом перебора вариантов.

 

  Решение задачи рассматривается на конкретном примере. 

  Пример. Имеется заявка на перевозку груза с условиями.

  

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

  Потребность в грузе первого пункта q₁=2 т; второго пункта – q₂=1 т; третьего пункта – q₃=1 т.

  Известны  адреса клиентов, поставщика и их взаимное расположение; грузы транспортно  однородны; затраты времени на погрузку–выгрузку 1 т груза τпв=0,1 т/ч; среднее время  на нахождение в пункте маршрута t₃=0,1 ч; условия эксплуатации – город, V_т=25 км/ч. Взаимное расположение поставщика и потребителей и расстояние между пунктами представлены на рис. 8.2. 

  Решение задачи 

  Число перестановок из w пунктов завоза (вывоза), включаемых в маршрут по w  пунктам:

                                                            Pw = w!,                                                 

  где w! – факториал целого положительного числа w, который равен произведению: w! = 1·2·3…· w. При трех пунктах груза количество возможных маршрутов М = w! = 3! = 1·2·3 = 6, таким образом, возможны шесть маршрутов доставки груза из пункта А (см. табл. 8.1). Выбор маршрута осуществляется по критерию «минимум затрат», чему соответствует минимум пробега. При наличии двух и более маршрутов одинаковой протяженности цели системы соответствует минимум грузооборота на маршруте. Результаты расчета пробега и грузооборота представлены в табл. 8.1. 
 

                                                                                                      Таблица 8.1

    Результаты расчета пробега и грузооборота в развозочной системе 
 

 
 

  Принимаем для дальнейшего проектирования системы маршрут №1-А-В₁-В₂-В₃-А, поскольку ему соответствует минимальный грузооборот. Расчет результатов функционирования автомобиля в системе выполним, используя модель развозочной системы. Результаты представлены в табл. 8.2.

                                                                                                          

    Таблица 8.2 

    Результаты функционирования автомобиля в системе 

 
 

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

      
 

2. Проектирование  маршрутов методом сумм.

 

  Пример 8.2. Имеется заявка на перевозку груза с условиями: необходимо доставить груз шести потребителям; потребность в грузе q_ж = 600 кг; q₃ = 200 кг; q_и = 400 кг; q_к = 500 кг; q_л = 400 кг; q_м = 400 кг.

  Известны  адреса клиентов, поставщика и их взаимное расположение; грузы транспортно-однородны; затраты времени на погрузку-выгрузку 1 т груза τпв=0,1 т/ч; среднее время на нахождение в пункте маршрута t₃=0,1 ч; условия эксплуатации – город, V_т=25 км/ч. Взаимное расположение поставщика и потребителей представлено на рис. 8.3. 

  Решение задачи

  Пусть все пункты, указанные на рис. 8.3, называются вершинами сети, а линия, соединяющая две соседних вершины, - звеном. Незамкнутая сеть, связывающая две и более вершины с минимальной суммарной длиной всех соединяющих их звеньев, называется кратчайшей связывающей сетью. Данная сеть находится следующим образом. На транспортной сети (см. рис. 8.3) находят наименьшее звено. В данном случае звено К-Л = 2 км. Затем рассматривают все звенья,  связанные с одной из  своих вершин  с выбранным звеном,  т. е. звенья

   К - М = 5;  К - И = 2;  К - 3 = 6;  К - Ж = 7;  Л - Ж = 6;  Л - И = 3;  Л - З = 7. Из них выбирают звено с наименьшим расстоянием К - И = 2. Далее рассматриваются звенья, связанные с вершинами полученной линии И-К-Л, и из них выбирается наименьшее. При этом нельзя выбирать звено, соединяющее две ранее включенные в сеть вершины. Таким звеном является И-Л, несмотря на то что оно наименьшее из всех, связанных с выбранной сетью И-К-Л одной из вершин, его нельзя включить в кратчайшую связывающую сеть. Другими звеньями, связанными  своими  вершинами с уже выбранной сетью, являются звенья М-К, З-К, И-З, И-Ж, И-А, И-М, Л-Ж, Л-З, звено И-З имеет наименьшее расстояние, равное 4, и в этом случае получим сеть З-И-К-Л.

  Далее опять рассматривают все звенья, связанные с вершинами полученной сети З-И-К-Л. Звенья И-Ж и К-М имеют одинаковую длину, равную 5, берем любое, например К-М. Получаем сеть З-                                       И-К-М (К-Л). Далее опять рассматривают все звенья, связанные с вершинами полученной сети, и из них выбирают наименьшее и так далее до тех пор, пока не будет выбрана сеть. На рис. 8.4 представлена кратчайшая связывающая сеть рассматриваемого примера, где также проставлена потребность пунктов в грузе (+).

  Далее все пункты маршрута, начиная с А, связываются такой замкнутой линией, которая соответствует кратчайшему пути объезда этих пунктов. Первоначально при использовании метода сумм строится таблица, называемая симметричной матрицей. Для маршрута АЖЗИКЛМ она приведена в табл. 8.3.

                                                                                                                  Таблица 8.3 

                            Симметричная матрица  для маршрута АЖЗИКЛМ

 

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

  ∆_кр =  L₁₃ + L₂₃ – L₁₂,

    

   Можно утверждать, что полученная последовательность объезда пунктов маршрута дает меньший  или весьма близкий к наименьшему путь движения. На рис. 8.5 представлены схемы движения автомобилей по маршрутам АЖИЛКМЗА  и АЗМКЛИЖА. Результаты расчета грузооборота представлены в табл. 8.4.

                                                                                                          Таблица 8.4

    Результаты расчета  

 

  Принимаем   для  дальнейшего   проектирования   системы   маршрут         №1 - АЖИЛКМЗА, поскольку ему соответствует минимальный грузооборот. Расчет результатов функционирования автомобиля в системе выполним, используя модель развозочной системы. Результаты представлены в табл. 8.5. 
 

                                                                                                             Таблица 8.5 

    Результаты функционирования автомобиля в системе 

 

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