A coalition-based metaheuristic for the vehicle routing problem

Abstract—This paper presents a population based Meta-heuristic adopting the metaphor of social autonomous agents. In this context, agents cooperate and self-adapt in order to collectively solve a given optimization problem. From an evolutionary computation point of view, mechanisms driving the search consist of combining intensification operators and diversification operators, such as local search and mutation or recombination. The multiagent paradigm mainly focuses on the adaptive capabilities of individual agents evolving in a context of decentralized control and asynchronous communication. In the proposed metaheuristic, the agent’s behavior is guided by a decision process for the operators ’ choice which is dynamically adapted during the search using reinforcement learning and mimetism learning between agents. The approach is called Coalition-Based Metaheuristic (CBM) to refer to the strong autonomy conferred to the agents. This approach is applied to the Vehicle Routing Problem to emphasize the performance of learning and cooperation mechanisms. I