A Heuristic Algorithm for Multi-Agent Vehicle Routing with Automated Negotiation

We investigate a problem that lies at the intersection of three research areas, namely Automated Negotiation, Vehicle Routing, and Multi-Objective Optimization. Specifically, we investigate the scenario that multiple competing logistics companies aim to cooperate by delivering truck loads for one another, in order to improve efficiency and reduce the distance they drive. In order to do so, these companies need to find ways to exchange their truck loads such that each of them individually benefits. We present a new heuristic algorithm that, given one set of orders to deliver for each company, tries to find the set of all order-exchanges that are Pareto-optimal and individually rational. Furthermore, we present experiments based on real-world test data from two major logistics companies, which show that our algorithm is able to find hundreds of solutions in a matter of minutes.This work was supported by project LOGISTAR funded by the E.U. Horizon 2020 Research and Innovation Programme, Grant Agreement 769142, by project CI-SUSTAIN funded by the Spanish Ministry of Science and Innovation (PID2019-104156GB-I00), and by a Juan de la Cierva research grant from the Spanish Ministry of Science and Innovation (IJC2018-036443-I)