close

Вход

Забыли?

вход по аккаунту

?

PFP

код для вставкиСкачать
РОСЖЕЛДОР
Государственное образовательное учреждение
высшего профессионального образования
«Ростовский государственный университет путей сообщения»
(РГУПС)
В.Н. Скляров
СОВЕРШЕНСТВОВАНИЕ ТЕХНОЛОГИИ
РАБОТЫ НАПРАВЛЕНИЙ И СИСТЕМЫ
ОРГАНИЗАЦИИ ВАГОНОПОТОКОВ
Учебно-методическое пособие
Часть 2. Расчет оптимального варианта плана формирования поездов
методом ветвей и границ.
Ростов-на-Дону
2008
УДК 656.225(07)+06
Скляров, В.Н.
Совершенствование технологии работы направлений и системы орга
­
низации вагонопотоков Ч. II
Расчет оптимального варианта плана формиро
­
вания поездов методом ветвей и границ/ В.Н. Скляров. Рост. гос. ун-т путей
сообщения. – Ростов
н/Д, 2008. ___ с. : ил.
Рецензенты: начальник службы перевозок СКЖД И.Н. Филатов
канд. техн. наук, проф. В.Н. Зубков (РГУПС)
Учебно-методическое пособие посвящено описанию методики и алго
­
ритма расчета оптимального варианта плана формирования поездов на транс
­
портном полигоне. Приведены постановка задачи, теоретические основы ре
­
шения, описана программа автоматизации расчета. Предложены варианты
исходных данных для самостоятельных вычислений.
Пособие рекомендовано для студентов очной и заочной форм обучения
по специальностям «190701 – Организация перевозок и управление на транс
­
порте (железнодорожный транспорт)».
© Ростовский государственный университет
путей сообщения, 2008
СОЖЕРЖАНИЕ
Стр.
Введение
4
1. Постановка задачи
4
2. Теоретические основы решения
9
3. Алгоритм поиска оптимального варианта плана формирования поез
­
дов
15
4. Адаптация исходных данных для автоматизированного расчета пла
­
на формирования поездов
19
5. Программа автоматизированного расчета плана формирования поез
­
дов
21
6. Варианты заданий для самостоятельных вычислений
23
7. Рекомендации по выполнению самостоятельных расчетов
27
8. Список литературы
30
9. Приложение 1. Краткие сведения из теории графов
31
ВВЕДЕНИЕ
Расчет
1
оптимального варианта плана формирования поездов является
важным этапом управления грузовыми перевозками на железнодорожном
транспорте. Данная задача характеризуется многовариантностью решений и
большим объемом итеративных вычислительных операций. Поэтому од
­
новременно с глубоким проникновением ЭВМ в производственные и обуча
­
ющие процессы актуальной стала автоматизация решения задачи расчета оп
­
тимального варианта плана формирования поездов.
В настоящем пособии описание метода и алгоритма решения задачи
основано на применении одной из программ автоматизированного расчета
плана формирования, разработанной автором. В обучающем процессе это
упрощает понимание излагаемого материала, позволяя опускать описание
отдельных вычислительных операций, выполняемых автоматически. С при
­
кладной точки зрения, пошаговое выполнение расчетов дает возможность ис
­
следовать устойчивость оптимального плана к изменениям исходных дан
­
ных, разработать рекомендации по ее повышению.
1. ПОСТАНОВКА ЗАДАЧИ
Основная цель задачи поиска оптимального варианта плана формиро
­
вания поездов - найти такой вариант включения вагонов с грузами в поез
­
да различных назначений и категорий и определить такие маршруты
следования поездов, которые обеспечат минимальные общие затраты на
выполнение перевозок
. Для наглядности дальнейших рассуждений приведем рисунок 1, на ко
­
тором изображен полигон транспортной сети )
,
(
E
V
G
=
(
V
- множество стан
­
ций полигона, E
- множество участков полигона). Ниже стрелками указаны
назначения
V
j
i
j
i
∈
,
);
,
(
вагонов с грузами, предъявленные на станциях к
1
Более корректно было бы говорить о поиске
оптимального варианта плана формирования поездов на мно
­
жестве возможных вариантов. Однако термин «
расчет
» является более традиционным в эксплуатационной
практике. В данном контексте эти выражения идентичны, в настоящем учебно-методическом пособии будут
применяться как одно, так и другое.
перевозке. Каждое назначение характеризуется мощностью
ij
N
- количе
­
ством вагонов, предъявленных к перевозке. Назначение )
,
(
j
i
с ненулевой
мощностью ij
N
называется вагонопотоком
.
Рисунок 1.
Существует два принципиальных способа включения вагонопотока
сквозного назначения
2
в различные поезда:
1) Назначить для вагонопотока отдельный поезд. Например, для вагонопото
­
ка назначением А-Г назначить поезд А-Г
. Для того, чтобы технологически
и экономически обосновать применение данного способа, определяется
необходимая (нормативная) длина поезда (измеряемая в условных ваго
­
нах). В ожидании накопления нужного количества вагонов для формиро
­
вания такого поезда, часть вагонов простаивает на станции формирования
поезда. В результате возникают затраты накопления
нак
Z
. Величина нак
Z
определяется как некоторое среднесуточное
значение за
­
трат формирования исходного среднесуточного вагонопотока в поезда
самостоятельного назначения. Анализ величины нак
Z
, приведенный в [1]
позволил установить, что ее значение не зависит от среднесуточной мощ
­
ности исходного вагонопотока. 2) Для того, чтобы уменьшить затраты нак
Z
применяют второй способ - вклю
­
чают вагонопоток сквозного назначения в состав поездов более коротких
2
Напомним, что сквозным называется назначение, маршрут следования которого включает хотя бы одну
транзитную станцию Маршрут назначения не обладающий данным свойством называется участковым.
)
,
(
E
V
G
=
А
Б
В
Г
назначений (сквозных или участковых), объединив тем самым несколько
различных вагонопотоков в один поезд. Например, вагонопоток назначе
­
нием А-Г можно включить в состав поезда А-Б, объединив его с вагоно
­
потоком соответствующего назначения, а затем на станции Б объеди
­
нить его с вагонопотоком Б-Г и назначить поезд Б-Г
. Тогда на транзит
­
ных стыковых станциях
3
(
в приведенном примере – станция Б
) возникают
затраты на переработку вагонов на транзитных станциях пер
Z
. При
­
рода возникновения и состав этих затрат подробно описаны в [2]. Затраты
пер
Z
вычисляются в расчете на один перерабатываемый вагон назначения.
Соответственно, общее значение затрат пропорционально мощности
перерабатываемого вагонопотока.
Таким образом, если принять что в практической задаче существует не
­
которое множество исходных сквозных вагонопотоков (
для примера на ри
­
сунке 1это множество состоит из двух элементов
), каждый из которых
имеет ij
K
вариантов включения в поезда различных назначений (
2
,
3
=
=
−
−
Г
Б
Г
А
K
K
), то существует ∏
∀
)
,
(
j
i
l
ij
K
вариантов организации вагонопото
­
ков, каждый из которых характеризуется некоторым значением затрат на ор
­
ганизацию перевозок. Возможные варианты для примера на рисунке 1 и со
­
ответствующие формулы расчета затрат приведены на рисунке 2.
Кроме затрат на накопление и переработку вагонов (т.е., затрат на орга
­
низацию перевозок) непосредственно при выполнении перевозок возникают
затраты в движении
дв
Z
, которые на разных участках могут быть различ
­
ны. Если схема транспортного полигона предусматривает несколько различ
­
ных маршрутов движения между станциями отправления и назначения, чис
­
ло возможных вариантов еще больше увеличивается. Так если затраты в дви
­
3
В данном контексте под стыковой транзитной станцией будем понимать станцию стыковки соприкасаю
­
щихся назначений
жении по линиям I
и II
направления А-Б (рисунок 2) не одинаковы, то общее
количество вариантов организации поездов возрастает до 12
4
.
Рисунок 2
4
Необходимо помнить, что при решении практической задачи ее сложность еще больше
возрастает, т.к. зависимость доли затрат на единицу перевозимого груза от объема перево
­
зок носит нелинейный характер. Поэтому в качестве альтернативных вариантов необходи
­
мо рассматривать различные ситуации при которых часть исходного вагонопотока целесо
­
образно перевозить по параллельным маршрутам.
)
(
)
(
)
(
В
Z
Z
В
Z
Б
Z
Z
пер
Г
Б
нак
Г
Б
пер
Г
А
пер
Г
А
нак
Г
А
−
−
−
−
−
+
+
+
+
А
Б
В
Г
Вариант №1
Г
А
N
−
Г
Б
N
−
Вариант №2
Г
А
N
−
Г
Б
N
−
Г
Б
N
−
Вариант №3
Г
А
N
−
Г
А
Г
Б
N
N
−
−
+
Вариант №4
Г
А
N
−
Г
А
Г
Б
N
N
−
−
+
Г
А
Г
Б
N
N
−
−
+
Вариант №5
Г
А
N
−
Г
Б
N
−
Г
А
N
−
Вариант №6
Г
А
N
−
Г
Б
N
−
Г
Б
Г
А
N
N
−
−
+
Затраты на организацию
перевозок
нак
Г
Б
нак
Г
А
Z
Z
−
−
+
пер
Г
Б
нак
Г
Б
нак
Г
А
Z
Z
Z
−
−
−
+
+
нак
Г
Б
пер
Г
А
нак
Г
А
Z
Б
Z
Z
−
−
−
+
+
)
(
нак
Г
Б
пер
Г
А
нак
Г
А
Z
В
Z
Z
−
−
−
+
+
)
(
)
(
)
(
В
Z
Z
В
Z
Z
пер
Г
Б
нак
Г
Б
пер
Г
А
нак
Г
А
−
−
−
−
+
+
+
I
II
Очевидно, что наилучшим (оптимальным) будет являться тот вариант,
который обеспечит минимальные общие затраты на организацию и выполне
­
ние перевозок:
min
→
+
+
=
∑
∑
∑
дв
пре
нак
Z
Z
Z
Z
(1)
Функция (1) называется целевой функцией
задачи расчета оптимально
­
го варианта плана формирования поездов.
Как видно, задача нахождения оптимального варианта плана формиро
­
вания поездов характеризуется многовариантностью
решений. Данное свой
­
ство означает, что для решаемых задач данного типа в пределах дороги (т.е.
когда число исходных сквозных вагонопотоков определяется десятками)
множество допустимых вариантов плана формирования настолько велико,
что поиск наилучшего, основанный на полном переборе всех возможных ва
­
риантов является неэффективным с точки зрения временных затрат.
Например, если на линейном участке (без параллельных маршрутов)
имеется 10 сквозных назначений, а среднее количество вариантов включения
каждого назначения в различные поезда равно 3, то общее количество вари
­
антов организации вагонопотоков будет равно 59049
3
10
=
.
Поэтому для решения задачи применяются различные алгоритмы [3,4],
построенные на принципе направленного перебора вариантов. Выбор того
или иного алгоритма осуществляется на основе двух критериев – точности и
скорости расчета. Более подробно описание критериев выбора приведено в
[5,6].
В данной работе для решения задачи расчета плана формирования
поездов применяется один из наиболее наглядных и эффективных алгорит
­
мов, основанный на методе «ветвей и границ». 2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ РЕШЕНИЯ
I
.
Результаты научных и экспериментальных исследований [1] природы
изменения затрат на организацию вагонопотоков в поезда (
пер
нак
Z
Z
,
) с одной
стороны, и затрат в процессе движения (
дв
Z
) – с другой не выявили функцио
­
нальных связей между ними. Это позволило привести целевую функцию (1) к
виду:
)
min(
)
min(
∑
∑
∑
+
+
=
дв
пер
нак
Z
Z
Z
Z
(2)
Целевая функция (2) позволяет разбить процедуру нахождения опти
­
мального варианта плана формирования поездов на два этапа
:
1. Выбор оптимальных маршрутов следования. На данном этапе для каждого
исходного вагонопотока определяется единственный, наиболее рациональ
­
ный маршрут следования, обеспечивающий минимальные затраты в дви
­
жении. По существу – это отдельная алгоритмическая задача, она доста
­
точно хорошо изучена, существуют различные алгоритмы ее решения по
­
дробно описанные в [7]
5
.
2. Направленный перебор возможных вариантов организации перевозок. По
результатам реализации данного этапа определяется вариант плана фор
­
мирования поездов, обеспечивающий минимальные общие затраты на ор
­
ганизацию и выполнение заданного объема перевозок.
II
.
Как известно [8], метод направленного перебора сводится к уменьше
­
нию множества рассматриваемых вариантов решения за счет исключения на
основе некоторых правил подмножества заведомо неперспективных вариан
­
тов.
Применительно к задаче нахождения оптимального плана формирова
­
ния поездов, правило исключения формулируется следующим образом: к
5
Поэтому, в целях обеспечения целостности восприятия изучаемого метода направленного перебора, в дан
­
ной лабораторной работе алгоритм решения первого этапа рассматриваться не будет, а схемы участков до
­
рог в вариантах заданий приняты линейными, т.е. не имеют параллельных маршрутов следования.
НЕперспективным относятся такие варианты, которые 1) НЕ включа
­
ют в себя все обязательные назначения и 2) включают хотя бы одно НЕ
­
перспективное назначение
. Приведенная постановка задачи разделяет все
множество исходных сквозных назначений на три непересекающиеся под
­
множества: обязательных назначений O
, неперспективных (исключаемых)
назначений I
и перспективных (рассматриваемых) назначений P
.
Накопленный опыт организации грузовых перевозок позволил сформу
­
лировать два эвристических условия, однозначно определяющие такое разде
­
ление. В основе формулируемых условий заложена следующая идея: для того
чтобы план формирования обеспечивал минимальные общие затраты на орга
­
низацию перевозок, необходимо и достаточно, чтобы прикрепление каждого
исходного вагонопотока к назначениям плана обеспечивало минимальные за
­
траты на его организацию в различные поезда.
Первое – общее достаточное условие
(ОДУ), - выделяет из множества
исходных сквозных назначений все обязательные. Оно формулируется следу
­
ющим образом: если затраты накопления исходного вагонопотока некоторо
­
го назначения меньше или равны
6
затратам на его переработку на любой из
транзитных станций маршрута следования, то одноименное назначение обя
­
зательно выделяется в оптимальный вариант плана формирования:
}
min{
пер
ij
нак
ij
Z
Z
≤
(3)
Т.е., если назначение, удовлетворяющее условию (3), не будет включе
­
но в оптимальный вариант, то организация одноименного вагонопотока лю
­
бым другим способом будет более затратной, а значит и оптимальный вари
­
ант плана формирования не будет найден. Все участковые назначения при
­
числяются к обязательным автоматически, без проверки на условие (3).
Второе – необходимое условие
(НУ) – позволяет выделить все непер
­
спективные назначения: если затраты накопления максимально усиленного
6
Необходимо заметить, что применение в данной формулировке нестрогого неравенства связано с особен
­
ностями организации перевозочного процесса и направлено на повышение транзитности перевозок.
вагонопотока некоторого назначения превышают суммарные затраты на его
переработку по всем транзитным станциям, то такое назначение не может
быть включено в оптимальный вариант плана формирования:
∑
>
пер
ij
нак
ij
Z
Z
(4)
Все назначения, которые не удовлетворяют ни одному из приведенных
условий являются перспективными. III
.
Процедура усиления любого рассматриваемого назначения сводится к
увеличению мощности его вагонопотока за счет объединения с более дальни
­
ми назначениями, маршрут следования которых включает в себя маршрут
рассматриваемого назначения. Например, если мы говорим, что усиливаем
назначение Б-Г (рисунок 1) за счет назначения А-Г, это значит, что мы
объединяем вагонопотоки соответствующих назначений на маршруте Б-Г
.
Соответственно, максимальное усиление вагонопотока рассматриваемого на
­
значения означает его объединение со всеми назначениями, включающими в
себя маршрут его следования.
Причину того, что при формулировании необходимого условия мы
рассматриваем максимально усиленный вагонопоток назначения, а не исход
­
ный, легко понять, рассмотрев пример, приведенный на рисунке 3.
Рисунок 3
Как видно, вагонопоток назначением А-Д является самым дальним,
поэтому он не может быть усилен никаким другим вагонопотоком и, соответ
­
4
)
(
=
−
В
Z
пер
Г
Б
30
=
−
Г
Б
N
4
)
(
;
3
)
(
=
=
−
−
В
Z
Б
Z
пер
Г
А
пер
Г
А
70
=
−
Г
А
N
А
Б
В
Г
Д
500
=
−
нак
Д
А
Z
500
=
−
нак
Г
А
Z
500
=
−
нак
Г
Б
Z
53
=
−
Д
А
N
3
)
(
;
4
)
(
;
3
)
(
=
=
=
−
−
−
Г
Z
В
Z
Б
Z
пер
Д
А
пер
Д
А
пер
Д
А
ственно, проверка его на НУ выглядит так:
(
)
530
)
(
)
(
)
(
*
;
500
=
+
+
=
=
−
−
−
−
−
Г
Z
В
Z
Б
Z
N
Z
Z
пер
Д
А
пер
Д
А
пер
Д
А
Д
А
пер
общ
нак
Д
А
⇒
пер
общ
нак
Д
А
Z
Z
<
−
Условие (4) не выполняется, а значит назначение не является непер
­
спективным (т.е., является перспективным).
Если, проверяя назначения А-Г и Б-Г, мы будем рассматривать лишь
исходные (не усиленные) вагонопотоки, то в этом случае оба назначения бу
­
дут удовлетворять условию (4), т.е. являться неперспективными:
(
)
пер
общ
нак
АГ
пер
Г
А
пер
Г
А
Г
А
пер
общ
нак
Г
А
Z
Z
В
Z
Б
Z
N
Z
Z
>
⇒
=
+
=
=
−
−
−
−
490
)
(
)
(
*
;
500
пер
общ
нак
Г
Б
пер
Г
Б
Г
Б
пер
общ
нак
Г
Б
Z
Z
В
Z
N
Z
Z
>
⇒
=
=
=
−
−
−
−
120
)
(
*
;
500
В этом случае, единственное перспективное назначение А-Д образует
лишь один вариант, включающий назначения {А-Д, А-Б, Б-В, В-Г, Г-Д}.
Именно этот вариант из-за отсутствия альтернативы и будет принят нами как
оптимальный. Затраты на организацию перевозок по варианту будут равны
(
)
(
)
3110
)
(
*
)
(
)
(
*
=
+
+
+
+
+
+
+
=
−
−
−
−
−
−
−
−
−
−
В
Z
N
В
Z
Б
Z
N
Z
Z
Z
Z
Z
Z
пер
Г
Б
Г
Б
пер
Г
А
пер
Г
А
Г
А
нак
Д
Г
нак
Г
В
нак
В
Б
нак
Б
А
нак
Д
А
общ
Однако, если мы усилим назначение А-Г назначением А-Д, а Б-Г - на
­
значением А-Д и А-Г, а затем проверим их на НУ, то увидим, что оба они бу
­
дут перспективными:
(
)
(
)
пер
общ
нак
Г
А
пер
Г
А
пер
Г
А
Д
А
Г
А
пер
общ
нак
Г
А
Z
Z
В
Z
Б
Z
N
N
Z
Z
<
⇒
=
+
+
=
=
−
−
−
−
−
−
861
)
(
)
(
*
;
500
(
)
пер
общ
нак
Г
Б
пер
Г
Б
Г
А
Д
А
Г
Б
пер
общ
нак
Г
Б
Z
Z
В
Z
N
N
N
Z
Z
<
⇒
=
+
+
=
=
−
−
−
−
−
−
612
)
(
*
;
500
При данных условиях различные сочетания полученных перспектив
­
ных назначений (А-Д, А-Г, Б-Г) образуют 8 различных схем перевозки исход
­
ных вагонопотоков (таблица 1). В общем случае, для каждой схемы суще
­
ствует несколько вариантов прикрепления исходных вагонопотоков, каждый
из которых характеризуется общими затратами на организацию перевозок.
Так, например, для схемы 5, образованной перспективными назначениями А-
Г и Б-Г существует 2 варианта прикрепления исходного вагонопотока А-Д
(рисунок 4).
А для схемы 7, включающей лишь одно сквозное назначение Б-Г суще
­
ствует 4 варианта прикрепления исходных вагонопотоков А-Д и А-Г ) рису
­
нок 5).
Таблица 1.
Таблица возможных схем, образованных перспективными назначениями
П
р
и
з
н
ак
в
к
л
ю
ч
е
н
и
я
н
аз
н
ач
е
н
и
я
в
с
хе
м
у
Перспективные назначения
Номер
схемы
А-Д
А-Г
Б-Г
Да
Да
Да
1
Нет
2
Нет
Да
3
Нет
4
Нет
Да
Да
5
Нет
6
Нет
Да
7
Нет
8
- станции переработки вагонопотока А-Д
Рисунок 4.
А
Б
В
Г
Д
Вариант 1
Вариант 2
Вариант 3
Однако, наименьшие общие затраты на организацию перевозок будет
иметь вариант, приведенный на рисунке 6 из которого видно, что достижение
оптимального варианта плана без усиления рассматриваемых назначений при
анализе на выполнение НУ невозможно.
- станции переработки вагонопотока А-Д
- станции переработки вагонопотока А-
Г
Рисунок 5.
(
)
3028
)
(
*
)
(
*
)
(
*
=
+
+
+
+
+
+
+
=
Г
Z
N
Б
Z
N
Б
Z
N
Z
Z
Z
Z
Z
Z
пер
АД
АД
пер
АГ
АГ
пер
АД
АД
нак
БГ
нак
ГД
нак
ВГ
нак
БВ
нак
АБ
общ
Рисунок 6.
А
Б
В
Г
Д
Вариант 1
Вариант 2
Вариант 3
Вариант 4
А
Б
В
Г
Д
АГ
АД
АБ
N
N
N
+
+
АГ
АД
БГ
N
N
N
+
+
АД
ГД
N
N
+
3. АЛГОРИТМ ПОИСКА ОПТИМАЛЬНОГО ВАРИАНТА ПЛАНА ФОР
­
МИРОВАНИЯ ПОЕЗДОВ
Очевидно, то каждое исходное назначение при проверке его на НУ мо
­
жет быть усилено потоками лишь тех назначений, которые не являются обя
­
зательными, т.е. не удовлетворяют ОДУ. В противном случае, выполнив та
­
кое усиление (т.е. отменив назначение удовлетворяющее ОДУ, и направив
его на усиление других более коротких назначений) мы не достигнем мини
­
мальных затрат на организацию его перевозки дальнего назначения. Поэто
­
му, на первом шаге
поиска методом направленного перебора необходимо из
множества исходных назначений найти и выделить все назначения, удовле
­
творяющие ОДУ.
Оставшиеся назначения необходимо разделить на перспективные и не
­
перспективные, применив условие (4). Но перед этим необходимо выполнить
операцию максимального усиления каждого назначения. Отсюда, вторым и
третьим шагом
алгоритма являются:
- максимальное усиление каждого назначения, более дальними, не удовлетво
­
ряющими ОДУ,
- выделение подмножества перспективных назначений по условию (4).
В результате выполнения этих шагов на первом этапе поиска оптималь
­
ного варианта плана мы разделили множество исходных назначений на три
непересекающиеся подмножества (O,I,P)
. Проанализируем их:
1. У нас имеются подмножество обязательных назначений оптимального пла
­
на формирования O
, которому соответствует некоторое фиксированное
значение затрат на накопление одноименных вагонопотоков (
нак
Z
min
).
2. У нас есть подмножество неперспективных назначений I
, которые не
должны включиться в оптимальный план, а значит одноименные потоки
должны быть прикреплены к более коротким обязательным назначениям
с минимальным значением затрат на переработку. Т.е. неперспективным
назначениям при их прикреплении с минимальными затратами на перера
­
ботку
7
соответствует некоторое фиксированное значение затрат перера
­
ботки (
пер
Z
min
).
3. О способе организации потоков одноименных с перспективными назначе
­
ниями (множество P
) мы пока не можем сказать ничего. Каждое из них
должно быть подвергнуто дополнительной проверке на целесообразность
выделения в оптимальный план.
Таким образом, результат выполнения первого этапа расчета мы можем
однозначно описать совокупностью данных )
,
,
,
,
(
min
min
пер
нак
Z
Z
P
I
O
, которые можно
интерпретировать следующим образом: на втором этапе расчета мы будем
осуществлять поиск оптимального варианта плана среди множества всех воз
­
можных вариантов которые 1) включают все назначения подмножества O
, 2)
не содержат ни одного назначения подмножества I
. Величина )
(
min
min
пер
нак
Z
Z
Z
+
=
определяет нижнюю границу затрат
на организацию перевозок по транс
­
портному участку на текущем шаге расчета.
Применив условия (3), (4), мы ввели ограничения на область дальней
­
шего поиска, тем самым сократив размерность решаемой задачи. Теперь мы
можем утверждать, что число допустимых вариантов плана после первого
этапа зависит только от количества перспективных назначений и определяет
­
ся как |
|
2
P
. Однако, это число может быть все еще настолько велико, что ме
­
тод полного перебора вариантов не будет эффективным.
Второй этап
расчета сводится к итеративной процедуре анализа пер
­
спективных назначений. Идея анализа заключается в следующем.
Имея на текущем шаге расчета множество перспективных назначений,
в оптимальный план прежде всего целесообразно выделить такое назначение
)
,
(
j
i
, которое обеспечит минимальное приращение )
min(
Z
Δ
нижней границы
затрат Z
. Это приращение включает следующие слагаемые:
- затраты накопления назначения )
,
(
j
i
- нак
j
i
Z
)
,
(
,
7
Данная задача сводится к определению кратчайшего пути на графе (см. приложение 1).
- приращение затрат переработки неперспективных вагонопотоков - пер
Z
Δ
.
Возникновение данной величины вызвано:
1) включением назначения )
,
(
j
i
в оптимальный план, и как следствие,
возможным изменением схемы переработки неперспективных ваго
­
нопотоков (рисунок 7).
2) изменением самого множества неперспективных вагонопотоков.
Данное изменение происходит из-за того, что выделяемый в опти
­
мальный план вагонопоток )
,
(
j
i
изменяет максимально усиленную
мощность более коротких перспективных назначений, а значит, не
­
которые из них уже возможно не будут удовлетворять условию (4)
(рисунок 8).
Таким образом, в результате присоединения назначения )
,
(
j
i
к множе
­
ству обязательных назначений происходят следующие изменения (рисунок
8):
- изменяется структура множеств I
P
,
,
- нижняя граница затрат увеличивается на величину )
min(
)
,
(
Z
Z
Z
нак
j
i
Δ
+
=
Δ
.
Анализ назначений множества P
следует повторять до тех пор, пока
оно не станет пустым.
- станции переработки вагонопотока А-Д
Рисунок 7
А
Б
В
Г
Д
Обязательные назначения
Перспективные назначения
Неперспективные назначения
Вариант прикрепления вагонопотока А-Д до
выделения Б-Г в множество обязательных
Вариант прикрепления вагонопотока А-Д после
выделения Б-Г в множество обязательных
Затраты переработки (ч) 2 3 3
После того как перспективных назначений не останется, оптимальный
вариант плана формирования поездов однозначно определяется тройкой
)
,
,
(
Z
I
O
в которой:
O
- множество назначений оптимального варианта плана формирова
­
ния поездов,
I
- множество неперспективных назначений, которые прикрепляются к
множеству обязательных с наименьшими затратами переработки,
Z
- значение затрат на организацию перевозок по оптимальному вари
­
анту плана формирования,
Рисунок 8
Расчет оптимального варианта плана формирования поездов по приве
­
денному алгоритму рекомендуется выполнять отдельно для каждого направ
­
Обязательные назначения
Перспективные назначения
Неперспективные назначения
Изменение множества неперспективных назначений после
включения назначения А-Г в множество обязательных
Затраты переработки (ч) 2 3 3
Обязательные назначения
Перспективных назначений НЕТ
Неперспективные назначения
Затраты накопления (в-ч)
500 500 500 500 360
2500
min
min
=
=
пер
нак
Z
Z
105
=
−
Г
А
N
65
=
−
Г
Б
N
60
=
−
Д
А
N
60
=
−
Д
А
N
65
=
−
Г
Б
N
375
3000
min
min
=
=
пер
нак
Z
Z
А
Б
В
Г
Д
ления (четного и нечетного). 4. АДАПТАЦИЯ ИСХОДНЫХ ДАННЫХ ДЛЯ АВТОМАТИЗИРОВАННО
­
ГО РАСЧЕТА ПЛАНА ФОРМИРОВАНИЯ ПОЕЗДОВ
Исходя из постановки задачи (раздел 1), к исходным данным относятся:
- транспортный полигон,
- множество вагонопотоков с заданными мощностями (измеряется в ко
­
личестве вагонов заявленных к перевозке за одни сутки),
- затраты накопления поездов на станциях формирования. В общем
случае размер затрат различен для каждого накапливаемого на стан
­
ции назначения (задается из расчета на один накапливаемый поезд),
- затраты переработки вагонов на транзитных станциях (также могут
быть различны для каждого перерабатываемого назначения, задают
­
ся из расчета на один перерабатываемый вагон),
Затраты могут изменяться в натуральных (вагонно-часы), стоимостных
(рубли) или иных единицах. Для выполнения автоматизированных расчетов оптимального варианта
плана формирования поездов, исходные данные необходимо адаптировать
для ввода в ЭВМ.
Транспортный полигон
Наиболее простым способом описания транспортного полигона являет
­
ся граф [7]. В свою очередь граф может быть представлен матрицей смежных
вершин T
(приложение 1). Если на рассматриваемом транспортном полигоне
для перегонов вводятся весовые коэффициенты ij
c
(которые могут, например
означать расстояние между соседними станциями i
и j
или себестоимость
проследования одного поезда от станции i
до станции j
), то каждый ненуле
­
вой элемент матрицы смежности T
заменяется соответствующим значением
коэффициента ij
c
.
Таким образом, описание транспортного полигона выполняется в сле
­
дующей последовательности. 1. Станции транспортного полигона нумеруются от 0 до 1
−
n
в произвольном
порядке.
2. Если станция с номером i
и станция с номером j
соединены участком, то
элементу матрицы, находящемуся на пересечении i
-й строки и j
-го столб
­
ца присваивается значение 1 (или если на транспортном полигоне введены
весовые коэффициенты – то соответствующее значение ij
c
). Остальные
элементы матрицы равны 0.
Исходные вагонопотоки
Данные представляются матрицей N
размерность n
n
×
по правилу:
если существует вагонопоток назначением )
,
(
j
i
и мощности ij
N
, то элемент
матрицы, находящийся на пересечении i
-й строки и j
-го столбца равен мощ
­
ности вагонопотока. Все остальные элементы равны 0
Затраты накопления
Затраты представляются матрицей нак
Z
размерности n
n
×
по правилу:
если на станции i
накапливается вагонопоток назначением на станцию j
, то
элемент матрицы, находящийся на пересечении i
-й строки и j
-го столбца ра
­
вен затратам накопления данного вагонопотока.
Затраты переработки
Данный вид затрат представлен матрицей пер
Z
размерности n
n
×
по пра
­
вилу: если на станции j
выполняется переработка вагонопотока, проследую
­
щего от станции i
, то элемент матрицы, находящийся на пересечении i
-й
строки и j
-го столбца равен затратам на один вагон переработки данного ва
­
гонопотока.
5. ПРОГРАММА АВТОМАТИЗИРОВАННОГО РАСЧЕТА ПЛАНА ФОРМИРОВАНИЯ ПОЕЗДОВ
Программа разработана для работы в среде Windows
. Интерфейс про
­
граммы представлен на рисунке 9.
Рисунок 9.
Ввод исходных данных начинается с задания количества станций
транспортного полигона (по умолчанию количество станций транспортного
полигона равно 7). Программа расчета автоматически генерирует матрицы
пер
нак
Z
Z
N
T
,
,
,
, все элементы которых равны 0.Выбор любой матрицы исход
­
ных данных для ее просмотра и корректировки выполняется нажатием соот
­
ветствующей кнопки на панели управления программы. Матрицы заполняют
­
ся в соответствиями с исходными значениями по правилам, описанным в
предыдущем разделе.
После ввода исходных данных программа автоматически рассчитывает
количество возможных вариантов плана формирования поездов (определяет
размерность задачи).
Расчет оптимального варианта плана формирования поездов выполня
­
ется пошагово в соответствии с алгоритмом, приведенным в разделе 3 посо
­
бия. Необходимые вычисления на каждом шаге расчета выполняются путем
нажатия соответствующей кнопки на панели управления программы.
Результаты расчетов отображаются в виде таблицы.
После последнего шага вычислений программа выводит следующие ре
­
зультаты:
- оптимальный вариант плана формирования поездов. Данные представлены
в виде квадратной матрицы в которой ненулевые элементы соответствуют
назначениям, включенным в оптимальный план. Выбрав любое назначение
(установив курсор на соответствующую ячейку) можно посмотреть следу
­
ющую информацию о вагонопотоках, прикрепляемых к данному назначе
­
нию и суммарную мощность назначения.
- общие затраты накопления и переработки по оптимальному варианту плана
формирования поездов.
Все исходные и расчетные данные автоматически сохраняются, что
позволяет выполнять их просмотр и корректировку во время последующих
запусков программы.
6. ВАРИАНТЫ ЗАДАНИЙ ДЛЯ САМОСТОЯТЕЛЬНЫХ РАСЧЕТОВ
Расчетный полигон транспортной сети
Номер станции
1
2
3
4
5
6
7
Затраты накопления
500
500
500
500
500
500
0
Затраты на переработку
Вариант № 1
0
2
3
2
3
2
0
Вариант № 2
0
4
5
2
4
3
0
Вариант № 3
0
4
2
5
3
4
0
Вариант № 4
0
4
2
3
2
4
0
Вариант № 5
0
3
3
4
4
2
0
Вариант № 6
0
3
4
2
4
4
0
Вариант № 7
0
3
3
5
4
5
0
Вариант № 8
0
5
2
4
5
2
0
Вариант № 9
0
5
3
2
2
3
0
Вариант № 1
0
0
5
2
3
2
4
0
Расчетные вагонопотоки
Вариант №1
Станция назначения
Станция отправления
1
2
3
4
5
6
7
1
100
100
60
10
50
300
2
100
20
70
10
260
3
100
240
10
20
4
100
120
10
5
100
200
6
100
7
Вариант №2
Станция назначения
Станция отправления
1
2
3
4
5
6
7
1
110
80
50
9
56
318
2
107
21
90
11
316
3
84
172
9
24
4
72
107
12
5
77
223
6
124
7
Вариант №3
Станция назначения
Станция отправления
1
2
3
4
5
6
7
1
89
93
49
10
65
259
2
73
24
61
11
212
3
77
282
10
16
4
110
95
9
5
76
157
6
102
7
Вариант №4
Станция назначения
Станция отправления
1
2
3
4
5
6
7
1
94
105
78
9
38
374
2
71
16
52
10
332
3
111
305
12
19
4
96
96
12
5
97
257
6
96
7
Вариант №5
Станция назначения
Станция отправления
1
2
3
4
5
6
7
1
128
79
77
13
40
336
2
105
15
52
12
250
3
93
245
11
17
4
104
103
12
5
95
158
6
82
7
Вариант №6
Станция назначения
Станция отправления
1
2
3
4
5
6
7
1
88
120
52
8
53
248
2
79
23
80
11
205
3
90
225
11
15
4
118
91
13
5
75
255
6
89
7
Вариант №7
Станция назначения
Станция отправления
1
2
3
4
5
6
7
1
78
119
67
12
47
266
2
80
23
63
12
195
3
86
177
10
25
4
80
112
10
5
92
209
6
98
7
Вариант №8
Станция назначения
Станция отправления
1
2
3
4
5
6
7
1
106
98
52
12
45
250
2
73
24
55
8
319
3
93
229
13
21
4
78
119
10
5
120
234
6
103
7
Вариант №9
Станция назначения
Станция отправления
1
2
3
4
5
6
7
1
126
75
57
7
54
222
2
95
20
89
12
194
3
113
276
9
22
4
93
153
10
5
90
207
6
125
7
Вариант №10
Станция назначения
Станция отправления
1
2
3
4
5
6
7
1
115
85
75
12
63
360
2
91
24
86
13
318
3
103
180
11
19
4
74
135
10
5
83
259
6
121
7
7. РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ САМОСТОЯТЕЛЬНЫХ РАСЧЕ
­
ТОВ
Выполнение самостоятельных расчетов по нахождению оптимального
варианта плана формирования поездов способствует закреплению освоенно
­
го теоретического материала. Последовательность и результаты расчетов ре
­
комендуется оформлять отчетом, включающим следующие разделы:
1.
Краткие теоретические сведения
. Раскрываются основные понятия
теории рассматриваемой задачи, приводится общая последователь
­
ность вычислений.
2.
Исходные данные
. В данном разделе приводятся численные значения
исходных данных в соответствии с выбранным вариантом.
3.
Результаты промежуточных расчетов
каждого шага вычислений, вы
­
полненных в программе автоматизированного расчета.
4.
Графическое отображение оптимального варианта плана формирова
­
ния поездов
. Данный раздел позволяет наглядно отобразить эксплуата
­
ционную работу рассматриваемого транспортного полигона. Опти
­
мальный варианта плана формирования представляется в двух раз
­
резах: 1) включение исходных вагонопотоков в поезда оптимального
варианта плана формирования (пример на рисунке 10), 2) переработка
исходных вагонопотоков на станциях транспортного полигона (пример
на рисунке 11).
Рисунок 10
.
300
6
0
=
=
−
N
N
260
6
1
=
=
−
N
N
120
50
10
60
5
0
4
0
3
0
=
+
+
=
+
+
=
−
−
−
N
N
N
N
310
240
70
4
2
4
1
=
+
=
+
=
−
−
N
N
N
220
10
120
20
10
10
50
6
3
5
3
6
2
5
2
5
1
5
0
=
+
+
+
+
+
=
+
+
+
+
+
=
−
−
−
−
−
−
N
N
N
N
N
N
N
200
100
100
2
0
1
0
=
+
=
+
=
−
−
N
N
N
300
10
70
20
100
100
5
1
4
1
3
1
2
1
2
0
=
+
+
+
+
=
+
+
+
+
=
−
−
−
−
−
N
N
N
N
N
N
160
20
10
100
10
20
6
2
5
2
3
2
5
1
3
1
=
+
+
+
+
=
+
+
+
+
=
−
−
−
−
−
N
N
N
N
N
N
110
100
10
4
3
4
0
=
+
=
+
=
−
−
N
N
N
300
200
100
6
4
5
4
=
+
=
+
=
−
−
N
N
N
330
100
200
10
20
6
5
6
4
6
3
6
2
=
+
+
+
=
+
+
+
=
−
−
−
−
N
N
N
N
N
Номер станции
0
1
2
3
4
5
6
Суммарный
объем перера
­
ботки по стан
­
ции (ваг)
100
100
100
230
- станции переработки вагонопотока
Рисунок 11
СПИСОК ЛИТЕРАТУРЫ
1.
Инструктивные указания по организации вагонопотоков на железных
дорогах СССР. – М. : Транспорт, 1984.
2.
«Технология перевозок» интернет ресурс 3.
Покавкин, В.А. Расчет плана формирования одногруппных поездов мо
­
дифицированным методом последовательного приближения / В.А. По
­
кавкин // Тр. РИИЖТа. Вып. 98. 1973. – С. 4–36.
4.
Угрюмов, А.К. Составление плана формирования одногруппных техни
­
ческих маршрутов методом аналитических сопоставлений / А.К. Угрю
­
мов. – Л. : ЛИИЖТ. – 1953. – 35 с. 5.
Скляров, В.Н. Основы совершенствования системы организации ваго
­
нопотоков на железнодорожном транспорте. Ч. I
. Автоматизация про
­
цессов управления грузовыми перевозками / В.Н. Скляров. Рост. гос.
ун-т путей сообщения. – Ростов
н/Д, 2006. 100 с.
6.
Носов, В.А. Основы теории алгоритмов и анализа их сложности: Курс
лекций МГУ. – М., 2002. – Режим доступа к изд. : http://intsys.msu.ru
.
7.
Графы в программировании: обработка, визуализация и применение. –
СПб.: БХВ-Петербург, 2003. – 1104 с.
ПРИЛОЖЕНИЕ 1. КРАТКИЕ СВЕДЕНИЯ ИЗ ТЕОРИИ ГРАФОВ
Графом G
называется пара множеств G
=(
V
,
E
)
где V
– множество вер
­
шин графа, E
– множество ребер графа. Пример графического изображения
графа приведен на рисунке 1.1.
Рисунок 1.1
Две вершины графа соединенные ребром, называются смежными
(например, вершины 3
v
и 4
v
рисунка 1.1). Если переход между смежными
вершинами по соответствующему ребру возможен только в одном направле
­
нии (графически направление допустимого перехода обозначается стрелкой
как у ребра 5
e
на рисунке 1.1), то ребро называется дугой
. Граф, включающий
только дуги, называется ориентированным
. Соответственно, не содержащий
дуг – неориентированным
, а состоящий из комбинации ребер и дуг – сме
­
шанным.
Последовательность вершин k
i
i
v
v
v
v
,...
,
,...
1
1
+
в которой каждые две сосед
­
ние вершины 1
,
+
i
i
v
v
являются смежными в ориентированном графе называет
­
ся путем
(
цепью
в неориентированном) от вершины 1
v
к вершине k
v
. Длиной
пути
называется число всех дуг включенных в путь.
Путь называется простым
, если ни одна вершина не встречается в нем
дважды. Простой путь ненулевой длины, начало и конец которого совпадают
называется контуром
(
циклом
в неориентированном графе).
1
v
2
v
3
v
4
v
5
v
1
e
2
e
3
e
4
e
5
e
}
,
,
,
,
{
}
,
,
,
,
{
5
4
3
2
1
5
4
3
2
1
e
e
e
e
e
E
v
v
v
v
v
V
=
=
Приведенные определения являются базовыми для постановки и реше
­
ния широкого круга задач. Присваивая графам дополнительные свойства
формулируются различные виды задач. Рассмотрим одну из них - задачу о
кратчайших путях.
Дополнительное свойство графа
. Каждому ребру (дуге) или вершине
графа присваивается число, которое называется весом ребра, дуги. Такой
граф называется взвешенным
. Вес пути на графе определяется как сумма ве
­
сов дуг (вершин) его образующих.
Данное свойство позволяет сформулировать задачу о кратчайших пу
­
тях в следующей постановке. Пусть задан граф G
=(
V
,
E
,
W
)
(где W
– множе
­
ство весовых значений дуг (вершин) графа). При условии, что путь из верши
­
ны l
v
к вершине k
v
существует, необходимо найти самый короткий путь (и
его длину) из l
v
в k
v
. Задача считается хорошо определенной, если никакой путь из l
v
в k
v
не
содержит контур отрицательной длины. Различные модификации задач дан
­
ного типа формируются путем ввода дополнительных ограничений на коли
­
чество искомых путей, на длину и вес пути. В качестве примеров приведем
некоторые постановки задач данного типа:
- найти кратчайший путь от фиксированной вершины графа до всех
остальных вершин,
- найти кратчайшие пути для всех пар вершин графа,
- существует ли простой путь из l
v
в k
v
, имеющий вес не более C
и дли
­
ну не более K
,
- существует ли простой путь из l
v
в k
v
, длины не меньше K
.
Способы представления графа
Одним из способов представления графа является матрица смежно
­
сти
, определяемая, как матрица ]
[
ij
b
B
=
размера n
n
×
, где 1
=
ij
b
, если суще
­
ствует ребро, идущее из вершины i
v
в вершину j
v
, и 0
=
ij
b
в противном слу
­
чае. Матрица смежности неориентированного графа всегда является симмет
­
ричной. Основным преимуществом матрицы смежности является тот факт,
что за один шаг можно получить ответ на вопрос «существует ли ребро i
v
из
в j
v
». Другой способ представления графа – матрица инцидентности
. Если
)
,
(
j
i
v
v
e
=
- ребро графа G
, то говорят что ребро e
инцидентно вершине i
v
или вершине j
v
. Матрица инцидентности имеет размер m
n
×
(
n
- множество
вершин графа, m
- множество ребер). Элемент матрицы 1
=
ij
b
если вершина
i
v
инцидентна ребру j
e
и равен 0 в противном случае.
Автор
Z
Z3   документа Отправить письмо
Документ
Категория
Без категории
Просмотров
294
Размер файла
1 066 Кб
Теги
pfp
1/--страниц
Пожаловаться на содержимое документа