Source-linked AI summary
Deep Learning Assisted Heuristic Tree Search for the Container Pre-marshalling Problem
André Hottung, Shunji Tanaka, Kevin Tierney
TL;DR
CPMP heuristics depend on problem-specific components that require expert development, while exact methods can take too long on real-world-sized instances. DLTS learns branching and bounding decisions from existing (near-)optimal solutions and integrates them into heuristic tree search. It reports stronger heuristic solutions than state-of-the-art methods, with gaps to optimality below 2% on real-world-sized instances.
Problem
Existing CPMP heuristics rely heavily on problem-specific components developed by experts, while exact approaches take too long on real-world-sized instances for decision-support use.
Source: §1 · p. 2Method
DLTS trains deep neural networks on existing (near-)optimal CPMP solutions to guide branching and estimate bounds for pruning a heuristic tree search.
Source: §1 · p. 2Results
0%–2% gaps to optimality on real-world-sized instances compare with 6%–15% for state-of-the-art metaheuristics.
Source: §1 · p. 2Takeaways & Limitations
DLTS finds better solutions than state-of-the-art approaches on real-world-sized CPMP instances while relying mostly on supplied (near-)optimal solutions to learn solution construction.
Source: §7 · p. 21Applying DLTS to other problems is a future direction, with the paper identifying sequential solution construction and quick DNN evaluation as conditions for promising applications.
Source: §7 · p. 21
Abstract
from arXiv · showhide
The container pre-marshalling problem (CPMP) is concerned with the re-ordering of containers in container terminals during off-peak times so that containers can be quickly retrieved when the port is busy. The problem has received significant attention in the literature and is addressed by a large number of exact and heuristic methods. Existing methods for the CPMP heavily rely on problem-specific components (e.g., proven lower bounds) that need to be developed by domain experts with knowledge of optimization techniques and a deep understanding of the problem at hand. With the goal to automate the costly and time-intensive design of heuristics for the CPMP, we propose a new method called Deep Learning Heuristic Tree Search (DLTS). It uses deep neural networks to learn solution strategies and lower bounds customized to the CPMP solely through analyzing existing (near-) optimal solutions to CPMP instances. The networks are then integrated into a tree search procedure to decide which branch to choose next and to prune the search tree. DLTS produces the highest quality heuristic solutions to the CPMP to date with gaps to optimality below 2% on real-world sized instances.
1 Introduction
The CPMP seeks to reorder yard containers during off-peak periods so they can be retrieved quickly when the port is busy. DLTS uses neural networks trained on existing (near-)optimal solutions to guide branching and pruning, and reports stronger heuristic solutions than state-of-the-art methods on real-world-sized instances.
1 Introduction
- The CPMP reorders containers during off-peak times to minimize moves and support quick retrieval when the port is busy.A rail-mounted gantry crane moves containers between stacks.Source: §1 · p. 2
- Existing CPMP heuristics rely on problem-specific components developed by experts with optimization knowledge and deep understanding of the problem.Exact approaches are also reported to take too long on real-world-sized instances for decision-support use.Source: §1 · p. 2
- DLTS trains deep neural networks on existing (near-)optimal CPMP solutions to guide branching and estimate bounds for pruning the search tree.The networks make branching and bounding decisions during search; the method aims to automate heuristic generation.Source: §1 · p. 2
- 0%–2% gaps to optimality on real-world-sized instances compare with 6%–15% for state-of-the-art metaheuristics.The authors also report that DLTS finds high-quality heuristic solutions in a fraction of the runtime of an exact approach.Source: §1 · p. 2
- The paper evaluates DLTS search strategies and DNN architectures and identifies the method as the first optimization tree search with learned branching and bounding decisions.The introduction lists the experimental evaluation among the paper’s contributions.Source: §1 · p. 2
2 Related work
The section reviews CPMP solvers and learning-based optimization methods to position DLTS among approaches that use learning in search. It distinguishes DLTS by its use of learned models to guide decisions throughout a heuristic tree search.
2.1 Container Pre-Marshalling Problem
- CPMP research includes exact and heuristic methods, with heuristics designed for fast solution generation on bays with many stacks and tiers.Reported approaches include corridor search, lowest-priority-first rules, beam search, and a biased random-key genetic algorithm; the latter two outperform a prior tree search on larger instances, with the genetic algorithm taking less than a minute.Source: §2.1 · p. 3
- Related CRP pattern-database approaches reuse offline solutions but do not learn to generalize beyond stored states, unlike DLTS’s learned branching at all tree levels.These approaches use their pattern databases at a predefined search-tree level.Source: §2.1 · p. 3
2.2 Machine Learning and Optimization
- Learning in optimization spans exact solvers, heuristic procedures, and deep-learning methods for generating solutions.The review frames DLTS against these related combinations of learning and optimization.Source: §2 · p. 3, §2.2 · p. 4
2.2.1 Learning in exact solvers
- In MIP exact solvers, learned models can approximate strong-branching scores; DLTS instead learns from (near-)optimal solutions and outputs branch probabilities.The review also distinguishes DLTS as searching sequences of container moves rather than branching in an exact MIP search.Source: §2.2.1 · p. 4
2.2.2 Learning (in) heuristics
- Learning-based heuristic methods include tuned branch ratings, greedy test-time search, learned node ordering, and learned transitions between heuristic components.The section notes that greedy search at test time offers no mechanism for correcting deviations from an optimal sequence.Source: §2.2.2 · pp. 4–5
2.2.3 Deep learning for optimization problems
- Deep-learning optimization studies train networks to generate solutions, but the reviewed approaches focus on training and architecture rather than integration into sophisticated search.The review says these methods cannot compete with state of the art on larger instances.Source: §2.2.3 · p. 5
3 Container Pre-Marshalling
The CPMP concerns rearranging containers in a yard bay so they can be retrieved efficiently, using a crane to move containers between stacks. Its formal objective is a minimum-length sequence of moves that leaves every stack sorted by retrieval group.
3 Container Pre-Marshalling
- A yard bay is a row of container stacks served by a rail-mounted gantry crane, with stacks subject to a common height limit.Figure 1 depicts a yard block and crane; the passage identifies a bay as a single row of stacks.Source: §3 · p. 5, Figure 1 · p. 6
- The CPMP re-sorts containers by scheduled exit group during off-peak periods to avoid blocking early-exit containers during busy retrieval operations.A single crane moves one container at a time from the top of one stack to another, and the problem is NP-hard.Source: §3 · p. 6
3.1 Formal problem definition
- A CPMP solution is a minimum-length sequence of stack-to-stack moves that sorts each stack by container group.The formal definition represents container group values as g_ij for stack i and tier j.Source: §3.1 · p. 6
- A search-tree node represents a bay configuration, and each branch represents a possible container move.Figure 2 illustrates an instance and its optimal solution, with gray containers identified as blockers that must be moved.Source: §3.1 · p. 6, Figure 2 · p. 7
- DLTS uses a neural network to estimate lower bounds instead of the lower bounds previously developed for CPMP.Existing bounds are computationally efficient but can have multiple-move gaps from the optimal value.Source: §3.1 · p. 6
4 Deep Learning assisted heuristic Tree Search
DLTS combines heuristic tree search with neural-network decisions about branching and pruning. The section introduces the search framework, the networks’ roles, and the strategies and pruning options used by DLTS.
4 Deep Learning assisted heuristic Tree Search
- DLTS uses a branching DNN to prune branches and order remaining children, and a bounding DNN to estimate lower bounds that prune nodes.The bounding network is used at selected tree levels to reduce the branching factor.Source: §4 · p. 7
- Traditional node-ordering strategies used in DLTS include depth-first search, limited discrepancy search, and weighted beam search.The order in which nodes are visited is determined by the selected strategy.Source: §4 · p. 7
- The section explains tree-search optimization, DLTS’s branching and lower-bound decisions, and three ways to prune branches using the branching network.It also presents different search strategies for DLTS.Source: §4 · p. 7
4.1 Tree Search
Tree search represents the optimization process as paths from an initial state to feasible leaves. In the CPMP, each move changes the container configuration, and solution cost is the number of moves.
4.1 Tree Search
- A complete solution is a path from the root state to a feasible leaf, formed by a sequence of branching decisions.The initial state is s0; c* denotes complete-solution cost and ck the cost of a partial solution.Source: §4.1 · p. 7
- In the CPMP, each tree node represents a container configuration, and each child represents a configuration reachable by one container movement.A solution ends at a sorted configuration.Source: §4.1 · p. 7
- CPMP solution cost equals the number of container movements, with each movement adding one to the cost.Source: §4.1 · p. 7
4.2 DNNs for Tree Search
DLTS uses supervised neural networks to guide branching and estimate completion costs for tree-search pruning. The networks are trained from examples extracted from optimal or near-optimal CPMP solutions.
4.2 DNNs for Tree Search
- The branching network predicts promising branches, while the bounding network estimates completion cost to support lower-bound pruning.The estimated completion cost is added to the partial-solution cost; a bound at least as large as the best known solution prunes the node, with a scaling factor available to reduce overestimation risk.Source: §4.2 · pp. 8–9
- At each node, the branching network outputs a probability distribution over available branches, which can rank them or discard low-probability choices.For the CPMP, the number of branch outputs depends on the instance's number of stacks and is constant across its nodes.Source: §4.2 · p. 8
4.2.1 DNN Training
- Training examples are extracted by solving representative instances exactly, or heuristically when an exact algorithm is unavailable, and examining their optimal or near-optimal solutions.Instances are split into training and validation sets.Source: §4.2.1 · p. 9
- For each move, the branching network uses the pre-move stack state as input and a move-related target; the bounding network instead predicts remaining completion cost.The branching output covers possible moves between distinct stacks, while infeasible moves are filtered later; the described training scheme uses one optimal solution per instance, though alternatives could use multiple optima.Source: §4.2.1 · p. 9
- Network weights are adjusted by gradient descent to reduce prediction loss over sampled training examples, with training continuing across epochs until error stops improving.Source: §4.2.1 · p. 9
4.3 Search Strategies
DLTS combines branching and bounding networks with different search orders. DFS follows network rankings, LDS prioritizes paths with fewer deviations, and WBS orders nodes using a weighted lower bound.
4.3 Search Strategies
- The evaluated high-level strategies are DFS, LDS, and BFS, with differing reliance on the branching and bounding networks.Source: §4.3 · pp. 9–10
4.3.1 Depth first search
- DFS explores deeper nodes first, orders successors by branching-network predictions, and prunes when node cost or a weakened heuristic lower bound reaches the best known solution cost.The bound is queried only at configured depths, and its estimate is scaled by a factor between zero and one to reduce the risk of overestimating it.Source: §4.3.1 · p. 10
4.3.2 Limited discrepancy search
- LDS searches paths by increasing deviations from the branching network's recommended path, testing the heuristic's advice first and then paths with more discrepancies.This is intended for settings where the branching direction is usually correct, while addressing DFS's tendency to exhaust a suboptimal subtree after an early mistake.Source: §4.3.2 · p. 10
- The DLTS-LDS priority queue avoids iterative DFS's repeated network queries by popping lower-discrepancy nodes first, with tunable zero-discrepancy treatment near the root.Ties favor nodes nearer a leaf; bounding and branching are then used to prune or expand nodes.Source: §4.3.2 · pp. 11–12
- Because CPMP nodes can have many branches, optional probability binning assigns equal discrepancy to branches whose network scores fall in the same probability range.The number of bins determines the ranges, ordered with higher probabilities first.Source: §4.3.2 · p. 12
4.3.3 Weighted beam search
- WBS explores nodes by a weighted sum of node cost and the bounding network's estimated cost, while the branching network determines beam width.Its pruning bound remains the one used by DFS and LDS; unlike those strategies, WBS computes the lower bound for every node.Source: §4.3.3 · p. 13
4.4 Branch pruning functions
The MP functions set a probability cutoff that determines which branches remain available for exploration. Their motivation is to control pruning in light of the greater cost of mistakes near the top of the tree.
4.4 Branch pruning functions
- MP sets a cutoff using branch probabilities, and branches below that threshold are pruned; its inputs include the pruning parameter, maximum branch probability, current cost, and best-solution cost.The motivation is that choosing the wrong branch near the tree root can remove optimal or near-optimal solutions, while mistakes deeper in the tree are described as less costly.Source: §4.4 · p. 13
- MP-Constant scales the highest branch probability by the pruning parameter and ignores the other inputs.The constant variant can be expensive because it leaves the same number of branches available at the top and bottom of the tree.Source: §4.4 · p. 13
- MP-Quadratic aims to reduce the number of explored child nodes more quickly, allowing more tree areas to be searched within the time limit.Source: §4.4 · p. 13
- A log-based function is introduced as an alternative to the quadratic pruning function.Source: §4.4 · p. 13
5 Solving the Container Pre-marshalling Problem with Deep Learning Heuristic Tree Search
DLTS uses DNNs to supply branching and bounding without domain-designed heuristics. Its CPMP network architecture incorporates stack structure, while additional rules filter some moves and omit specialized symmetry handling.
5.1 DNN models
- Each stack/tier position enters locally connected, stack-binding layers; tier-wise shared weights extract common stack features before fully connected layers produce outputs.Figure 5 depicts the branching network’s shared-weight layers connected to its output layer by fully connected layers.Source: §5.1 · p. 14, Figure 5 · p. 15
- Weight sharing slightly improves DNN performance but does not encode CPMP stack-order symmetry; the architecture can also serve variants where stack order matters.Source: §5.1 · p. 14
- The branching network scores every container move as a probability distribution, while the bounding network uses one output.Branching outputs represent possible moves, including infeasible ones; the bounding network differs in having a single output node.Source: §5.1 · p. 14
5.2 Additional problem knowledge
- Infeasible moves and immediate reversals are filtered, but omitting symmetry-aware rules permits cycles of length ≥3, which value-network pruning should limit.Source: §5.2 · pp. 14–15
6 Computational Results
Experiments assess DNN configurations and search strategies, then compare DLTS with state-of-the-art methods on generated and literature CPMP instances. DLTS-G123 maintains high-quality results across instance groups, while DLTS-G1’s performance depends on how closely test instances match its training distribution.
6.1 Experimental setup
- Training used more than 900,000 generated instances, with G1-only and mixed G123 datasets; testing used generated sets of 250 per size and class, plus 750 G123 instances per size.Networks were trained on TT reference solutions; when TT did not find an optimum within its time limit, the best solution found was used.Source: §6.1 · p. 16
6.2 Experimental question 1: DNN configurations
- The configuration experiments varied network size and used validation sets to compare prediction quality and resulting DLTS performance.For branching networks, DFS and log-based branch pruning were used; bounding networks were evaluated with the best-performing branching network and tuned parameters.Source: §6.2 · pp. 16–17
6.2.1 Branching networks
- Lower branching-network CCE corresponded to lower DLTS gaps, but larger networks were not always better and undersized networks sacrificed predictive accuracy.On 7x7 instances, DLTS reached about a 9% gap even with a branching network whose CCE was 0.95, outperforming cited literature heuristics.Source: §6.2.1 · pp. 17–18
6.2.2 Bounding networks
- For bounding networks, MSE correlated with DLTS gap, while larger networks performed nearly the same as medium-sized networks.Source: §6.2.2 · p. 18
6.3 Experimental question 2: Search strategy evaluation
- LDS and DFS solved every instance, but neither dominated across categories; LDS had under half DFS’s gap on 5x7, while DFS did better on larger instances.The authors conclude that DLTS requires algorithm configuration because strategy performance varies.Source: §6.3 · p. 19, Table 3 · p. 19
- DLTS opened many orders of magnitude fewer search nodes than TT, usually for a penalty of one or two moves in solution quality.On 10x7 instances, LDS explored roughly 36,000 nodes on average; TT explored upwards of 5 million nodes per second.Source: §6.3 · p. 19, Table 4 · p. 20
6.4 Experimental question 3: Comparison to the state-of-the-art
- On CV instances, DLTS-G1 achieved the best gap to optimality to date in under 60 seconds; BRKGA’s gaps were 3–23 times larger than DLTS’s.Across instance groups, DLTS-G123 showed high-quality results, while DLTS-G1’s performance suffered as test instances became more different from G1.Source: §6.4 · p. 20
- Without CV-dataset training or validation, DLTS averaged 42.17 moves on CV 5-10 instances, usually about one move from optimal versus three to four for BRKGA and BS-B.The CV instances share G1’s single-group-per-container structure; the paper notes that improving solutions by even two moves could reduce terminal crane movements by hundreds or thousands.Source: §6.4 · pp. 20–21
7 Conclusion and future work
DLTS uses deep learning to guide and prune heuristic tree search, finding better solutions than state-of-the-art approaches on real-world-sized CPMP instances. The authors identify other sequential-construction problems with quickly evaluable instance and partial-solution structure as potential applications.
7 Conclusion and future work
- DLTS finds better solutions than state-of-the-art approaches on real-world-sized CPMP instances while relying mostly on near-optimal solutions and little user input.The authors describe it as the first optimization search approach whose learned model fully controls search decisions while achieving state-of-the-art performance.Source: §7 · p. 21
- DLTS uses deep learning for search guidance and pruning in a heuristic tree search applied to the container pre-marshalling problem.Source: §7 · p. 21
- Potential applications include problems with sequential solution construction and instance and partial-solution structures that allow quick DNN evaluation.The authors also suggest reinforcement learning and changes to the networks or search procedure as future work.Source: §7 · p. 21