|
От редактора перевода
|
9
|
|
Предисловие
|
13
|
|
Часть 1. Теоретические аспекты оптимизации транспортных сетей
|
|
|
1. Некоторые математические понятия и обозначения, используемые в этой книге
|
16
|
|
1.1. Оптимизация
|
16
|
|
1.1.1. Определение задачи оптимизации
|
16
|
|
1.1.2. Методы оптимизации
|
18
|
|
1.2. Потоки в сетях
|
24
|
|
1.2.1. Графы и сети
|
24
|
|
1.2.2. Потоки в сетях
|
27
|
|
1.2.3. Многопродуктовые потоки
|
28
|
|
2. Перевозки
|
34
|
|
2.1. Перевозки — описание системы
|
34
|
|
2.1.1. Транспортная сеть
|
34
|
|
2.1.2. Потребность в перевозках
|
35
|
|
2.1.3. Равновесие в транспортной сети
|
37
|
|
2.1.4. Распределение перевозок
|
41
|
|
2.1.4.1. Задача распределения перевозок
|
41
|
|
2.1.4.2. Методы решения задачи распределения перевозок
|
42
|
|
2.1.4.3. Другие аспекты распределения
|
43
|
|
2.2. Дескриптивные и нормативные системы
|
43
|
|
2.2.1. Дескриптивные и нормативные системы
|
43
|
|
2.2.2. Дескриптивное и нормативное распределение
|
44
|
|
2.2.2.1. Различие между дескриптивным и нормативным распределением
|
44
|
|
2.2.2.2. Парадокс Брайеса
|
46
|
|
2.2.2.3. Уменьшение различия между дескриптивным и нормативным распределением
|
48
|
|
3. Задача оптимизации транспортной сети
|
50
|
|
3.1. Оптимальное физическое планирование
|
50
|
|
3.2. Оптимальная транспортная инфраструктура для заданного землепользования
|
52
|
|
3.2.1. Искомые переменные
|
52
|
|
3.2.2. Целевая функция
|
53
|
|
3.2.2.1. Общие замечания
|
53
|
|
3.2.2.2. Прибыль потребителей при планировании перевозок
|
55
|
|
3.2.3. Ограничения
|
60
|
|
4. Известные методы решений задачи оптимизации транспортных сетей
|
64
|
|
4.1. Краткая постановка задачи
|
64
|
|
4.2. Математическое программирование
|
66
|
|
4.3. Ветви и границы
|
69
|
|
4.3.1. Метод ветвей и границ
|
69
|
|
4.3.2. Метод ограниченных подмножеств Ридли
|
71
|
|
4.3.3. Алгоритм ветвей и границ Очоа-Россо и Сильвы
|
73
|
|
4.3.4. Алгоритм ветвей и границ Чана
|
76
|
|
4.3.5. Алгоритм ветвления с возвратом Очоа-Россо и Сильвы
|
78
|
|
4.3.6. Алгоритм ветвей и границ для общей задачи
|
80
|
|
4.3.7. Обсуждение методов ветвей и границ
|
83
|
|
4.4. Эвристические методы
|
84
|
|
4.4.1. Сущность эвристических методов
|
84
|
|
4.4.2. Игнорирование взаимозависимости подзадач
|
85
|
|
4.4.2.1. Непрерывная оптимальная корректировка
|
85
|
|
4.4.2.2. Отбор наиболее перспективных проектов
|
88
|
|
4.4.3. Метод Барбье
|
91
|
|
4.4.3.1. Первоначальный вариант метода Барбье
|
91
|
|
4.4.3.2. Хаубричевские расширения метода Барбье
|
94
|
|
4.4.4. Интерактивное программирование
|
96
|
|
4.5. Иерархическая структура, агрегирование и декомпозиция
|
97
|
|
4.5.1. Иерархическая структура
|
97
|
|
4.5.2. Агрегирование
|
98
|
|
4.5.3. Декомпозиция, или разбиение
|
99
|
|
5. Пошаговое распределение по минимуму суммарной дифференциальной стоимости перевозок: новый метод
|
103
|
|
5.1. Введение
|
103
|
|
5.2. Декомпозиция задачи
|
104
|
|
5.3. Условия оптимальности решения основной задачи
|
105
|
|
5.4.. Методы решения основной задачи
|
108
|
|
5.4.1. Пошаговое распределение
|
108
|
|
5.4.2. Правильность получаемых решений
|
109
|
|
5.4.3. Параметры метода
|
114
|
|
5.5. Использование нормативного распределения вместо дескриптивного и механизм цен
|
116
|
|
5.6. Применение метода для максимизации прибыли
|
117
|
|
5.7. Некоторые эксперименты на небольшой сети
|
120
|
|
5.7.1. Введение
|
120
|
|
5.7.2. Количественная оценка решения для выпуклой квадратичной целевой . функции
|
122
|
|
5.7.3. Чувствительность относительно параметров распределения
|
126
|
|
5.7.4. Использование метода для невыпуклых функций
|
135
|
|
6. Расширения задачи
|
142
|
|
6.1. Оптимизация в динамике
|
142
|
|
6.1.1. Постановка задачи
|
142
|
|
6.1.2. Решение методом динамического программирования
|
146
|
|
6.1.3. Решение другими методами
|
148
|
|
6.1.4. Оптимизация для одного момента времени с учетом колебаний потока
|
150
|
|
6.2. Оптимизация сетей для нескольких видов транспорта
|
151
|
|
6.2.1. Постановка задачи
|
151
|
|
6.2.2. Возможные методы решения
|
155
|
|
6.3. Некоторые замечания по оптимальной структуре сети
|
157
|
|
6.3.1. Некоторые простейшие методы оптимизации структуры сети
|
157
|
|
6.3.2. Оптимальная трасса
|
160
|
|
6.3.3. Индикаторы для структуры графа
|
161
|
|
7. Алгоритмы кратчайшего пути
|
164
|
|
7 1, Введение
|
164
|
|
7 1.1. Необходимость этой главы
|
164
|
|
7 1.2. Постановка задачи
|
165
|
|
7 1.3. Общие замечания по алгоритмам
|
166
|
|
7.2. Алгоритмы построения дерева
|
168
|
|
7.2.1. Алгоритм Мура—Форда—Беллмана
|
168
|
|
7.2.2. Алгоритмы «однократного просмотра»
|
170
|
|
7.3. Матричные алгоритмы
|
172
|
|
7.3.1. Алгоритм Флойда
|
172
|
|
7.3.2- Алгоритм Данцига
|
174
|
|
7.4. Сравнение алгоритмов построения дерева с матричными алгоритмами
|
175
|
|
7.4.1. Оценка необходимой памяти ЭВМ
|
175
|
|
7.4.2. Оценка необходимого времени счета на ЭВМ
|
175
|
|
7.5. Эвристические методы
|
176
|
|
7.5.1. Эвристический метод нахождения кратчайшего пути между двумя узлами
|
176
|
|
7.5.2. Эвристические методы нахождения кратчайших путей между многими или всеми узлами
|
176
|
|
7.6. Разбиение
|
177
|
|
7.7. Малые изменения в сети
|
179
|
|
7.7.1. Пересчет всех кратчайших путей после изменения длины одной дуги по Лоубалу
|
180
|
|
7.7.2. Пересчет всех кратчайших путей после изменения длины одной дуги по Марчланду
|
183
|
|
Часть 2. Конкретное исследование: оптимизация дорожной сети Нидерландов
|
|
|
8. Место оптимизации дорожной сети в общем исследовании транспорта и в определении оптимальной территориальной структуры
|
187
|
|
9. Целевая функция
|
191
|
|
9.1. Общая структура целевой функции
|
191
|
|
9.1.1. Общие замечания
|
191
|
|
9.1.2. Элементы целевой функции
|
192
|
|
9.2. Стоимостная оценка времени поездки
|
194
|
|
9.2.1. Оценка времени поездки
|
194
|
|
9.2.2. Соотношение между временем поездки и степенью использования пропускной способности
|
197
|
|
9.2.3. Суммарные годовые затраты, зависящие от времени поездки
|
203
|
|
9.3. Затраты, связанные с эксплуатацией автомобилей
|
212
|
|
9.3.1. Затраты, связанные с владением автомобилем
|
213
|
|
9.3.2. Затраты, связанные с пробегом
|
213
|
|
9.4. Издержки, связанные с дорожно-транспортными происшествиями
|
215
|
|
9.5. Капитальные вложения и текущие затраты на содержание
|
219
|
|
9.5.1. Общие замечания
|
219
|
|
9.5.2. Форма используемых функций
|
221
|
|
9.5.3. Используемые коэффициенты
|
222
|
|
9.6. Затраты на охрану окружающей среды
|
226
|
|
9.7. Норма дисконта
|
228
|
|
9.8. Целевая функция и дифференциальная стоимость перевозок для дороги
|
229
|
|
10. Оптимальное число полос при заданной интенсивности движения
|
235
|
|
10.1. Вид целевой функции и математическое решение подзадачи
|
235
|
|
10.1.1. Постановка задачи
|
235
|
|
10.1.2. Методы решения задачи минимизации
|
236
|
|
10.1.2.1. Полный перебор
|
236
|
|
10.1.2.2. Методы поиска
|
236
|
|
10.1.2.3. Решение при помощи дифференцирования
|
237
|
|
10.1.3. Вид используемых функций и математические взаимосвязи между уровнем технической оснащенности и интенсивностью движения и между целевой функцией и интенсивностью движения
|
238
|
|
10.1.4. Максимальный и минимальный уровни технической оснащенности дороги
|
243
|
|
10.2. Некоторый анализ чувствительности
|
244
|
|
10.2.1. Чувствительность оптимального соотношения между интенсивностью движения и числом полос
|
245
|
|
10.2.2. Чувствительность целевой функции и суммарной дифференциальной стоимости перевозок
|
251
|
|
10.3. Оптимальное соотношение между интенсивностью движения и числом полос
|
254
|
|
10.4. От непрерывно измеряемого уровня технической оснащенности к целому числу полос
|
259
|
|
10.5. Оптимизация в динамике
|
263
|
|
11. Применение метода SALMOF для оптимизации дорожной сети при заданной матрице поездок
|
265
|
|
11.1. Исходные данные
|
265
|
|
11.1.1. Матрица поездок
|
265
|
|
11.1.2. Сеть
|
267
|
|
11.1.3. Используемые значения коэффициентов целевой функции
|
270
|
|
11.2. Применяемый вычислительный процесс и значения его параметров
|
274
|
|
11.2.1. Вычислительная схема
|
274
|
|
11.2.2. Выбор числа шагов и величины долей, распределяемых в SALMOF
|
278
|
|
11.2.3. Выбор величины Ах в SALMOF
|
281
|
|
11.2.4. Функция выбора маршрута и параметры распределения в DES-CASS
|
284
|
|
11.3. Иллюстрация работы метода на некоторых участках сети
|
287
|
|
11.3.1. Автомобильные дороги между Утрехтом, Гаагой и Роттердамом
|
288
|
|
11.3.2. Сеть дорог к северу от Гааги
|
293
|
|
11.3.3. Автомобильная дорога №58 между городами Берген-оп-Зом и Гус
|
298
|
|
11.3.4. Плотина
|
299
|
|
11.4. Сравнение результатов, полученных пошаговым распределением по минимуму суммарной дифференциальной стоимости перевозок, с результатами, полученными при оптимальной корректировке числа полос проезжей части по транспортным потокам
|
300
|
|
11.5. Результаты расчета и их интерпретация
|
305
|
|
11.6. Выводы для экономической политики
|
310
|
|
Список обозначений
|
313
|
|
Именной указатель
|
317
|
|
Предметный указатель
|
319
|
Содержание книг 
