Применение мультиагентных технологий в транспортной задаче с временными окнами и несколькими пунктами погрузки

Предлагается метод построения расписания в задаче транспортной логистики MDVRPTW на основе мультиагентного подхода. Рассматривается мультиагентная система взаимодействующих грузовиков, складов и заказов. Для ограничения интенсивности переговоров агентов предложена организация сцены на основе триангуляции Делоне. Показано, что решение мультиагентной системы на 10–30 процентов отличается от известных эталонных решений, однако значительно превышает их по скорости получения, что дает возможность применять метод в системах реального времени.
In this paper a multi-agent approach to MDVRP (Multiple Depot Vehicle Routing Problem with Time Windows) problem is presented. The multi-agent system consists of interacting trucks, depots and orders interacting in an artificial environment. Truck agents are seeking to maximize the number of orders delivered with minimal route cost. Order agents are looking for a truck with minimal tariff. Depot agents are in charge for the whole coordination. Every agent can interact only with agents in its local neighborhood. The performance of the system depends on the number of messages processed by every agent. Delaney triangulation based scene structure is proposed to limit the intensity of agent negotiations. The system was evaluated on a number of testbed problems known from literature. It's shown that solutions obtained by the method proposed is worse by 10-30% from best known solutions, but the method is quick enough and then can be applied in real-time systems.
№64 (2018)