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

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

 

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

 

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

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

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

G = (x, y).

 

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

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

Пусть задана транспортная сеть, состоящая из пунктов А1, А2…, Аi…, Аm и дорог, соединяющих эти пункты между собой. Длины участков дороги между каждой парой соседних пунктов Аi Аj известны и равны ljj. Если два соседних пункта  Аi и Аj непосредственно не соединены между собой участком дороги, то принимаем ljj= ∞. Из начального пункта А1 в конечный пункт Аm можно попасть по большому числу маршрутов, проходящих через разные промежуточные пункты. Требуется найти среди этих маршрутов путь наименьшей протяженности.

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

,                                                  (4)

при условии

   i=2, 3, …, m-1;              (4)

;                                          (6)                         

;                                      (7)

                                                         

                                                                     xij ≤1, i, j =1,2………….m                            (8)

 

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

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

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

Общая вычислительная схема применительно к данной задаче следующая. В специальную таблицу типа «шахматной» заносят расстояния lji от каждого пункта Аi  ((i=1, 2, …, m ) до всех соседних с ним пунктов Аi  ((i=1, 2, …, m ). После этого для каждого пункта Аi и Аj рассчитывают индексы ui и υj следующим образом. Индекс ui принимают равным нулю (ui =0). Затем по порядку, начиная с первой строки таблицы, рассматривают клетки с заполненными lji . Если для некоторой заполненной клетки (I, j) индекс ui уже известен, а υj - ещё нет, то определяют υj по формуле

 υj= ui+ lji  .                                               (9)

Если при определении очередного υj в i-м столбце имеется более одной клетки с записанными lji и известными ui , то принимают

   υj = min (ui+ lj) .                                      (10)

Найденные значения υj записывают в соответствующие клетки вспомогательной строки, а также в клетки вспомогательного столбца, исходя из правила: u1= υ1, u2= υ2, … um= υm. После определения всех индексов υj и ui проверяют оптимальность данного решения, сравнивая все lji с их разностями (υj- ui). Если для всех заполненных клеток соблюдается условие

lij ≥υj- υj,                                                (11)

то решение оптимально и каждое найденное число υj дает кратчайшее расстояние от пункта А1 до соответствующего пункта Аi, до соответствующего пункта Аj (i=1,2,…m). При наличии хотя бы одной клетки с величиной lij <υj- ui решение неоптимально и вычисления необходимо продолжить.

Предположим, что в клетке Аi n Аj n нарушено условие оптимальности (6.10), т.е.

li njn< υ i n- ui n.

В этих условиях необходимо изменить решение следующим образом. Индекс υ j n заменяют индексом υ` i n , величину которого определяют по формуле

υ i n= υ i n+ li njn.

На каждой итерации корректируют индексы υj у всех клеток с lij< υj- ui, после чего решение снова проверяют на оптимальность. Вычисления повторяют до тех пор, пока в таблице не будет выполнено условие оптимальности (11).

При определении кратчайших расстояний от пункта А2 до всех остальных принимают u2=0, после чего находят все индексы и выполняют все описанные выше вычисления. При определении кратчайших расстояний от пункта А3 до всех остальных принимают u3=0 и т.д.

 

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

 

6.1. Классификация задач.

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

При этих перевозках автомобили функционируют на развозочных, сборных, развозочно-сборных (далее развозочных) маршрутах в составе комплекса различных автотранспортных систем (РСТС). Используется классификация систем по комплексу признаков (выполняемая функция, конфигурация системы, мощность грузопотоков, количество пунктов погрузки-выгрузки и подвижного состава и другие). Все РСТС делятся на 9 видов.

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

2. Сборная Sс – система, состоящая из множества пунктов погрузки, пункта разгрузки, транспортных связей между ними и одного автомобиля, осуществляющего доставку груза. Технологическая схема доставки груза представляет собой сборный маршрут.

3. Развозочно-сборная Spc – система, представляющая собой совокупность предыдущих транспортных систем, включающая в себя множество пунктов погрузки и разгрузки, транспортных связей между ними и один автомобиль, осуществляющий доставку груза. Технологическая схема доставки груза представляет собой развозочно-сборный маршрут.

4. Простая Sп – система, состоящая из множества Sp (Sс или Spc), в которой осваиваются, по сравнению с предыдущими системами, большие грузопотоки.

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

5. Развозочная с центром  погрузки Sрц – система, состоящая из совокупности Sp, в которой осваиваются, по сравнению с Sp, большие грузопотоки.

Пример функционирования Sрц - развоз газа в цистернах; развоз стеновых панелей с домостроительного комбината потребителям, раствора и другие.

6. Сборная с центром  разгрузки Sсц – система, состоящая из совокупности Sс, в которой осваиваются, по сравнению со сборной системой, большие грузопотоки.

Пример функционирования Sсц – сбор и вывоз бытовых отходов на мусороперерабатывающий (сжигающий) завод, сбор и вывоз строительного мусора по системе «несменяемых» контейнеров.

7. Комбинированная первого  вида Sк1 – система, состоящая из центрального пункта с несколькими фронтами погрузки (разгрузки и погрузо-разгрузки) и множества предыдущих транспортных систем (кроме простой системы Sп), в которой по условиям перевозок работают несколько единиц или даже десятков автомобилей.

8. Комбинированная второго  вида Sк2 – система, состоящая из центрального и множества периферийных пунктов погрузки и разгрузки, транспортных связей между ними и автомобилей, осуществляющих доставку груза.

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

9. Город-регион Sr-p– это система, состоящая из множества РСТС, приведенных выше, в которой по условиям перевозок работают несколько десятков и даже сотен автомобилей автотранспортного предприятия.

             Для грузовых перевозок можно  отметить следующие: метод перебора  вариантов маршрута; метод сумм; метод «ветвей и границ»; Кларка-Райта  и другие. Для пассажирских перевозок - метод Б.Л. Геронимуса и другие.

Необходимость учета при проектировании РСТС многочисленных требований и ограничений, часто противоречащих друг другу, особенностей функционирования реальных РСТС; выполнение значительного количества вычислительных процедур приводят к необходимости использования ЭВМ. Это обусловливает необходимость разработки обобщенного алгоритма проектирования РСТС, учитывающего особенности решения задачи проектирования для различных РСТС. Блок-схема алгоритма проектирования РСТС представлена на рис. 2.

Приведем краткое описание блоков алгоритма (рис. 2).

1. Получение исходной  информации

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

2. Закрепление потребителей  за поставщиками

Решение задачи производится по транспортно-однородным грузам с равными потребительскими свойствами, когда количество поставщиков (потребителей) более одного.

3. Определение кратчайших  расстояний

Обслуживание потребителей должно осуществляться по заранее спланированным маршрутам, спроектированным на основе оперативной

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 2. Блок-схема алгоритма проектирования развозочных автотранспортных систем: М – количество маршрктов; ─− - направление вычислений информации по кратчайшим расстояниям, обеспечивая тем самым минимальные затраты потребителей услуг автомобильного транспорта.

 

 

4. Маршрутизация

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

5. Блок сравнения количества  маршрутов

Если условие выполняется, то далее работает блок 6. Если не выполняется, то далее работает блок 7.

6. Блок установления функции, реализуемой в транспортной системе, и выбор математической модели  транспортной системы для решения  задачи блока 11.

7. Блок сравнения условий  работы автомобилей

Если условие не выполняется, то далее работает блок 8. Если условие выполняется, то далее работает блок 9.

8. Набор плановых заданий

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

9. Блок установления функции, реализуемой в транспортной системе, и выбор  математической  модели  транспортной  системы  для  решения  задачи  блока 11.

10. Составление графика (расписания) работы автомобилей

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

11. Расчет результатов функционирования автомобилей в РСТС Произво- дится с применением модели функционирования конкретной РСТС.

 

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

 

Теория массового обслуживания является одним из разделов теории вероятностей. В последние годы она получила развитие и выделилась в самостоятельный раздел математики. Основоположником теории массового обслуживания является датский ученый А.К. Эрланг. Его первая работа по этому вопросу была опубликована в 1909 году.

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