Анализ времени и стоимости является важным элементом планирования строительных проектов. Он оценивает альтернативные графики строительства и устанавливает в качестве оптимального по времени тот, который завершает работы в кратчайшее время. Одновременно, инвесторы стремятся свести к минимуму затраты на проект и продолжительность финансирования. Для подрядчиков, минимизация расходов увеличивает их прибыль, а раннее завершение проекта снижает риск инфляции и дефицита рабочей силы [6]. Трудности планирования возникают потому, что для сотен работ проекта, существует большое количество возможностей улучшения деятельности на основе сочетания различных значений параметров человеческих ресурсов и оборудования. Проект, включающий только 10 работ, с 2 возможностями изменения параметров в каждой, будет иметь 1024 альтернативных варианта. Это доказывает высокую трудоемкость перебора всех возможных комбинаций, чтобы идентифицировать лучшие решения и закончить проект в целевое время с минимальной стоимостью.
Цель исследования заключается в развитии нового метода, который использует данные, хранящиеся в информационной модели здания, и генетические алгоритмы для анализа затрат времени, чтобы достичь оптимального времени окончания проекта при минимальной общей стоимости.
Существующие методы
За последние несколько десятилетий было проведено много исследований, посвященных решению проблемы оптимизации графика строительства. Эти исследования можно разделить на три группы, в зависимости от использованных методов: на основе математического программирования, на основе эвристических методов, на основе эволюционных алгоритмов.
Математические программные модели преобразуют проблему в математическую модель и используют для решения линейное программирование, целочисленное программирование или динамическое программирование. Главные недостатки математических программных моделей – сложность формулировки и неспособность иметь дело с большими проектами [7].
Эвристические методы ищут пути интерпретации информации для каждого опыта, а затем подбирают методы, которые приводят к вычислительному алгоритму для нахождения общего решения. Эвристические методы просты для понимания и, следовательно, легче осуществимы, но нахождение оптимального решения не может быть гарантировано.
Эволюционные алгоритмы показали высокую эффективность решения задач оптимизации и получили большое распространение. Особенное внимание привлекают генетические алгоритмы (GAs), которые разработаны, чтобы имитировать некоторые процессы, наблюдаемые в естественной эволюции[2].
В работе [1] на основе интеграции эволюционного и имитационного моделирования предлагался эвристический метод решения задачи планирования работ. В работе [7] представлялась многоцелевая модель генетических алгоритмов для оптимизации общего времени и общей стоимости одновременно. Был установлен и ограничен срок действия контракта на выполнение работ, требовалось определить только минимальную общую стоимость проекта.
В работе [4] рассмотрены параметры времени и стоимости для решения проблемы дисконтирования потоков денежных средств на основе эвристических методов. В работе [3] применилась новая фитнесс-функция многих переменных для того, чтобы решить эту же проблему на основе GA. В работе [5] рассмотрена задача выравнивания используемых ресурсов и применились GA для ее решения с недоминантной сортировкой.
Существует необходимость создания гибкого метода, которая принимает во внимание различные типы последовательности работ, ограничение длительности работ, минимизирует общую стоимость проекта и время для выполнения всего проекта.
Предлагаемый метод
Рисунок 1 представляет структуру процесса предлагаемого метода.
Целевая функция служит для сокращения времени проекта до достижения оптимальной длительности, которая минимизирует общую стоимость проекта.
Где 
- число работ в проекте;
- число альтернатив работы i;
- прямые издержки на i-ую работу, когда альтернатива j выбирается;
- двоичная переменная работы i, когда альтернатива j выбирается равна 1, иначе равна 0;
- косвенные издержки на проект в единицу времени;
- время выполнения проекта;
- косвенный процент издержек.
При минимизации общей стоимости, каждой работе назначается одна из ее возможных альтернатив, также не должны быть нарушены ограничения предшествования.
На первом этапе работы генетического алгоритма, начальная популяция должна формироваться из случайных особей (хромосом). Хромосомы, как правило, состоят из ряда генов, которые могут рассматриваться в качестве линейной структуры, как показано на рис. 2. Ген содержит атрибуты работы, такие как ее длительность и соответствующая стоимость.
Для каждой созданной особи, данный метод проверяет ее повторяемость. Если существует в популяции одинаковая особь, то новая особь будет переформироваться случайным образом, чтобы поддерживать разнообразие решений. Кроме того, каждое решение проверяется на возможность применения. Если полученная продолжительность проекта от этого решения больше, чем крайний срок выполнения проекта, то данный алгоритм начинает случайным образом выбирать некоторые ускоренные режимы выполнения критических работ.
Рис. 1. Схема предлагаемого метода
Для каждой хромосомы должно быть определено значение (качество) соответствующего решения. Такое значение называется приспособленностью данной хромосомы (особи). Приспособленность каждой особи в популяции вычисляется с помощью инверсии ее общей стоимости. Использование инверсии оказалось наиболее эффективным путем определения приспособленности для предлагаемого метода.
Отбор хромосом (родителей) для выполнения кроссовера и/или мутации заключается в выборе по рассчитанной функции приспособленности тех хромосом, которые будут участвовать в создании потомков для следующего поколения. Для отбора родителей применяется методика рулетки.
Рис.2. Популяция и структура хромосом
Из поколения в поколение хорошие характеристики особей распространяются по всей популяции. Алгоритм использует двухточечный кроссовер, который моделируется следующим образом. Сначала проводится отбор двух родительских особей из популяции, а потом случайным образом определяются две точки внутри хромосом (точки разрыва), в которых каждая хромосома делится на три части. Затем особи обменивается частями друг с другом.
Мутация в данном методе моделируется следующим образом. Выбираются родительские особи (хромосомы, выбранные отбором) и их потомки после кроссовера. У каждой особи случайным образом выбирается ген и вместо него назначается новый случайный вариант гена из множества связанных альтернатив.
После оператора кроссовера и оператора мутации появятся новые особи (потомки). Все созданные потомки оцениваются по общей стоимости и длительности проекта, чтобы определить двух наилучших потомков для обновления популяции.
Популяция подвергается оценке, селекции, рекомбинации и адаптации (замене) до тех пор, пока не будет достигнуто число генерации поколений. Как только число поколений достигнет указанного, GA определяет лучшее решение в текущей популяции.
Далее, алгоритм проходит через процесс сжатия самого длинного пути (ей) сетевого графика. После сжатия за счет значительного сокращения косвенных расходов общая стоимость может быть уменьшена. На заключительном этапе программы применяется процесс расслабления, целью которого является выбор более высокой продолжительности некритических работ, что, не влияя на общее время выполнения проекта, также может уменьшить общую стоимость проекта.
Разработанный алгоритм GA был закодирован в Visual Basic на персональном компьютере. Программа имеет гибкость для интеграции с программным обеспечением управления проектами, Project Microsoft, с BIM, а также с Navisworks и может импортировать результаты оптимального графика строительства, чтобы продолжать развивать 4D график строительства.
Выводы
Предложенный метод может быть полезен для лиц, принимающих решения, так как дает им инструмент оптимизации времени выполнения и стоимости проекта. Алгоритм использует ускоренный поиск оптимального решения, путем анализа каждой работы и ее каждого атрибута для оценки влияния работы на продолжительность проекта и его общую стоимость. Разработана программа, реализующая представленный алгоритм.
Работа выполнена при поддержке Министерства образования и науки РФ (грант Президента РФ №14.Z57.14.6545-НШ).
Рецензенты:
Гинзбург А.В., д.т.н., профессор, профессор кафедры информационных систем, технологий и автоматизации в строительстве ФГБОУ ВПО «Московский государственный строительный университет», г. Москва;
Синенко С.А., д.т.н., профессор, профессор кафедры технологии и организации строительного производства ФГБОУ ВПО «Московский государственный строительный университет», г. Москва.
Библиографическая ссылка
Эльшейх А.М. ОПТИМИЗАЦИЯ ГРАФИКА СТРОИТЕЛЬСТВА НА ОСНОВЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ // Современные проблемы науки и образования. – 2015. – № 1-1. ;URL: https://science-education.ru/ru/article/view?id=18002 (дата обращения: 17.04.2024).