Recomputing Solutions to Perturbed Multi-Commodity Pickup and Delivery Vehicle Routing Problems using Monte Carlo Tree Search
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Liner Shipping Network Design with Reinforcement Learning
This paper proposes a novel reinforcement learning framework to address the Liner Shipping Network Design Problem (LSNDP), a challenging combinatorial optimization problem focused on designing cost-efficient maritime shi…
Combinatorial Optimizationreinforcement-learningReinforcement LearningLarge Neighborhood-Based Metaheuristic and Branch-and-Price for the Pickup and Delivery Problem with Split Loads
We consider the multi-vehicle one-to-one pickup and delivery problem with split loads, a NP-hard problem linked with a variety of applications for bulk product transportation, bike-sharing systems and inventory re-balanc…
Optimizing Ride-Pooling Operations with Extended Pickup and Drop-Off Flexibility
The Ride-Pool Matching Problem (RMP) is central to on-demand ride-pooling services, where vehicles must be matched with multiple requests while adhering to service constraints such as pickup delays, detour limits, and ve…
Deep Learning--Accelerated Multi-Start Large Neighborhood Search for Real-time Freight Bundling
Online Freight Exchange Systems (OFEX) play a crucial role in modern freight logistics by facilitating real-time matching between shippers and carrier. However, efficient combinatorial bundling of transporation jobs rema…
The Multi-Agent Pickup and Delivery Problem: MAPF, MARL and Its Warehouse Applications
We study two state-of-the-art solutions to the multi-agent pickup and delivery (MAPD) problem based on different principles -- multi-agent path-finding (MAPF) and multi-agent reinforcement learning (MARL). Specifically, …
Multi-Agent Path FindingMulti-agent Reinforcement Learningreinforcement-learningReinforcement Learning (RL)