An agent-based optimisation approach for vehicle routing problem with unique vehicle location and depot. (15th April 2022)

• Record Type: Journal Article
• Authors: Abu-Monshar, Anees; Al-Bazi, Ammar; Palade, Vasile
• Is Part Of: Expert systems with applications. Volume 192(2022)
• Publication Date: 2022-04-15
• Subjects: Vehicle Routing Problem -- Unique vehicle location and depot -- Agent-based modelling -- Optimisation -- Hybrid messaging protocol; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2021.116370
• Languages: English
• ISSNs: 0957-4174

Abstract

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. Highlights: A VRP where each vehicle has a unique location for starting and ending its route. A hybrid agent interaction messaging protocol to construct feasible routes. Higher quality solutions than popular for benchmarked MDVRPTW instances. In Modified MDVRPTW instances, generated routes miss customers.