javascript - Creating a trie (or tree) for a branch and bound multiple TSP -

i'm struggling increasing speed of pseudo branch & bound algo & thought trie structure might fit, i'm stuck.

the problem (simplified & isolated best can):

i've got 9 nodes & 3 vehicles. each vehicle must visit 3 unique nodes. so, created every possible trip (9 choose 3 = 84) & stuck in array. now, want find every combination. example, trip 1 111000000. trip 2 000110001 , trip 3 000001110. (84^3 = 592704 combinations). find out if match, bitwise & , accept trip combination if value 0.

i can't use nested loops since # of vehicles may change, keep track of combinations counter ticks depth-wise odometer (e.g. 0,0,82, 0,0,83, 0,1,0).

i reduce combinations keeping following digit greater 1 increased (e.g. 11,83,83 goes 12,13,14 because less 12 in 2nd column repeat 12,1,1 duplicate of 1,1,12).

i perform bitwise , check @ each change (e.g. if (val[12] & val[13]) > 0 don't bother checking 71 possibilities in 3rd column, because 12 , 13 invalidate route. reduces combinations 24720.

since i'm doing depth-first, it's space efficient (no queue save), computationally expensive. i'd use width-first approach create subsets , minimize search space. example, assume counter @ 11,19,20. currently, check 20 - 83 in 3rd column before incrementing 19 20. compute , 19 - 83 in 2nd column before moving on. in doing so, know values don't work 11 in first column , use subarray 3rd column (e.g. if (val[11] & val[45]) > 0, don't bother checking 11 & 19 & 45, rather use array excludes 45 3rd column.

my idea create trie, each key result of , operation end key subarray.

for example:

doc = {     1: {         5: {             end: [8,9,10]         },         7: {             end: [11,14,42]         },         end: [81, 13, 42]     } } 

my problem can't life of me figure out how iterate on data grow trie. or maybe there's better approach? advice or code snippets great, , reading through wall of text.