Comparison between Hybrid and Centralised Agent-Based Optimisation Models for Vehicle Routing Problems with Unique Vehicles

Crowdshipping services require heterogeneous resource modelling as the supply of service is occasional. Classical routing problem such as the Vehicle Routing Problem (VRP) assumes vehicles' similarity; therefore, this research study is questioning this similarity by considering a unique vehicle with different capacities, shifts and starting/ending locations. By modelling the unique vehicles as agents, an agent-based optimisation architecture is proposed along with two types of cooperative messaging protocols, hybrid and centralised, to emerge in optimal routes. The hybrid protocol adopts a hard constraint strategy and may result in missing customers, while the centralised protocol adopts a relaxed strategy, aided with a multi-objective evolutionary algorithm, that may result in constraints violations. Tests on benchmark instances resulted in a reduction in vehicles with around 5% compared to best-known solutions to MDVRPTW instances. At the same time, centralised protocol further reduced waiting times with an average of 2.21 time units, however, at the expense of increased computational complexity. To further test the proposed architecture, both protocols are tested on the same benchmark instances but modified by randomising vehicles' locations, shifts and capacities