Главная » Справочник » Основы организации и управления транспортными системами » Идея и алгоритм определения оптимального варианта плана формирования поездов

Идея и алгоритм определения оптимального варианта плана формирования поездов

Существует несколько алгоритмов решения задачи построения оптимального варианта ПФ поездов, но все они являются комбинаторными, то основанными на идее последовательного перебора возможных вариантов решения задачи и выбора из множества этих вариантов наилучшего.

Одним из методов, реализующих идею постепенного уменьшения количества возможных вариантов решения задачи, является метод сокращения множества планов. Идея метода заключается в том, что вначале определяются назначения, удовлетворяющие достаточному условию выделения струи вагонопотока в самостоятельное назначение: Cmi≤⋅ N ij ∑Тэкk , то k1= есть чтобы затраты на накопление вагонопотока выделенного назначения не превышали затрат на его переработку по всем промежуточным станциям его движения.

Затем из множества таких назначений выбирается оптимальное по критерию минимума суммарных затрат на накопление и переработку вагонов. Оптимальное назначение временно переводится в состав запрещенных и определяется вариант с двумя выделенными назначениями, затем с тремя и т.д. В результате последовательного запрещения вариантов с одним, двумя, тремя и т.д. назначениями достигается значительное сокращение общего количества рассматриваемых вариантов.

Алгоритм метода сокращения множества планов состоит из следующих действий:

сформировать вариант ПФ, состоящий только из участковых назначений, то есть струй, движущихся непрерывно только между соседними железнодорожными станциями;
поочередно выделяя струи, удовлетворяющие достаточному условию. Из множества вариантов с одним выделенным назначением выбирается вариант, при котором суммарные затраты на накопление и переработку вагонов будут минимальными. Это назначение временно переводится в состав запрещенных;
последовательно формируются варианты, содержащие одновременно два, три, четыре и т.д. назначений, удовлетворяющих достаточному условию. В каждом множестве вариантов выбирается наилучший по критерию минимума затрат на накопление и переработку вагонов. Это действие продолжается до тех пор, пока существуют варианты, удовлетворяющие достаточному условию;
из множества вариантов с одним, двумя, тремя и т.д. выделенными назначениями выбирается оптимальный, при котором суммарные затраты на накопление и переработку вагонов будут минимальными.

Идея метода сокращения множества планов основана на теореме, согласно которой если выделенное назначение ПФ является наилучшим по сравнению с другими назначениями, то нельзя выделить ни одного назначения одновременно с этим, чтобы не увеличить суммарную оценку ПФ. Это утверждение справедливо для двух, трех и любого количества одновременно выделенных назначений.

Предыдущая статья Задачи взаимодействия видов транспорта Следующая статья Идея и общий алгоритм метода динамического программирования

Статьи по теме