Список работ

Оптимизация расписания движения трамваев

Бартеньев О. В., Ефремова Н. Г.

Содержание

Цель работы

Исследовать возможность применения генетического алгоритма для решения задачи оптимизации расписания движения трамваев. В качестве критерия оптимизации используется сумма среднего времени ожидания (в секундах) и числа рейсов расписания.
Задача решается при следующих допущениях:

  1. Пассажиров перевозят трамваи одного маршрута, например, маршрута 29.
  2. На всех остановках площадки высадки и посадки пассажиров совпадают (на маршрутах с турникетами имеются остановки с двумя площадками – первая для высадки пассажиров, вторая для посадки).
  3. Движение трамваев осуществляется по обособленным путям.
  4. Время выхода пассажиров из трамвая принимается меньшим, чем время посадки в трамвай.
  5. Начальная популяция состоит из случайно сгенерированных расписаний.
  6. Все пассажиры, находящиеся на остановке, входят в пришедший трамвай.
  7. Время начала движения первого и последнего рейсов одинаковы для всех расписаний популяции.

Параметры модели

Задание расписания и исходной популяции

Расписание задается в виде следующего массива:
S = {t1, t2, …, tm},
где
ti – время отправления рейса i с начальной (конечной) остановки маршрута;
m – суточное число рейсов на маршруте.
В этом массиве неизменными являются значения t1 и tm – соответственно время первого и последнего рейсов. Прочие элементы могут в процессе решения задачи изменяться.
Значение m определяет размерность решаемой задачи. В случае одного маршрута, если t1 = 5 час и tm = 24 час и среднее время между рейсами составляет 3 мин, то m = 380.
Популяция – это множество расписаний:
P = {S1, S2, …, Sn},
Расписания генерируются по следующему правилу:
tj + 1 = tj + Δt,
где Δt = rand(tmin, tmax),
где tmin, tmax – соответственно минимально и максимально допустимые промежутки между рейсами (задаются разными для часов пик, утренних, вечерних и дневных часов движения).

Критерий оптимизации

Минимизируется сумма среднего времени ожидания (в секундах) и числа рейсов расписания. Значение критерия минимизируется
Время ожидания рассчитывается следующим образом:
T = ΣRk = 1Σni = 1Ti / Σni = 1Ni
гдеR – число рейсов в расписании;
n – число остановок на маршруте;
Ti – время ожидания трамвая на остановке i;
Ni – число пассажиров, севших в трамвай на остановке i.
В свою очередь, расчет Ti ведется по следующей формуле:
Ti = Tij – Tij – 1,
гдеTij – время отправления рейса j с остановки i.
Время отправления рейса j с остановки i есть сумма времени прибытия рейса j на остановку i и времени посадки (или высадки) пассажиров, ожидающих на остановке трамвай этого рейса.
Время посадки пассажиров в прибывший трамвай оценивается следующим образом:
TOij = to * Nij
где to – среднее время посадки одного пассажира;
Nij – число пассажиров, севших в трамвай рейса j на остановке i.
Полагается, что в трамвай входят все находящиеся на остановке пассажиры.

Диаграмма прихода/выхода пассажиров

Число пассажиров, ожидающих трамвай, и число пассажиров, его покидающих, – это случайная величина, для работы с которой используются диаграммы прихода/выхода пассажиров.
Диаграммы формируются для каждой остановки на основе статистических данных отдельно для рабочих дней, выходных и праздников.
Пример диаграммы показан на рис. 1.

Диаграмма прихода/выхода пассажиров

Рис. 1. Диаграмма прихода пассажиров (рабочий день)

Каждый временной интервал диаграммы показывает, сколько пассажиров пришло на остановку в этот интервал.
Диаграмма позволяет найти число пассажиров, пришедших на остановку в промежуток между двумя соседними рейсами. Если этот промежуток принадлежит интервалу диаграммы, то это число равно:
NCij = NTij * (Tij– T ij – 1) / ΔT
гдеΔT – длина временного интервала диаграммы;
NTij – показание диаграммы (число пассажиров, приходящих на остановку в рассматриваемый интервал).
Если же промежуток между двумя соседними рейсами принадлежит нескольким интервалам диаграммы, то при вычислении числа пришедших пассажиров учитывается вклад каждого интервала.
Аналогично оценивается и число пассажиров, выходящих из трамвая.
В работе диаграммы прихода/выхода генерируются автоматически. Программа их построения описана в [1].

Операции генетического алгоритма

Генетический алгоритм содержит операции скрещивания, мутации и селекции [2].
Поскольку в результате скрещивания и мутации могут нарушаться ограничения расписания, в алгоритм добавлены операции перестройки расписания, призванные устранить эти нарушения.
Операция скрещивания
В результате ее выполнения создается новое расписания Sr по двум расписаниям Sk и Sl текущей популяции.
Время отправления рейса j с первой остановки результирующего расписания вычисляется по следующему алгоритму:
// Nk, Nl, Nr, – соответственно число рейсов в расписаниях Sk, Sl, Sr
// S [j] – начало рейса j
Nr = max(Nk, Nl)
j = 1 // Номер рейса
пока j <= Nr выполнить
     если j <= Nk и j <= Nl тогда
          Sr[j] = (Sk[j] + Sl[j]) / 2
     иначеЕсли Nk < Nl тогда
           Sr[j] = Sl[j]
     иначе
           Sr[j] = Sk[j]
     конецЕсли
      j = j + 1
конецЦикла
При равном числе рейсов в расписаниях Sk и Sl результирующее расписание – это полусумма исходных расписаний:
Sr = (Sk + Sl) / 2
В качестве Sk и Sl поочередно берутся два расписания из ранее сформированного подмножества лучших критерию оптимизации расписаний текущей популяции.
Операция мутации
Скрещивание выполняется, пока наблюдается улучшение расписания по критерию оптимизации.
Если скрещивания не приводят к улучшению расписания, то выполняется операция мутации расписания второго по качеству расписания, заключающаяся в уменьшении или увеличении числа его рейсов.
Увеличение числа рейсов выполняется по следующему алгоритму:
  1. Найти пару соседних рейсов с максимальным интервалом.
  2. Вставить рейс между этими рейсами так, чтобы не нарушить ограничения расписания.
  3. Повторить пп. 1 и 2 заданное число раз.
Удаление числа рейсов выполняется по следующему правилу:
  1. Найти рейсы (j - 1) и (j + 1) с минимальным интервалом.
  2. Удалить рейс j.
  3. Повторить пп. 1 и 2 заданное число раз.
Перестройки расписания
Результирующее расписание проверяется на предмет удовлетворения ограничениям расписания. Если интервал между рейсами j и j + 1 меньше допустимого значения, то выполняется первая перестройка расписания, устраняющая это нарушение:
// tmin – минимально допустимое время между соседними рейсами
если Sr[j + 1] – Sr[j] < tmin тогда
     Sr[j + 1] = Sr[j] + tmin
конецЕсли
Если до начала утреннего интервала часов пик или после завершения вечернего интервала часов пик рейсы следуют слишком «густо», то выполняется вторая перестройка расписания, разряжающая обнаруженную густоту:
// tmax – максимально допустимое время между соседними рейсами
если Sr[j + 2] – Sr[j] < 0.5 * tmin тогда
     удалить из расписания рейс Sr[j + 1]
конецЕсли
Эта перестройка способствует снижению числа рейсов в расписании.
Если превышено максимально допустимый интервал между соседними рейсами, то выполняется третья перестройка расписания, устраняющая это нарушение:
// tmax – максимально допустимое время между соседними рейсами
если Sr[j + 1] – Sr[j] > tmax тогда
     вставить в расписание между рейсам j и j + 1 рейс
     с временем отправления (Sr[j + 1] + Sr[j]) / 2
конецЕсли
Расписание Sr, если оно лучше своих предков, заменяет в популяции худшее по критерию оптимизации расписание.

Генетический алгоритм

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

  1. Выполнить генерацию начальной популяции.
  2. Рассчитать значение критерия оптимизации для каждого расписания популяции.
  3. Отсортировать популяцию по возрастанию значению критерия оптимизации.
  4. Отобрать k лучших расписаний популяции и выполнить попарные скрещивания. Число скрещиваний равно k * (k - 1).
  5. После каждого скрещивания устранить обнаруженные при скрещивании нарушения ограничения расписания (выполнить перестройки расписания).
  6. Вычислить значение критерия оптимизации полученного в результате скрещивания расписания Sn.
  7. Если расписание Sn превосходит по качеству своих предков, то заменить худшее расписание популяции на найденное расписание Sn.
  8. Если расписание все полученные в результате скрещивания расписания уступают своим предкам, то выполнить мутацию второго по качеству расписания популяции (лучшее расписание популяции сохраняем).
  9. Повторить пп. 3 - 8 заданное число раз.

Результаты

Реализованное на C# приложение позволяет искать расписания как при движении с турникетами, так и без них.
Выбор варианта расчета указывается в форме, приведенной на рис. 2.

Интерфейс пользователя

Рис. 2. Пользовательский интерфейс

При движении с турникетами имеем следующие значения критериев:
При движении без турникетов имеем следующие значения критериев: (Первая часть критерия – это среднее время ожидания (в секундах), вторая – число рейсов в расписании.)
В обоих случаях заданы одинаковые значения параметров модели (перечисленных ниже и прочих): При минимизации только времени ожидания можно получить существенное снижение этого показателя [3], но при этом неизбежно вырастет число рейсов.

Использование метода Нелдера-Мида

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

Реализация

Код, воплощающий и генетический алгоритм, и метод Нелдера-Мида:

// Перестройка (restructuring) заключается в изменении числа рейсов в расписании, полученном в результате скрещивания
// В результате может получиться недопустимое расписание. Тем не менее с ним ведется работа.
// Допустимое расписание будет получено позже в результате последующих скрещиваний и корректировок
using System;
using System.IO; // StreamReader
using System.Collections.Generic; // List
using System.Windows.Forms;

namespace WindowsFormsApplicationTram
{
    public partial class FormTram : Form
    {
        const int nCrossMax = 20; // Предельное число скрещиваний в одной эпохе
        const int nRestructMax = 9; // Предельное число мутаций
        const int pDI = 5, pDI2 = 9; // pDI - pDI2 - диапазон выбора величины, на которую будет уменьшено (увеличено) число рейсов расписаниия при его перестройке
        const int rDecr = 8; // Параметр выбора действия из альтернативы: уменьшать или увеличивать число рейсов при перестройке (0 < rDecr < 10)
        const int nDoors = 4; // Число входов в трамвай

        const double pasCor = 2.2; // Коэффициент масштабирования числа пассажиров
        const double kSpeed = 0.5; // Коэффициент поправки скорости
        const double kSpeedTact = 1.0; // Коэффициент поправки скорости тактового расписания
        const double nPAdd = 0.25; // Поправка числа пассажиров (до округления)

        const int tMinPeak = 120; // Минимальное время между соседними трамваями в часы пик, с
        const int tMaxPeak = 240; // Максимальное время между соседними трамваями в часы пик, с
        const int tMinOth = 300; // Минимальное время между соседними трамваями в утренние и вечерние часы до и после часов пик, с
        const int tMaxOth = 600; // Максимальное время между соседними трамваями в утренние и вечерние часы до и после часов пик, с
        const int tMinOthDay = 240; // Минимальное время между соседними трамваями в дневные прочие часы, с
        const int tMaxOthDay = 480; // Максимальное время между соседними трамваями в дневные прочие часы, с

        const int tactPeak = 210; // Такт в часы пик, с
        const int tactOth = 450; // Такт в утренние и вечерние прочие часы, с
        const int tactOthDay = 330; // Такт в дневные прочие часы, с

        const int nStops = 24; // Число остановок (без начальной)
        const int tStart = 5 * 3600 + 20 * 60; // Время начала движения первого рейса, с (= 19200)
        const int tEnd = 25 * 3600 + 20 * 60; // Время начала движения последнего рейса, с (= 91200 / 87600)
        // Учет подхода пассажиров во время посадки
        const int dtPeak = 30; // Добавка к текущему времени в часы пик, с
        const int dtOth = 5; // Добавка к текущему времени в прочие часы, с
        const int tInOneMin = 1; // Минимальное время посадки одного пассажира, с
        const int tInOneMax = 3; // Максимальное время посадки одного пассажира, с
        const int tOnStopMin = 1; // Минимальное время стоянки трамвая на остановке, с (стоит, даже если нет пассажиров)

        const string fileDists = "dists.txt";
        const string fileSpeeds = "speeds.txt";
        const string fileParams = "params.txt"; // Читаем из файла интервал и число интервалов диаграммы прихода
        const string fileStop = "stop"; // Начало имени файлов остановок
        const string fileRoutes = "routes.txt"; // Файл времени прибытия трамваев маршрутов на остановки
        const string fileRoutePas = "routePas.txt"; // Файл, содержащиий для каждого рейса время его начала и число перевезенных пассажиров
        const string fileWaitTime = "_waitTime.txt"; // Файл, содержащиий среднее время ожидания начальных расписаний
        const string fileWaitTimeOpt = "_waitTimeOpt.txt"; // Файл, содержащиий среднее время ожидания оптимизированных расписаний
        const string fileBestShedI = "bestShedI.txt"; // Файл, содержащиий лучшее начальное расписание
        const string fileBestShed = "bestShed.txt"; // Файл, содержащиий лучшее расписание
        const string fileBestShedC = "bestShedC.txt"; // Файл, содержащиий исправленное лучшее расписание

        const string textIntVal = "Интервал диаграммы прихода (мин): ";
        const string textN = "Число интервалов диаграммы прихода: ";
        const string textNStops = "Число остановок: ";
        const string textMorn = "Утренний интервал часов пик (ч): ";
        const string textEv = "Вечерний интервал часов пик (ч): ";
        const string textShed0 = " - лучшего начального расписания (с): ";
        const string textShed0Tact = " - начального тактового расписания (с): ";
        const string textShedC = " - лучшего найденного расписания (с): ";
        const string textShedRoutsN = "Начальные время ожидания и число рейсов: ";
        const string textTimeSum = "Время движения по маршруту без остановок (с): ";
        const string textNPasByDiags = "Нужно перевести: ";
        const string textNPAll = "Всего перевезено: ";
        const string textTimeStart = "Время начала движения (с): ";
        const string textTimeDiagLast = "Время завершения последнего интервала диаграммы прихода (с): ";
        const string textNCross = "Число скрещиваний: ";
        const string textNRestruct = "Число мутаций: ";
        const string textNViolations = "Число нарушений в лучшем расписании: ";

        const bool diffNumberOfRoots = true; // true, если в распиисаниях популяции может быть разное число рейсов
        const bool onlyEqualSheds = false;

        bool tactShed; // Если true и allInitShedAreTact = false, то первое начальное расписание является тактовым
        bool allInitShedAreTact = true; // Если true и tactShed = true, то все начальные расписания являются тактовыми (такты задаются с учетом часов пик)
        bool improvedShed; // Если true, то генерируется улучшенное расписание (интервалы задаются с учетом часов пик)
        bool simpleShed; // Если true, то генерируется простое расписание (интервалы задаются в диапазоне tMinPeak - tMaxOth)
        bool turnstile; // false, если без турникета
        bool doOpt; // Если false то вывод лучшего расписания начальной популяции (отмена оптимизации)
        int nShedules; // Число расписаний в популяции (размер популяции)
        int nCrossings; // Допустимое число попыток скрещивания в одной итерации с целью улучшения популяции
        int nPAll; // Общее число перевезенных пассажиров всеми рейсами расписания
        int timeInAll; // Сумммарное время посадки пассажиров в трамваи расписания, с
        int timeEnd; // // Время отправления последнего рейса с последней остановки, с
        int nCrossAll = 0; // Всего скрещиваний
        double kOut = 1.0; // Коэффициент учета времени выхода пассажиров из травмая, равен 1 при движении с турникетами
        double[] arrDist; // Массив расстояний между остановками, м
        double[] arrSpeed; // Массив средних скоростей между остановками, м/с
        int[] arrTMov = new int[nStops]; // Массив, каждый элемент которого - это время движения от предшествующей остановки до текущей
        int[] arrTCur = new int[nStops]; // Массив времени прибытия текущего рейса на остановки маршрута, с
        int[] arrTPrev = new int[nStops]; // Массив времени прибытия прежнего рейса на остановки маршрута, с
        // Массив расписаний популяции. Каждый элемент массива - это список, содержащий расписание
        List<int>[] arrShedules;
        int[] arrWaitTime; // Массив значений среднего времени ожидания + число рейсов расписания
        int[] arrNPAll; // Массив, элемент которого - это общее число перевезенных пассажиров всеми рейсами расписания
        int[] arrTimeInAll; // Массив, элемент которого - это суммарное время посадки пассажиров в трамваи расписания
        int[] arrTimeEnd; // Массив, элемент которого - это время прибытия последнего рейса расписания на последнюю остановку
        int[,] arrDiags; // Массив диаграмм прихода
        int[] arrTactPeak; // Массив тактов в часы пик, с
        int[] arrTactOth; // Массив тактов в утренние и вечерние прочие часы, с
        int[] arrTactOthDay; // Массив тактов в дневные прочие часы, с
        int intLen; // Длина интервала диаграммы прихода, с
        int N; // Число интервалов диаграммы прихода
        int tLastIntEnd; // Время завершения последнего интервала диаграммы прихода, с
        int timeSum; // Суммарное время движения по маршруту без остановок
        int nPasByDiags; // Число перевезенных пассажиров по диаграмамм прихода (нужно перевести пассажиров)
        // Начало и конец утреннего и вечернего интервалов часов пик, с
        int tPeakMornStart = 0, tPeakMornEnd = 0, tPeakEvStart = 0, tPeakEvEnd = 0;
        int nShedInitBest; // Лучшее начальное расписание
        int seed; // Затравка датчика случайных чисел
        string[] arrWaitTimeShed; // Массив отсортированных расписаний
        Random rand; // Датчик случайных чисел с затравкой 24
        StreamReader sR;
        StreamWriter sW;

        // Нелдер-Мид
        int nOfTacts; // Число тактов тактового расписания
        double[,] simplex;
        double[] FN; // Значения функции в вершинах симплекса
        double[] TW; // Значения времени ожидания в вершинах симплекса
        double[] NR; // Значения числа рейсов в вершинах симплекса
        List<double> LShedD = new List<double>(); // Текущее расписания
        double nPAllD; // Общее число перевезенных пассажиров всеми рейсами расписания
        double timeInAllD; // Сумммарное время посадки пассажиров в трамваи расписания, с
        int timeLastRoutLastStop; // Время прибытия последнего рейса на последнюю остановку

        public FormTram()
        {
            InitializeComponent();
            readParams();
            checkBoxTurnstile.Checked = false;
            checkBoxRestruct.Checked = false;
            boolValues();
            readDistsSpeeds(); // Чтение файлов расстояний и средних скоростей между остановками
            readDiags(); // Чтение диаграмм прихода пассажиров
            //
            labelShedBest0.Text = tactShed ? textShed0Tact : textShed0;
            labelShedBestC.Text = textShedC;
            labelShedRoutsN.Text = textShedRoutsN;
            labelNPAll.Text = textNPAll;
            labelTimeInAll0.Text = tactShed ? textShed0Tact : textShed0;
            labelTimeInAllC.Text = textShedC;
            labelTimeStart.Text = textTimeStart + tStart;
            labelTimeEnd0.Text = tactShed ? textShed0Tact : textShed0;
            labelTimeEndC.Text = textShedC;
            tLastIntEnd = tStart + N * intLen; // Время начала движения + число интервалов диаграммы прихода * длина интервала диаграммы прихода
            labelTimeDiagLast.Text = textTimeDiagLast + tLastIntEnd;
            labelNCross.Text = textNCross;
            labelNRestruct.Text = textNRestruct;
            labelNViolations.Text = textNViolations;
        }
        private void readParams()
        {
            sR = new StreamReader((checkBoxWeekEnd.Checked ? "Выходные/" : "Будни/") + fileParams);
            intLen = Convert.ToInt32(sR.ReadLine()); // Длина интервала диаграммы прихода, с
            N = Convert.ToInt32(sR.ReadLine()); // Число интервалов диаграммы прихода
            // Начало и конец утреннего и вечернего интервалов часов пик, с
            tPeakMornStart = Convert.ToInt32(sR.ReadLine());
            tPeakMornEnd = Convert.ToInt32(sR.ReadLine());
            tPeakEvStart = Convert.ToInt32(sR.ReadLine());
            tPeakEvEnd = Convert.ToInt32(sR.ReadLine());
            sR.Close();
            labelIntVal.Text = textIntVal + (intLen / 60);
            labelN.Text = textN + N;
            labelNStops.Text = textNStops + nStops;
            labelMorn.Text = textMorn + findhM(tPeakMornStart) + " - " + findhM(tPeakMornEnd);
            labelEv.Text = textEv + findhM(tPeakEvStart) + " - " + findhM(tPeakEvEnd);
        }
        // Возвращает строку, содержащую время в формате ЧЧ:ММ
        string findhM(int time)
        {
            int hour = time / 3600;
            int min = (time - hour * 3600) / 60;
            return "" + hour + ":" + (min < 10 ? "0" : "") + min;
        }
        private void readDistsSpeeds()
        {
            string sL;
            arrDist = new double[nStops]; // Массив расстояний между остановками, м
            arrSpeed = new double[nStops]; // Массив средних скоростей между остановками, м/с
            sR = new StreamReader(fileDists);
            int k = -1;
            while (!sR.EndOfStream)
            {
                k++;
                if (k == nStops) break;
                sL = sR.ReadLine();
                arrDist[k] = 1000.0 * Convert.ToDouble(sL); // Переводим км в м
            }
            sR.Close();
            sR = new StreamReader(fileSpeeds);
            k = -1;
            double kSpeed2 = kSpeed * (checkBoxWeekEnd.Checked ? 1.2 : 1.0);
            while (!sR.EndOfStream)
            {
                k++;
                if (k == nStops) break;
                sL = sR.ReadLine();
                arrSpeed[k] = (tactShed && allInitShedAreTact ? kSpeedTact : kSpeed2) * Convert.ToDouble(sL) / 3.6; // Переводим км/ч в м/с
            }
            sR.Close();
            double t;
            for (k = 0; k < nStops; k++)
            {
                t = arrDist[k] / arrSpeed[k];
                arrTMov[k] = Convert.ToInt32(t);
            }
            timeSum = 0; // Суммарное время движения по маршруту без остановок
            for (k = 0; k < nStops; k++) timeSum += arrTMov[k];
            labelTimeSum.Text = textTimeSum + timeSum; // Суммарное время движения по маршруту без остановок, c
        }
        private void genPopulation()
        {
            int t = 0, dt = 0;
            List<int> LShed;
            arrShedules = new List<int>[nShedules];
            arrTactPeak = new int[nShedules];
            arrTactOth = new int[nShedules];
            arrTactOthDay = new int[nShedules];
            if (tactShed && allInitShedAreTact)
            {
                for (int k = 0; k < nShedules; k++)
                {
                    arrTactPeak[k] = rand.Next(tMinPeak, tMaxPeak);
                    arrTactOth[k] = rand.Next(tMinOth, tMaxOth);
                    arrTactOthDay[k] = rand.Next(tMinOthDay, tMaxOthDay);
                }
            }
            for (int k = 0; k < nShedules; k++)
            {
                LShed = new List<int>(); // Список, содержащий текущее расписание
                t = tStart;
                LShed.Add(t);
                while (t < tEnd)
                {
                    if (tactShed)
                        dt = findTact(t, k);
                    else if (improvedShed)
                        dt = find_dt(t);
                    else if (simpleShed)
                        dt = rand.Next(tMinPeak, (int)(1.5 * tMaxOth));
                    t += dt;
                    LShed.Add(Math.Min(t, tEnd));
                }
                arrShedules[k] = LShed;
                if (simpleShed && !diffNumberOfRoots)
                    break;
                else if (tactShed && !allInitShedAreTact)
                {
                    tactShed = false; // Только первое расписание является тактовым
                    improvedShed = true; // Остальные генерируются по схеме улучшенного расписания
                }
            }
            // Генерация популяции на основе первого расписания
            if (simpleShed && !diffNumberOfRoots)
            {
                List<int> LShed0 = arrShedules[0];
                int cnt0 = LShed0.Count - 1, t2, t3;
                for (int k = 1; k < nShedules; k++)
                {
                    LShed = new List<int>(); // Список, содержащий текущее расписание
                    t = tStart;
                    t2 = LShed0[1];
                    LShed.Add(tStart);
                    for (int m = 1; m < cnt0; m++)
                    {
                        t3 = LShed0[m + 1];
                        if (rand.Next(0, 1) > 0.5)
                            dt = -rand.Next(0, t2 - t);
                        else
                            dt = rand.Next(0, t3 - t2);
                        LShed.Add(t + (int)(0.75 * dt));
                        t = t2;
                        t2 = t3;
                    }
                    LShed.Add(tEnd);
                    arrShedules[k] = LShed;
                }
            }
        }
        // Возвращает размер такта в зависимости от периода движения
        private int findTact(int t, int k)
        {
            if (allInitShedAreTact)
            {
                if (t < tPeakMornStart || t > tPeakEvEnd)
                    return arrTactOth[k];
                else if (t > tPeakMornEnd && t < tPeakEvStart)
                    return arrTactOthDay[k];
                else
                    return arrTactPeak[k];
            }
            else
            {
                if (t < tPeakMornStart || t > tPeakEvEnd)
                    return tactOth;
                else if (t > tPeakMornEnd && t < tPeakEvStart)
                    return tactOthDay;
                else
                    return tactPeak;
            }
        }
        // Возвращает интервал между рейсам в зависимости от периода движения
        private int find_dt(int t)
        {
            if (t < tPeakMornStart || t > tPeakEvEnd)
                return rand.Next(tMinOth, tMaxOth);
            else if (t > tPeakMornEnd && t < tPeakEvStart)
                return rand.Next(tMinOthDay, tMaxOthDay);
            else
                return rand.Next(tMinPeak, tMaxPeak);
        }
        // Возвращает минимально допустимый интервал мажду рейсами в зависимости от типа расписания и периода движения
        private int findTMin(int t)
        {
            if (simpleShed) return (tMinPeak + tMinOth) / 2;
            if (t < tPeakMornStart || t > tPeakEvEnd)
                return tMinOth;
            else if (t > tPeakMornEnd && t < tPeakEvStart)
                return tMinOthDay;
            else
                return tMinPeak;
        }
        // Возвращает максимально допустимый интервал мажду рейсами в зависимости от типа расписания и периода движения
        private int findTMax(int t)
        {
            if (simpleShed) return (tMaxPeak + tMaxOth) / 2; // tMaxOth;
            if (t < tPeakMornStart || t > tPeakEvEnd)
                return tMaxOth;
            else if (t > tPeakMornEnd && t < tPeakEvStart)
                return tMaxOthDay;
            else
                return tMaxPeak;
        }
        private int calcTimeOnStop(int nP)
        {
            int tInOne = rand.Next(tInOneMin, tInOneMax); // // Время посадки одного пассажира, с
            int tOnStop = nP * tInOne; // Сокращаем время посадки при отсутствии турникета
            tOnStop = turnstile ? tOnStop : (int)((kOut * tOnStop) / nDoors);
            return Math.Max(tOnStop, tOnStopMin);
        }
        // Симуляция расписания
        private int simShed(List<int> LShed)
        {
            int tBT; // Время между рейсами
            int tPrev; // Время предшествующего трамвая рассматриваемого рейса
            int tCur; // Время текущего трамвая рассматриваемого рейса
            int tWaitShed = 0; // Суммарное среднее время ожидания расписания, с
            int nPRout; // Общее число пассажиров, перевезенных одним рейсом
            int timeRout; // Суммарное время посадки в трамвай одного рейса, с
            int nP; // Число пассажиров на остановке (все входят в трамвай)
            int rout = -1;
            int tOnStop; // Время пребывания трамвая на остановке
            int tMin; // Минимально допустимое время между рейсами
            nPAll = 0; // Общее число перевезенных пассажиров всеми рейсами расписания
            timeInAll = 0; // Суммарное время посадки на трамваи расписания
            foreach (int tSR in LShed) // tSR - начало движения рейса (время рейса)
            {
                nPRout = 0; // Общее число пассажиров, перевезенных одним рейсом
                timeRout = 0; // Суммарное время посадки в трамвай одного рейса
                tCur = tSR;
                rout++;
                if (rout == 0) // Первый рейс расписания
                {
                    tPrev = tSR;
                    for (int k = 0; k < nStops; k++)
                    { // Время прибытия на остановку (добавляем к текущему времени время движения между остановками)
                        tCur += arrTMov[k];
                        arrTCur[k] = tCur;
                        nP = findNOfPas(k, tPrev, tCur); // Число пассажиров, ожидающих трамвай
                        tPrev = tCur;
                        tOnStop = calcTimeOnStop(nP);
                        tCur += tOnStop; // Увеличиваем текущее время и получаем время отправления трамвая с остановки
                        timeRout += tOnStop;
                        nPRout += nP;
                    }
                }
                else // Прочие рейсы расписания
                {
                    for (int k = 0; k < nStops; k++)
                    {
                        tCur += arrTMov[k]; // Время прибытия на остановку текущего рейса
                        tPrev = arrTPrev[k]; // Время прибытия на остановку прежнего рейса
                        tBT = tCur - tPrev; // Время между соседними рейсами
                        tMin = findTMin(tCur); // Минимально допустимое время между рейсами
                        if (tBT < 0) tCur = tPrev + tMin;
                        arrTCur[k] = tCur;
                        nP = findNOfPas(k, tPrev, tCur);
                        if (nP < 0) nP = 1;
                        tOnStop = calcTimeOnStop(nP);
                        tCur += tOnStop; // Увеличиваем текущее время и получаем время отправления трамвая с остановки
                        timeRout += tOnStop;
                        tWaitShed += nP * (tBT + tOnStop) / 2; // Увеличиваем время ожидания текущего рейса на время ожидания на текущей остановке
                        nPRout += nP;
                    }
                }
                nPAll += nPRout;
                timeInAll += timeRout;
                for (int k = 0; k < nStops; k++) arrTPrev[k] = arrTCur[k];
            }
            timeEnd = arrTCur[nStops - 1]; // Время прибытия последнего рейса на последнюю остановку (глобальная переменная)
            tWaitShed = tWaitShed / nPAll + (this.radioButtonTwoCriteria.Checked ? LShed.Count : 0);
            return tWaitShed; // Среднее время ожидания + число рейсов
        }
        private void readDiags() // Читает диаграммы прихода пасссажиров
        {
            int k, k2 = -1;
            double pCor = checkBoxWeekEnd.Checked ? pasCor / (double)nDoors : pasCor, nPs;
            string dir = (checkBoxWeekEnd.Checked ? "Выходные/" : "Будни/");
            arrDiags = new int[nStops, N]; // Массив диаграмм прихода; N - число интервалов диаграммы прихода
            nPasByDiags = 0;
            for (k = 0; k < nStops; k++)
            {
                sR = new StreamReader(dir + fileStop + k + ".txt");
                k2 = -1;
                while (!sR.EndOfStream)
                {
                    k2++;
                    nPs = pCor * Convert.ToInt32(sR.ReadLine());
                    arrDiags[k, k2] = (int)nPs;
                    nPasByDiags += (int)nPs;
                }
            }
            labelNPas.Text = textNPasByDiags + nPasByDiags;
        }
        // k - номер остановки; tPrev, tCur - соответственно время предшествующего и текущего рейсов
        private int findNOfPas(int k, int tPrev, int tCur)
        {
            // k - номер остановки; N - число интервалов диаграммы прихода
            int tCur2, nP; // Правая граница времени и число пассажиров на остановке
            // Время может быть в одном из трех интервалов: утреннем, вечернем или прочем
            // Добавки dtPeak и dtOth введены для учета подхода пассажиров во время посадки
            if (tCur >= tPeakMornStart && tCur <= tPeakMornEnd || tCur >= tPeakEvStart && tCur <= tPeakEvEnd)
                tCur2 = tCur + (turnstile ? dtPeak : dtPeak / 10);
            else
                tCur2 = tCur + (turnstile ? dtOth : dtOth / 10);
            int kT = (tCur2 - tStart) / intLen; // Номер интервала диаграмы прихода, на котором лежит tCur2
            if (kT > N - 1) return -1; // Плохой рейс
            int nPDiag = arrDiags[k, kT]; // Число пассажиров по диаграмме на интервале kT
            int kP = (tPrev - tStart) / intLen; // Номер интервала диаграмы прихода, на котором лежит tPrev
            if (kP == kT) // nPasByDiags - число пассажиров, перевозимых по диаграмме прихода (нужно перевести пассажиров)
            {
                nP = (int)Math.Round(1.0 * nPDiag * (tCur2 - tPrev) / (1.0 * intLen) + nPAdd);
            }
            else
            {
                int tDiag = tStart + kT * intLen; // Начало текущего интервала диаграммы
                int tDiagP = tStart + (kP + 1) * intLen; // Конец предшествующего интервала диаграммы
                int t = tPrev;
                int kC = kP;
                nP = 0;
                while (tDiagP <= tDiag)
                {
                    nP += (int)Math.Round(1.0 * arrDiags[k, kC] * (tDiagP - t) / (1.0 * intLen) + nPAdd);
                    kC++;
                    t = tDiagP;
                    tDiagP += intLen;
                }
                nP += (int)Math.Round(1.0 * nPDiag * (tCur2 - tDiag) / (1.0 * intLen) + nPAdd);
            }
            return nP;
            //return Math.Max(nP, 1);
        }
        // Первая корректировка расписания; устраняем нарушение ограничения tMin
        private void corrShed(List<int> LShed)
        {
            int tSR, tSR2, nR = LShed.Count - 2, tMin; // Не трогаем последний рейс
            bool isCorr = true;
            while (isCorr)
            {
                isCorr = false;
                for (int k = 0; k < nR; k++)
                {
                    tSR = LShed[k];
                    tSR2 = LShed[k + 1];
                    tMin = findTMin(tSR2);
                    if (tSR2 - tSR < tMin)
                    {
                        LShed[k + 1] = tSR + tMin; // tMin - минимально допустимое время между рейсами
                        isCorr = true;
                    }
                }
            }
        }
        // Вторая корректировка расписания; сокращаем число рейсов за счет их разрежения
        private void corrShed2(List<int> LShed)
        {
            int tSR, nR, nDelMax = 15, nDel = 0, tMax;
            bool isDel = true;
            while (isDel && nDel < nDelMax)
            {
                isDel = false;
                nR = LShed.Count - 2;
                for (int k = 0; k < nR; k++)
                {
                    tSR = LShed[k];
                    tMax = findTMax(tSR);
                    if (LShed[k + 2] - tSR < 0.5 * tMax)
                    {
                        tSR = LShed[k + 1];
                        LShed.RemoveAt(k + 1); // Сокращаем число рейсов за счет разрежения рейсов
                        if (checkShed(LShed, false) > 0)
                            LShed.Insert(k + 1, tSR);
                        else
                        {
                            isDel = true;
                            nDel++;
                            break;
                        }
                    }
                }
            }
        }
        // Третья корректировка расписания; устраняем нарушение tMax
        private void corrShed3(List<int> LShed)
        {
            int tSR, tSR2, nInsMax = 50, nIns = 0, tMax, nR = LShed.Count - 3; // Время последнего рейса не меняем
            bool isCorr = true, isIns = true;
            while (isCorr)
            {
                isCorr = false;
                for (int k = 0; k < nR; k++)
                {
                    tSR = LShed[k];
                    tSR2 = LShed[k + 1];
                    tMax = findTMax(tSR2);
                    if (tSR2 - tSR > tMax) // tMax - максимально допустимый интервал между соседними рейсами
                    {
                        LShed[k + 1] = tSR + tMax;
                        isCorr = true;
                    }
                }
            }
            // Контроль последнего интервала
            while (isIns && nIns < nInsMax)
            {
                isIns = false;
                tSR = LShed[nR];
                if (LShed[nR + 1] - tSR > (simpleShed ? (tMaxPeak + tMaxOth) / 2 : tMaxOth)) // tMaxOth - максимально допустимый интервал между рейсами утром и вечером до и после часов пик
                {
                    LShed.Insert(nR + 1, tSR + 3 * (simpleShed ? (tMaxPeak + tMaxOth) / 2 : tMaxOth) / 4); // Вставляем рейс
                    nIns++;
                    isIns = true;
                }
                nR++;
            }
        }
        private int checkShed(List<int> LShed, bool writeToFile) // Проверка расписания
        {
            int nLess = 0, nMore = 0, nR = LShed.Count - 2;
            int errtMin = int.MinValue, errtMax = int.MinValue;
            int kMin = 0, kMax = 0, tMin, tMax, dt, tSR, tSR2;
            for (int k = 0; k < nR; k++)
            {
                tSR = LShed[k];
                tSR2 = LShed[k + 1];
                tMin = findTMin(tSR2);
                tMax = findTMax(tSR2);
                dt = tSR2 - tSR;
                if (dt < tMin)
                {
                    nLess++;
                    if (tMin - dt > errtMin)
                    {
                        kMin = k + 1;
                        errtMin = tMin - dt;
                    }
                }
                if (dt > tMax)
                {
                    nMore++;
                    if (dt - tMax > errtMax)
                    {
                        kMax = k + 1;
                        errtMax = dt - tMax;
                    }
                }
            }
            if (writeToFile)
            {
                if (nLess > 0)
                {
                    sW.WriteLine("Число нарушений нижнего интервала: " + nLess);
                    sW.WriteLine("Величина наибольшего нарушения, с: " + errtMin + ". Рейс: " + (kMin + 1));
                }
                if (nMore > 0)
                {
                    sW.WriteLine("Число нарушений верхнего интервала: " + nMore);
                    sW.WriteLine("Величина наибольшего нарушения, с: " + errtMax + ". Рейс: " + (kMax + 1));
                }
            }
            return nLess + nMore;
        }
        // Скрещивание пар отобранных расписаний
        private bool crossing()
        {
            string shed, shedS2, shedB, shedW;
            int nShed, nShed2, nShedB, nShedW, m, nR, tSR, nR2, tWaitShedC;
            List<int> LShed, LShed2, LShedC;
            shedB = arrWaitTimeShed[0]; // Лучшее расписание
            nShedB = Convert.ToInt32(shedB.Substring(4));
            // nCrossings - допустимое число попыток скрещивания в одной итерации с целью улучшения популяции
            for (int k = 0; k < nCrossings - 1; k++)
            {
                shed = arrWaitTimeShed[k];
                nShed = Convert.ToInt32(shed.Substring(4));
                LShed = arrShedules[nShed];
                nR = LShed.Count;
                for (int k2 = 1; k2 < nShedules; k2++)
                {
                    shedS2 = arrWaitTimeShed[k2];
                    nShed2 = Convert.ToInt32(shedS2.Substring(4));
                    LShed2 = arrShedules[nShed2];
                    nR2 = LShed2.Count;
                    if (onlyEqualSheds && nR != nR2) continue;
                    LShedC = new List<int>(); // Результат скрещивания
                    for (m = 0; m < nR; m++) LShedC.Add(LShed[m]);
                    for (m = 1; m < nR; m++)
                    {
                        tSR = LShed[m]; // tSR - начало движения рейса
                        if (m < nR2) LShedC[m] = (tSR + LShed2[m]) / 2;
                        if (checkShed(LShedC, false) > 0) LShedC[m] = tSR;
                    }
                    LShedC[nR - 1] = tEnd;
                    corrShed(LShedC); // Устраняем нарушение ограничения tMin
                    corrShed2(LShedC); // Сокращаем число рейсов за счет разрежения рейсов
                    corrShed3(LShedC); // Устраняем нарушение tMax
                    tWaitShedC = simShed(LShedC); // Симуляция расписания
                    if (tWaitShedC < arrWaitTime[nShedB]) // nShedB - номер текущего лучшего расписания
                    {
                        shedW = arrWaitTimeShed[nShedules - 1]; // Худшее расписание
                        nShedW = Convert.ToInt32(shedW.Substring(4));
                        arrShedules[nShedW] = LShedC;
                        arrWaitTime[nShedW] = tWaitShedC;
                        arrNPAll[nShedW] = nPAll;
                        arrTimeInAll[nShedW] = timeInAll;
                        arrTimeEnd[nShedW] = timeEnd; // Время отправления последнего рейса с последней остановки (глобальная переменная)
                        return true;
                    }
                }
            }
            return false;
        }
        private void sortSheds()
        {
            for (int k = 0; k < nShedules; k++) arrWaitTimeShed[k] = "" + arrWaitTime[k] + "-" + k;
            Array.Sort(arrWaitTimeShed);
        }
        // Находит время ожидания для вывода на экран и файл
        private string findTWaitShed(int tWR, int nR)
        {
            int tW = (radioButtonTwoCriteria.Checked ? tWR - nR : tWR);
            return "" + tW + " / " + nR + ". Время ожидания + число рейсов: " + (tW + nR);
        }
        private void mutation(int nShed) // Мутация расписания
        {
            List<int> LShed; // Текущее расписание
            LShed = arrShedules[nShed];
            // Получаем случайное число k от pDI до pDI2
            // Получаем случайное число k2 от 0 до 10
            // Если k2 < rDecr, то уменьшаем число рейсов текущего лучшего расписания на k%,
            // в противном случае увеличиваем число рейсов на те же k%
            int k = rand.Next(pDI, pDI2);
            int k2 = rand.Next(0, 10);
            int nR = LShed.Count - 1; // Число рейсов
            int dt, dt2, rToDel = 0, rToIns = 0, tSR;
            if (k2 < rDecr) // Удаляем рейсы
            {
                for (int i = 0; i < k; i++)
                {
                    // Находим рейс вне часов пик, для которого tSubs - tPrev минимально, где
                    // tPrev - время предшествующего рейса
                    // tSubs - время последующего рейса (subsequent)
                    dt = int.MaxValue;
                    for (int j = 1; j < nR; j++)
                    {
                        tSR = LShed[j];
                        if (tSR < tPeakMornStart || tSR > tPeakMornEnd && tSR < tPeakEvStart || tSR > tPeakEvEnd) // Время рейса вне часов пик
                        {
                            dt2 = LShed[j + 1] - LShed[j - 1]; // tSubs - tPrev
                            if (dt2 < dt)
                            {
                                rToDel = j;
                                dt = dt2;
                            }
                        }
                    }
                    tSR = LShed[rToDel];
                    LShed.RemoveAt(rToDel);
                    if (checkShed(LShed, false) > 0)
                        LShed.Insert(rToDel, tSR);
                    else
                        nR--;
                }
            }
            else // Добаляем рейсы
            {
                for (int i = 0; i < k; i++)
                {
                    // Находим рейс вне часов пик, для которого tSubs - tSR максимально, где
                    // tSR - время текущего рейса
                    // tSubs - время последующего рейса (subsequent)
                    dt = int.MinValue;
                    for (int j = 1; j < nR; j++)
                    {
                        tSR = LShed[j];
                        if (tSR < tPeakMornStart || tSR > tPeakMornEnd && tSR < tPeakEvStart || tSR > tPeakEvEnd) // Время рейса вне часов пик
                        {
                            dt2 = LShed[j + 1] - tSR; // tSubs - tSR
                            if (dt2 > dt)
                            {
                                rToIns = j;
                                dt = dt2;
                            }
                        }
                    }
                    LShed.Insert(rToIns, (LShed[rToIns - 1] + LShed[rToIns]) / 2);
                    nR++;
                }
            }
        }
        private void writeResult(List<int> LShed, StreamWriter sW)
        {
            int nV = checkShed(LShed, true); // Число нарушений в расписании LShed
            labelNViolations.Text = textNViolations + nV;
            sW.WriteLine("Расписание:");
            int m = 0, tPrev = LShed[0], tMin, tMax, dt;
            string add = "", sPeak = ". Часы пик";
            foreach (int tSR in LShed)
            {
                tMin = findTMin(tSR);
                tMax = findTMax(tSR);
                if (m > 1)
                {
                    dt = tSR - tPrev;
                    if (dt > tMax)
                        add = " dt > tMax на " + (dt - tMax) + "; dt = " + dt + "; tMax = " + tMax;
                    else if (dt < tMin)
                        add = " dt < tMin на " + (tMin - dt) + "; dt = " + dt + "; tMin = " + tMin;
                    else
                        add = "";
                }
                m++;
                sW.WriteLine("" + tSR + " - " + m + add + (tSR > tPeakMornStart && tSR < tPeakMornEnd || tSR > tPeakEvStart && tSR < tPeakEvEnd ? sPeak : ""));
                tPrev = tSR;
            }
            sW.Close();
        }
        private void putWaitTime(string fileNm, string s)
        {
            int nShed, tW, nR;
            List<int> LShed;
            sW = new StreamWriter(fileNm);
            sW.WriteLine("Время ожидания и число рейсов " + s);
            for (int k = 0; k < nShedules; k++)
            {
                nShed = Convert.ToInt32(arrWaitTimeShed[k].Substring(4));
                tW = arrWaitTime[nShed];
                LShed = arrShedules[nShed];
                nR = LShed.Count;
                sW.WriteLine("" + (radioButtonTwoCriteria.Checked ? tW - nR : tW) + "/" + LShed.Count + "; число нарушений: " + checkShed(LShed, false));
            }
            sW.Close();
        }
        private void buttonGo_Click(object sender, EventArgs e)
        {
            List<int> LShed, LShedInitBest; // Текущее и лучшее начальное расписания
            int nCross, nShed = 0, nRInitBest, tWInitBest, timeInAllInitBest, timeEndInitBest, nPAllInitBest, nR, seed, tW;
            string routsN = ""; // Строка с временем ожидания и числа рейсов расписаний начальной популяции
            boolValues();
            seed = (int)numericUpDownSeed.Value;
            rand = new Random(seed); // Датчик случайных чисел с затравкой seed
            // Инициализация
            arrWaitTime = new int[nShedules];
            arrNPAll = new int[nShedules];
            arrTimeInAll = new int[nShedules];
            arrTimeEnd = new int[nShedules];
            genPopulation(); // Генерация начальной популяциии расписаний
            for (nShed = 0; nShed < nShedules; nShed++) // Симуляция начальной популяции
            {
                LShed = arrShedules[nShed]; // Текущее расписание
                arrWaitTime[nShed] = simShed(LShed); // Симуляция расписания; минимизируем число рейсов и/или среднее время ожидания
                arrNPAll[nShed] = nPAll;
                arrTimeInAll[nShed] = timeInAll;
                arrTimeEnd[nShed] = timeEnd; // Время отправления последнего рейса с последней остановки (глобальная переменная)
                if (nShed == 0) labelNPAll.Text = textNPAll + nPAll;
            }
            arrWaitTimeShed = new string[nShedules];
            sortSheds();
            for (int k = 0; k < nShedules; k++) // Симуляция начальной популяции
            {
                nShed = Convert.ToInt32(arrWaitTimeShed[k].Substring(4));
                tW = arrWaitTime[nShed];
                nR = arrShedules[nShed].Count; // Число рейсов в расписании
                routsN = routsN + (radioButtonTwoCriteria.Checked ? tW - nR : tW) + "/" + nR + "; ";
            }
            labelShedRoutsN.Text = textShedRoutsN + routsN;
            bool rbt = radioButtonTactShed.Checked && !allInitShedAreTact;
            nShedInitBest = rbt ? 0 : Convert.ToInt32(arrWaitTimeShed[0].Substring(4));
            LShedInitBest = arrShedules[nShedInitBest];
            nRInitBest = LShedInitBest.Count;
            nPAllInitBest = arrNPAll[nShedInitBest];
            tWInitBest = arrWaitTime[nShedInitBest];
            timeInAllInitBest = arrTimeInAll[nShedInitBest]; // Суммарное время посадки лучшего начального расписания
            timeEndInitBest = arrTimeEnd[nShedInitBest]; // Время прибытия последнего рейса на конечную остановку лучшего начального расписания
            labelShedBest0.Text = (rbt ? textShed0Tact : textShed0) + findTWaitShed(tWInitBest, nRInitBest);
            labelTimeInAll0.Text = (rbt ? textShed0Tact : textShed0) + timeInAllInitBest;
            labelTimeEnd0.Text = (rbt ? textShed0Tact : textShed0) + timeEndInitBest;
            putWaitTime(fileWaitTime, "начальных расписаний");
            sW = new StreamWriter(fileBestShedI);
            sW.WriteLine("Начальная популяция: " + (radioButtonTactShed.Checked ? "на базе тактового" : (simpleShed ? "простая" : "улучшенная")));
            sW.WriteLine("Движение " + (checkBoxTurnstile.Checked ? "с турникетом" : "без турникета"));
            sW.WriteLine("Лучшее начальное расписание:");
            sW.WriteLine(" - среднее время ожидания: " + findTWaitShed(tWInitBest, nRInitBest));
            sW.WriteLine(" - число рейсов: " + nRInitBest);
            writeResult(LShedInitBest, sW);
            sW.Close();
            // Оптимизация
            int nRestruct = 0;
            nCrossAll = 0;
            if (doOpt)
            {
                if (checkBoxRestruct.Checked && diffNumberOfRoots)
                {
                    while (nRestruct < nRestructMax)
                    {
                        nRestruct++;
                        for (int k = 1; k < nCrossings; k++)
                        {
                            nShed = Convert.ToInt32(arrWaitTimeShed[1].Substring(4)); // Второе по качеству расписание
                            mutation(nShed);
                            LShed = arrShedules[nShed]; // Текущее расписание
                            arrWaitTime[nShed] = simShed(LShed); // Симуляция расписания после мутации
                            arrNPAll[nShed] = nPAll;
                            arrTimeInAll[nShed] = timeInAll;
                            arrTimeEnd[nShed] = timeEnd; // Время отправления последнего рейса с последней остановки (глобальная переменная)
                        }
                        sortSheds();
                        nCross = 0; // Число скрещиваний после мутации
                        while (crossing() && nCross < 10 * nCrossMax) // Скрещивание лучших расписаний
                        {
                            nCross++;
                            nCrossAll++;
                            sortSheds();
                        }
                    }
                }
                else
                {
                    while (crossing() && nCrossAll < nCrossMax) // Скрещивание лучших расписаний
                    {
                        nCrossAll++;
                        sortSheds();
                    }
                }
                putWaitTime(fileWaitTimeOpt, "оптимизированных расписаний");
            }
            nShed = Convert.ToInt32(arrWaitTimeShed[0].Substring(4)); // Лучшее расписание
            LShed = arrShedules[nShed]; // Лучшее расписание
            nR = LShed.Count;
            nRestruct = (checkBoxRestruct.Checked && diffNumberOfRoots ? nRestructMax : 0); // Число мутаций
            labelShedBestC.Text = textShedC + findTWaitShed(arrWaitTime[nShed], nR);
            labelTimeInAllC.Text = textShedC + arrTimeInAll[nShed];
            labelTimeEndC.Text = textShedC + arrTimeEnd[nShed];
            labelNCross.Text = textNCross + nCrossAll;
            labelNRestruct.Text = textNRestruct + nRestruct;
            sW = new StreamWriter(fileBestShed);
            sW.WriteLine("Начальная популяция: " + (radioButtonTactShed.Checked ? "на базе тактового" : (simpleShed ? "простая" : "улучшенная")));
            sW.WriteLine("Движение " + (checkBoxTurnstile.Checked ? "с турникетом" : "без турникета"));
            sW.WriteLine("Число скрещиваний: " + nCrossAll);
            sW.WriteLine("Число мутаций: " + nRestruct);
            sW.WriteLine("Среднее время ожидания:");
            sW.WriteLine("- лучшего начального расписания: " + findTWaitShed(tWInitBest, nRInitBest));
            sW.WriteLine("- лучшего расписания: " + findTWaitShed(arrWaitTime[nShed], nR));
            sW.WriteLine("Число рейсов:");
            sW.WriteLine("- лучшего начального расписания: " + nRInitBest);
            sW.WriteLine("- лучшего расписания: " + nR);
            sW.WriteLine("Нужно перевезти пассажиров: " + nPasByDiags);
            sW.WriteLine("Перевезено пассажиров:");
            sW.WriteLine("- лучшим начальным расписанием: " + nPAllInitBest);
            sW.WriteLine("- лучшим расписанием: " + arrNPAll[nShed]);
            sW.WriteLine("Суммарное время посадки: ");
            sW.WriteLine("- лучшго начального расписания: " + timeInAllInitBest);
            sW.WriteLine("- лучшего расписания: " + arrTimeInAll[nShed]);
            sW.WriteLine("Время прибытия последнего рейса на последнюю остановку:");
            sW.WriteLine("- лучшего начального расписания: " + timeEndInitBest);
            sW.WriteLine("- лучшего расписания: " + arrTimeEnd[nShed]);
            sW.WriteLine("Время завершения последнего интервала: " + tLastIntEnd);
            writeResult(LShed, sW);
        }
        private void boolValues()
        {
            tactShed = radioButtonTactShed.Checked; // Если true, то генерируются тактовые начальные расписания (такты задаются с учетом часов пик)
            improvedShed = radioButtonImprovedShed.Checked; // Если true, то генерируется улучшенное расписание (интервалы задаются с учетом часов пик)
            simpleShed = radioButtonSimpleShed.Checked; // Если true, то генерируется простое расписание (интервалы задаются в диапазоне tMinPeak, tMaxOth)
            turnstile = checkBoxTurnstile.Checked;
            doOpt = checkBoxDoOpt.Checked; // Если false то вывод лучшего расписания начальной популяции (отмена оптимизации)
            nShedules = Convert.ToInt32(numericUpDownNShedules.Value); // Число расписаний в популяции (размер популяции)
            nCrossings = 10; // Допустимое число попыток скрещивания в одной итерации с целью улучшения популяции
            labelShedBest0.Text = tactShed ? textShed0Tact : textShed0;
            labelTimeInAll0.Text = tactShed ? textShed0Tact : textShed0;
            labelTimeEnd0.Text = tactShed ? textShed0Tact : textShed0;
        }
        private void buttonChange_Click(object sender, EventArgs e)
        {
            List<int> LShed = new List<int>(); // Расписание
            sR = new StreamReader(fileBestShed);
            int k, nR, tW, nR0 = 0;
            string s = "";
            rand = new Random(); // Датчик случайных чисел с затравкой seed
            boolValues();
            for (k = 0; k < 50; k++)
            {
                if (sR.EndOfStream)
                {
                    MessageBox.Show("Плохой файл " + fileBestShed);
                    return;
                }
                if (sR.ReadLine() == "Расписание:") break;
            }
            while (!sR.EndOfStream)
            {
                s = sR.ReadLine();
                LShed.Add(Convert.ToInt32(s.Substring(0, 5)));
                nR0++;
            }
            sR.Close();
            corrShed(LShed); // Устраняем нарушение ограничения tMin
            corrShed2(LShed); // Сокращаем число рейсов за счет разрежения рейсов
            corrShed3(LShed); // Устраняем нарушение tMax
            tW = simShed(LShed); // Среднее время ожидания расписания
            nR = LShed.Count;
            sW = new StreamWriter(fileBestShedC);
            sW.WriteLine("После правки:");
            sW.WriteLine(" - перевезено пассажиров: " + nPAll);
            sW.WriteLine(" - среднее время ожидания: " + findTWaitShed(tW, nR));
            sW.WriteLine(" - число рейсов: " + nR);
            sW.WriteLine("Число рейсов до правки: " + nR0);
            writeResult(LShed, sW);
            sW.Close();
            labelNPas.Text = textNPasByDiags + nPasByDiags;
            labelNPAll.Text = textNPAll + nPAll;
            labelShedBestC.Text = textShedC + findTWaitShed(tW, nR);
            labelTimeInAllC.Text = textShedC + timeInAll;
            labelTimeEndC.Text = textShedC + timeEnd;
            labelShedRoutsN.Text = textShedRoutsN + nR;
        }
        private void radioButtonTactShed_CheckedChanged(object sender, EventArgs e)
        {
            boolValues();
            readDistsSpeeds();
        }
        private void buttonClose_Click(object sender, EventArgs e)
        {
            Close();
        }
        private double F(double[] X, int NP, int i) // Функциия составления и симуляции расписания
        {
            double t = tStart, dt = 0;
            LShedD = new List<double>();
            LShedD.Add(t);
            while (t < tEnd)
            {
                if (NP == 2)
                {
                    if (t < tPeakMornStart || t > tPeakEvEnd || t > tPeakMornEnd && t < tPeakEvStart)
                        dt = X[0]; // Такт для прочих часов
                    else
                        dt = X[1]; // Такт для часов пик
                }
                else if (NP == 3)
                {
                    if (t < tPeakMornStart || t > tPeakEvEnd)
                        dt = X[0]; // Такт до утренних и после вечерних часов пик
                    else if (t > tPeakMornEnd && t < tPeakEvStart)
                        dt = X[2]; // Такт для дневных непиковых часов
                    else
                        dt = X[1]; // Такт для часов пик
                }
                else if (NP == 4)
                {
                    if (t < tPeakMornStart || t > tPeakEvEnd)
                        dt = X[0]; // Такт до утренних и после вечерних часов пик
                    else if (t > tPeakMornEnd && t <= tPeakEvStart)
                        dt = X[2]; // Такт для дневных непиковых часов
                    else if (t <= tPeakMornEnd)
                        dt = X[1]; // Такт для утренних часов пик
                    else
                        dt = X[3]; // Такт для вечерних часов пик
                }
                else if (NP == 5)
                {
                    if (t < tPeakMornStart)
                        dt = X[0]; // Такт до утренних часов пик
                    else if (t > tPeakMornEnd && t <= tPeakEvStart)
                        dt = X[2]; // Такт для дневных непиковых часов
                    else if (t > tPeakEvEnd)
                        dt = X[4]; // Такт для вечерних непиковых часов
                    else if (t <= tPeakMornEnd)
                        dt = X[1]; // Такт для утренних часов пик
                    else
                        dt = X[3]; // Такт для вечерних часов пик
                }
                t += dt;
                LShedD.Add(Math.Min(t, tEnd));
            }
            double C = simShedD(LShedD);
            NR[i] = LShedD.Count;
            TW[i] = C - NR[i];
            return C;
        }
        // Создает из точки X регулярный симплекс с длиной ребра L и с NP + 1 вершиной
        // Формирует массив FN значений оптимизируемой функции F в вершинах симплекса
        private void makeSimplex(double[] X, double L, int NP, bool first)
        {
            double qn, q2, r1, r2;
            int i, j;
            qn = Math.Sqrt(1.0 + NP) - 1.0;
            q2 = L / Math.Sqrt(2.0) * (double)NP;
            r1 = q2 * (qn + (double)NP);
            r2 = q2 * qn;
            for (i = 0; i < NP; i++) simplex[i, 0] = X[i];
            for (i = 1; i < NP + 1; i++)
                for (j = 0; j < NP; j++)
                    simplex[j, i] = X[j] + r2;
            for (i = 1; i < NP + 1; i++) simplex[i - 1, i] = simplex[i - 1, i] - r2 + r1;
            for (i = 0; i < NP + 1; i++)
            {
                for (j = 0; j < NP; j++) X[j] = simplex[j, i];
                //sW.WriteLine("Вершины начального симплекса:");
                //for (j = 0; j < NP; j++) sW.WriteLine(X[j]);
                FN[i] = F(X, NP, i); // Значения функции в вершинах начального симплекса
            }
            if (first)
            {
                sW.WriteLine("Значения функции в вершинах начального симплекса:");
                for (i = 0; i < NP + 1; i++) sW.WriteLine("" + FN[i] + " = (" + TW[i] + " + " + NR[i] + ")");
                sW.WriteLine("Значения времени ожидания в вершинах начального симплекса:");
                for (i = 0; i < NP + 1; i++) sW.WriteLine(TW[i]);
                sW.WriteLine("Значения числа рейсов в вершинах начального симплекса:");
                for (i = 0; i < NP + 1; i++) sW.WriteLine(NR[i]);
            }
        }
        private double[] center_of_gravity(int k, int NP) // Центр тяжести симплекса
        {
            int i, j;
            double s;
            double[] xc = new double[NP];
            for (i = 0; i < NP; i++)
            {
                s = 0;
                for (j = 0; j < NP + 1; j++) s += simplex[i, j];
                xc[i] = s;
            }
            for (i = 0; i < NP; i++) xc[i] = (xc[i] - simplex[i, k]) / (double)NP;
            return xc;
        }
        private void reflection(int k, double cR, int NP) // Отражение вершины с номером k относительно центра тяжести
        {
            double[] xc = center_of_gravity(k, NP); // cR – коэффициент отражения
            for (int i = 0; i < NP; i++) simplex[i, k] = (1.0 + cR) * xc[i] - simplex[i, k];
            // Контроль ограничения
            double s = 0.75 * tMinPeak;
            for (int i = 0; i < NP; i++) if (simplex[i, k] < s) simplex[i, k] = s;
            s = 1.01 * tMaxOth;
            for (int i = 0; i < NP; i++) if (simplex[i, k] > s) simplex[i, k] = s;
        }
        private void reduction(int k, double gamma, int NP) // Редукция симплекса к вершине k
        {
            int i, j; // gamma – коэффициент редукции
            double[] xk = new double[NP];
            for (i = 0; i < NP; i++) xk[i] = simplex[i, k];
            for (j = 0; j < NP; j++)
                for (i = 0; i < NP; i++)
                    simplex[i, j] = xk[i] + gamma * (simplex[i, j] - xk[i]);
            for (i = 0; i < NP; i++) simplex[i, k] = xk[i]; // Восстанавливаем симплекс в вершине k
            // Контроль ограничения
            double s = 0.75 * tMinPeak;
            for (j = 0; j < NP; j++)
                for (i = 0; i < NP; i++)
                    if (simplex[i, j] < s) simplex[i, j] = s;
        }
        private void shrinking_expansion(int k, double alpha_beta, int NP) // Сжатие/растяжение симплекса. alpha_beta – коэффициент растяжения/сжатия
        {
            double[] xc = center_of_gravity(k, NP);
            for (int i = 0; i < NP; i++)
                simplex[i, k] = xc[i] + alpha_beta * (simplex[i, k] - xc[i]);
            double s;
            // Контроль ограничения
            if (alpha_beta < 1)
            {
                s = 0.75 * tMinPeak;
                for (int j = 0; j < NP; j++)
                    for (int i = 0; i < NP; i++)
                        if (simplex[i, j] < s) simplex[i, j] = s;
            }
            else
            {
                s = 1.01 * tMaxOth;
                for (int j = 0; j < NP; j++)
                    for (int i = 0; i < NP; i++)
                        if (simplex[i, j] > s) simplex[i, j] = s;
            }
        }
        private double findL(double[] X2, int NP) // Длиина ребра симплекса
        {
            double L = 0;
            for (int i = 0; i < NP; i++) L += X2[i] * X2[i];
            return Math.Sqrt(L);
        }
        private double minval(double[] F, int N1, ref int imi) // Минимальный элемент массива и его индекс
        {
            double fmi = double.MaxValue, f;
            for (int i = 0; i < N1; i++)
            {
                f = F[i];
                if (f < fmi)
                {
                    fmi = f;
                    imi = i;
                }
            }
            return fmi;
        }
        private double maxval(double[] F, int N1, ref int ima) // Максимальный элемент массива и его индекс
        {
            double fma = double.MinValue, f;
            for (int i = 0; i < N1; i++)
            {
                f = F[i];
                if (f > fma)
                {
                    fma = f;
                    ima = i;
                }
            }
            return fma;
        }
        private void simplexRestore(int NP) // Восстанавление симплекса
        {
            int i, imi = -1, imi2 = -1;
            double fmi, fmi2 = double.MaxValue, f;
            double[] X = new double[NP], X2 = new double[NP];
            fmi = minval(FN, NP + 1, ref imi);
            for (i = 0; i < NP + 1; i++)
            {
                f = FN[i];
                if (f != fmi && f < fmi2)
                {
                    fmi2 = f;
                    imi2 = i;
                }
            }
            if (imi2 == -1) imi2 = 1 - imi;
            for (i = 0; i < NP; i++)
            {
                X[i] = simplex[i, imi];
                X2[i] = simplex[i, imi] - simplex[i, imi2];
            }
            makeSimplex(X, findL(X2, NP), NP, false);
        }
        private bool notStopYet(double L_thres, int NP) // Возвращает true, если длина хотя бы одного ребра симплекса превышает L_thres, или false - в противном случае
        {
            int i, j, k;
            double[] X = new double[NP], X2 = new double[NP];
            for (i = 0; i < NP; i++)
            {
                for (j = 0; j < NP; j++) X[j] = simplex[j, i];
                for (j = i + 1; j < NP + 1; j++)
                {
                    for (k = 0; k < NP; k++) X2[k] = X[k] - simplex[k, j];
                    if (findL(X2, NP) > L_thres) return true;
                }
            }
            return false;
        }
        // k - номер остановки; tCur - время текущего рейса
        private double findNOfPasD(int k, double T, double tCur, int rout)
        {
            double tCur2, nP; // Текущее время с учетом времени подхода и число пассажиров на остановке
            // Время может быть в одном из трех интервалов: утреннем, вечернем или прочем
            // Добавки dtPeak и dtOth введены для учета подхода пассажиров во время посадки
            if (tCur >= tPeakMornStart && tCur <= tPeakMornEnd || tCur >= tPeakEvStart && tCur <= tPeakEvEnd)
                tCur2 = tCur + (turnstile ? dtPeak : dtPeak / 10.0);
            else
                tCur2 = tCur + (turnstile ? dtOth : dtOth / 10.0);
            // Номер интервала диаграмы прихода, на котором лежит tCur2
            // tStart - время начала движения (первого рейса)
            int kT = (int)((tCur2 - tStart) / (double)intLen);
            if (kT > N - 1) // N - число интервалов диаграммы прихода
            {
                kT = N - 1;
            }
            if (kT < 0)
            {
                kT = 0;
            }
            double nPDiag = arrDiags[k, kT]; // Число пассажиров по диаграмме на интервале kT
            double tPrev = tCur - T;
            // Номер интервала диаграмы прихода, на котором лежит время tPrev прихода предыдущего рейса
            int kP = (int)((tPrev - tStart) / (double)intLen);
            if (kP > kT)
            {
                kP = kT;
            }
            if (kP < 0)
            {
                kP = 0;
            }
            if (kP == kT) // nPasByDiags - число пассажиров, перевозимых по диаграмме прихода (столько пассажиров нужно перевести)
            {
                nP = nPDiag * (tCur2 - tPrev) / (double)intLen;
            }
            else
            {
                double tDiag = tStart + kT * intLen; // Начало текущего интервала диаграммы
                double tDiagP = tStart + (kP + 1) * intLen; // Конец предшествующего интервала диаграммы
                double t = tPrev;
                int kC = kP;
                nP = 0;
                while (tDiagP <= tDiag)
                {
                    nP += (double)arrDiags[k, kC] * (tDiagP - t) / (double)intLen;
                    kC++;
                    t = tDiagP;
                    tDiagP += intLen;
                }
                nP += nPDiag * (tCur2 - tDiag) / (double)intLen;
            }
            return nP;
        }
        // Симуляция расписания
        private double simShedD(List<double> LShedD)
        {
            double tCur = 0; // Время текущего трамвая рассматриваемого рейса
            double tWaitShed = 0; // Суммарное среднее время ожидания расписания, с
            double nPRout; // Общее число пассажиров, перевезенных одним рейсом
            double timeRout; // Суммарное время посадки в трамвай одного рейса, с
            double nP; // Число пассажиров на остановке (все входят в трамвай)
            int rout = -1;
            double tOnStop; // Время пребывания трамвая на остановке
            double T = LShedD[1] - LShedD[0]; // Размер такта; разный для разных рейсов
            nPAllD = 0; // Общее число перевезенных пассажиров всеми рейсами расписания
            timeInAllD = 0; // Суммарное время посадки на трамваи расписания
            int m = -1;
            foreach (double tSR in LShedD) // tSR - начало движения рейса (время рейса)
            {
                m++;
                nPRout = 0; // Общее число пассажиров, перевезенных одним рейсом
                timeRout = 0; // Суммарное время посадки в трамвай одного рейса
                tCur = tSR;
                rout++;
                if (rout == 0) // Первый рейс расписания
                {
                    for (int k = 0; k < nStops; k++)
                    { // Время прибытия на остановку (добавляем к текущему времени время движения между остановками)
                        if (T < tMinPeak)
                        {
                            sW.WriteLine("T < tMinPeak (0)");
                            T = tactOthDay;
                        }
                        tCur += T;
                        nP = findNOfPasD(k, T, tCur, rout); // Число пассажиров, ожидающих трамвай
                        tOnStop = calcTimeOnStopD(nP);
                        timeRout += tOnStop;
                        nPRout += nP;
                        tWaitShed += nP * T / 2.0; // Увеличиваем время ожидания текущего рейса на среднее время ожидания на текущей остановке
                    }
                }
                else // Прочие рейсы расписания
                {
                    T = tSR - LShedD[m - 1];
                    for (int k = 0; k < nStops; k++)
                    {
                        tCur += T; // Время прибытия на остановку текущего рейса
                        if (tCur > tLastIntEnd)
                        {
                            tCur -= T;
                            break;
                        }
                        nP = findNOfPasD(k, T, tCur, rout);
                        if (nP < 0)
                        {
                            sW.WriteLine("nP < 0. k = " + k + ". rout = " + rout);
                            nP = 1;
                        }
                        tOnStop = calcTimeOnStopD(nP);
                        timeRout += tOnStop;
                        tWaitShed += nP * T / 2.0; // Увеличиваем время ожидания текущего рейса на среднее время ожидания на текущей остановке
                        nPRout += nP;
                    }
                }
                nPAllD += nPRout;
                timeInAllD += timeRout;
            }
            timeLastRoutLastStop = (int)tCur;
            if (radioButtonTwoCriteria.Checked)
                tWaitShed = tWaitShed / nPAllD + LShedD.Count;
            else if (radioButtonOnlyNR.Checked)
                tWaitShed = LShedD.Count;
            else
                tWaitShed = tWaitShed / nPAllD;
            return tWaitShed; // Среднее время ожидания + число рейсов, если radioButtonTwoCriteria.Checked = true
        }
        private double calcTimeOnStopD(double nP)
        {
            double tInOne = ((double)tInOneMin + (double)tInOneMax) / 2; // Время посадки одного пассажира, с
            double tOnStop = nP * tInOne;
            tOnStop = turnstile ? tOnStop : kOut * (tOnStop / nDoors); // Сокращаем время посадки при отсутствии турникета
            return Math.Max(tOnStop, tOnStopMin);
        }
        private void checkBoxWeekEnd_CheckedChanged(object sender, EventArgs e)
        {
            readParams();
            readDistsSpeeds(); // Чтение файлов расстояний и средних скоростей между остановками
            readDiags();
        }
        // Выполняет поиск экстремума (минимума) функции F
        private void nelMead(ref double[] X, int NP, double L, double L_thres, double cR, double alpha, double beta, double gamma, int jMx, int kr_todo)
        {
            int i, j2, imi = -1, ima = -1, kr = 0; // kr - число шагов после восстановления симплекса
            int nIt = 0; // Число шагов алгоритма
            double[] X2 = new double[NP], X_R = new double[NP];
            double Fmi, Fma, F_R, F_S, F_E;
            double TW_R, NR_R, TW_S, NR_S, TW_E, NR_E;
            makeSimplex(X, L, NP, true);
            while (notStopYet(L_thres, NP) && nIt < jMx)
            {
                nIt++; // Число итераций
                kr++;
                if (kr == kr_todo)
                {
                    kr = 0;
                    simplexRestore(NP); // Восстановление симплекса
                }
                Fmi = minval(FN, NP + 1, ref imi);
                Fma = maxval(FN, NP + 1, ref ima); // ima - Номер отражаемой вершины
                for (i = 0; i < NP; i++) X[i] = simplex[i, ima];
                reflection(ima, cR, NP); // Отражение
                for (i = 0; i < NP; i++) X_R[i] = simplex[i, ima];
                F_R = F(X_R, NP, ima); // Значение функции в вершине ima симплекса после отражения
                TW_R = TW[ima];
                NR_R = NR[ima];
                if (F_R > Fma)
                {
                    shrinking_expansion(ima, beta, NP); // Сжатие
                    for (i = 0; i < NP; i++) X2[i] = simplex[i, ima];
                    F_S = F(X2, NP, ima); // Значение функции в вершине ima симплекса после его сжатия
                    TW_S = TW[ima];
                    NR_S = NR[ima];
                    if (F_S > Fma)
                    {
                        for (i = 0; i < NP; i++) simplex[i, ima] = X[i];
                        reduction(ima, gamma, NP); // Редукция
                        for (i = 0; i < NP + 1; i++)
                        {
                            if (i == ima) continue;
                            for (j2 = 0; j2 < NP; j2++) X2[j2] = simplex[j2, i];
                            // Значения функций в вершинах симплекса после редукции. В вершине ima значение функции сохраняется
                            FN[i] = F(X2, NP, i);
                        }
                    }
                    else
                        FN[ima] = F_S;
                    TW[ima] = TW_S;
                    NR[ima] = NR_S;
                }
                else if (F_R < Fmi)
                {
                    shrinking_expansion(ima, alpha, NP); // Растяжение
                    for (j2 = 0; j2 < NP; j2++) X2[j2] = simplex[j2, ima];
                    F_E = F(X2, NP, ima); // Значение функции в вершине ima симплекса после его растяжения
                    TW_E = TW[ima];
                    NR_E = NR[ima];
                    if (F_E > Fmi)
                    {
                        for (j2 = 0; j2 < NP; j2++) simplex[j2, ima] = X_R[j2];
                        FN[ima] = F_R;
                        TW[ima] = TW_R;
                        NR[ima] = NR_R;
                    }
                    else
                        FN[ima] = F_E;
                    TW[ima] = TW_E;
                    NR[ima] = NR_E;
                }
                else
                    FN[ima] = F_R;
                TW[ima] = TW_R;
                NR[ima] = NR_R;
            }
            sW.WriteLine("Число итераций: " + nIt);
            // Ищем лучшую вершину симплекса
            int vB = -1;
            minval(FN, NP + 1, ref vB);
            for (i = 0; i < NP; i++) X[i] = simplex[i, vB];
        }
        private void buttonNelderMead_Click(object sender, EventArgs e)
        {
            nOfTacts = (int)numericUpDownNumberOfTacts.Value; // Число аргументов - число тактов (2, 3, 4 или 5)
            double[] X = new double[nOfTacts]; // Первая вершина начального симплекса (начальная точка)
            double L, L_thres, cR, alpha, beta, gamma;
            int jMx = 150; // Предельное число шагов алгоритма;
            int kr_todo = 50; // kr_todo - число шагов алгоритма, после выполнения которых симплекс восстанавливается
            double C; // Значение критерия
            turnstile = checkBoxTurnstile.Checked;
            simplex = new double[nOfTacts, nOfTacts + 1]; // NP + 1 - число вершин симплекса
            FN = new double[nOfTacts + 1];
            TW = new double[nOfTacts + 1];
            NR = new double[nOfTacts + 1];
            if (nOfTacts == 2)
            {
                X[0] = tMinOth;
                X[1] = tMinPeak;
                //X[0] = 420;
                //X[1] = 240;
            }
            else if (nOfTacts == 3)
            {
                X[0] = tMinOth;
                X[1] = tMinPeak;
                X[2] = tMinOthDay;
                //X[0] = 420;
                //X[1] = 240;
                //X[2] = 420;
            }
            else if (nOfTacts == 4)
            {
                X[0] = tMinOth;
                X[1] = tMinPeak;
                X[2] = tMinOthDay;
                X[3] = tMinPeak + 20;
                //X[0] = 420;
                //X[1] = 240;
                //X[2] = 420;
                //X[3] = 300;
            }
            else if (nOfTacts == 5)
            {
                X[0] = tMinOth;
                X[1] = tMinPeak;
                X[2] = tMinOthDay;
                X[3] = tMinPeak + 20;
                X[4] = tMinOth + 20;
                //X[0] = 300;
                //X[1] = 300;
                //X[2] = 420;
                //X[3] = 240;
                //X[4] = 600;
            }
            else
            {
                MessageBox.Show("Плохое число тактов");
                return;
            }
            L = 10; // Начальная длина ребра симплекса
            L_thres = 0.02; // Предельное значение длины ребра симплекса
            cR = 1.0; // Коэффициент отражения симплекса
            alpha = 1.5; // Коэффициент растяжения симплекса
            beta = 0.5; // Коэффициент сжатия симплекса
            gamma = 0.5; // Коэффициент редукции симплекса
            sW = new StreamWriter("_res.txt"); // Результат
            sW.WriteLine("Затравка ДСЧ: " + seed);
            sW.WriteLine("Параметры: ");
            sW.WriteLine("Начальная длина ребра симплекса: " + L);
            sW.WriteLine("Предельное значение длины ребра симплекса: " + L_thres);
            sW.WriteLine("Коэффициент отражения симплекса: " + cR);
            sW.WriteLine("Коэффициент растяжения симплекса: " + alpha);
            sW.WriteLine("Коэффициент сжатия симплекса: " + beta);
            sW.WriteLine("Коэффициент редукции симплекса: " + gamma);
            sW.WriteLine("Начальная точка:");
            for (int i = 0; i < nOfTacts; i++) sW.WriteLine(X[i]);
            sW.WriteLine("Предельное число шагов алгоритма: " + jMx);
            C = Math.Round(F(X, nOfTacts, 0)); // Значение критерия начального расписания
            labelShedBest0.Text = textShed0Tact + (int)C + " (" + (int)Math.Round(TW[0]) + "+" + NR[0] + ")";
            labelTimeInAll0.Text = textShed0Tact + (int)timeInAllD;
            labelTimeEnd0.Text = textShed0Tact + timeLastRoutLastStop;
            labelShedRoutsN.Text = textShedRoutsN + "-";
            labelNCross.Text = textNCross + "-";
            labelNRestruct.Text = textNRestruct + "-";
            labelNViolations.Text = textNViolations + "0";
            string XS_XE = "(";
            foreach (double t in X) XS_XE += (int)Math.Round(t) + ", ";
            XS_XE = XS_XE.Substring(0, XS_XE.Length - 2);
            XS_XE += "); (";
            // Поиск минимума функции Розенброка
            nelMead(ref X, nOfTacts, L, L_thres, cR, alpha, beta, gamma, jMx, kr_todo);
            sW.WriteLine("Результат:");
            sW.WriteLine("Конечная точка:");
            for (int i = 0; i < nOfTacts; i++) sW.WriteLine(X[i]);
            sW.WriteLine("Значения функции в вершинах конечного симплекса:");
            for (int i = 0; i < nOfTacts + 1; i++) sW.WriteLine("" + FN[i] + " = (" + TW[i] + " + " + NR[i] + ")");
            sW.WriteLine("Значения времени ожидания в вершинах конечного симплекса:");
            for (int i = 0; i < nOfTacts + 1; i++) sW.WriteLine(TW[i]);
            sW.WriteLine("Значения числа рейсов в вершинах конечного симплекса:");
            for (int i = 0; i < nOfTacts + 1; i++) sW.WriteLine(NR[i]);
            sW.Close();
            C = Math.Round(F(X, nOfTacts, 0)); // Значение критерия лучшего расписания
            labelNPAll.Text = textNPAll + (int)nPAllD;
            labelShedBestC.Text = textShedC + (int)C + " (" + (int)Math.Round(TW[0]) + "+" + NR[0] + ")";
            labelTimeInAllC.Text = textShedC + (int)timeInAllD;
            labelTimeEndC.Text = textShedC + timeLastRoutLastStop;
            string timeSumD = "";
            int tM;
            foreach (double x in X)
            {
                tM = (int)Math.Round(x);
                timeSumD += tM * nStops + "/" + tM + "; ";
            }
            labelTimeSum.Text = textTimeSum + timeSumD; // Суммарное время движения по маршруту без остановок, c
            foreach (double t in X) XS_XE += (int)Math.Round(t) + ", ";
            XS_XE = XS_XE.Substring(0, XS_XE.Length - 2); XS_XE += ")";
            labelShedRoutsN.Text = "Начальные и конечные точки: " + XS_XE;
        }
    }
}

Список литературы

  1. Построение диаграммы прихода пассажиров на остановку. http://100byte.ru/stdntswrks/cshrp/chart.html.
  2. Genetic algorithm. Wikipedia. The free encyclopedia. https://en.wikipedia.org/wiki/Genetic_algorithm.
  3. Бартеньев О. В., Ефремова Н. Г. Оптимизация расписания движения трамваев. Ростовский научный журнал. 2017. № 8. С. 187-193.
  4. Clock-face scheduling. Wikipedia. The free encyclopedia. https://en.wikipedia.org/wiki/Clock-face_scheduling
  5. Поиск минимума функции методом Нелдера-Мида. http://www.100byte.ru/stdntswrks/hj/nm.html.

Список работ

Рейтинг@Mail.ru