What?

Deep Policy Dynamic Programming (DPDP), a framework for solving vehicle routing problems combining heatmap generation from Joshi et al. with an iterative algorithm doing beam search over it in a smart way.

Why?

Routing problems are important. Combining dynamic programming with learnt neural heuristics is a promising way to get the best of both worlds.

How?

Source: original paper.

Source: original paper.

TL;DR Use a GNN to get most promising edges in the graph and run beam search over it pruning branches dominated by other intermediate solutions found so far.

The paper goes into details explaining specific design choices for TSP and VRP. Below, I will describe TSP in my highly inefficient pseudo science code and comments:

def solve(nodes, gnn, beam_size=10):
  heatmap = gnn(nodes)
  visited = {nodes[0]}
  num_nodes = len(nodes)
  partial_solutions = DefaultDict(list)
  partial_solutions[0] = [[0]]

  while not_solved:
    for t in range(len(nodes)):
      over_budget = False # enforce beam constraint
      for sol in partial_solutions[t]: 
        # pop already used actions
        actions_left = get_actions_left(sol, initial_actions)

        # expand most promising states
        scores = [take_most_promising(heatmap, partial_solution + a) 
	      for a in actions_left]
        idx = get_top_k_argmax(scores, k=beam_size) 
        actions = actions_left[idx]
        for a in actions:
	  if len(partial_solutions[t]) > beam_size:
            over_budget = True
            break
          sol.put_left(sol+a)
        if over_budget:
          break
      # prune if dominated, i.e. same nodes, but higher cost
      prune_solutions(partial_solutions)
return 

The heat of a partial solution is just the sum of the heat of the edges: $\mathrm{heat}(a) = \sum^{t-1}{i=1}h{a_{i-1}, a_i}.$ To avoid dead-end solutions, the heat potential is used: $\mathrm{potential}(a) = \mathrm{potential}0(a) + \sum{i \notin \mathrm{visited}(a)}\mathrm{potential}i(a)$, where $\mathrm{potential}i(a) = w_i \sum{j \notin \mathrm{visited}(a)}\frac{h{ji}}{\sum_{j'=0}^{n-1}h_{j'i}}$ and $w_i = (\max_j h_{ji})\cdot(1-0.1(\frac{c_{i0}}{\max_j{c_{j0}}}-0.5))$. The intuition is that the more nodes a partial solution has, the fewer good edges remains and the potential decreases. The rightmost term in $w_{ij}$ is to give higher weights of nodes close to the start node (as I understood $c_{i0}$ is a cost of going to the starting node from node $i$.

And?