Количество груза к доставке потребителю

Пункт разгруз-ки	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

a2

 

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. В результате решения определили два маршрута, связывающие начальные пункты a₁ с десятью пунктами, а именно b₂, b₃, b₅, b₆, b₇, b₉, b₁₀, b₁₁, b₁₄, b₁₅ и a₂ с пятью пунктами – b₁, b₄, b₈, b₁₂, b₁₃. Объем перевозки соответственно на первом маршруте составит 4,9 т и на втором маршруте 1,4 т. Для рассматриваемого примера предположим, что на автотранспортном предприятии есть автомобили грузоподъемностью 1,5 т и 5,0 т, и они могут быть использованы на данной перевозке. В случае если на автотранспортном предприятии нет автомобилей подходящей грузоподъемности или для данной перевозки они не могут быть использованы, то необходимо дальнейшее выделение маршрутов, например, путем решения транспортной задачи с ограничениями по вывозу из пункта количество груза равное грузоподъемности транспортного средства.

4. Условие четвертого этапа алгоритма не выполняется, поэтому на пятом этапе требуется решить задачу маршрутизации (коммивояжера), целью которой является определение длины маршрута и порядка объезда автомобилем пунктов на маршруте. Исходной информацией для поставленной задачи будут расстояния между рассматриваемыми на маршруте пунктами (табл. 10.6 и табл. 10.7). Матрица кратчайших расстояний симметричная.

Таблица 10.6

Матрица кратчайших расстояний между пунктами первого маршрута

	a1
a1	∞	b2
b2		∞	b3
b3			∞	b5
b5				∞	b6
b6					∞	b7
b7						∞	b9
b9							∞	b10
b10								∞	b11
b11									∞	b14
b14										∞	b15
b15											∞

 

Задача коммивояжера решалась методом "ветвей и границ".

Длина первого маршрута составила 28 км, порядок объезда пунктов на маршруте следующий: a₁ – b₁₅ – b₁₁ – b₃ – b₆ – b₉ – b₁₄ – b₅ – b₇ – b₂ – b₁₀ – a₁. Для второго маршрута – 26 км; a₂ – b₈ – b₁₂ – b₁ – b₁₃ – b₄ – a₂.

 

Таблица 10.7

Матрица кратчайших расстояний между пунктами второго маршрута

 

	a1
a1	∞	b2
b2		∞	b3
b3			∞	b5
b5				∞	b6
b6					∞	b7
b7						∞	b9

 

5. Перед началом моделирования перевозочного процесса на маршрутах (шестой этап) необходимо задать временные ограничения (время в наряде, время обеденных перерывов, время начала и окончания работы в пунктах) и определить среднее значение, среднее квадратическое отклонение (СКО) и закон распределения случайных величин:

- скорости движения на участках маршрутов;

- времени погрузки;

- времени разгрузки.

Пусть все пункты разгрузки работают без обеденного перерыва с 08-00 до 16-00, за исключением пункта b₅ (обеденный перерыв с 12-00 до 13-00) и пункта b₁₃ (доставка груза должна быть осуществлена до 15-00). Начало погрузки в 09-00.

Формула для расчета времени движения на маршруте имеет вид:

(10.14)

 

где t_погр – время погрузки в начальном пункте;

τ_i – время движения на i-м участке, ч;

i –количество участков движения на маршруте;

θ_j – время на разгрузку в j-м пункте разгрузки, ч;

j – количество пунктов разгрузки на маршруте.

Таблица 10.8

Характеристика случайных величин

 

Случайная величина	Среднее значение	СКО	Закон распределения
Скорость, км/ч		2,5	нормальный
Время простоя под погрузкой на первом маршруте, ч		0,5	нормальный
Время простоя под погрузкой на втором маршруте, ч	1,5	0,4	нормальный
Время простоя под разгрузкой в пунктах маршрута, ч	0,5	-	экспоненциальный

 

Время движения на участке маршрута определяется по формуле:

(10.15)

где l_i – длина i-го участка маршрута, км;

V_i – скорость на i-м участке маршрута, км/ч.

 

Смоделируем перевозочный процесс на первом маршруте.

Для первой реализации время погрузки в пункте a₁, подчиняется нормальному закону и рассчитывается по формуле:

 

(10.16)

где ξ' – нормально распределенная случайная величина.

t_погр = 2 + 0,5 · 0,6880 = 2,344 ч. (ξ' = 0,6880) Автомобиль начнет движение по маршруту в 11-21.

 

 

Расстояние a₁b₁₅ 2 км (табл. 10.6). Смоделируем скорость движения автомобиля на рассматриваемом участке (нормальный закон распределения, ξ' = - 0,127): V₁ = 31 + 2,5 · (-0,127) = 30,6825 км/ч.

Время движения: τ₁ = 2 / 30,6825 = 0,0652 ч или τ₁ = 4 мин. Таким образом, в пункт b₁₅ автомобиль приедет в 11-25.

Время разгрузки подчиняется экспоненциальному закону и рассчитывается по формуле:

(10.17)

где ξ – равномерно распределенное случайное число в интервале [0;1].

θ₁ = 0,5 · (-ln(0,9117)) = 0,0462 ч. (ξ = 0,9117) или θ₁ = 3 мин. Разгрузка в пункте b₁₅ закончится 11-28.

Поступая аналогичным образом (движение – разгрузка) для дальнейших пунктов первого маршрута находим временные интервалы первой реализации:

9-00: 11-21 погрузка в a₁; 11-21: 11-25 движение на участке a₁b₁₅; 11-25: 11-28 разгрузка в b₁₅; 11-28: 11-31 b₁₅b₁₁; 11-31: 11-46 разгрузка в b₁₁; 11-46: 11-53 b₁₁b₃; 11-53: 11-57 разгрузка в b₃ и т.д.

Результаты моделирования по десяти реализациям алгоритма для пунктов a₁ и a₂ приведены в табл.10.9 и 10.10. Необходимо помнить, что разгрузка не производится, если автомобиль прибыл во время обеденного перерыва или если время оставшееся до начала обеденного перерыва меньше самого времени разгрузки. В этих случаях определяется время незапланированных простоев t_пр и затем суммируется по всем реализациям.

Построим график функции распределения времени прибытия автомобиля к последним четырем потребителям на первом маршруте, то есть в пункты b₅, b₇, b₂ и b₁₀.

График функции распределения показывает, какая часть от общего количества автомобилей прибудет к заданному времени к конкретному потребителю (рис. 10.2).

 

 

 

Рис. 10.2 График функции распределения времени прибытия автомобиля в пункт разгрузки на первом маршруте

 

Анализ результатов моделирования показал:

- временные ограничения будут выполнены полностью на втором маршруте;

- обеденный перерыв в пункте b₅ на первом маршруте не увеличит время работы автомобиля;

- доставка груза на первом маршруте может быть осуществлена к 16-00 с вероятностью 90% только потребителю b₇. Вероятность обслуживания потребителя b₂ составляет 80%, а b₁₀ только 40%.

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

 

Таблица 10.9

Результаты моделирования перевозочного процесса на первом маршруте

N реализации	a1	b15	b11	b3	b6	b9	b14	b5	b7	b2	b10	a1
отпр	приб	отпр	приб	отпр	приб	отпр	приб	отпр	приб	отпр	приб	отпр	приб	отпр	приб	отпр	приб	отпр	приб	отпр	приб
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
отпр	приб	отпр	приб	отпр	приб	отпр	приб	отпр	приб	отпр	приб
	10-23	10-29	11-44	11-52	12-56	13-00	13-22	13-29	14-04	14-14	14-34	14-49
	9-59	10-08	10-37	10-45	10-55	10-58	11-12	11-17	12-23	12-33	12-39	12-56
	10-36	10-44	12-49	12-56	13-56	14-00	14-04	14-09	14-11	14-20	14-30	14-44
	11-01	11-10	11-15	11-23	12-49	12-53	13-22	13-27	13-32	13-40	13-54	14-10
	10-59	11-06	11-15	11-23	11-31	11-35	11-57	12-03	12-06	12-16	12-39	12-56
	11-12	11-20	11-32	11-40	12-15	12-18	12-21	12-26	13-34	13-45	13-47	14-01
	9-38	9-46	10-10	10-20	11-59	12-02	12-20	12-26	13-05	13-16	13-14	14-01
	10-24	10-32	10-40	10-49	11-55	11-59	13-18	13-23	13-51	14-01	14-06	14-21
	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-04	10-11	11-03	11-10	11-17	11-21	12-05	12-11	12-15	12-20	12-45	12-59

 

 

- заключение соглашения с поставщиками или потребителями о изменении времени погрузки или разгрузки соответственно, в этом случае корректировки маршрута не требуется;

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

- использование дополнительного автомобиля на маршруте.

 

 

Алгоритм ускоренного планирования автомобильных перевозок

Рассмотренный пример выявил также и проблемы применения общего алгоритма планирования грузовых автомобильных перевозок. Так его применение трудоемкая и занимающая достаточно много времени задача. На каждом этапе предлагается получать оптимальный маршрут, который в последствии корректируется в зависимости от условий перевозки. Следует так же помнить, полученный после реализации алгоритма оптимальный маршрут может не отвечать требованиям клиентов по срокам доставки груза, что приводит к повторному решению некоторых блоков. Отметим, что, во-первых, на практике в основном требуется решать задачи небольшой размерности (для развозочных маршрутов до шести – восьми пунктов) и, во-вторых, не всегда есть возможность применять ЭВМ при оперативном планировании. Таким образом, практическую значимость имеют приближенные методы решения задач, решаемых при реализации алгоритма, а также оценка времени доставки груза, используемая вместо статистического моделирования.

Для соответствующих блоков общего алгоритма предлагается использовать следующие методы:

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

2. Для составления маршрутов – метод воображаемого луча (метод Свира).

3. Для решения задачи коммивояжера – ускоренный метод "ветвей и границ" (решение ведется только по одной "ветке", без проверки на оптимальность других).

4. Вместо моделирования составляющих перевозочного процесса проводится оценка интервалов времени прибытия транспортного средства и времени окончания разгрузки для каждого потребителя по формулам (время доставки груза "точно – во – время" Т_тв):

для верхней границы (10.18)

для нижней границы (10.19)

где - среднее значение доставки объема груза, ч;

σ_тс – среднеквадратичное отклонение времени доставки груза, ч;

α_p – квантиль нормального распределения, соответствующий вероятности P.

Величины и σ_тс определяются по формулам:

(10.20)

 

(10.21)

 

где - среднее значение времени доставки груза к j-ому потребителю,ч;

σ_j – среднеквадратичное отклонение времени доставки груза к j-ому потребителю, ч;