Содержание к диссертации
Введение
Глава 1. Постановка задачи исследования по выбору рациональной структуры флота для доставки грузов в пункты с необорудованным берегом 7
1.1. Тенденции транспортного освоения зарубежной Арктики 7
1.2. Арктические транспортные системы России 8
1.2.1. Основные порты и пункты арктических районов 8
1.2.2. Природно-климатические условия Арктики 8
1.2.2.1. Ледовые и гидрометеорологические условия арктического бассейна 8
1.2.2.2. Географические и природно-климатические условия арктических пунктов 9
1.2.3. Грузопотоки 10
1.2.3.1. Классификация 10
1.2.3.2. Вывоз грузов 10
1.2.3.3. Арктическое транзитное сообщение 10
1.2.3.4. Ввоз снабженческих грузов в арктические районы 10
1.2.4. Арктические транспортные системы 12
1.3. Структура флота снабжения арктических пунктов с необорудованным берегом .- 14
1.3.1. Место флота снабжения в системе арктического флота и его структура 14
1.3.2. Линейные суда-снабженцы 15
1.3.3. Средства рейдовой разгрузки судов на необорудованный берег 17
1.3.4. Лихтеровозы 19
1.3.5. Фидерные снабженцы 20
1.4. Магистрально-фидерная транспортно-технологическая система доставки грузов в арктические пункты с необорудованным берегом 22
1.4.1. Общая характеристика магистрально-фидерной технологии организации перевозок 22
1.4.2. Влияние гидрометеофакторов на маршруты судов и производство работ при магистрально-фидерной и линейной схемах доставки грузов (сравнительный анализ) 23
1.5. Постановка задачи исследования 27
1.5.1. Постановка задачи оптимизации состава комплекса транспортных средств для доставки грузов в пункты с необорудованным берегом (Вербальное описание) 27
1.5.2. Критерий эффективности 29
1.5.2.1. Выбор критерия эффективности 29
1.5.2.2. Выбор расчетного размера ренты 31
1.6. Обзор (анализ) выполненных исследований по теме диссертационной работы 33
1.6.1. Обзор работ по обоснованию технических средств транспортной системы доставки грузов на необорудованный берег 33
1.6.2. Анализ работ по оптимизации структуры флота 34
1.6.2.1. Обзор работ по оптимизации состава флота 34
1.6.2.2. Анализ методов оптимизации в задачах оптимизации состава флота 35
1.6.2.3. Анализ математических моделей функционирования системы в задачах оптимизации состава флота 53
Глава 2. Разработка модели функционирования транспортной системы 57
2.1. Предварительный отбор транспортных средств 57
2.2. Выбор качественного состава комплекса береговых сооружений для обеспечения функционирования транспортной системы 64
2.3. Влияние гидрометеофакторов на функционирование транспортных средств системы 65
2.4. Вербальное описание процесса функционирования 67
2.5. Разработка математической модели функционирования флота 68
2.5.1. Формальное описание элементов системы 68
2.5.2. Алгоритмическое формирование модели функционирования флота 71
2.5.2.1. Понятие системы допустимых маршрутов и формирование схемы функционирования 71
2.5.2.2. Алгоритмы построения маршрутов судов 73
2.5.2.3. Алгоритмическое формирование схемы функционирования комплекса 80
2.5.3. Алгоритмы выбора береговых сооружений 81
Глава 3. Разработка методики оптимизации транспортной системы доставки грузов в пункты с необорудованным берегом 85
3.1. Постановка задачи оптимизации структуры транспортной системы (формальное описание) 85
3.2. Метод решения задачи оптимизации 89
3.3. Первый Этап решения задачи (Маятниковые маршруты судов) 92
3.3.1. Общая характеристика метода 92
3.3.2. Описание формального аппарата метода 96
3.4. Второй Этап решения задачи (Маршруты - совокупности линий) 102
3.4.1. Общая характеристика метода 102
3.4.2. Описание формального аппарата метода 103
3.4.2.1. Оценки маршрутов 103
3.4.2.2. Проверка оптимальности решения и выбор маршрута с наивысшей оценкой для включения в базис 105
3.4.2.3. Описание модифицированного симплекс- метода с алгоритмическим формированием маршрута 107
3.5. Третий Этап решения задачи (Маршруты последовательности пунктов ) 113
3.5.1. Общая характеристика метода 113
3.5.2. Описание формального аппарата метода 114
Глава 4. Практическая реализация разработанной методики оптимизации транспортной системы 116
4.1. Алгоритм задачи оптимизации первого этапа 116
4.2. Алгоритм задачи оптимизации второго этапа 117
4.3. Алгоритм задачи оптимизации третьего этапа 120
4.4. Реализация разработанной методики в программе 122
4.4.1. Требования к системе 123
4.4.2. Ключевые абстракции и механизмы 125
4.4.3. Архитектура системы 127
4.4.4. Особенности программы 136
4.5. Расчетный пример. Сравнение морских транспортно- технологических схем снабжения пунктов с необорудованным берегом Чукотки 136
Заключение 141
Список литературы 143
- Арктические транспортные системы России
- Выбор качественного состава комплекса береговых сооружений для обеспечения функционирования транспортной системы
- Метод решения задачи оптимизации
- Алгоритм задачи оптимизации второго этапа
Введение к работе
Первые работы в области оптимизации структуры флота, в которых комплекс транспортных средств рассматривался как сложная система, состоящая из взаимосвязанных и взаимовлияющих друг на друга и на качество функционирования системы в целом элементов, могут быть отнесены к середине 60-х годов. В эти годы впервые появляются работы, в которых потребность в судах определяется на основе совместного рассмотрения всех направлений перевозок, выполняемых флотом. Уже в первых работах были учтены практически все основные обстоятельства, которые сопутствуют решению подобных задач и в настоящее время, включая серийность постройки судов и существующий флот.
В семидесятые годы происходит бурный рост количества работ по оптимизации флота. Согласно складывающейся в судостроении терминологии эти задачи получили название задач внешнего проектирования. Наряду с рассмотрением транспортного флота как объекта оптимизации, появились работы, посвященные рыбопромысловому флоту.
В последние два десятилетия работы по оптимизации флота получили свое дальнейшее развитие. Выполнены работы по оптимизации комплексов средств освоения Мирового океана, включая фундаментальные исследования по разработке методологии оптимизации состава флота для обслуживания нефтегазовых месторождений и по автоматизированному проектированию и планированию структуры нефтепромыслового флота. Исследовались возможности использования экспертных систем для планирования транспортно-технологических схем. Разрабатывались автоматизированные системы для обоснования развития транспортного флота. Рассматривались суда внутреннего и смешанного плавания, в том числе в условия продленной навигации.
Выполнены работы по оптимизации и моделированию деятельности флота на Северном морском пути; разработаны методики оптимизации ледокольно-транспортных комплексов; исследовалась методика оптимизации сухогрузного флота Дальневосточного бассейна, включающая задачу обоснования флота арктической навигации (судов и ледоколов) и имитационную модель деятельности флота в Арктике. Характерным для работ арктической тематики является рассмотрение в качестве основной -проблемы доставки грузов в крупные арктические порты и портопункты с большим грузопотоком.
Одной из задач которая может быть рассмотрена в рамках оптимизации состава флота является задача выбора оптимальной структуры флота снабжения арктических пунктов с необорудованным берегом, которой посвящено данное диссертационное исследование.
Арктика является предметом исследований на протяжении столетий, и интерес к ней не ослабевает в последние десятилетия. Это подтверждается объемом публикаций, существованием и открытием новых государственных, общественных, коммерческих организаций, программ, рабочих групп и институтов, которые занимаются проблемами Арктики. В область их интересов входят: разведка, разработка и транспортировка природных ресурсов, наука, охрана окружающей среды, образование, пассажирские перевозки и туризм. В 1996 году был открыт международный межправительственный координационный форум - Совет по Арктике (Arctic Council), в который вошли Дания, Канада, Исландия, Норвегия, Россия, США, Швеция, Финляндия. Проблемами Арктики занимается ООН (UNECE, UNEP).
В качестве примера динамичных преобразований в Арктических районах России можно привести Чукотку, где заметны изменения в социальной сфере, энергоснабжении, связи и транспорте. Грузооборот морских портов Чукотки за 2001 г. удвоился, а объем авиаперевозок вырос на 50%. Характерная особенность транспортного комплекса Чукотки — полное отсутствие железных дорог и трубопроводов. Суммарная протяженность автомобильных дорог общего пользования составляет более 5000 км, причем почти половина из них построена за последнее десятилетие. Утверждена программа строительства дорог «Золотого арктического кольца» — круглогодично действующей трассы от берегов Ледовитого и Тихого океанов до золотодобывающих предприятий.
Морская транспортная схема Чукотки включает 5 морских портов: Певек, Провидения, Эгвекинот, Анадырь и Беринговский. Порты Чукотки не имеют собственного средне- и крупнотоннажного флота. Кроме портов, имеются пункты с необорудованным берегом, в которые грузы снабжения доставляются в летний период судами-снабженцами, и круглогодично — воздушным флотом, небольшими партиями.
Единственным видом круглогодичного транспорта является воздушный флот.
В данной диссертационной работе предлагается в качестве объекта исследования рассмотреть альтернативную фидерную морскую транспортную систему снабжения пунктов с необорудованным берегом, обеспечивающую круглогодичное сообщение между портами и прибрежными пунктами Восточной Чукотки, включая зиму - в погодные окна, наряду с воздушным флотом. Предполагается, что грузы завозятся в морские порты Чукотки в летний период линейным флотом снабжения из Владивостока и других портов, и далее развозятся местным фидерным флотом по пунктам. В качестве основных транспортных средств-претендентов на включение в систему фидерного флота предлагается рассмотреть амфибийные суда на воздушной подушке (СВП), для обеспечения круглогодичного сообщения в пределах Чукотки, а также суда снабженцы с аппарелью для летного сообщения.
Задача может не ограничиваться рамками Восточной Чукотки; общее количество пунктов с необорудованным берегом, с устойчивым грузопотоком, в России - порядка 100.
В предлагаемом исследовании разработана методика оптимизации арктического флота снабжения пунктов с необорудованным берегом. Первая глава посвящена постановке задачи исследования. Рассматриваются тенденции транспортного освоения зарубежной Арктики и Арктические транспортные системы России, структура флота снабжения Арктических пунктов с необорудованным берегом и пути ее совершенствования. Анализируются работы, выполненные по исследуемой тематике; классифицируются математические методы оптимизации и модели. Во второй главе приводится разработка модели функционирования флота. Особенностью модели является динамическое формирование системы оптимальных маршрутов судов, составляющих транспортную схему функционирования флота. Система оптимальных маршрутов формируется в процессе решения задачи оптимизации, с учетом рациональных соображений и требований, аналогичных тем, которые в действительности влияют на назначение маршрута судна. Обоснование выбора типов судов-претендентов выполнено на основе проведенного экспертного опроса. Третья глава посвящена разработке методики оптимизации. Приводится формальная постановка задачи исследования. Обосновываются методы и подход к решению задачи. Метод решения задачи предлагается строить на комбинации методов теории математического программирования, доработанных с учетом специфики задачи. Решение ищется в целочисленной постановке. Четвертая глава содержит описание практической реализации разработанной методики. Приводятся алгоритмы оптимизации, основанные на предложенной модели функционирования флота и разработанных методах оптимизации. Описывается программа для персонального компьютера, реализованная на базе выполненных исследований; представлены основные требования, ключевые абстракции и архитектура системы. Программа, позволяет решать элементы задач пополнения флота и проектирования оптимальной структуры флота: . Принятие решения по замене судов подлежащих списанию. . Проверка рациональности использования отдельных судов флота и целесообразности их замены. . Планирование транспортной инфраструктуры для новых районов и поиск наиболее эффективных решений по выбору транспортных средств. . Перспективное планирование развития флота. . Проверка эффективности существующего флота.
Арктические транспортные системы России
В диссертационной работе рассматривается комплекс технических средств, выполняющий задачу доставки грузов в пункты с необорудованным берегом Арктики. В данном разделе схематично рассматриваются все виды арктических перевозок, и отмечается место флота снабжения в арктической транспортной системе. Крупнейшими терминальными портами Западного района Арктики являются Мурманск и Архангельск, Восточного района — Владивосток, Находка, порт Восточный. Помимо терминальных важнейшими портами являются Дудинка, Игарка, Тикси, Певек, а для района Восточной Чукотки -Проведения, Эгвекинот, Беринговский (см. [ш1]). Кроме портов в районах Арктики имеется значительное количество пунктов, где погрузочно-разгрузочные операции производятся у необорудованного берега. Согласно [а2], суда министерства морского флота обслуживали около 80 арктических рейдовых портопунктов, расположенных между 68 и 82 с.ш. и простирающихся от 36 в.д. до 169 з.д. . Средняя продолжительность летней навигации для участков арктического бассейна составляет: Баренцево море — о. Диксон 95... 110 суток; Диксон - море Лаптевых 90 суток; Чукотское и Восточносибирское море 90 суток. ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ ГЛАВА 1 Арктические транспортные системы России Средняя скорость ветра в течение навигации — 6 м/с с повторяемостью 65 %. Наибольшее число дней с туманом приходится на навигационный период. В июле - августе повторяемость туманов 30...40 %, в сентябре — 20.. .30 %, в октябре -5...10%. Метели в навигационный период редки -5...10% дней. Ледовые условия различаются по районам арктического бассейна. В работе [р2] приведены обобщенные данные о ледовой обстановке для летне-осеннего периода. Для районов арктической акватории восточнее 100-го меридиана характерна сильная торосистость льда. Арктические пункты расположены на островах и на побережье материка. Описание некоторых пунктов, их географических, топографических и гидрологических особенностей можно найти в работах [рі], [р2], [ті], [cl], [ol]. Пункты можно классифицировать по следующим признакам: 1) гидрографическим: глубина при подходе к пункту, удаленность якорной стоянки и места складирования от берега, волнение в месте выгрузки; 2) метеорологическим: ветровой и температурный режимы, повторяемость туманов; 3) ледовым: сроки начала ледообразования и разрушения ледового покрова; 4) характеру места выгрузки: условия выгрузки, длительность светлого времени суток; 5) волнению: высота волн трех процентной обеспеченности; 6) расстоянию от якорной стоянки: расстоянию от якорной стоянки до берега и от берега до склада; 7) уклону берега. Пример классификации арктических пунктов приведен в работе [cl], где пункты восточного сектора Арктики и Дальнего Востока, обслуживаемые судами ДВМП, распределяются на четыре группы: 1) с достаточными глубинами (54 %); 2) с мелководными берегами и подходами (14 %); 3) с каменистыми берегами и сложными подходами (12 %); 4) с мелководьем и подводными камнями (20 %). Перевозки грузов в арктических районах России можно разделить на три вида: 1) вывоз сырья, главным образом руды и лесоматериалов; 2) транзитные перевозки по северному морскому пути между портами Европы и Дальнего Востока; 3) ввоз снабженческих грузов в арктические порты и пункты. Перевозки западного сектора Арктики. Наибольшими по объему являются перевозки района реки Енисей. Через Дудинку осуществляется вывоз медно-никелевой руды и металла Норильского комбината в Мурманск и Кандалакшу для частичной переработки в Мончегорске. Круглогодичное сообщение с Дудинкой по Северному морскому пути стало возможным благодаря пополнению флота атомными ледоколами типа "Арктика" (1975г.), мелкосидящими ледоколами типа "Капитан Сорокин" (1977-1978гг.), контейнерно-навалочным судами класса УЛ (1977г.), многоцелевыми судами типа СА-15 (1983 г.). С лесокомбината Игарки вывозятся лесоматериалы примерно в 20 стран мира. Выраженный в тоннах, вывоз лесоматериалов значительно меньше, чем вывоз руды, но он ориентирован в значительной степени на экспорт. Перевозки восточного сектора Арктики. Вывоз грузов из восточного сектора Арктики меньше, чем из западного. Отсюда вывозятся золото, олово и алмазы, а также лесоматериалы. Транзитное сообщение по Северному морскому пути стало международным в 1984 году. Суда типа СА-15 доставили трубы из Японии на реку Обь, а также зерно из Ванкувера в Мурманск и Архангельск, сэкономив за 6 рейсов 65 суток времени, что соответствует более, чем 3000 тонн топлива, не говоря о других издержках. Таким образом удалось доказать, что при использовании соответствующих судов возможно экономично осуществлять трансарктические перевозки (см. [ш1]). Грузопотоки снабженческих грузов рассматриваются в работах [р2], [ті], [ol], [к1], [к2], [ш1], [кЗ], [т2] и др. ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ ГЛАВА I Арктические транспортные системы России Доставка снабженческих грузов осуществляется в пункты Арктики и Чукотки, общее количество которых из года в год остается почти постоянным (см.[2]). Потоки грузов можно условно разделить на две группы: 1) мелкопартионные перевозки, величина которых остается стабильной в течении многих лет (перевозки в большинство арктических пунктов); 2) перевозки, связанные с геологоразведочными работами и освоением месторождений полезных ископаемых, и отличающиеся устойчивым ростом грузопотоков, достигающих сотен тысяч тонн (перевозки на п-ов Ямал, Обскую губу, Хатангу). На рис. 1.1 приведен график тенденции развития арктических перевозок, на основании данных Союзморниипроекта [к2] по анализу развития грузопотоков в Арктике с учетом перспективы; за базу взят 1985г. Доли составляющих грузопотока в % приведены в таблице 1.1.
Выбор качественного состава комплекса береговых сооружений для обеспечения функционирования транспортной системы
Береговые сооружения являются составляющей комплекса транспортного обслуживания и предназначены для обеспечения функционирования транспортных средств комплекса. Качественный состав береговых сооружений в пунктах зависит от ряда факторов: - типов судов, обслуживающих пункты; - географических характеристик пунктов; - видов грузов. В то же время, при выборе оптимального состава флота в рамках какой-либо одной, исследуемой, системы организации перевозок, могут не приниматься во внимание береговые сооружения, номенклатура которых не зависит от транспортной составляющей комплекса, а является функцией только видов грузов (например хранилища грузов). При сравнении же различных систем (линейная и магистрально-фидерная) эти сооружения должны быть рассмотрены, поскольку лишь магистрально-фидерная схема требует их дополнительного сооружения. Следует также отметить, что географические характеристики пунктов оказывают влияние на выбор типа берегового сооружения не непосредственно, а через назначение приемлемого типа транспортного средства. Учитывая сказанное, в рассматриваемой задаче можно предположить, что состав комплекса транспортных средств определяет необходимые береговые сооружения в пунктах. Таким образом, в задаче оптимизации состава комплекса обслуживания пунктов с необорудованным берегом предполагается рассматривать следующие береговые сооружения. Базовые пункты: -причалы для водоизмещающих судов; - береговые площадки для судов на воздушной подушке; - площадки и ангары для вертолетов; - ремонтные базы. Пункты с необорудованным берегом: - причалы; - береговые площадки для водоизмещающих судов, оборудованных носовой аппарелью и приспособленных к беспричальной обработке; - площадки для СВП; - площадки для вертолетов. Влияние гидрометеофакторов на функционирование транспортных средств. На функционирование системы транспортного обслуживания арктических пунктов с необорудованным берегом наиболее существенное влияние оказывают следующие гидрометеорологические факторы: - ветер; - волнение; - туман; - облачность; - метели; - ледовый покров; - температура воздуха. Природные факторы оказывают влияние на следующие параметры функционирования транспортных средств и системы в целом (что учтено, в основном, в модели): - скорость хода судна; - время ожидания по метеоусловиям; - выбор курса судна при движении к заданному пункту (не учитывается в модели); - время под грузовыми операциями; - выбор маршрута при обслуживании в одном рейсе нескольких пунктов; - порядок обслуживания пунктов в течение навигационного периода; - продолжительность навигационного периода. Степень влияния гидрометеофакторов на различные характеристики работы одного и того же транспортного средства неодинакова. Отличается также влияние природных факторов и на разные типы транспортных средств. В таблице 2.1 приведена матрица соответствий, отображающая зависимость скорости хода различных транспортных средств от ряда факторов (1 - зависит; 0 - не зависит). Аналогично составлена таблица 2.2 для времени грузообработки судов в пунктах с необорудованным берегом. Подобным образом могут быть построены и другие матрицы соответствий параметров работы судов и гидрометеофакторов. При этом, однако, следует принять во внимание, что подобный подход весьма упрощен и условен. Влияние гидрометеофакторов на функционирование транспортных средств. Способы учета влияния гидрометеофакторов в задачах оптимизации. При решении оптимизационной задачи выбора рациональной структуры флота гидрометеорологические условия, в районах функционирования транспортных средств, представляют собой внешние параметры по отношению к рассматриваемой системе. Можно выделить следующие три основных уровня неопределенности в знании указанных параметров: - параметры детерминированы и их значения заданы; - параметры недетерминированы (случайны), но их вероятностные характеристики полностью известны; - параметры недетерминированы и их вероятностные характеристики неизвестны (см. [хЗ]). Задачи первого типа - детерминированы. Задачи с неопределенностью второго уровня могут ставиться как задачи стохастического программирования, сводиться к детерминированным аналогам и решаться методами нелинейного программирования (см. раздел 1.6.2. данной работы, [п2]) . Знание законов распределения случайных параметров позволяет имитировать реальные транспортные процессы на ЭВМ [63]. Задачи с неопределенностью третьего уровня решаются методами теории игр. Суть данного подхода состоит в многократном использовании детерминированных моделей - отбор конечного числа "состояний природы", решение для каждого состояния детерминированной задачи, обработка результатов и выявление рациональных вариантов структуры системы (см. раздел 1.6.2. данной работы, [хЗ], [п2]) . В ходе исследования анализировались все три подхода к учету влияния гидрометеофакторов. Однако, учитывая сложность принятой целочисленной постановки задачи, а также реализацию механизма алгоритмического построения маршрутов судов в процессе решения задачи оптимизации, было принято решение учитывать влияние гидрометеофакторов в модели -детерминировано. В то же время, если данная задача получит развитие, представляется возможным ввести стохастическое представление гидрометеоинформации.
Метод решения задачи оптимизации
В результате формализации модели получена задача целочисленного программирования с разрывной функцией критерия, содержащей линейные и нелинейные члены и с ограничениями, одно из которых не линейно, а остальные линейны. Нелинейные составляющие в целевой функции и ограничении капиталовложений относятся к затратам на строительство судов и объясняются зависимостью стоимости судна от порядкового номера судна в серии. Первый этап решения задачи. Маятниковые маршруты судов. Нелинейная функция может быть аппроксимирована кусочно-линейной. При этом задача сводится к целочисленной задаче линейного программирования с кусочно-линейной целевой функцией. Стоимость всех судов серии может быть принята одинаковой, а затраты на подготовку производства и освоение серийной продукции могут учитываться фиксированной величиной. В этом случае будет получена так называемая задача с фиксированными доплатами, на переменные которой наложено требование целочисленности. Целевая функция задачи в обоих случаях является выпуклой, что следует из ее экономического содержания: где D (доход) - выпуклая функция (линейная); R (расходы) - вогнутая функция (в первом случае), или выпуклая (линейная, в задаче с фиксированными доплатами). Область допустимых решений в первом случае невыпукла, во втором -выпукла. Оба типа представления задачи относятся к классу нерегулярных задач математического программирования. В ходе исследования, проведенного в настоящей работе, при анализе методов решения задач оптимизации, включая сходные по содержанию задачи транспортного типа, а также в результате теоретического анализа методов математического программирования (см. глава 1, раздел 1.6.2.2.), было выявлено следующее: - эффективных в вычислительном плане алгоритмов, приводящих к точному решению рассматриваемой задачи, не существует; - для решения задачи могут быть использованы эвристические методы; - методы решения задачи должны опираться на ее специфику; - учитывая большую размерность задачи, целесообразно использовать линейную аппроксимацию нелинейной функции и применять элементы теории линейного программирования; - план перевозок заданного объема грузов (система маршрутов судов) может быть построен в процессе решения оптимизационной задачи; для построения системы маршрутов судов может быть использована процедура динамического программирования; - метод решения практической задачи целесообразно строить не на одном каком либо методе теории математического программирования, а использовать разбиение задачи на подзадачи искать для каждой из них наиболее подходящий метод из существующих, либо разрабатывать оригинальный на основе математической теории; - поиск целочисленного решения задачи может быть осуществлен поэтапно, параллельно построению системы допустимых маршрутов, при этом решения на более поздних этапах должны детализировать и дополнять уже имеющееся частичное решение; - для оценки созданного метода, полученное с его помощью решение можно сравнить с решением той же задачи, поставленной в упрощенном виде, как нецелочисленная, гладкая и линейная, полученным одним из методов линейного программирования; - качество метода должно быть подтверждено экспериментально. Ниже рассматривается разработанный в ходе настоящего исследования подход к решению поставленной задачи. Задачу предлагается решать в три этапа. На первом этапе решения задачи маршруты судов предполагаются маятниковыми, что соответствует работе судна в течение эксплуатационного периода на одной линии. Решается задача нецелочисленного линейного программирования, на каждом шаге которой, для учета влияния количества судов в серии на строительную стоимость судна, производится пересчет значений стоимостных коэффициентов. В результате решения задачи первого этапа получается система оптимальных маршрутов. Система маршрутов фиксируется; маршрутам приписываются только целые количества судов, а также объемы перевозок выполненные этими судами. Если хотя бы одному маршруту соответствует нецелое количество транспортных средств, то в результате решения задачи данного этапа остаются невыполненные перевозки. С этим объемом перевозок должна решаться задача второго этапа. Значение целевой функции для оптимального плана нецелочисленной задачи первого этапа может быть использовано для сравнительного анализа решения поставленной в исследовании целочисленной задачи. На втором этапе решения задачи маршруты судов представляются как наборы линий; при этом предполагается, что судно в процессе эксплуатационного периода последовательно обслуживает несколько линий, а линии объединяются в маршруты наиболее целесообразным способом. Решается нецелочисленная задача линейного программирования с пересчетом стоимостных коэффициентов целевой функции и алгоритмическим формированием маршрутов для ввода в базис. Маршруты для включения в базис строятся с помощью процедуры динамического программирования. В результате решения задачи второго этапа строится система оптимальных маршрутов. Система маршрутов фиксируется; маршрутам приписываются только целые количества судов, а также объемы перевозок, выполненные этими судами. Данная система, с целым количеством транспортных средств, включается в оптимальный план целочисленной задачи, путем добавления к системе маршрутов, с целым количеством судов, первого этапа. Если хотя бы на одном маршруте количество судов нецелое, то после второго этапа остаются невыполненные перевозки. С этими объемами перевозок должна решаться задача третьего этапа. На третьем этапе маршрут судна представляется как набор пунктов, которые судно обходит в течение эксплуатационного периода наиболее целесообразным образом. Решается целочисленная задача с оставшимися от первых двух этапов объемами перевозок. Вычисления производятся следующим образом. По процедуре динамического программирования находится маршрут с наивысшей оценкой (значением функции критерия) для одного транспортного средства из множества судов-претендентов. Затем выполненные на маршруте перевозки исключаются из дальнейшего рассмотрения, и строится следующий маршрут. Процесс продолжается до тех пор, пока все заданные объемы перевозок не будут выполнены. В результате решения задачи третьего этапа получается система оптимальных маршрутов с целым количеством судов на них, которая включается в решение поставленной целочисленной задачи.
Алгоритм задачи оптимизации второго этапа
Алгоритм разработан на основе результатов, полученных в разделах 2.1.,...,2.5., 3.1., 3.2., 3.4. и позволяет: - получить оптимальное нецелочисленное решение задачи оптимизации флота и частичное решение целочисленной задачи; алгоритм принципиально независим от задач первого и третьего этапов (см. 4.1, 4.3), и может использоваться самостоятельно; - построить схему функционирования комплекса судов - систему маршрутов, которая с целым количеством судов войдет в оптимальное решение поставленной целочисленной задачи оптимизации флота; маршруты судов представляют собой упорядоченный набор линий работы судна в течение эксплуатационного периода. Блок-схема алгоритма приведена на рисунке 4.2. Ниже приводится описание алгоритма, включая особенности реализации. Схема алгоритма задачи второго этапа подобна рассмотренному выше алгоритму первого этапа оптимизации (см. раздел 4.1). Принципиальное различие заключается в форме представления маршрута, и, в связи с этим, - в реализации алгоритма построения маршрутов судов. На втором этапе оптимизации маршруты судов представляют собой наборы линий функционирования судов, и для построения маршрутов используется процедура динамического программирования. Маршруты строятся по критерию минимума протяженности перехода судов с линии на линию. Алгоритм разработан на основе результатов, полученных в разделах 2.1,...,2.5, 3.1, 3.2,3.5 и позволяет: - получить целочисленное решение задачи оптимизации состава флота; - построить систему маршрутов судов; при этом маршрут представляется как набор пунктов перевозок в порядке обхода их судном в течение эксплуатационного периода. Таким образом, алгоритм позволяет завершить процесс построения оптимального решения поставленной целочисленной задачи оптимизации состава флота, а также позволяет алгоритмически формировать схему функционирования флота как набора маршрутов судов, при обходе пунктов в течении эксплуатационного периода. Алгоритм принципиально независим от задач первого и второго этапов (см. 4.1, 4.2), и может использоваться самостоятельно для решения задач выбора структуры флота. Блок-схема алгоритма приведена на рисунке 4.3. Алгоритм начинается с подготовки информации, полученной на первом и втором этапах решения задачи. Выясняются невыполненные объемы перевозок. Строится начальный базисный план. Далее организуется перебор районов перевозок (базовых пунктов) и судов-претендентов. Для каждого судна из списка судов претендентов строится кратчайший маршрут обхода пунктов судном в течение эксплуатационного периода. Для построения маршрута используется процедура динамического программирования (см. раздел 2.5.2.2.). Маршруты проверяются на существование (аналогично алгоритму первого этапа; см. раздел 4.1). ПРАКТИЧЕСКАЯ Алгоритмы задачи оптимизации транспортной системы Для построенного кратчайшего маршрута судна вычисляется оценка, включая: - годовой доход от работы судна на маршруте; - годовой платеж в счет погашения затрат на строительство судна; - годовой платеж в счет погашения затрат на строительство береговых сооружений флота (в случае если выбрана опция учитывать береговые сооружения); при этом выясняется необходимость в достройке береговых сооружений маршрута, обеспечивающих работу нового судна; выясняется строительная стоимость; Оценка маршрута сравнивается с оценкой маршрута предыдущего судна-претендента, и выбирается лучшая. В результате перебора всех судов (и исключения недопустимых маршрутов), выбирается маршрут с лучшей оценкой. Этот маршрут включается в базисный план задачи. Выполненные судном перевозки на маршруте исключаются из дальнейшего рассмотрения. Процесс продолжается до тех пор, пока не будут выполнены все заданные перевозки. На основании анализа системы, проведенного в предыдущих разделах диссертации, и разработанных алгоритмов оптимизации, реализована программа оптимизации состава флота. При разработке программы использовался объектный подход, получивший широкое развитие в программировании в последнее десятилетие, и принятый, как наиболее рациональный для программирования сложных систем. Основные принципы объектного подхода, используемые в программе, и архитектура программы описаны в данном разделе. Описание программы и рекомендации по практическому применению, приводятся в приложении П6. В ходе работы были использованы следующие методологии, составляющие объектного подхода в программировании (см. [615]),: - объектно-ориентированный анализ: метод анализа, согласно которому требования рассматриваются с точки зрения классов и объектов, составляющих словарь предметной области; - объектно-ориентированное проектирование: методология проектирования, соединяющая в себе процесс объектной декомпозиции и приемы представления логической и физической, а также статической и динамической моделей проектируемой системы; - объектно-ориентированное программирование: методология программирования, основанная на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определенного класса, а классы образуют иерархию наследования. Назначение программы: решение задач пополнения флота и проектирования оптимальной структуры флота. Задача пополнения флота заключается в нахождении судов пополнения с оптимальными характеристиками, при этом предполагается, что определенная часть флота остается без изменения. Возможное практическое применение: - принятие решения по замене существующих судов, подлежащих списанию; - проверка рациональности использования определенных судов флота и целесообразности их замены. Задача проектирования оптимальной структуры флота заключается в нахождении (проектировании) максимально эффективного комплекса транспортных средств, предназначенного для выполнения заданного перспективного плана доставки грузов. Требование к неизменности имеющейся части флота может не выдвигаться. Возможное практическое применение: - планирование транспортной инфраструктуры для новых районов и поиск эффективных решений по выбору транспортных средств; - перспективное планирование развития флотов; - проверка эффективности существующего флота, выполняющего определенную задачу. Вероятные пользователи программы: - инженерные и экономические службы пароходств, предприятий судовладельцев; - проектные и исследовательские бюро и институты, выполняющие проекты технико-экономического обоснования и проектирования новых судов. Требования к программе: 1. Система должна обеспечивать решение задач, согласно сформулированному назначению, и быть ориентирована на указанную категорию пользователей.
