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

Общая постановка проблемы

В настоящие время многие производственные предприятия сталкиваются с задачей загрузки транспортного средства [1]. При решении данной задачи возникает проблема поиска оптимального распределения некоторого ресурса при наличии ряда ограничивающих факторов. Таким образом, задачу о загрузке можно свести к задаче о рюкзаке [4] и задаче о раскрое [3]. Задача о рюкзаке, как и многие оптимизационные комбинаторные задачи, принадлежит к классу NP-полных задач. Ее можно решить полным перебором всех допустимых вариантов заполнения рюкзака имеющимися предметами, однако при больших массивах входных данных такой переборный алгоритм практически неприемлем, поскольку имеет экспоненциальную сложность относительно длины входа. Если же применить идеи «метода ветвей и границ» [5], то в большинстве случаев объем перебираемых вариантов можно сократить. Подобные алгоритмы с ограниченным перебором могут иметь неплохую сложность в среднем, но в худшем случае все равно остаются экспоненциальными. Поэтому на практике часто используют различные модификации «жадного» алгоритма [5], который имеет полиномиальную сложность, что и является его основным достоинством. В данной работе будет представлен метод загрузки транспортного средства на основе генетического алгоритма.

Цель статьи

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

Постановка задачи

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

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

Исследования

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

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

Методы решения

Для решения классических задач о рюкзаке и раскрое существуют уже известные генетические алгоритмы [1]. Приведем описание генетического алгоритма, позволяющего решить задачу о загрузке транспортного средства. В данной задаче генетический алгоритм, позволяет получить оптимальные решения, сочетающие в себе случайные методы. Размер начальной популяции составляет 20 особей. Хромосома представлена в виде матрицы. В качестве способа кодирования хромосом было выбрано бинарное кодирование. Формирование новой популяции осуществляется с помощью таких генетических операторов: отбор родителей – заключается в турнирном отборе, скрещивание – происходит обмен одним геном, мутация – является генномной. Поскольку в задаче о загрузке транспортного средства суммарная стоимость загруженного груза должна стремиться к максимуму. Предположим, что количество типов груза равно n. Обозначим стоимость i-го предмета как pi, а i-й ген хромосомы как hi.

Но на значение фитнесс-функции влияют некоторые условия задачи: грузоподъемность транспортного средства, площадь кузова транспортного средства, габариты груза. Эти ограничения учтены в штрафной функции.

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