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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Множество H = AV\BV\CV\...: множество расписаний с оптимальными условиями труда. (4.1)

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

н{d)A{d)в{d)c{d)... (4.2)

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

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

Зяачеят Aid)

Время работы \-Норма времени по расписанию d работы

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

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

4.2.3. ОЦЕНКА РЕЗУЛЬТАТОВ

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

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

команды редактирования расписания, отображаемого на дисплее.

Примеры

На рис. 4.2 приведен пример решения, выбранного среди кандидатур в расписание, полученных с помощью компьютера. Этому результату как решению трудно дать хорошую Оценку, но с помощью простых операций, с точки зрения специалиста, его можно превратить в расписание на рис. 4.3, имеющее практическое значение. Последовательность операций состоит в следующем: прежде всего расписание А на рис. 4.2 присоединяется в начало расписания 1, затем расписания \ и В на этом же рисунке разрезаются в соответствующих окрестностях расписания С, и, наконец, формируется вновь расписание из первой части расписания В, расписания С и последней части расписания 1. Затем первая часть расписания 1 стыкуется с последней частью расписания В. В результате образуется расписание на рис. 4.3. Если сравнить эти два расписания (рис. 4.2 и рис. 4.3), то окажется, что в том и другом случае необходимо 6 автобусов. Однако расписание на рис. 4.3 более эффективно, чем расписание на рис. 4.2. Действительно, в интервалах 14 ч-14 ч 30 мин и 19 ч 20 мин-20 ч уже отсутствуют два перегона автобусов, отмеченных на рис. 4.2 штриховыми линиями, при этом сохранена интенсивность движения автобусов. Число рабочих расписаний, время работы в которых превышает принятые 8 ч, увеличилось на единицу, причем время движения находится в допустимых пределах (5 ч). Протяженность специальных расписаний в часы пик стала также больше, но все еще в пределах допустимых норм.

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

Сравиеиие времени составления расписания иа компьютере и вручную

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

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

На практике после перебора всех зубцов даже при получении готового расписания работа по его составлению не заканчивается. При работе вручную необходимо прежде всего аккуратно переписать готовое расписание заново. Кроме того, из такого расписания следует выписать все числовые значения, необходимые для соблюдения расписания на практике, и оформить их в виде соответствующих документов. Одним из составленных таким образом документов являются таблицы времен прибытия автобусов, которые вывешиваются на остановках. Затем каждое рабочее расписание прослеживается от выхода автобуса из гаража до конца рабочего дня и составляются небольшого размера памятки водителям, содержащие маршрут следования и время в пути. Такие памятки размещаются рядом с местом водителя.

Кроме того, из всех документов записи неоднократно переносятся в различного рода гроссбухи, необходимые для управления автобусным предприятием. В настоящее время подобную работу вручную выполняют примерно за 70 ч. С помощью компьютера всю информацию можно вывести на графопостроители и печатающие устройства примерно за 10 ч. Объем работы по составлению расписания с учетом последующей коррекции сокращается примерно в 7 раз (табл. 4.2).