<< Пред.           стр. 9 (из 10)           След. >>

Список литературы по разделу

  Для решения поставленных задач в транспортной логистике используются следующие методы и модели:
 1. модели выбора перевозчика;
  2. маршрутизация перевозок (транспортная задача, задача коммивояжера и др.);
  3. модель "точно - во - время";
  4. экономико-математическая модель макрологистической системы (производственно-транспортная задача);
  5. модели "производство - транспорт - потребление" и др.
  При решении задач по оперативному планированию грузовых автомобильных перевозок основными экономико-математическими моделями являются модели транспортной задачи и задач маршрутизации. Развитие систем доставки грузов показывает, что дальнейшая интенсификация процесса перевозки возможна только за счет внедрения принципа фиксированного времени доставки грузов потребителям, то есть применения логистического принципа "точно - во - время".
  С точки зрения организации перевозочного процесса возможны три основные схемы, с которыми сталкиваются автотранспортные предприятия (табл. 10.2 )
  Первая схема организации перевозок, наиболее простая с точки зрения планирования, "один - к - одному" не требует от автотранспортного предприятия решения ни транспортной задачи, ни задачи маршрутизации.
  Планирование деятельности автотранспортного предприятия в случае организации перевозки по схеме 2 ("один - ко - многим") требует решения задачи маршрутизации, которая включает в себя решение:
  - задачи "увязки" ездок, если между грузоотправителями и грузополучателями перевозка осуществляется только по маятниковым маршрутам [3; 8, 17];
 
  Таблица 10. 2
  Схемы организации перевозочного процесса
 
  Условное название схемы Схема перевозочного процесса 1. Один - к - одному 2. Один - ко - многим
  3. Многие - ко - многим
 
 
 
  - задачи коммивояжера, если между грузоотправителями и грузополучателями перевозка осуществляется только по развозочным (сборным или сборно-развозочным) маршрутам [1, 3, 8];
  - двух вышеперечисленных типов задач, если при организации перевозочного процесса используются как маятниковые, так и развозочные (сборные или сборно-развозочные) маршруты.
  При организации движения по схеме "многие - ко - многим" требуется на первом этапе решить транспортную задачу [4, 9], затем задачу маршрутизации (второй этап).
  Учитывая возможные варианты схемы организации движения автомобиля на маршруте и временные ограничения, накладываемые на перевозку, планирование на автотранспортном предприятии можно представить в виде алгоритма (рис.10.1).
  Рассмотрим более подробно блоки разработанного алгоритма. В первом блоке формируется база данных, включающая сведения о количестве транспортных средств, их типе и грузоподъемности; количестве грузоотправителей и грузополучателей; ограничениях, накладываемых грузоотправителем и грузополучателем на партию груза, которая может быть отправлена и получена соответствующим субъектом; временных ограничениях по доставке грузов в пункты назначения и их вывозу из пунктов отправления; затратах на перемещение единицы груза от каждого отправителя каждому получателю и другие. На основе полученной информации определяется схема организации перевозок (второй блок). Анализ клиентурных заявок позволяет сгруппировать их по схемам согласно табл. 10.2.
  В третьем блоке, вначале, проверяется условие: используется ли при перевозке груза схема "многие - ко - многим". Если условие выполняется, то решается транспортная задача.
  Экономико-математическая модель классической транспортной задачи в общем виде представлена формулами (1) - (10.5) [3]:
 
  , (10.1)
  , (10.2)
  , (10.3)
  , (10.4)
  , (10.5)
  где i - количество поставщиков;
  j - количество потребителей;
  ai - ограничения по предложению;
  bj - ограничения по спросу;
  cij - элементы целевой функции;
  xij - объем корреспонденции между i-й и j-й точками.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Рис.10.1 Общий алгоритм планирования грузовых автомобильных перевозок.
 
  Критерием оптимальности в транспортной задаче могут выступать минимум транспортной работы в тонно-километрах, затраты времени или стоимость перевозки.
  Для решения транспортной задачи широко применяется распределительный метод, который имеет несколько разновидностей, отличающихся в основном способом выявления оптимального решения. Наиболее известны три метода решения задач данного типа: метод Хичкова; метод Креко; модифицированный распределительный метод или метод потенциалов [8].
  В настоящее время классическая транспортная задача с успехом может быть решена с помощью программы Microsoft Excel.
  На последнем этапе третьего блока определяется, по каким маршрутам - маятниковому или развозочному (сборному или сборно-развозочному) - будет перевозиться груз от каждого отправителя к получателям, закрепленными за ним после решения транспортной задачи.
  В четвертом блоке проверяется условие: используется ли при перевозке груза схема "один - к - одному". Если условие не выполняется, то перевозка между грузоотправителями и грузополучателями осуществляется по схеме 2 ("один - ко - многим"), при которой требуется решать задачи маршрутизации.
  Математическая постановка задачи зависит от типа маршрута, по которому перевозятся грузы. В качестве примера одной из задач маршрутизации рассмотрим задачу отыскания маршрута движения автомобиля, осуществляющего развозку некоторого вида груза из некоторого базового пункта по нескольким пунктам, связанными между собой автомобильными дорогами [3]. Пусть число таких пунктов равно n и cij - расстояние от пункта i до пункта j, i,j = , где 0 соответствует базовому пункту. В каждый пункт с номером автомобиль должен побывать ровно один раз, и после развозки всех грузов ему необходимо вернуться в базовый пункт.
  Задача состоит в определении порядка посещения автомобилем пунктов с номерами так, чтобы суммарное расстояние, проходимое автомобилем, было минимальным.
  Для математической формулировки рассмотренной задачи вводятся переменные xij, которые могут принимать следующие значения:
 если автомобиль из пункта с номером i переезжает в пункт с номером j;
 в противном случае,
  где i,j = , i ? j.
  Следующая система соотношений образует математическую модель и отражает закономерность функционирования системы развозки грузов по n пунктам из базового пункта:
  (10.6)
  (10.7)
  (10.8)
 
  где Ui и Uj - произвольные вещественные значения.
  Условия (10.6) - (10.7) исключают циклы (петли) на маршруте, поскольку приезд автомобиля в каждый пункт и выезд из каждого пункта происходит ровно один раз. Условие (10.8) не допускает расщепления замкнутого из n+1 звеньев маршрута автомобиля на несколько замкнутых маршрутов меньшего числа звеньев. В качестве целевой функции в рассмотренной задаче выступает длина маршрута автомобиля, которая подлежит минимизации:
  (10.9)
  В качестве целевой функции можно рассматривать не только длину маршрута, но и связанные с ней экономические показатели. Например, затраты на перевозку, а также показатели качества обслуживания, например, время доставки грузов.
  Сформулированная задача известна как задача коммивояжера. Существует множество математических методов, позволяющих найти как точное, так и приближенное решение поставленной задачи. Среди методов, дающих точное решение, наибольшее распространение получил метод "ветвей и границ" [8].
  Приближенный метод Кларка - Райта решения задачи коммивояжера основан на понятии "выгоды", которая получается от объединения двух маятниковых маршрутов в один кольцевой. Использование этого метода дает возможность учесть расположение автотранспортного предприятия [8].
  Составленный маршрут не учитывает случайного характера составляющих перевозочного процесса; их количественная оценка может быть получена с использованием моделирования (шестой блок).
  Для внутригородской перевозки необходимо определить время на движение автомобиля с грузом (tгрi) и без груза (tхi) на i-ом участке, время на погрузку у j-ого поставщика (tпj) и на разгрузку у l-ого потребителя(tрl), включающие время ожидания погрузки и разгрузки соответственно. Сумма всех составляющих дает время в наряде (Tн) :
  Tн = ?tпj + ?tгрi + ?tрl + ?tхi (10.10)
  Логистический подход к моделированию времени на выполнение транспортных услуг требует увязки работы автомобильного транспорта с режимом работы поставщиков и потребителей груза, т.е. необходимо учитывать время начала и окончания обеденных (технологических) перерывов в работе клиентов. Поэтому формула (10.10) должна быть откорректирована и представлена в виде:
  Tн = ?tпj + ?tгрi + ?tрl + ?tх + ??j + ??l (10.11)
  где ?j - случайная составляющая, учитывающая обеденные (технологические) перерывы j-ого поставщика;
  ?l - случайная составляющая, учитывающая обеденные (технологические) перерывы l-ого потребителя.
  Включение составляющих ?j и ?l обусловлено возможными пересечениями, частичными накладками составляющих перевозочного процесса и времени обеденных (технологических) перерывов поставщика или потребителя. Так, например, погрузка автомобиля у поставщика не будет выполняться, если на момент прибытия оставшееся время до обеда меньше самого времени погрузки или если автомобиль прибыл во время обеденного перерыва. Аналогичные простои, связанные с технологическими (обеденными) перерывами, могут возникнуть и в пункте разгрузки.
  При международной перевозке общее время нахождения автомобиля в рейсе определяется по следующей формуле [13]:
  (10.12)
  где ti,i+1 - время движения между i-м и (i+1)-м пунктами;
  ?j - время оформления таможенных документов в j-м пункте;
  ?k - время погрузки, разгрузки и складирования в k-ом пункте;
  A, B, C - количество участков движения автомобиля, пунктов таможенного оформления и пунктов погрузки-разгрузки соответственно.
  Формула (10.12) расчета времени рейсе не учитывает специфику международных перевозок: во-первых, ограничением режима труда и отдыха водителя или экипажа согласно ЕСТР; во-вторых, запретами (ограничениями) на движение большегрузных автомобилей по территории некоторых европейских стран в выходные и праздничные дни; в-третьих, необходимостью проведения ремонтно-профилактических воздействий, в частности, устранением отказов, а также другими причинами простоя на линии, например, поверками дорожной полицией нагрузок на оси, которые входят в период производственной деятельности водителя в течение рабочего дня, иной, чем управление автомобилем.
  Таким образом, формула (10.12) для общей продолжительности рейса должна быть откорректирована с учетом вышеуказанных факторов и представлена в виде:
  (10.13)
  где ?i - случайная составляющая, отражающая увеличение времени рейса для проведения ремонтно-профилактических воздействий и других причин;
  ?m - случайная составляющая, отражающая ограничения связанные с ЕСТР;
  ?n - случайная составляющая, отражающая запреты на движения большегрузных автомобилей;
  D, E, F -число случаев простоя автомобиля с учетом указанных факторов, соответственно.
  Рассчитанное значение времени рейса позволяет определить гарантированный срок доставки груза потребителю.
  Количество временных составляющих, включаемых во время рейса, возрастает при интермодальных или смешанных перевозках. В этом случае требование к соблюдению сроков перевозки диктуется не только клиентом, но и спецификой организации такого рода перевозки (например, опоздание на паром приводит к незапланированным многочасовым простоям).
  Особенностью расчета времени рейса и в наряде по формулам (10.11) и (10.13) являются нелинейность, из-за ограничений связанных с ЕСТР, режимом работы складов и т.д., и случайного характера временных составляющих перевозочного процесса.
  В седьмом блоке определяется соотношение смоделированных значений времени нахождения автомобиля в наряде (в рейсе) с требованиями клиентов по срокам доставки груза. Например, для внутригородской перевозки определяется возможность обслуживания всех потребителей на маршруте в пределах установленных временных интервалов. Если условие не выполняется, то требуется откорректировать маршрут, или, если возможно, время работы складов, грузоподъемность используемого на данном маршруте подвижного состава и заново смоделировать время движения.
  Таким образом, предлагаемая иерархия моделей формирует единый подход к формализации методов решения транспортной логистики и теории организации перевозок; охватывает основные типы транспортных задач, применительно к автомобильным перевозкам в пространстве (распределительная задача, маршрутизация) и во времени; позволяет осуществить трехуровневую оптимизацию по мере редуцирования количества рассматриваемых объектов (поставщики, потребители) и последовательного включения дополнительных факторов, связанных с конкретными маршрутами перевозок.
  С целью апробации разработанного алгоритма были выполнены расчеты на условных примерах, подтверждающие эффективность подложенной методики с точки зрения сокращения времени разработки оптимальных маршрутов автомобильных перевозок.
  Для иллюстрации предложенного алгоритма рассмотрим пример.
 1. Из пунктов a1 и a2 необходимо доставить груз в пункты b1 - b15 в требуемом количестве (табл. 10.3). Согласно алгоритму (рис.10.1) на втором этапе определяется схема доставки. В соответствии с предложенной в табл. 10.2 классификацией при доставке груза используется схема "многие - ко - многим".
  Условие третьего этапа выполняется, поэтому необходимо решить транспортную задачу (исходная информация приведена в табл. 3).
 Таблица 10.3
  Количество груза к доставке потребителю
 Пункт разгруз-ки b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15 Всего Кол-во груза, т 0,25 0,2 0,4 0,3 0,6 0,7 1,0 0,5 0,6 0,3 0,5 0,15 0,2 0,3 0,3 6,3 Таблица 10.4
  Расстояние между пунктами погрузки и разгрузки
 Пункт погрузки Расстояние до пункта разгрузки, км b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15 a1 10 6 7 1 4 5 8 9 5 4 6 10 11 5 2 a2 5 7 9 8 6 12 15 4 5 7 8 10 8 6 5
  2. Для решения транспортной задачи используется Microsoft Excel "Поиск решения" (блок 3). Критерием оптимальности в задаче является минимум транспортной работы в ткм.
 Таблица 10.5
  Результаты решения транспортной задачи
 Пункт погруз-ки Объем перевозок в пункт, т b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15 Всего a1 0,2 0,4 0,6 0,7 1,0 0,6 0,3 0,5 0,3 0,3 4,9 a2 0,25 0,3 0,5 0,15 0,2 1,4
  3. В результате решения определили два маршрута, связывающие начальные пункты a1 с десятью пунктами, а именно b2, b3, b5, b6, b7, b9, b10, b11, b14, b15 и a2 с пятью пунктами - b1, b4, b8, b12, b13 . Объем перевозки соответственно на первом маршруте составит 4,9 т и на втором маршруте 1,4 т. Для рассматриваемого примера предположим, что на автотранспортном предприятии есть автомобили грузоподъемностью 1,5 т и 5,0 т, и они могут быть использованы на данной перевозке. В случае если на автотранспортном предприятии нет автомобилей подходящей грузоподъемности или для данной перевозки они не могут быть использованы, то необходимо дальнейшее выделение маршрутов, например, путем решения транспортной задачи с ограничениями по вывозу из пункта количество груза равное грузоподъемности транспортного средства.
  4. Условие четвертого этапа алгоритма не выполняется, поэтому на пятом этапе требуется решить задачу маршрутизации (коммивояжера), целью которой является определение длины маршрута и порядка объезда автомобилем пунктов на маршруте. Исходной информацией для поставленной задачи будут расстояния между рассматриваемыми на маршруте пунктами (табл. 10.6 и табл. 10.7). Матрица кратчайших расстояний симметричная.
 Таблица 10.6
  Матрица кратчайших расстояний между пунктами первого маршрута
  a1 a1 ? b2 b2 6 ? b3 b3 7 10 ? b5 b5 4 4 8 ? b6 b6 5 8 2 11 ? b7 b7 8 2 7 2 8 ? b9 b9 5 6 5 8 2 5 ? b10 b10 4 3 2 7 11 3 4 ? b11 b11 6 7 5 5 8 7 7 6 ? b14 b14 5 7 8 2 7 9 3 8 9 ? b15 b15 2 4 6 4 3 11 9 3 2 10 ?
  Задача коммивояжера решалась методом "ветвей и границ".
  Длина первого маршрута составила 28 км, порядок объезда пунктов на маршруте следующий: a1 - b15 - b11 - b3 - b6 - b9 - b14 - b5 - b7 - b2 - b10 - a1. Для второго маршрута - 26 км; a2 - b8 - b12 - b1 - b13 - b4 - a2.
 
 
 
  Таблица 10.7
  Матрица кратчайших расстояний между пунктами второго маршрута
 
  a1 a1 ? b2 b2 5 ? b3 b3 8 6 ? b5 b5 4 7 9 ? b6 b6 10 2 11 4 ? b7 b7 8 3 5 8 7 ? b9
  5. Перед началом моделирования перевозочного процесса на маршрутах (шестой этап) необходимо задать временные ограничения (время в наряде, время обеденных перерывов, время начала и окончания работы в пунктах) и определить среднее значение, среднее квадратическое отклонение (СКО) и закон распределения случайных величин:
  - скорости движения на участках маршрутов;
  - времени погрузки;
  - времени разгрузки.
  Пусть все пункты разгрузки работают без обеденного перерыва с 08-00 до 16-00, за исключением пункта b5 (обеденный перерыв с 12-00 до 13-00) и пункта b13 (доставка груза должна быть осуществлена до 15-00). Начало погрузки в 09-00.
  Формула для расчета времени движения на маршруте имеет вид:
  (10.14)
 
  где tпогр - время погрузки в начальном пункте;
 ?i - время движения на i-м участке, ч;
 i -количество участков движения на маршруте;
 ?j - время на разгрузку в j-м пункте разгрузки, ч;
 j - количество пунктов разгрузки на маршруте.
  Таблица 10.8
  Характеристика случайных величин
 
 Случайная величина Среднее значение СКО Закон распределения Скорость, км/ч 31 2,5 нормальный Время простоя под погрузкой на первом маршруте, ч 2 0,5 нормальный Время простоя под погрузкой на втором маршруте, ч 1,5 0,4 нормальный Время простоя под разгрузкой в пунктах маршрута, ч 0,5 - экспоненциальный
  Время движения на участке маршрута определяется по формуле:
  (10.15)
  где li - длина i-го участка маршрута, км;
 Vi - скорость на i-м участке маршрута, км/ч.
 
  Смоделируем перевозочный процесс на первом маршруте.
  Для первой реализации время погрузки в пункте a1, подчиняется нормальному закону и рассчитывается по формуле:
 
  (10.16)
  где ?' - нормально распределенная случайная величина.
  tпогр = 2 + 0,5 · 0,6880 = 2,344 ч. (?' = 0,6880) Автомобиль начнет движение по маршруту в 11-21.
 
 
  Расстояние a1b15 2 км (табл. 10.6). Смоделируем скорость движения автомобиля на рассматриваемом участке (нормальный закон распределения, ?' = - 0,127): V1 = 31 + 2,5 · (-0,127) = 30,6825 км/ч.
  Время движения: ?1 = 2 / 30,6825 = 0,0652 ч или ?1 = 4 мин. Таким образом, в пункт b15 автомобиль приедет в 11-25.
  Время разгрузки подчиняется экспоненциальному закону и рассчитывается по формуле:
  (10.17)
  где ? - равномерно распределенное случайное число в интервале [0;1].
  ?1 = 0,5 · (-ln(0,9117)) = 0,0462 ч. (? = 0,9117) или ?1 = 3 мин. Разгрузка в пункте b15 закончится 11-28.
  Поступая аналогичным образом (движение - разгрузка) для дальнейших пунктов первого маршрута находим временные интервалы первой реализации:
  9-00 : 11-21 погрузка в a1; 11-21 : 11-25 движение на участке a1b15; 11-25 : 11-28 разгрузка в b15; 11-28 : 11-31 b15b11; 11-31 : 11-46 разгрузка в b11; 11-46 : 11-53 b11b3; 11-53 : 11-57 разгрузка в b3 и т.д.
  Результаты моделирования по десяти реализациям алгоритма для пунктов a1 и a2 приведены в табл.10.9 и 10.10. Необходимо помнить, что разгрузка не производится, если автомобиль прибыл во время обеденного перерыва или если время оставшееся до начала обеденного перерыва меньше самого времени разгрузки. В этих случаях определяется время незапланированных простоев tпр и затем суммируется по всем реализациям.
  Построим график функции распределения времени прибытия автомобиля к последним четырем потребителям на первом маршруте, то есть в пункты b5, b7, b2 и b10.
  График функции распределения показывает, какая часть от общего количества автомобилей прибудет к заданному времени к конкретному потребителю (рис. 10.2).
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  Рис. 10.2 График функции распределения времени прибытия автомобиля в пункт разгрузки на первом маршруте
 
  Анализ результатов моделирования показал:
  - временные ограничения будут выполнены полностью на втором маршруте;
  - обеденный перерыв в пункте b5 на первом маршруте не увеличит время работы автомобиля;
  - доставка груза на первом маршруте может быть осуществлена к 16-00 с вероятностью 90% только потребителю b7. Вероятность обслуживания потребителя b2 составляет 80%, а b10 только 40%.
  Рассмотренный пример показал перспективность применения единого алгоритма планирования автотранспортных перевозок в транспортной логистике. Для активного использования в практической деятельности алгоритм должен быть дополнен, на наш взгляд, матрицей принятия решений, в которой будут отражены все возможные варианты корректировки полученного результата. Например:
 
 
  Таблица 10.9
  Результаты моделирования перевозочного процесса на первом маршруте
 N реализации a1 b15 b11 b3 b6 b9 b14 b5 b7 b2 b10 a1 отпр приб отпр приб отпр приб отпр приб отпр приб отпр приб отпр приб отпр приб отпр приб отпр приб отпр приб 1 11-21 11-25 11-28 11-31 11-46 11-53 11-57 12-00 12-18 12-21 12-42 12-48 13-23 13-28 14-50 14-54 15-16 15-20 16-18 16-23 17-28 17-37 2 10-48 10-52 12-14 12-18 12-58 13-05 13-12 13-15 13-25 13-29 14-15 14-20 14-44 14-48 15-11 15-15 15-26 15-30 15-59 16-06 18-05 18-13 3 10-48 10-52 11-00 11-04 11-47 11-53 12-36 12-40 13-12 13-18 13-58 14-03 15-00 15-40 16-02 16-05 16-20 16-24 16-53 16-59 17-14 17-21 4 10-37 10-40 10-47 10-51 11-07 11-16 11-34 11-37 12-23 12-25 12-53 12-59 13-56 14-00 14-09 14-13 15-30 15-34 16-09 16-16 17-04 17-11 5 11-14 11-17 11-22 11-25 11-30 11-39 12-12 12-15 12-45 12-49 14-19 14-25 14-31 14-34 14-47 14-50 15-02 15-06 15-52 15-58 16-01 16-09 6 10-49 10-52 10-53 10-57 11-40 11-49 12-07 12-10 12-21 12-25 12-46 12-52 13-26 13-30 13-53 14-02 14-53 14-57 15-20 15-26 16-43 16-50 7 11-47 11-52 12-53 12-57 13-08 13-16 13-35 13-39 14-02 14-06 14-09 14-14 14-15 14-19 14-41 14-45 15-09 15-12 16-09 16-15 17-23 17-29 8 10-59 11-03 11-18 11-22 11-36 11-45 12-29 12-33 13-19 13-23 13-51 13-57 14-02 14-06 14-14 14-19 14-29 14-32 15-21 15-27 15-37 15-44 9 11-42 11-46 11-54 11-58 12-39 13-48 13-29 13-33 13-45 13-49 14-23 14-28 14-45 14-49 15-01 15-04 15-16 15-20 15-22 15-28 16-04 16-11 10 11-29 11-34 11-57 12-02 12-09 12-18 13-25 13-29 14-48 14-52 15-28 15-34 15-46 15-50 16-52 16-55 17-04 17-08 17-11 17-06 18-09 18-17 Таблица 10.10
  Моделирование перевозочного процесса на втором маршруте
 N реали-
 зации a2 b8 b12 b1 b13 b4 a2 отпр приб отпр приб отпр приб отпр приб отпр приб отпр приб 1 10-23 10-29 11-44 11-52 12-56 13-00 13-22 13-29 14-04 14-14 14-34 14-49 2 9-59 10-08 10-37 10-45 10-55 10-58 11-12 11-17 12-23 12-33 12-39 12-56 3 10-36 10-44 12-49 12-56 13-56 14-00 14-04 14-09 14-11 14-20 14-30 14-44 4 11-01 11-10 11-15 11-23 12-49 12-53 13-22 13-27 13-32 13-40 13-54 14-10 5 10-59 11-06 11-15 11-23 11-31 11-35 11-57 12-03 12-06 12-16 12-39 12-56 6 11-12 11-20 11-32 11-40 12-15 12-18 12-21 12-26 13-34 13-45 13-47 14-01 7 9-38 9-46 10-10 10-20 11-59 12-02 12-20 12-26 13-05 13-16 13-14 14-01 8 10-24 10-32 10-40 10-49 11-55 11-59 13-18 13-23 13-51 14-01 14-06 14-21 9 10-56 11-03 11-42 11-49 12-17 12-20 12-27 12-32 12-51 13-01 13-35 13-50 10 10-04 10-11 11-03 11-10 11-17 11-21 12-05 12-11 12-15 12-20 12-45 12-59
 
 
  - заключение соглашения с поставщиками или потребителями о изменении времени погрузки или разгрузки соответственно, в этом случае корректировки маршрута не требуется;
  - корректировка маршрутов, когда пункт из одного маршрута переносится в другой, где есть запас времени, с целью выполнения всех договорных обязательств. Выбирается тот пункт, перемещение которого вызовет наименьшее увеличение транспортной работы.
  - использование дополнительного автомобиля на маршруте.
 
 
 10.2 Алгоритм ускоренного планирования автомобильных перевозок
 
 Рассмотренный пример выявил также и проблемы применения общего алгоритма планирования грузовых автомобильных перевозок. Так его применение трудоемкая и занимающая достаточно много времени задача. На каждом этапе предлагается получать оптимальный маршрут, который в последствии корректируется в зависимости от условий перевозки. Следует так же помнить, полученный после реализации алгоритма оптимальный маршрут может не отвечать требованиям клиентов по срокам доставки груза, что приводит к повторному решению некоторых блоков. Отметим, что, во-первых, на практике в основном требуется решать задачи небольшой размерности (для развозочных маршрутов до шести - восьми пунктов) и, во-вторых, не всегда есть возможность применять ЭВМ при оперативном планировании. Таким образом, практическую значимость имеют приближенные методы решения задач, решаемых при реализации алгоритма, а также оценка времени доставки груза, используемая вместо статистического моделирования.
 Для соответствующих блоков общего алгоритма предлагается использовать следующие методы:
 1. Для решения транспортной задачи - метод аппроксимации Фогеля, являющийся способом составления первого допустимого плана. Полученное распределение, особенно при небольшой размерности задачи, является оптимальным или достаточно близким к нему.
 2. Для составления маршрутов - метод воображаемого луча (метод Свира).
 3. Для решения задачи коммивояжера - ускоренный метод "ветвей и границ" (решение ведется только по одной "ветке", без проверки на оптимальность других).
 4. Вместо моделирования составляющих перевозочного процесса проводится оценка интервалов времени прибытия транспортного средства и времени окончания разгрузки для каждого потребителя по формулам (время доставки груза "точно - во - время" Ттв):
 для верхней границы (10.18)
 для нижней границы (10.19)
 где - среднее значение доставки объема груза, ч;
 ?тс - среднеквадратичное отклонение времени доставки груза, ч;
 ?p - квантиль нормального распределения, соответствующий вероятности P.
 Величины и ?тс определяются по формулам:
 (10.20)
 
 (10.21)
 
 где - среднее значение времени доставки груза к j-ому потребителю,ч;
  ?j - среднеквадратичное отклонение времени доставки груза к j-ому потребителю, ч;
  rij - коэффициент парной корреляции между временем на выполнение i-ой и j-ой едки.
  Для расчетов можно принять значение коэффициента парной корреляции равным нулю.
  Проведем расчет с использование выделенных методов. Предположим, что требуется из двух пунктов a1 и a2 перевезти груз восьми грузополучателям b1, b2, ... , b8, в объеме (Q), представленном в табл. 10.11; там же приведены расстояния между грузоотправителями и грузополучателями.
 Таблица 10.11
 Объем перевозок груза и расстояние между грузообразующими и грузопоглощающими пунктами
 Объем перевозок Пункты разгрузки Итого Пункт погрузки b1 b2 b3 b4 b5 b6 b7 b8 Q, т 0,25 0,3 0,45 1,5 0,5 0,6 1,0 1,1 5,7 a1 l, км 10 12 15 11 13 15 14 10 - a2 l, км 9 18 14 17 11 10 12 8 -
 Решим транспортную задачу методом Фогеля. В каждой строке и столбце матрицы кратчайших расстояний найдем два наименьших элемента и определим абсолютную разность между ними. Например, для первой строки, относящейся к первому пункту погрузки, значения наименьших элементов равны 10 км, таким образом, разность равна нулю. Затем выбираем наибольшую величину разности и в клетку с минимальным элементом заносим максимально возможную загрузку, учитывая при этом ресурсы поставщика и спрос потребителя. При наличии двух одинаковых наибольших разностей загрузку записывают в клетку, имеющую наименьший элемент (табл. 10.12). Если окажется, что спрос потребителя полностью удовлетворен или ресурс поставщика полностью исчерпан, то данная строка или столбец из дальнейшего рассмотрения исключается.
 
 
 Таблица 10.12
 Определение первого загруженного элемента
 Объем
 перевозок Пункты разгрузки Столбец разностей Пункт погрузки b1 b2 b3 b4 b5 b6 b7 b8 Q, т 0,25 0,3 0,45 1,5 0,5 0,6 1,0 1,1 a1 l, км 10 12 15 11 13 15 14 10 0 a2 l, км 9 18 14 17 11 10 12 8 1 Строка
 разностей 1 6 1 6 2 5 2 2
  Наибольшая разность равна шести, минимальный элемент - 11, из пункта a1 в пункт b4 перевозится максимально возможный объем - 1,5 тонны груза. Спрос потребителя полностью удовлетворен, поэтому данный столбец из дальнейшего рассмотрения исключается. Необходимо пересчитать разности (табл. 10.13).
  В табл. 10.13 наибольшая разность - 6, минимальный элемент - 12, таким образом, из пункта a1 в пункт b2 перевозится максимально возможный объем - 0,3 тонны груза. Далее операция повторяется до тех пор пока не будет составлена допустимая программа распределения (табл. 10.14).
 Таблица 10.13
 Определение второго загруженного элемента
 Объем перевозок Пункты разгрузки Столбец разностей Пункт погрузки b1 b2 b3 b5 b6 b7 b8 Q, т 0,25 0,3 0,45 0,5 0,6 1,0 1,1 a1 l, км 10 12 15 13 15 14 10 0 a2 l, км 9 18 14 11 10 12 8 1 Строка разностей 1 6 1 2 5 2 2
  Таблица 10.14
  Решение транспортной задачи
 Пункт погрузки Пункты разгрузки Итого: b1 b2 b3 b4 b5 b6 b7 b8 a1 0,25 0,3 1,5 2,05 a2 0,45 0,5 0,6 1,0 1,1 3,65
  Набор пунктов в маршрут выполним методом Свира, используя схему дислокации пунктов относительно друг друга, представленную на рис. 10.3. Грузоподъемность транспортных средств предполагается равной 2,2 тонны.
 
 
 
 
 
 
 
 
 
 
 Рис. 10.3. Дислокация грузообразующих и грузопоглощающих пунктов
 
  Согласно методу Свира воображаемый луч, исходящий из пункта погрузки, например а1, вращаясь против (или по) часовой стрелки "стирает" изображения пунктов разгрузки. Маршрут считается сформированным, если включение следующего пункта приведет к превышению объема перевозки над грузоподъемностью транспортного средства. Первым пунктов маршрута будет b2 с объемом перевозки 0,3 тонны, следующий пункт - b4, суммарный объем составит 1,8 тонны. Включение пункта b1 в маршрут так же возможно, так как не произойдет превышение грузоподъемности подвижного состава.
  Метод Свира для пункта а2 позволяет получить два маршрута. Первый включает два пункта b6 и b7 с суммарным объемом перевозки 1,6 тонны, а второй - три b3, b5 и b8, объем - 2,05 тонны.
  Порядка объезда пунктов на маршруте предлагается определять ускоренным методом "ветвей и границ", для применения которого необходимо определить кратчайшие расстояния между пунктами включаемыми в один маршрут (табл. 10.15). Предположим, что матрица симметрична.
 
  Таблица 10.15
 Таблица кратчайших расстояний между пунктами маршрутов
 а1 а1 а2 а2 а2 а2 b1 10 b1 b6 10 b6 b3 14 b3 b2 12 20 b2 b7 12 3 b7 b5 11 4 b5 b4 11 19 4 b4 b8 11 7 4 b8
  Применение метода рассмотрим на маршруте, включающем пункты a1, b1, b2 и b4.
  1. Определяем нижнюю границу. Для этого из каждого элемента строки вычитаем наименьший элемент этой строки (табл. 10.16, а). Затем из полученных элементов каждого столбца новой матрицы вычитают наименьший элемент этого столбца (табл. 10.16, б).
  Приведенная матрица показана в табл. 10.16, б. Справа и внизу матрицы показаны константы приведения - минимальные элементы, которые вычитались вначале из строк, а затем из столбцов матрицы.
 
  Таблица 10.16
  Определение нижней границы множества "все решения"
 а). а1 b1 b2 b4 б). а1 b1 b2 b4 а1 ? 0 2 1 10 а1 ? 0 2 1 10 b1 0 ? 10 9 10 b1 0 ? 10 9 10 b2 8 16 ? 0 4 b2 8 16 ? 0 4 b4 7 15 0 ? 4 b4 7 15 0 ? 4 0 0 0 0 28
  Сумма констант, равная 28, является нижней границей протяженности для всех маршрутов, то есть для множества "все решения".
  2. Нулевые расстояния в клетках матрицы указывают на наличие минимальных по протяженности маршрутов, поэтому при построении развозочного маршрута в первую очередь рассматриваются элементы с нулевыми протяженностями.
  Для этого определяются оценки всех элементов приведенной матрицы как сумму наименьших величин протяженности соответствующей строки и столбца. Например, для нулевого элемента a1b1 оценка составит 1 + 15. Оценка показывает на потери от невключения данного элемента в маршрут. Проставим ее в правом верхнем углу (табл. 10.17).
  Таблица 10.17
 Определение оценок для нулевых элементов матрицы
  а1 b1 b2 b4 а1 ? 0 16 2 1 b1 0 16 ? 10 9 b2 8 16 ? 0 9 b4 7 15 0 9 ?
  Для того, что бы избежать больших потерь, следует в первую очередь включить в маршрут нулевой элемент с наибольшей оценкой. В примере максимальная оценка, равная 16, соответствует двум элементам. В этом случае выбирается любая из пар, например a1b1.
  3. Для ветвления множества его необходимо разделить на два вида: маршруты первого подмножества будут включать пару a1b1, а маршруты второго ее не включают.
  Нижняя граница второго подмножества равна сумме значений нижней границы разделяемого множества и величины оценки пары a1b1, то есть 28 + 16 = 44. Строку a1 и столбец b1 исключают из рассмотрения, то сеть удаляют из матрицы. Выбор в дальнейшем пары b1a1 привел бы к нарушению условия о заезде в каждый пункт только по одному разу. Поэтому пара b1a1 блокируется, проставляя в соответствующую клетку матрицы знак блокировки ( ) вместо прежнего значения.
  4. Преобразованная и приведенная матрица приведена в табл. 10.18. В процессе вычисления констант появились константы, равные 9 и 7 соответственно. Следовательно, протяженность подмножества, включающего пару a1b1, увеличивается на 16 (28 + 16 = 44).

<< Пред.           стр. 9 (из 10)           След. >>

Список литературы по разделу