A multi-agent approach for integrated emergency vehicle dispatching and covering problem

The most important decisions that should be made by emergency vehicle managers are related to the allocation and the covering problems. The allocation (or dispatching) problem consists of deciding which vehicle must be assigned to assist an emergency in the best times. The covering problem aims at keeping the region under surveillance well-covered by relocating available vehicles. As components are geographically distributed, decentralized solution approaches may present several advantages. This paper develops a decentralized distributed solution approach based on multi-agent systems (MAS) to manage the emergency vehicles. The proposed system integrates the dispatching of vehicles to calls with zone coverage issues. This integration means that allocation and covering decisions are considered jointly. The idea of MAS has been applied in many others real-world contexts, and has been proven to provide more flexibility, reliability, adaptability and reconfigurability. To our knowledge, there is no existing work that uses MAS for real-time emergency vehicle allocation problem while accounting for the coverage requirements for future demands. We propose a multi-agent architecture that fit the real emergency systems, and that aims at keeping good performance compared to the centralized solution. The objective is to coordinate agents to reach good quality solutions in a distributed way. For this purpose two approaches are examined. The first one is used to show the impact of distributing data and control on the solution quality, since the dispatching decisions are based only on local evaluations of the fitness. The second approach is based on implicit agents' coordination using a more refined and efficient auction mechanism. The performance of each approach is compared to the centralized solution obtained by solving the proposed model with ILOG CPLEX solver. The obtained results show the importance of the coordination method to keep a good quality of service while distributing data and decision making, and prove the performance of the second approach.