VIII Международная студенческая научная конференция Студенческий научный форум - 2016

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

Я предпочитаю начать с последнего, так как разъяснение данного вопроса упростит дальнейшее понимание работы, потому что примеры ситуаций, в которых может быть применим подобный алгоритм, дают чёткое представление о принципах его составления и использования. В качестве основного примера я хочу использовать составление маршрута для автобуса. Маршрут под условным номером N предполагает, что работающий на данном маршруте автобус двигается по определённым дорогам, останавливаясь на определённых остановках в определённое время. Основной целью создаваемого мной алгоритма в данной ситуации является вычисление времени прибытия каждого конкретного автобуса на каждую конкретную станцию. Расчёты производятся на основании данных о значении остальных характеристик, о которых речь пойдёт дальше. В качестве примеров использования подобного алгоритма также можно рассматривать движение других видов общественного транспорта, таких как метро, лёгкое метро и монорельсовая ЖД, электрички и различные другие транспортные средства. Также алгоритм возможно применять с целью построения расписания движения внутреннего транспорта на предприятии. Для удобства в дальнейшем я буду использовать в качестве примера построение расписания для автобусного маршрута.

Теперь необходимо разъяснить, что подразумевается под линейным путём. Это не вариативный маршрут, который можно представить в виде отрезка, на котором начальной и конечной точкой являются конечные станции с обеих сторон маршрута. Остановки на маршруте в данном случае являются точками, лежащими на отрезке, причём на различном расстоянии друг от друга (Рисунок 1). Соответственно, автобус в данном случае будет двигаться по отрезку в обоих направлениях.

Рис. 1. Представление маршрута в виде отрезка.

Если маршрут рассматривать в виде графа, мы получим простой граф, содержащий n вершин и n-1 рёбер. Но тут стоит отметить, что для составления алгоритма было бы целесообразно представить маршрут не в виде ненаправленного графа, а в виде направленного графа. И в подобном случае каждая остановка (или станция), за исключением конечных, будет представлена как две вершины, одна – для движения в направлении Конечной станции 2, вторая – для движения в направлении Конечной станции 1. Таким образом, представленный на Рисунке 1 в качестве отрезка маршрут при преобразовании в направленный простой граф примет вид, продемонстрированный на Рисунке 2.

Рис. 2. Представление маршрута в виде простого направленного графа.

Думаю, дальнейших пояснения касательно этого вопроса не требуется, так что можно перейти к разъяснению того, какие в данном алгоритме будут переменные. Поскольку целью алгоритма является вычисление времени прибытия транспортного средства на станции, все остальные параметры маршрута являются переменными, значения которых являются моделью пути. Такие параметры графа, как количество вершин и длина рёбер, необходимо дополнить информацией о транспортном средстве, предполагающемся для движения по маршруту, о его скорости, о количество используемых машин. Также необходима информация о остановках, необходимо указать время, проводимое транспортным средством на остановке. В ходе разработки данной модели будут приняты некоторые условности и упрощения, используемые для сокращения объёма работы, но я попытаюсь отмечать их использование в соответствующих местах. Перечислять все используемые в алгоритме переменные сейчас я не стану и буду их упоминать по ходу объяснения алгоритма.

На этом объяснение цели работы и необходимые пояснения заканчиваются, и я перехожу непосредственно к описанию алгоритма.

Поскольку для наглядной демонстрации алгоритма мной будут использоваться блок-схемы, на Рисунке 3 представлена принятая в данной работе легенда.

Рис. 3. Легенда для блок-схем, представленных в работе.

Отправной точкой для начала алгоритма является указание станций, расположенных на маршруте. Для этой информации используется переменная ChisloSt. Узнав число станций, мы тут же зададим время остановки для каждой из станций. Само собой, это относительная величина и время остановки приблизительное. Также возможно указание времени остановки для станции дважды: на случай движения как в одном, так и в другом направлении. Но это не оказывает существенного влияния на алгоритм и в данной работе опускается. Для хранения данной информации используется массив VremjaOst. Мы вводим в массив значения до тех пор, пока количество значений не будет соответствовать количеству станций. Далее указываются длины рёбер графа, т. е. расстояние между станциями. Опять же, маловероятно, но возможно, что расстояние между двумя станциями немного различается на разных направлениях движения. В данном алгоритме считается, что расстояние между двумя станциями идентично в обоих направлениях движения. Для массива DlinnaPuty значения задаются, начиная со второго элемента, это делается для удобства обращения к данному массиву в дальнейшем, т. к. значение расстояния между двумя станциями будет вызываться, как правило, в момент работы со значениями, касающимися станции прибытия, а значит при работе на промежутке между первой и второй станциями идентификатор будет иметь значение «2». Полученный на данный момент фрагмент алгоритма демонстрируется на Рисунке 4.

Таким образом, на данный момент мы указали основные характеристики пути, описав наш граф: количество вершин графа и длину между его рёбрами (Рисунок 5). Число вершин на первый взгляд в данном случае будет равно переменной ChisloSt, умноженной на два, но, поскольку основной целью нашего алгоритма являются расчёты времени, а не длины, значения времени остановок на станции мы можем представить также, превратив каждую вершину в две, между которыми располагается дополнительное ребро, по длине равное времени остановки, умноженному на скорость движения транспорта (переменная TrainSpeed), речь о которой пойдёт дальше (Рисунок 6).

Рис. 4. Фрагмент алгоритма.

Рис. 5. Граф пути, на котором демонстрируется, к какому промежутку относится какое значение массива DlinnaPuty.

Рис. 6. Представление остановки на станции как движения по ребру между двумя вершинами графа.

После этого указываются остальные данные, необходимые для расчётов, это: время начала работы маршрута, продолжительность работы маршрута, длительность одной смены машиниста или водителя, время, по истечении которого машинист уходит на перерыв (в данном алгоритме мной предполагается, что машинист может уйти на перерыв исключительно находясь на Конечной станции 1, но, само собой, данное исключение легко убирается), длительность перерыва. Также задаётся условное текущее время, необходимое алгоритму, т.к. он будет моделировать деятельность системы. Текущим временем в начале вычисления станет время старта работы системы. Также мы указываем количество транспортных средств и их скорость (в данном алгоритме предполагается, что все транспортные средства имеют идентичное значение данного параметра, что, как мне кажется, логично, потому что движущиеся на различной скорости по одному маршруту объекты нецелесообразны в алгоритме, решающем задачи, поставленные мной в начале работы, а для других задач можно составить и другой алгоритм). Ввод описанной в этом абзаце информации в отдельной блок-схеме я рассматривать не буду, потому что он линеен и не требует дополнительного рассмотрения, но в итоговом алгоритме, само собой, он будет учтён. Далее перечислены все используемые переменные:

1. Количество станций (ChisloSt: integer);

2. Время остановки на каждой из станций (VremjaOst: array of real);

3. Расстояние между двумя станциями (DlinnaPuty: array of real);

4. Время начала движения (TimeStart: real);

5. Время отправления последнего автобуса со станции №1 (общее время пути будет считаться вычитанием из значения времени окончания значения времени начала) (TimeGlobal: real);

6. Длительность одной смены одного машиниста (TimeSme: real);

7. Время, проходящее от начала смены до перерыва (TimePerer: real);

8. Время перерыва (TimeLong: real);

9. Количество трансопртных стредств (NumOfTrains: integer);

10. Скорость трансопртного средства (TrainSpeed: real).

Сразу же создаём вспомогательную переменную для различных циклов (i: real) и переменную, в которой будет храниться значение текущего времени (TimeNow), ей будет присвоено значение переменной TimeStart. Также нам понадобится переменная (TimeOtpr), которая будет означать время между отправлениями автобусов из депо в начале дня. Еще одной переменной, которую я буду использовать, станет переменная (Working) логического типа, обозначающая состояние движения (движение есть, движение остановлено), она понадобится нам, чтобы понимать, когда все автобусы завершат движение и работа системы может быть остановлена.

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

Теперь у нас есть все данные, которые необходимы для моделирования. Проводить его мы будет по принципу добавления минимального временного шага. То есть мы будем каждый раз добавлять к текущему времени минимальный шаг и, если в текущее время происходит какое- то событие, мы это демонстрируем. Также возможно моделирование по принципу ближайшего события, которое упрощает нагрузку на компьютер, но в таком случае мы сталкиваемся с большим объёмом логических условий, что затянет создание программы, а мы можем позволить себе запустить более тяжелую программу. Итак, первым делом мы "создадим" автобусы. Для этого мы создадим массив (Poezd) объектов типа "PoezdType", число объектов в котором будет равно числу, заданному пользователем. Каждый автобус обладает следующими параметрами:

1. Номер машиниста (MashinistNo: integer);

2. Время, прошедшее с начала смены машиниста (TimeOfWork: real);

3. Станция, на которой автобус находится в данный момент или с которой он выехал, не достигнув на данный момент следующей (StationNo: integer);

4. Находится ли данный автобус в пути, либо он в депо (OnWay: boolean);

5. Если автобус в депо, то находится ли он на перерыве (Pause: boolean);

6. Во сколько автобус пришёл на прошлую станцию (When: integer);

7. В каком направлении автобус совершает движение (Way: boolean, здесь значение "True" будет означать путь от депо, а значение "False"- в его сторону).

При создании объекта конструктором будет выдаваться каждому из "автобусов" следующее значение:

MashinistNo := 1; {отсчёт номерам машиниста на каждом автобусе ведется отдельно, тут, как и, например, и на автобусах, и на поездах, каждый водитель или машинист работает только на одной машине}

TimeOfWork := 0; {время работы равно нулю так как на смену машинист только вышел}

StationNo := 1; {в начале рабочего дня все машины в депо, на станции "№1"}

OnWay := false; {в начале рабочего дня все составы числятся нерабочими}

When := 0; {задаётся позже}

Pause := false; Way := true; {перерыва сейчас нет, направление- от депо}

Далее запускается цикл, который будет функционировать, пока хотя бы один из автобусов находится в пути. Тут мы в самом начале используем проверку на соответствие текущего времени тому времени. Если текущее время равно времени какого- то события, то мы запускаем соответственное действие. После запуска системы автоматически, без проверки, стартует первый автобус.

Первым, на что мы сделаем проверку, станет проверка на то, не пора ли автобусу выйти из депо. В случае, если текущее время равно времени, в которое автобус должен выйти из депо, мы вызываем процедуру Start, которая уже упоминалась ранее, перед запуском цикла. Данная процедура демонстрируется на Рисунке 7.

Таким образом мы обозначаем отбытие автобуса из депо и приход его на станцию "№1", откуда он после остановки отправится на станцию "№2". Данную процедуру мы применяем к каждому автобусу в самом начале цикла, ответственного за моделирование работы системы.

Далее нам требуется отслеживать события. Для этого будем использовать специальную процедуру (Events), она будет проверять, происходят ли какие- либо события, а также увеличивать значения переменных, созданных для счётчиков. Она будет запускаться для каждого из автобусов. Первым делом будет проверяться, находится ли автобус в пути, дальнейшие действия совершаются, если автобус в пути. Дальше мы проверяем, если автобус находится на перерыве, не пора ли ему опять выходить на работу. Далее, если автобус не находится на перерыве, мы начинаем выполнение действий. Если с прибытия автобуса до настоящего момента прошло время, соответствующее времени остановки, то мы выводим сообщение о том, что автобус отправился.

Рис. 7. После запуска системы мы делаем для каждого автобуса проверку на необходимость запуска.

Если время, прошедшее с последнего прибытия на станцию, соответствует времени, необходимому на остановку и путь, то мы обозначаем, что автобус прибыл на следующую станцию и выводим соответствующее сообщение. Если станция, на которую автобус прибыл, это n- я станция, то направление пути задаётся обратное. Если станция, на которую автобус прибыл - станция "№1", то направление пути задаётся прямое. Если станция прибытия- "№1", то выполняются следующие действия:

1. Если время одной смены меньше времени, прошедшего с начала смены, к которому мы прибавляем теоретическое время всего пути, то машинист меняется, а значит переменная, обозначающая номер машиниста на данном автобусе, увеличивается на один и время на смене приравнивается нулю.

2. Если время на смене больше времени, через которое можно уйти на перерыв или равно ему и время на смене, из которого вычли время последнего круга, меньше времени до перерыва (что означает, что на предыдущем круге машинисту рано было уходить на перерыв, а сейчас уже можно), то машинист уходит на перерыв.

3. Если текущее время больше суммы времени начала и времени работы всей системы или равно ей, то поезд отправляется обратно в деп

Как только данная процедура закончит свою работу для одного автобуса, она будет выполнять его для следующего и так до того момента, пока не пройдётся по каждому и не достигнет последнего. Далее запускается другая процедура. Она, в случае, если поле "OnWay" у абсолютно всех автобусов имеет значение "false", будет присваивать переменной "Working" значение "false". Это позволит нам выйти из цикла. Далее, в самом конце цикла мы присваиваем переменой "TimeNow" значение, равное значению этой переменной, увеличенной на одну сотую.

Полный алгоритм метода класса PoezdType, проверяющего соответствие текущего времени с временем каких-либо событий представлен далее, на Рисунках 8 и 9.

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

Рис. 8. Первая половина блок-схемы алгоритма.

Рис. 9. Вторая половина блок-схемы алгоритма.

Код для цитирования: Скопировать