А В Белогурова - Алгоритм уменьшения затрат на доставку груза в кратчайшие сроки - страница 1

Страницы:
1  2 

>          части ёмкостей мегарайонов, корреспондирующих через ЦДЧГ, определяются проще и точнее, чем ёмкости отдельных транс­портных районов;

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

>          метод разработан специально для расчёта потоков в ЦДЧГ. Дальнейшие исследования следует направить на уточнение вида

функции тяготения путём увеличения числа факторов, влияющих на её

вид.

1.Брайловский Н.О., Грановский Б.И. Моделирование транспортных систем. - М.: Транспорт, 1978. - 125 с.

2.Капитанов В.Т., Хилажев Е.Б. Управление транспортными потоками в городах. -М.: Транспорт, 1985. - 94 с.

3.Сильянов В.В. Теория транспортных потоков в проектировании дорог и органи­зации движения. - М.: Транспорт, 1977. - 303 с.

4.Михайлов А.Ю., Головных И.М. Оценка существующей матрицы коррес-понденций на основе данных интенсивности движения // Вестник КГТУ. Вып.35. -Красноярск: ИПЦ КГТУ, 2004. - С.191-199.

5.Дубровский В.В. Функция тяготения населения по трудовым целям // Автомо­бильный транспорт: Сб. науч. трудов. Вып.6. - Харьков: РИО ХГАДТУ, 2001. - С.22-24.

6.Toshio Yoshii Masao Kuwahara Estimation of a Time Dependent OD Matrix from Traffic Counts Using Dynamic Traffic Simulation Institute of Industrial Science, University of Tokyo, 1997. - рр.41-49.

7.Oneyama, H., Kuwahara, M & Yoshii, T. "Estimation of a Time Dependent OD Ma­trix from Traffic Counts", The Third Annual World Congress on Intelligent Transport Systems '96 Orlando. - pp.77-81.

8.Yoshii, T & Kuwahara, M. "Development of Traffic Network Simulation Model for Oversaturated Traffic Flow on Urban expressways", Traffic Engineering Vol.30, No.1, 1995. - pp.33-41.

9.Sheffi, Y. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods, Prentice Hall, 1985. - p.117, web.mit.edu.

10.Лозе Д. Моделирование транспортного предложения и спроса на транспорт для личного и служебного автотранспорта - обзор теорий моделирования, Дрезденский Технический Университет. Институт транспортного планирования и дорожного движе­ния, 2007 // www.ptv-vision.de.

Получено 17.02.2009

 

УДК 519.85

А.В.БЕЛОГУРОВА, канд. техн. наук

Харьковская национальная академия городского хозяйства

АЛГОРИТМ УМЕНЬШЕНИЯ ЗАТРАТ НА ДОСТАВКУ ГРУЗА В КРАТЧАЙШИЕ СРОКИ

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

Задача доставки груза в кратчайшие сроки возникает при стихий­ных бедствиях, при планировании крупных военных операций, для уменьшения ущерба при пожаротушении и др. [1, 2]. Эту задачу мож­но отнести к классу «транспортных задач», когда необходимо опти­мальным образом перевезти груз из m пунктов отправления в n пунктов назначения.

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

В [3] предлагается алгоритм нахождения плана перевозок, позво­ляющий подобрать план с наименьшим временем доставки груза, од­нако не приводится математическая модель данной задачи и нет дока­зательств сходимости метода.

Чтобы записать математическую модель, введем следующие обо­значения: ai - объемы груза, находящиеся в i -м пункте отправления

(i = 1, m); bj - объемы груза, которые необходимо доставить в j

пункт назначения (j = 1, n); [tj ] - матрица затрат времени на перевоз­ку груза из i -го пункта отправления в j -й пункт назначения (i = 1, m , j = 1, n); Xj - количество груза, перевозимого из i -го пункта

(1 (Л                                        — —

отправления в j        I -й пункт назначения (i = 1, m , j = 1, n); [е{, ] -

1°   1J

матрица денежных затрат на перевозку груза из i -го пункта отправле­ния в j -й пункт назначения (i = 1, m , j = 1, n).

Данная задача относится к классу закрытых транспортных задач,

m n

т.е. ^at = ^bj . Ограничения оптимизационной задачи можно запи-

i=1 j=1

сать следующим образом: ^ xff = at , i = 1, m , ^ Xj = bj , j = 1, n,

 

Xj > ° (i = 1, m , j = 1,n).

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

Тогда время на выполнение всей операции по доставке груза будет определяться самым долгим маршрутом от i к j, по которому перево­зится    хотя    бы    одна    единица    груза.    Введем функцию

t j(xj)

Г °, Xj = °

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

от к j, если по этому маршруту перевозят хотя бы одну единицу груза. Тогда, целевую функцию можно записать следующим образом:у (x)


= max

k ® minде k = 1, m X n.

Математическая модель задачи доставки груза в кратчайшие сро­ки принимает вид:

У (x) = max

k


t (k)

j

Ь" (x)


® min,

 

I

W:\L xj =b

I =1

 

 

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

Алгоритм поиска минимального по времени плана перевозок, предложенный в [3], обладает тем свойством, что получаемое решение сильно зависит от исходного опорного плана, поскольку при поиске оптимального решения затрагиваются только ячейки с максимальным временем и ячейки, входящие в цикл. Поэтому для решения задачи доставки груза в кратчайшие сроки с минимальными затратами пред­лагается, сначала сузить область допустимых решений, решив обыч­ную транспортную задачу на минимизацию издержек (например, ме­тодом потенциалов), а потом искать оптимальное в смысле временирешение. Этот подход соответствует принципу Беллмана для много­критериальной задачи [4].

Предлагается следующий алгоритм:

1.   Решаем задачу доставки груза с минимумом затрат. Находим невырожденный оптимальный план задачи

m n

VV с. ■ x.. ® min,

 

n

Z

x.. = a.,

 

m

W: \V xv = Ъ ,

x.. > 0, .

 

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

max[rv ] ® min ,

n m

W: x.. = Ъ.,

i=1

x.. > 0. .

2.   Среди всех t j (i = 1, m , j = 1, n), для которых xj > 0, опреде­ляем наибольший элемент tmax , tmax = max    J и вычеркиваем все

пустые клетки, в которых время доставки выше tmax .

3.   Из клетки с tmax строим разгрузочный цикл так, чтобы разгру­зить ячейку с tmax (аналогично методу потенциалов).

4.   Сделав в свободную вершину цикла поставку р (определяе­мую как в методе потенциалов), проводим компенсации по вершинам цикла и строим новый опорный план.

5. Переходим к шагу 2 данного алгоритма. Зачеркнутые ячейки в дальнейшем рассмотрении не участвуют.

Шаги 2-5 выполняем до тех пор, пока удается построить разгру­зочный цикл. Последний полученный план является оптимальным с точки зрения временных затрат, а время доставки груза будет опреде­ляться tmax на последней итерации.

Пример решения задачи доставки груза в кратчайшие сроки

T = t

C = с

5   6   9 7

4 1 6 10

Допустим, мы располагаем тремя источниками груза: в первом сосредоточено 30 единиц груза, во втором - 35 единиц, а в третьем -40 единиц. Груз необходимо доставить как можно быстрее в пять пунктов, причем в первый пункт - 20 единиц, во второй - 34 единицы, в третий - 16 единиц, в четвертый - 10 единиц, а в пятый - 25 единиц груза. Временные затраты на перевозку по каждому маршруту заданы матрицей Т, а денежные затраты - матрицей С ( 2   6   3   4   8 ^

(5 4

8

5

1 ^

3 2

4

5

2

v3 1

2

3

3,

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

1. Решаем задачу минимизации затрат на доставку груза методом потенциалов и получаем следующее оптимальное решение:

 

Пункт отправления

Запасы груза

Пункты назначения

ui

 

 

1      1     2     |     3     |     4     | 5

 

 

 

Потребность

 

 

 

20

34

16

10

25

 

1

30

5

4

8

5

5

1

25

2

2

35

3

20

2

15

4

5

2

1

3

40

3

1

19

2

16

3

5

3

0

 

2

1

2

3

-1

 

Денежные   затраты   на   реализацию   этого   плана составят z* = 25 + 25 + 60 + 30 +19 + 32 +15 = 206 . Теперь матрицу С заменяем матрицей Т и получаем:


Пункт отправления

Запасы груза

Пункты назначения

 

 

1              2              3              4 5

 

 

Потребность

 

Страницы:
1  2 


Похожие статьи

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