algorithms.two_traversal_tree_alg

algorithms.two_traversal_tree_alg(H)[source]

2-TT: Two Traversal Tree Algorithm: Heuristic.

Adaptation of Prim’s MST algorithm for PDP instances. Composes a tour from spanning tree through pre-order traversal (see helper.preorder_st_traversal).

  1. Spanning tree construction:

    1. Adds the branch (s, t) and

    b. Adds subsequent branches greedily to ensure final tree is traversed a maximum of 2 times when using pre-order traversal.

  2. Traverses spanning tree using pre-order traversal.