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

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

Речь идет о Tristar — дочерней компании нашего заказчика Addison Lee. Tristar — служба такси с большим парком машин представительского класса. В частности, она занимается доставкой пассажиров на круизные лайнеры компании Saga. Перед каждым рейсом около 1000 пассажиров со всей Великобритании нужно вовремя доставить на борт, а после путешествия — отвезти домой.

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

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