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.
|Journal||Expert Systems with Applications|
|Early online date||20 Dec 2021|
|Publication status||Published - 15 Apr 2022|
Bibliographical note© 2022, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright © and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders.
This document is the author’s post-print version, incorporating any revisions agreed during the peer-review process. Some differences between the published version and this version may remain and you are advised to consult the published version if you wish to cite from it.
- Vehicle Routing Problem
- Unique Vehicle Location and Depot
- Agent-Based Modelling
- Hybrid Messaging Protocol