2023/04/22 by Mithun Goutham, Goutham, Mithun, Stephanie Stockar +1
Engineering · #Advanced Manufacturing and Logistics Optimization #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Systems and Control (eess.SY) #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2304.11444
openalex publication_date 2023/04/22 · openalex created_date 2023/04/27 · openalex updated_date 2026/07/28
The Multi-Commodity Pickup and Delivery Vehicle Routing Problem aims to optimize the pickup and delivery of multiple unique commodities using a fleet of several agents with limited payload capacities. This paper addresses the challenge of quickly recomputing the solution to this NP-hard problem when there are unexpected perturbations to the nominal task definitions, likely to occur under real-world operating conditions. The proposed method first decomposes the nominal problem by constructing a search tree using Monte Carlo Tree Search for task assignment, and uses a rapid heuristic for routing each agent. When changes to the problem are revealed, the nominal search tree is rapidly updated with new costs under the updated problem parameters, generating solutions quicker and with a reduced optimality gap, as compared to recomputing the solution as an entirely new problem. Computational experiments are conducted by varying the locations of the nominal problem and the payload capacity of an agent to demonstrate the effectiveness of utilizing the nominal search tree to handle perturbations for real-time implementation.