Задача

Допустим, вы отвечаете за управление самолетным парком и хотите построить рас- писание полетов. Ниже описана очень простая модель. В ходе маркетинговых ис- следований были определены m рейсовых сегментов, обслуживание которых могло бы принести высокую прибыль; сегмент j определяется четырьмя параметрами: аэропортом отправления, аэропортом прибытия, временем отправления и време- нем прибытия.
На рис. 7.17, a изображен простой пример с шестью сегментами, которые вам хотелось бы обслуживать в течение одного дня:

(1) Бостон (BOS, отправление 6:00) — Вашингтон (DCA, прибытие 7:00)

(2) Филадельфия (PHL, отправление 7:00) — Питтсбург (PIT, прибытие 8:00)

(3) Вашингтон (DCA отправление 8:00) — Лос-Анджелес (LAS, прибытие 11:00)

(4) Филадельфия (PHL, отправление 11:00) — Сан-Франциско (SFO, прибытие 14:00)

(5) Сан-Франциско (SFO, отправление 14:15) — Сиэтл (SEA, прибытие 15:15)

(6) Лас-Вегас (LAX, отправление 17:00) — Сиэтл (SEA, прибытие 18:00)

В каждый сегмент включается время отправления и прибытия, а также аэро- порты.

Чтобы один самолет мог использоваться для сегмента i, а затем позднее для сегмента j, если:

(a) аэропорт прибытия i совпадает с аэропортом отправления j, и времени

между рейсами достаточно для технического обслуживания самолета; или

(b) между рейсами можно добавить сегмент, который переводит самолет из

аэропорта прибытия i в аэропорт отправления j с достаточным промежуточным

временем.

Рис. 7.17. a — простой экземпляр задачи планирования авиаперелетов; b — расширенный граф, показывающий возможности перехода между рейсами


Например, если время технического обслуживания составляет один час, один самолет может использоваться для полетов (1), (3) и (6), чтобы самолет находился в Вашингтоне между рейсами (1) и (3), а затем вставить перелет между рейса- ми (3) и (6).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии
  16. Основные задачи МПП.
  17. Задачи и упражнения