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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обработка нечеткостей

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

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

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

Таблица 4.1. Время работы и его составляющие

В данном случае лучше всего следовать общим правилам обработки нечеткостей. Эти правила основаны на понятии нечеткого множества. Говоря о расписании автобусов, в качестве нечеткого множества выделим «множество расписаний с оптимальным временем работы», представим его

соответствующим образом и используем. Пусть это будет множество А.

Множество А: множество расписаний с оптимальным временем работы.

Аналогично можно говорить о времени движения и времени отдыха.

Множество В: множество расписаний с оптимальным временем движения.

Множество С: множество расписаний с оптимальным временем отдыха.

Рассмотрим затем множество Н расписаний с оптимальными условиями труда. В соответствии с пересечением множеств его можно представить в виде

Множество множество расписаний с оптимальными условиями труда. (4.1)

Множество Н также нечеткое. Степень принадлежности некоторого расписания d множеству Н определяется по тому, насколько это расписание удовлетворяет условиям труда. Функцию, определяющую эту степень, обозначим через и используем ее для представления нечеткого множества Н. Функция является функцией принадлежности множества Н. Существуют различные способы ее определения. Наиболее часто используется запись функции с учетом выражения (4.1):

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

Как уже говорилось выше, логическое произведение в правой части (4.2) можно вычислить на основе соответствующих функций принадлежности. Таким образом, получаем

Рис. 4.5. Функция принадлежности.

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