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

Anees Abu-Monshar*, Ammar Al-Bazi, Vasile Palade

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Article number116370
Number of pages12
JournalExpert Systems with Applications
Early online date20 Dec 2021
Publication statusPublished - 15 Apr 2022

Bibliographical note

Publisher Copyright: © 2022 Elsevier Ltd. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International


  • Agent-based modelling
  • Hybrid messaging protocol
  • Optimisation
  • Unique vehicle location and depot
  • Vehicle Routing Problem


Dive into the research topics of 'An agent-based optimisation approach for vehicle routing problem with unique vehicle location and depot'. Together they form a unique fingerprint.

Cite this