A Parallel Monte-Carlo Tree Search-Based Metaheuristic For Optimal Fleet Composition Considering Vehicle Routing Using Branch & Bound
Autonomous mobile robots enable increased flexibility of manufacturing systems. The design and operating strategy of such a fleet of robots requires careful consideration of both fixed and operational costs. In this paper, a Monte-Carlo Tree Search (MCTS)-based metaheuristic is developed that guides a Branch & Bound (B&B) algorithm to find the globally optimal solution to the Fleet Size and Mix Vehicle Routing Problem with Time Windows (FSMVRPTW).The metaheuristic and exact algorithms are implemented in a parallel hybrid optimization algorithm where the metaheuristic rapidly finds feasible solutions that provide candidate upper bounds for the B&B algorithm. The MCTS additionally provides a candidate fleet composition to initiate the B&B search. Experiments show that the proposed approach results in significant improvements in computation time and convergence to the optimal solution.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Structured Parallel Programming for Monte Carlo Tree Search
In this paper, we present a new algorithm for parallel Monte Carlo tree search (MCTS). It is based on the pipeline pattern and allows flexible management of the control flow of the operations in parallel MCTS. The pipeli…
ManagementTwice Sequential Monte Carlo for Tree Search
Model-based reinforcement learning (RL) methods that leverage search are responsible for many milestone breakthroughs in RL. Sequential Monte Carlo (SMC) recently emerged as an alternative to the Monte Carlo Tree Search …
Reinforcement LearningPMCTS: Particle Monte Carlo Tree Search for Principled Parallelized Inference Time Scaling
Monte Carlo Tree Search (MCTS) is a widely used approach for policy improvement through search with increasing popularity for real world applications. Due to the sequential and deterministic nature of its search, runtime…
Parallelization of Monte Carlo Tree Search in Continuous Domains
Monte Carlo Tree Search (MCTS) has proven to be capable of solving challenging tasks in domains such as Go, chess and Atari. Previous research has developed parallel versions of MCTS, exploiting today's multiprocessing a…
Trajectory PlanningMonte Carlo Search Algorithms Discovering Monte Carlo Tree Search Exploration Terms
Monte Carlo Tree Search and Monte Carlo Search have good results for many combinatorial problems. In this paper we propose to use Monte Carlo Search to design mathematical expressions that are used as exploration terms f…