Об одной задаче распределения земляных масс и алгоритме ее решения
Приводится постановка задачи распределения земляных масс для случая, когда грунт с выемок непригоден для сооружения насыпей и поставщиками грунта для насыпей являются карьеры, расположенные вдоль трассы дороги на некотором расстоянии от нее. Отмечаются особенности задачи распределения земляных масс...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2009 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/46638 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Об одной задаче распределения земляных масс и алгоритме ее решения / В.И. Билецкий // Теорія оптимальних рішень: Зб. наук. пр. — 2009. — № 8. — С. 50-55. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859693573566365696 |
|---|---|
| author | Билецкий, В.И. |
| author_facet | Билецкий, В.И. |
| citation_txt | Об одной задаче распределения земляных масс и алгоритме ее решения / В.И. Билецкий // Теорія оптимальних рішень: Зб. наук. пр. — 2009. — № 8. — С. 50-55. — Бібліогр.: 3 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Приводится постановка задачи распределения земляных масс для случая, когда грунт с выемок непригоден для сооружения насыпей и поставщиками грунта для насыпей являются карьеры, расположенные вдоль трассы дороги на некотором расстоянии от нее. Отмечаются особенности задачи распределения земляных масс карьеров, описывается схема алгоритма ее решения на основе метода последовательного анализа вариантов.
Наводиться постановка однієї задачі розподілення земляних мас, коли грунт із виїмок непридатний для спорудження насипів і поставщиками грунту для них є кар’єри, які розташовані вздовж траси дороги на певній відстані від неї. Відмічаються особливості задачі розподілення земляних мас кар’єрів, описується схема алгоритму розв’язування задачі на основі методу послідовного аналізу варіантів.
We consider a problem of soil mass distribution, when the soil from the groove is inappropriate for levee construction and the soil is taken from borrows, located along the road at a certain distance from it. We point out peculiarities of the borrov soil mass distribution problem, describe the algorithm of its solution using the method of sequential analysis of variants.
|
| first_indexed | 2025-12-01T00:08:10Z |
| format | Article |
| fulltext |
50 Теорія оптимальних рішень. 2009,
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Приводится постановка задачи
распределения земляных масс
для случая, когда грунт с вы-
емок непригоден для сооруже-
ния насыпей и поставщиками
грунта для насыпей являются
карьеры, расположенные вдоль
трассы дороги на некотором
расстоянии от нее. Отмеча-
ются особенности задачи
распределения земляных масс
карьеров, описывается схема
алгоритма ее решения на
основе метода последователь-
ного анализа ва-риантов.
В.И. Билецкий, 2009
ÓÄÊ 519.8
Â.È. ÁÈËÅÖÊÈÉ
ÎÁ ÎÄÍÎÉ ÇÀÄÀ×Å
ÐÀÑÏÐÅÄÅËÅÍÈß ÇÅÌËßÍÛÕ ÌÀÑÑ
È ÀËÃÎÐÈÒÌÅ ÅÅ ÐÅØÅÍÈß
Как известно, строительство железных
дорог осуществляется лишь после нахожде-
ния оптимального варианта продольного
профиля железнодорожной линии.
На этапе строительства возникают раз-
личные оптимизационные задачи. Одна из
них – задача нахождения оптимального
плана перевозки (или распределения) зем-
ляных масс (объемов гранта) от поставщи-
ков к потребителям. Поставщиками грунтов
могут быть либо выемки, получены в ре-
зультате нахождения оптимального вариан-
та проектной линии, либо карьеры, нахо-
дящиеся на каком-то расстоянии от трассы
железной дороги, либо выемки и каръеры в
совокупности.
Грунт выемок может быть использован
для насыпей лишь в случае его пригодности
для их сооружения. Но есть случаи (напри-
мер, болотисте места и т. п.), когда грунт
выемок непригоден для возведения насы-
пей. Тогда возникает задача нахождения
оптимального плана перевозки грунтов от
каръеров к потребителям (насыпям), други-
ми словами – задача распределения зем-
ляных масс каръеров (РЗМК), которые рас-
положены вдоль трассы на некотором
расстоянии от нее и строго упорядочены по
расстоянию от начала участка дороги.
В общем случае задача распределения
земляных масс каръеров отличается от клас-
сической транспортной задачи тем, что ее
целевая функция может быть нелинейной.
ОБ ОДНОЙ ЗАДАЧЕ РАСПРЕДЕЛЕНИЯ ЗЕМЛЯНЫХ МАСС И АЛГОРИТМЕ ЕЕ РЕШЕНИЯ
Теорія оптимальних рішень. 2009, № 8 51
Стоимость перевозки грунта от поставщиков к потребителям зависит не только
от транспортных затрат, но и от количества поставщиков грунтов, их типов
и т. п. Кроме того, необходимо учитывать дополнительные затраты на строи-
тельство дороги от поставщиков грунтов к сооружаемому объекту и другие
расходы. Задача РЗМК – это задача со своими специфическими особенностями,
в общем случае, и нелинейная, и недифференцируемая, суть которой состоит
в следующем.
Есть множество потребителей грунта, расположенных по трассе железной
дороги, каждому из которых требуется определенный объем грунта для соору-
жения насыпи, и множество поставщиков грунта. Требуется определить план
перевозки (доставки) грунта таким образом, чтобы все потребности (объемы
грунта) потребителей были удовлетворены и суммарные повариантно-
составляющие стоимости сооружения земляного полотна были минимальными.
Структура задачи РЗМК такова, что для нахождения ее решения может быть
применен известный и эффективный для решения оптимизационных задач на
объектах протяжной структуры метод последовательного анализа вариантов [1].
В математических терминах задачу РЗМК можно сформулировать следую-
щим образом [2].
Пусть на участке сооружения земляного полотна [ ]nxx ,0 заданы множество
абсцисс характерных точек земли вдоль трассы { } njxX j ,0, == , и множество
{ }, 1,jV v j n= = , каждый элемент которого определяет необходимое количество
(объем) грунта для возведения насыпи на участке [ ] njxx jj ,1,,1 =− . Пусть
{ }mM ,...,2,1= – множество номеров поставщиков грунта (карьеров),
{ }nN ,...,2,1= – множество номеров потребителей грунта, { }m
izZ
1
= – множество
абсцисс характерных точек земли, определяющих участки [ ] mizz ii ,1,,1 =− ,
XZxzxz nm ⊂== ,,00 , на которые может быть осуществлена доставка грунта в
заданных объемах от і-го поставщика.
Каждому Zz i ∈ поставим в соответствие множества
{ }1 , , 1,i j i j i jX x z x z x X i m−= < ≤ ∈ = , (1)
и { } { }jjiiji zxzMjjvV ≤<∈== −1:, .
Множества miX i ,1, = , таковы, что U
m
i
iXX
1
.
=
=
В.И. БИЛЕЦКИЙ
Теорія оптимальних рішень. 2009,
№ 8
52
Задача заключается в нахождении таких { } ,,1,, miXzzZ ii =∈= опреде-
ляющих участки [ ]ii zz ,1− и множества
{ } ,,,,0,,| 1 MsrsrXXXxzxzxX srjijiji ∈≠=∈≤<= − I
и { } { }, : , 1, ,iji ijV v j j x X i m= ∈ ∈ = чтобы при разработке грунтов в i -х
источниках (поставщиках), а также при перевозке их и возведении земляного
полотна на участках [ ] ,,1,,1 mizz ii =− достигался минимум суммарных строи-
тельных (по стоимости) затрат, т. е. найти
1 1
min ( )
m n
i ij
i j
f v
= =
∑∑
(2) при выполнении условий:
∑
∈
=≤
iJj
iij miBv ,,1, (3)
,,,1,0 iij Jjmiv ∈=≥ (4)
{ } .,,1,:
1
NJmiXxjJ
m
i
iiji ==∈=
=
U
Здесь ijv – объем грунта, разрабатываемого в i -м источнике и перевозимого
на j -й участок насыпи 1, , ( )j j ij ijx x f v− – строительные стоимостные затраты,
связанные с разработкой и доставкой грунта от i -го источника в количестве ijv
и возведением земляного полотна на участке 1, ,j j ix x B− – мощность
(объем грунта) i -го поставщика.
В критерий оценки повариантно-составляющих на сооружение насыпи на
участке [ ] ,,1,,1 njxx jj =− входят стоимость перевозки грунта от источника к
потребителю, стоимость сооружения дороги от поставщика к трассе железной
дороги, ее ремонта и содержания, стоимость подготовительных работ, разработ-
ки непригодных грунтов выемок и их транспортирования, и другие составляю-
щие.
Для описания схемы алгоритма решения дадим постановку задачи (2)–(4)
в несколько другом виде.
Как уже было сказано, особенность задачи РЗМК состоит в том, что по-
ставщики грунта, как правило, расположены вдоль трассы дороги на некотором
расстоянии от нее и строго упорядочены по расстоянию относительно начала
строительства железнодорожного полотна.
Предположим, что каждый поставщик Ni∈ обеспечивает грунтом группу
потребителей iX , расположенных один за одним, которые образуют таким
образом сплошной отрезок и определяют зону влияния поставщика. Тогда реше-
ОБ ОДНОЙ ЗАДАЧЕ РАСПРЕДЕЛЕНИЯ ЗЕМЛЯНЫХ МАСС И АЛГОРИТМЕ ЕЕ РЕШЕНИЯ
Теорія оптимальних рішень. 2009, № 8 53
нием задачи (2)–(4) будет совокупность (или последовательность) непересекаю-
щихся отрезков [ ] ,,,,0,,1,,1 MsrsrXXmixxX sriii ∈≠=== − I
которые покрывают весь участок строительства [ ] U
m
i
in Xxx
1
0 ,
=
= .
Начало каждого такого отрезка совпадает с абсциссой начала первой насы-
пи, а конец отрезка совпадает с абсциссой конца последней насыпи в зоне влия-
ния поставщика.
Предположим, что мощности каждого поставщика достаточно для того, что-
бы обеспечить в потребности отведенный ему отрезок насыпи, т. е. для каждого
потребителя выполняется условие
{ }∑
∈
− =∈≤<=⊃≥
iJj
iijiiiji miXxxxxjJNvB ,1,,:, 1
.
Общие затраты могут быть выражены в виде суммы
∑∑ ∑
= ∈ =
−==
m
i Jj
i
m
i
iiji
i
xxFvfXZ
1 1
1 ),()()( , (5)
где ),( 1 ii xxF − – затраты, связанные с доставкой грунта и сооружением насыпи
на участке [ ]ii xx ,1− – зоны влияния i -го поставщика.
В такой трактовке задачу РЗМК можно сформулировать следующим обра-
зом.
Необходимо найти такую последовательность непересекающихся отрезков
1
, 1, , , 0, , , ,
m
i i r s
i
X i m X X X X r s r s M
=
= = = ≠ ∈U I
чтобы общие затраты (5) были минимальными, т. е. необходимо найти
)(min XZ (6)
при выполнении условий:
, 1, ,
i
ij i
j J
v B i m
∈
≤ =∑ (7)
1
0, 1, , , .
m
ij i i
i
v i m j J J N
=
≥ = ∈ =U (8)
В.И. БИЛЕЦКИЙ
Теорія оптимальних рішень. 2009,
№ 8
54
Если на каком-то участке строительства [ ] ,,,1 Njxx jj ∈− насыпи нет (отсут-
ствует), то для таких участков 0.ijv =
Для решения задачи (5)–(8) можно применить один из алгоритмов решения
оптимизационных задач на объектах протяженной структуры методом последо-
вательного анализа вариантов – это алгоритм корректирования проектных
решений по одному параметру [3].
Пусть ),...,,,...,,( 000
1
0
1
0
0
0
mii xxxxxX −= – некоторое начальное решение за-
дачи (5)–(8), nm xxxx == 0
,0
0
0 . Для каждого ,1,1,0 −= mixi определяем область
варьирования 0 0,i i iG x x = − δ + δ , где δ – некоторый заданный параметр и
такой, чтобы выполнялось условие [ ]0
1
0
1 , +−⊆ iii xxG . Для всего участка строи-
тельства дороги область варьирования определяется таким образом:
mGGGG ×××= ...21 .
На первом шаге для всех отрезков [ ] ,,,, 11
0
0010 Gxxxxx ∈= определяем
расходы ),()( 1011 xxFxZ = на доставку грунта от первого поставщика.
На всех последующих шагах mi ,2= последовательно для каждого i
определяем суммарные строительные затраты
,),()()( 111 iiiiii xxFxZxZ −−− +=
где ),( 1 ii xxF − – расходы на доставку грунта от i -го поставщика на отрезок
насыпей [ ]ii xx ,1− , а затем из множества сравнимых вариантов для каждого
ii Gx ∈ отбираем лучший (по критерию стоимости), используя рекуррентное
соотношение
.,2,)),()((min)( 111
11
mixxFxZxZ iiii
Gx
ii
ii
=+= −−−
∈ −−
(9)
Оптимальный вариант определяется по формуле (9) при значении Mi = .
Необходимо отметить, что при конструировании допустимых вариантов
учитываются единственные ограничения – это реальные мощности каждого
поставщика.
Для нахождения решения обязательным является выполнение условия
∑ ∑∑
= = =
≥
m
i
m
i
n
j
iji vB
1 1 1
,
(10) т. е. сумма объемов грунта по всем поставщикам должна превышать сум-
марные потребности всех потребителей грунта.
Если условие (10) не выполняется, то необходимо найти дополнительный
источник грунта (возможно не один), лишь бы достичь его выполнения.
ОБ ОДНОЙ ЗАДАЧЕ РАСПРЕДЕЛЕНИЯ ЗЕМЛЯНЫХ МАСС И АЛГОРИТМЕ ЕЕ РЕШЕНИЯ
Теорія оптимальних рішень. 2009, № 8 55
Если начальное решение 0X задачи (5)– (8) неизвестно, то оно может быть
задано последовательностью полусумм абсцисс крайних точек отрезков
,,1,1 miXXd iii == − I при выполнении условия
MiXX ii ∈∀≠− 01 I . (11)
Если условие (11) не выполняется, то необходимо подкорректировать зоны
влияния поставщиков таким образом, чтобы оно выполнялось.
Замечание. Если сооружение насыпей осуществляется из грунтов различных
типов, то поиск решения задачи сводится к последовательности решения задач
(5)–(8) для каждого типа грунта путем целенаправленного распределения мно-
жества источников грунта различных типов.
В.І. Білецький
ПРО ОДНУ ЗАДАЧУ РОЗПОДІЛЕННЯ ЗЕМЛЯНИХ МАС
І АЛГОРИТМ ЇЇ РОЗВ’ЯЗУВАННЯ
Наводиться постановка однієї задачі розподілення земляних мас, коли грунт із виїмок непри-
датний для спорудження насипів і поставщиками грунту для них є кар’єри, які розташовані
вздовж траси дороги на певній відстані від неї. Відмічаються особливості задачі розподілення
земляних мас кар’єрів, описується схема алгоритму розв’язування задачі на основі методу
послідовного аналізу варіантів.
V.I. Biletsky
ON A PROBLEM OF SOIL MASS DISTRIBUTION AND THE
ALGORITHM OF ITS SOLUTION
We consider a problem of soil mass distribution, when the soil from the groove is inappropriate for
levee construction and the soil is taken from borrows, located along the road at a certain distance
from it. We point out peculiarities of the borrov soil mass distribution problem, describe the algo-
rithm of its solution using the method of sequential analysis of variants.
1. Вычислительные методы выбора оптимальных проектных решений / В.С. Михалевич,
Н.З. Шор, Л.А. Галустова и др. − Киев: Наук. думка, 1977. − 178 с.
2. Сибирко А.Н., Зайцев Р.В. Последовательные алгоритмы оптимизации при строительстве
сложных протяженных объектов // Кибернетика. – 1988. – № 5. – С. 63–69.
3. О комплексе задач оптимизации проектных решений по профилю сложных участков
дорог (на примере БАМ) / В.С. Михалевич, В.И. Билецкий, Р.В. Зайцев и др. – Киев, 1980.
– 46 с. – (Препр./ ИК АН УССР, Ин-т кибернетики; 80-29).
Получено 19.03.2009
|
| id | nasplib_isofts_kiev_ua-123456789-46638 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-01T00:08:10Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Билецкий, В.И. 2013-07-04T18:49:44Z 2013-07-04T18:49:44Z 2009 Об одной задаче распределения земляных масс и алгоритме ее решения / В.И. Билецкий // Теорія оптимальних рішень: Зб. наук. пр. — 2009. — № 8. — С. 50-55. — Бібліогр.: 3 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/46638 519.8 Приводится постановка задачи распределения земляных масс для случая, когда грунт с выемок непригоден для сооружения насыпей и поставщиками грунта для насыпей являются карьеры, расположенные вдоль трассы дороги на некотором расстоянии от нее. Отмечаются особенности задачи распределения земляных масс карьеров, описывается схема алгоритма ее решения на основе метода последовательного анализа вариантов. Наводиться постановка однієї задачі розподілення земляних мас, коли грунт із виїмок непридатний для спорудження насипів і поставщиками грунту для них є кар’єри, які розташовані вздовж траси дороги на певній відстані від неї. Відмічаються особливості задачі розподілення земляних мас кар’єрів, описується схема алгоритму розв’язування задачі на основі методу послідовного аналізу варіантів. We consider a problem of soil mass distribution, when the soil from the groove is inappropriate for levee construction and the soil is taken from borrows, located along the road at a certain distance from it. We point out peculiarities of the borrov soil mass distribution problem, describe the algorithm of its solution using the method of sequential analysis of variants. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Об одной задаче распределения земляных масс и алгоритме ее решения Про одну задачу розподілення земляних мас і алгоритм її розв’язування On a problem of soil mass distribution and the algorithm of its solution Article published earlier |
| spellingShingle | Об одной задаче распределения земляных масс и алгоритме ее решения Билецкий, В.И. |
| title | Об одной задаче распределения земляных масс и алгоритме ее решения |
| title_alt | Про одну задачу розподілення земляних мас і алгоритм її розв’язування On a problem of soil mass distribution and the algorithm of its solution |
| title_full | Об одной задаче распределения земляных масс и алгоритме ее решения |
| title_fullStr | Об одной задаче распределения земляных масс и алгоритме ее решения |
| title_full_unstemmed | Об одной задаче распределения земляных масс и алгоритме ее решения |
| title_short | Об одной задаче распределения земляных масс и алгоритме ее решения |
| title_sort | об одной задаче распределения земляных масс и алгоритме ее решения |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/46638 |
| work_keys_str_mv | AT bileckiivi obodnoizadačeraspredeleniâzemlânyhmassialgoritmeeerešeniâ AT bileckiivi proodnuzadačurozpodílennâzemlânihmasíalgoritmíírozvâzuvannâ AT bileckiivi onaproblemofsoilmassdistributionandthealgorithmofitssolution |