A delivery company choosing routes faces a branching set of decisions: which customer to serve next, and when to use another vehicle. Monte Carlo Tree Search (MCTS) plans by sampling possible futures rather than examining every route. It builds a search tree incrementally, giving promising choices more attention while still testing less-explored alternatives. section 7.0 section 7.3
Each MCTS iteration repeats four phases:
- Selection: follow existing children from the root, balancing their observed rewards against how little they have been explored. Stop at a node with an untried action or a terminal state. section 7.5
- Expansion: if an untried action is available, add a child representing its resulting state. section 7.5
- Simulation: complete a possible solution from that state using a rollout policy, such as a random or greedy policy, and evaluate the outcome. section 7.5
- Backpropagation: pass the outcome up the path to the root, updating visit counts and accumulated rewards so later selections can use the experience. section 7.5
Figure 7.4 The four-phase cycle of Monte Carlo Tree Search.
Use the four-phase diagram to follow how one iteration grows the tree and updates its estimates. section 7.3
UCB1 is one way to select a child. It combines average reward with an exploration bonus that favors less-visited children; an exploration weight controls the balance. In the routing implementation, unvisited children receive priority. After searching, the implementation can choose the root action with the most visits. section 7.4
Capacitated vehicle routing
Represent a state by the routes built so far, the unvisited customers, and the current vehicle. An action adds an eligible customer or, when no customer can be added, moves to the next vehicle. Eligibility checks both whether the customer is unvisited and whether its demand fits the vehicle’s remaining capacity. The objective is to serve every customer exactly once while minimizing total fleet distance. One solver completes rollouts greedily using the nearest eligible customer, improves routes with 2-opt, and penalizes rollouts that cannot finish. Repeated simulations guide the search toward better route combinations. section 7.4
MCTS trades exhaustive coverage for selective sampling: it can spend more computation on promising routes without checking every possibility. The result depends on the search budget and rollout choices, so a promising sampled solution is not a guarantee of the optimal route. section 7.3 section 7.4

