An agent-based optimisation approach for vehicle routing problem with unique vehicle location and depot

Abstract

The Vehicle Routing Problem (VRP) is a well studied logistical problem along with its various variants such as VRP with customer Time-Window (VRPTW). However, all the previously studied variants assume that vehicles are mostly the same in terms of their capacity, location and home location (depot). This study uses the agent-based approach for solving VRPTW with vehicle's unique location and depot. This is to minimise the number of used vehicles as the main target. Other targets including total distance travelled, waiting time and time are also considered as criteria to evaluate the quality of the generated vehicle routes. This is achieved by proposing a Messaging Protocol-based Heuristics Optimisation (MPHO) model that balances between centrally-distributed agents’ interactions and accommodates certain priority rules specifically developed for the problem. Furthermore, modifications to certain constraints checking techniques are introduced by implementing time Push Forward (PF) checking recursively tailored to the route's unique start/ending locations as well as calculating the reduced waiting time to find and check the limit of the total route duration. In order to justify the superiority of the proposed MPHO model, numerical tests have been conducted on benchmark problems including single and multiple depot instances as well as modified instances tailored to the problem. This is made possible by randomising vehicles’ capacities and their unique locations and depots. Key results reveal that, in multiple depot instances, higher quality solutions compared with previous benchmark outcomes are obtained in terms of minimising the total number of vehicles along with fastest solution time (CPU) at the expense of total time and distance travelled.