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

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

Пусть маршруты выбраны так, как на рис. 4.1. Наибольшая потребность в перевозках между станцией D и городом Е, чуть меньшая потребность в перевозках - между городом Е и пригородом F. Привокзальная площадь на станции D тесная, на ней трудно выделить площадку для стоянки автобусов во время отдыха водителей. Однако вблизи станций С и В есть автостоянки, которые можно использовать как место отдыха. В общем случае, если есть удобное место в гараже, на него можно поставить автобус и отдохнуть, но в данном случае гараж А находится довольно далеко от станции D, поэтому из экономических соображений следует

Пригород F

Железная дорога

Стаисия С

Гарак А

Рис. 4.1. Пример маршрутов автобусов.

Рис. 4.2. Пример 1: расписание и его четыре элемента.

всячески избегать того, чтобы водители для отдыха специально возвращались в гараж.

Прежде всего определим для данного маршрута четыре элемента расписания. Эти элементы становятся очевидными, если их представить в виде ломаных линий (рис. 4.2 и 4.3). На рис. 4.2 и 4.3 даны одни и те же четыре элемента расписания для второй половины дня. По вертикали отложено не расстояние, а требуемое время. При этом очевидно, что пути движения автобусов в одном направлении представлены параллельными линиями. По горизонтали отложено время дня. Автобус, отправившись от гаража А, направляется к станции D. В это время в нем нет потребности, поэтому он просто перегоняется (на рисунке это обозначено штриховой линией). От станции D он направляется к станции Е, где обслуживает пассажиров, направляющихся либо в пригород F, либо к станциям С и В. Все это время он перевозит пассажиров, что на рисунках показано сплошной линией. Маршрут движения автобуса в оба конца пред-

Рис. 4.3. Пример 2: расписание и его четыре элемента.

ставлен в виде пилообразной линии. Вершины каждого зубца показьгеают отстой автобуса. Четыре элемента расписания можно представить как множество таких пилообразных линий, показаных на рисунках жирными линиями. На этом этапе эти линии еще не имеют какой-либо связи. Они являются входными условиями для составления расписания.

Условия составления расписания

Соединим вместе пилообразные линии, представляющие четыре элемента расписания, и сгруппируем их по времени работы каждого водителя. На рис. 4.2 можно выделить группы линий, помеченных цифрами 1-4. Длина линии должна соответствовать времени работы водителя. Если длина большая, приходится выплачивать водителям за сверхурочную работу, что уменьшает прибыль, а превышение времени в несколько раз влияет на движение автобусов в целом. Если же, наоборот, длина линии короткая, появляются неиспользумые ресурсы за счет вместимости и числа автобусов, что невыгодно. Во время работы водителям необходимо предоставить минимально необходимый отдых. Короткий отдых ухудшит условия работы, повредит безопасности. Слишком большой-невьп-оден. Для отдыха важно выбрать не только его продолжительность, но и время. Отдых не обязательно должен быть разовым, лучше это сделать два раза, а еще лучше отдыхать, когда водитель почувствует усталость. В случае многократного отдыха необходимо по крайней мере однажды предусмотреть время для обеда. Помимо отдыха принимаются во внимание места соединения зубцов на рисунках, т. е. времена отстоев на конечных станциях перед отправлением автобусов. Рассуждения о временах отстоя как местах соединения зубцов аналогичны рассуждениям о временах отстоя в вершинах зубцов. Желательно, чтобы эти времена были в разумных пределах небольшими, но в местах, где ожидаются заторы на дорогах, времена устанавливаются заведомо больше, что гарантирует периодичность движения. Оставшееся время-время движения, которое, конечно, должно быть минимально необходимым. То, что связывает и объединяет между собой зубцы этих линий, назовем рабочим расписанием.

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

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

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

4.2.2. ФУНКЦИИ АВТОМАТИЗИРОВАННОГО СОСТАВЛЕНИЯ РАСПИСАНИЯ АВТОБУСОВ

Проблема состоит в поиске комбинации зубцов как формы представления четырех элементов расписания, следуя конкретной цели при различных ограничениях (от частного к общему). В этом смысле основной метод решения этой

14-6830

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

Многие из условий комбинирования зубцов не являются строгими. Например, обычно невозможно создать расписание, в котором будет полный набор длин рабочих расписаний, т. е. времен работы водителей за день, поэтому на практике выбираются конкретные целевые значения, и составители вынуждены более или менее придерживаться этих значений. То же самое можно сказать о времени отстоя и времени отдыха. Другими словами, главная цель-составление оптимального расписания в целом, в котором все или многие факторы находятся в допустимых на практике пределах и отличны от идеальных значений.

Эвристический метод

Будем составлять расписание, повторяя процедуру иэ-влечения одного расписания и подбора из оставшихся зубцов второго расписания (рис. 4.4). Очевидно, что при такой процедуре образуется дерево, а число комбинаций растет в геометрической прогрессии, и метод полного перебора всех

Каншдатура )

(ПерваяЧ кандидатура \ в распасатв J

\mapa в рисписате

(Последняя \ кандидатура ) в расписание J

Рис. 4.4. Дерево принятия решения.

случаев здесь не пригоден из-за слишком большого времени вычислений.

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

Прежде всего, очевидны следующие три условия (они существенно сокращают число комбинаций);

1) зубцы соединяются друг с другом таким образом, что автобус, вернувшийся в какой-либо конечный пункт, отправляется из этого же пункта;

2) комбинации, в которых предусматривается отдых в конечном пункте, не оборудованном для отдыха, исключаются;

3) при приближении времени отдыха преимущественно выбирается комбинация зубцов, ведущая через заданный зубец к конечному пункту, оборудованному для отдыха.

Кроме того, добавим следующее эвристическое правило как средство прогноза выбора комбинаций:

4) преимущественно выбирается комбинация, при которой отдых переносится на менее напряженное время дня.

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

5) комбинации, в которых предусматривается отдых в часы пик, не выбираются, т.е. используются комбинации с непрерывным следованием зубцов в расписании.