1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

    Consider 4 cities with the following distance matrix:
    
              A      B      C      D
         ┌────────────────────────────┐
       A │   0     10     15     20   │
       B │  10      0     35     25   │
       C │  15     35      0     30   │
       D │  20     25     30      0   │
         └────────────────────────────┘
    
    This is a SYMMETRIC TSP: distance(u,v) = distance(v,u)
    
    Possible tours (starting and ending at A):
    
    Tour 1: A → B → C → D → A
            = 10 + 35 + 30 + 20 = 95
    
    Tour 2: A → B → D → C → A
            = 10 + 25 + 30 + 15 = 80  ✓ Optimal!
    
    Tour 3: A → C → B → D → A
            = 15 + 35 + 25 + 20 = 95
    
    Tour 4: A → C → D → B → A
            = 15 + 30 + 25 + 10 = 80  ✓ Same as Tour 2 (reversed)
    
    Tour 5: A → D → B → C → A
            = 20 + 25 + 35 + 15 = 95
    
    Tour 6: A → D → C → B → A
            = 20 + 30 + 35 + 10 = 95
    
    For n = 4 cities, there are (n-1)!/2 = 3!/2 = 3 distinct tours
    (symmetric TSP - each tour equals its reverse)
    
    For n = 10: 181,440 tours
    For n = 20: ~60 quadrillion tours
    For n = 50: more than atoms in the observable universe

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

/**
 * Brute force TSP - generates all permutations
 * 
 * Time Complexity: O(n! × n)
 * Space Complexity: O(n)
 * 
 * Only feasible for n ≤ 12 or so
 */
function tspBruteForce(distances: number[][]): {
    tour: number[];
    cost: number;
} {
    const n = distances.length;
    
    // Generate all permutations of cities 1 to n-1
    // (city 0 is fixed as start/end)
    const cities = Array.from({ length: n - 1 }, (_, i) => i + 1);
    
    let bestTour: number[] = [];
    let bestCost = Infinity;
    
    // Heap's algorithm for generating permutations
    function permute(arr: number[], size: number): void {
        if (size === 1) {
            // Evaluate this tour: 0 → arr[0] → arr[1] → ... → 0
            let cost = distances[0][arr[0]];  // Start to first city
            for (let i = 0; i < arr.length - 1; i++) {
                cost += distances[arr[i]][arr[i + 1]];
            }
            cost += distances[arr[arr.length - 1]][0];  // Last city to start
            
            if (cost < bestCost) {
                bestCost = cost;
                bestTour = [0, ...arr, 0];
            }
            return;
        }
        
        for (let i = 0; i < size; i++) {
            permute(arr, size - 1);
            
            // Swap based on parity of size
            if (size % 2 === 0) {
                [arr[i], arr[size - 1]] = [arr[size - 1], arr[i]];
            } else {
                [arr[0], arr[size - 1]] = [arr[size - 1], arr[0]];
            }
        }
    }
    
    permute(cities, cities.length);
    
    return { tour: bestTour, cost: bestCost };
}
 
// Example usage
const distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
];
 
const result = tspBruteForce(distances);
console.log("Best tour:", result.tour);  // [0, 1, 3, 2, 0] or equivalent
console.log("Cost:", result.cost);        // 80
 
// Time this for educational purposes
function timeIt(n: number) {
    // Create random distance matrix
    const d: number[][] = Array.from({ length: n }, () =>
        Array.from({ length: n }, () => Math.floor(Math.random() * 100))
    );
    // Make symmetric
    for (let i = 0; i < n; i++) {
        d[i][i] = 0;
        for (let j = i + 1; j < n; j++) {
            d[j][i] = d[i][j];
        }
    }
    
    const start = performance.now();
    tspBruteForce(d);
    const end = performance.now();
    
    console.log(`n = ${n}: ${(end - start).toFixed(2)} ms`);
}
 
// Try: timeIt(8), timeIt(10), timeIt(12)
// Watch the exponential growth!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

/**
 * Held-Karp Algorithm for TSP
 * 
 * Time Complexity: O(n² × 2ⁿ)
 * Space Complexity: O(n × 2ⁿ)
 * 
 * Feasible for n ≤ 20-25 depending on memory
 */
function tspHeldKarp(distances: number[][]): {
    tour: number[];
    cost: number;
} {
    const n = distances.length;
    const INF = Infinity;
    
    // dp[mask][j] = min cost to visit cities in mask, ending at j
    // mask is a bitmask where bit i is set if city i is visited
    const dp: number[][] = Array.from(
        { length: 1 << n },
        () => Array(n).fill(INF)
    );
    
    // parent[mask][j] = previous city before j in optimal path
    const parent: number[][] = Array.from(
        { length: 1 << n },
        () => Array(n).fill(-1)
    );
    
    // Base case: start at city 0
    dp[1][0] = 0;  // mask = 1 means only city 0 is visited
    
    // Process subsets in order of size
    for (let mask = 1; mask < (1 << n); mask++) {
        // mask must include city 0 (our start)
        if ((mask & 1) === 0) continue;
        
        for (let last = 0; last < n; last++) {
            // 'last' must be in the current set
            if ((mask & (1 << last)) === 0) continue;
            
            // Skip if this is just the starting point
            if (mask === 1 && last === 0) continue;
            
            // prevMask = mask without 'last'
            const prevMask = mask ^ (1 << last);
            
            // Try all possible previous cities
            for (let prev = 0; prev < n; prev++) {
                if ((prevMask & (1 << prev)) === 0) continue;
                
                const newCost = dp[prevMask][prev] + distances[prev][last];
                
                if (newCost < dp[mask][last]) {
                    dp[mask][last] = newCost;
                    parent[mask][last] = prev;
                }
            }
        }
    }
    
    // Find the best final city before returning to 0
    const fullMask = (1 << n) - 1;  // All cities visited
    let bestCost = INF;
    let lastCity = -1;
    
    for (let j = 1; j < n; j++) {
        const totalCost = dp[fullMask][j] + distances[j][0];
        if (totalCost < bestCost) {
            bestCost = totalCost;
            lastCity = j;
        }
    }
    
    // Reconstruct the tour
    const tour: number[] = [0];  // End at 0
    let mask = fullMask;
    let current = lastCity;
    
    while (current !== 0) {
        tour.push(current);
        const prev = parent[mask][current];
        mask ^= (1 << current);
        current = prev;
    }
    tour.push(0);  // Start at 0
    tour.reverse();
    
    return { tour, cost: bestCost };
}
 
// Example usage
const dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
];
 
const result = tspHeldKarp(dist);
console.log("Optimal tour:", result.tour);  // [0, 1, 3, 2, 0]
console.log("Optimal cost:", result.cost);  // 80
 
// Performance comparison
function compareTimes(n: number): void {
    // Generate random symmetric distance matrix
    const d: number[][] = Array.from({ length: n }, () =>
        Array.from({ length: n }, () => Math.floor(Math.random() * 100))
    );
    for (let i = 0; i < n; i++) {
        d[i][i] = 0;
        for (let j = i + 1; j < n; j++) {
            d[j][i] = d[i][j];
        }
    }
    
    console.log(`\nTesting n = ${n}:`);
    
    // Held-Karp
    const startHK = performance.now();
    const resultHK = tspHeldKarp(d);
    const endHK = performance.now();
    console.log(`  Held-Karp: ${(endHK - startHK).toFixed(2)} ms, cost = ${resultHK.cost}`);
    
    // Brute force (only for small n)
    if (n <= 10) {
        const startBF = performance.now();
        const resultBF = tspBruteForce(d);
        const endBF = performance.now();
        console.log(`  Brute Force: ${(endBF - startBF).toFixed(2)} ms, cost = ${resultBF.cost}`);
    }
}
 
// Try: compareTimes(10), compareTimes(15), compareTimes(18)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

/**
 * Nearest Neighbor Heuristic
 * 
 * Simple greedy approach with no worst-case guarantee.
 * Often produces decent solutions quickly.
 * 
 * Time Complexity: O(n²)
 */
function nearestNeighborTSP(distances: number[][]): {
    tour: number[];
    cost: number;
} {
    const n = distances.length;
    const visited: boolean[] = new Array(n).fill(false);
    const tour: number[] = [0];
    visited[0] = true;
    let totalCost = 0;
    
    for (let count = 1; count < n; count++) {
        const current = tour[tour.length - 1];
        let nearestCity = -1;
        let nearestDist = Infinity;
        
        for (let j = 0; j < n; j++) {
            if (!visited[j] && distances[current][j] < nearestDist) {
                nearestDist = distances[current][j];
                nearestCity = j;
            }
        }
        
        tour.push(nearestCity);
        visited[nearestCity] = true;
        totalCost += nearestDist;
    }
    
    // Return to start
    totalCost += distances[tour[tour.length - 1]][0];
    tour.push(0);
    
    return { tour, cost: totalCost };
}
 
/**
 * Double-Tree Algorithm (2-approximation for Metric TSP)
 * 
 * Uses MST to build approximate tour.
 * Guarantee: Solution ≤ 2 × OPT (if triangle inequality holds)
 * 
 * Time Complexity: O(n² log n) for MST + O(n) for tour
 */
function doubleTreeTSP(distances: number[][]): {
    tour: number[];
    cost: number;
} {
    const n = distances.length;
    
    // Step 1: Build MST using Prim's algorithm
    const inMST: boolean[] = new Array(n).fill(false);
    const key: number[] = new Array(n).fill(Infinity);
    const parent: number[] = new Array(n).fill(-1);
    
    key[0] = 0;
    
    for (let count = 0; count < n; count++) {
        // Find minimum key vertex not in MST
        let u = -1;
        let minKey = Infinity;
        for (let v = 0; v < n; v++) {
            if (!inMST[v] && key[v] < minKey) {
                minKey = key[v];
                u = v;
            }
        }
        
        inMST[u] = true;
        
        // Update keys of adjacent vertices
        for (let v = 0; v < n; v++) {
            if (!inMST[v] && distances[u][v] < key[v]) {
                key[v] = distances[u][v];
                parent[v] = u;
            }
        }
    }
    
    // Build adjacency list from MST (doubled edges)
    const adj: number[][] = Array.from({ length: n }, () => []);
    for (let v = 1; v < n; v++) {
        adj[v].push(parent[v]);
        adj[parent[v]].push(v);
        // Double the edges (for Eulerian graph)
        adj[v].push(parent[v]);
        adj[parent[v]].push(v);
    }
    
    // Step 2: Find Eulerian tour via DFS and shortcut
    const visited: boolean[] = new Array(n).fill(false);
    const tour: number[] = [];
    
    function dfs(u: number): void {
        if (!visited[u]) {
            visited[u] = true;
            tour.push(u);
        }
        
        while (adj[u].length > 0) {
            const v = adj[u].pop()!;
            // Remove reverse edge
            const idx = adj[v].indexOf(u);
            if (idx !== -1) adj[v].splice(idx, 1);
            dfs(v);
        }
    }
    
    dfs(0);
    tour.push(0);  // Complete the cycle
    
    // Calculate actual tour cost
    let totalCost = 0;
    for (let i = 0; i < tour.length - 1; i++) {
        totalCost += distances[tour[i]][tour[i + 1]];
    }
    
    return { tour, cost: totalCost };
}
 
// Christofides algorithm sketch (1.5-approximation)
// Full implementation requires minimum-weight perfect matching
// which is complex - here's the conceptual outline:
/*
function christofidesTSP(distances: number[][]): { tour: number[], cost: number } {
    // Step 1: Build MST
    const mst = computeMST(distances);
    
    // Step 2: Find vertices with odd degree in MST
    const oddVertices = findOddDegreeVertices(mst);
    
    // Step 3: Find minimum weight perfect matching on odd vertices
    // This is the complex part - requires Blossom algorithm O(n³)
    const matching = minimumWeightPerfectMatching(distances, oddVertices);
    
    // Step 4: Combine MST and matching to get Eulerian multigraph
    const combined = combineGraphs(mst, matching);
    
    // Step 5: Find Eulerian tour
    const eulerTour = findEulerianTour(combined);
    
    // Step 6: Shortcut to Hamiltonian cycle
    return shortcutToTour(eulerTour, distances);
}
*/
 
// Example comparison
const cities = [
    [0, 10, 15, 20, 25],
    [10, 0, 35, 25, 30],
    [15, 35, 0, 30, 20],
    [20, 25, 30, 0, 15],
    [25, 30, 20, 15, 0]
];
 
console.log("Nearest Neighbor:", nearestNeighborTSP(cities));
console.log("Double Tree:", doubleTreeTSP(cities));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177

/**
 * 2-opt Local Search for TSP
 * 
 * Iteratively improves a tour by swapping edge pairs.
 * Often produces near-optimal solutions.
 * 
 * Time Complexity: O(n²) per iteration, total varies
 * Typically converges quickly on random instances.
 */
function twoOptImprove(tour: number[], distances: number[][]): {
    tour: number[];
    cost: number;
} {
    const n = tour.length - 1;  // tour includes return to start
    let improved = true;
    
    // Calculate initial cost
    const tourCost = (t: number[]) => {
        let cost = 0;
        for (let i = 0; i < t.length - 1; i++) {
            cost += distances[t[i]][t[i + 1]];
        }
        return cost;
    };
    
    while (improved) {
        improved = false;
        
        for (let i = 0; i < n - 1; i++) {
            for (let j = i + 2; j < n; j++) {
                if (j === n - 1 && i === 0) continue;  // Skip if adjacent
                
                // Current edges: (tour[i], tour[i+1]) and (tour[j], tour[j+1])
                // Proposed: (tour[i], tour[j]) and (tour[i+1], tour[j+1])
                
                const currentCost = 
                    distances[tour[i]][tour[i + 1]] + 
                    distances[tour[j]][tour[j + 1]];
                
                const newCost = 
                    distances[tour[i]][tour[j]] + 
                    distances[tour[i + 1]][tour[j + 1]];
                
                if (newCost < currentCost) {
                    // Reverse the segment between i+1 and j
                    const newTour = [
                        ...tour.slice(0, i + 1),
                        ...tour.slice(i + 1, j + 1).reverse(),
                        ...tour.slice(j + 1)
                    ];
                    tour = newTour;
                    improved = true;
                }
            }
        }
    }
    
    return { tour, cost: tourCost(tour) };
}
 
/**
 * Full 2-opt TSP solver
 * Start with nearest neighbor, then apply 2-opt
 */
function twoOptTSP(distances: number[][]): {
    tour: number[];
    cost: number;
} {
    // Get initial tour using nearest neighbor
    const initial = nearestNeighborTSP(distances);
    console.log("Initial (NN) cost:", initial.cost);
    
    // Improve with 2-opt
    const improved = twoOptImprove(initial.tour, distances);
    console.log("After 2-opt cost:", improved.cost);
    
    return improved;
}
 
/**
 * Or-opt: move a sequence of 1, 2, or 3 consecutive cities
 * to another position in the tour.
 */
function orOptImprove(tour: number[], distances: number[][]): {
    tour: number[];
    cost: number;
} {
    const n = tour.length - 1;
    let improved = true;
    
    const tourCost = (t: number[]) => {
        let cost = 0;
        for (let i = 0; i < t.length - 1; i++) {
            cost += distances[t[i]][t[i + 1]];
        }
        return cost;
    };
    
    while (improved) {
        improved = false;
        
        // Try moving segments of length 1, 2, 3
        for (let segLen = 1; segLen <= 3; segLen++) {
            for (let i = 1; i < n - segLen; i++) {
                // Segment: tour[i] to tour[i + segLen - 1]
                for (let j = 0; j < n; j++) {
                    if (j >= i - 1 && j <= i + segLen) continue;
                    
                    // Try inserting segment after position j
                    const segment = tour.slice(i, i + segLen);
                    const before = tour.slice(1, i);
                    const after = tour.slice(i + segLen, n);
                    
                    // Reconstruct based on j's position
                    let newMiddle: number[];
                    if (j < i) {
                        newMiddle = [
                            ...before.slice(0, j),
                            ...segment,
                            ...before.slice(j),
                            ...after
                        ];
                    } else {
                        const adjustedJ = j - segLen;
                        newMiddle = [
                            ...before,
                            ...after.slice(0, adjustedJ - before.length + 1),
                            ...segment,
                            ...after.slice(adjustedJ - before.length + 1)
                        ];
                    }
                    
                    const newTour = [0, ...newMiddle, 0];
                    const newCost = tourCost(newTour);
                    
                    if (newCost < tourCost(tour)) {
                        tour = newTour;
                        improved = true;
                    }
                }
            }
        }
    }
    
    return { tour, cost: tourCost(tour) };
}
 
// Example: Large random instance
function solveRandomTSP(n: number) {
    // Generate random cities in 2D
    const cities = Array.from({ length: n }, () => ({
        x: Math.random() * 1000,
        y: Math.random() * 1000
    }));
    
    // Euclidean distances
    const dist: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            const dx = cities[i].x - cities[j].x;
            const dy = cities[i].y - cities[j].y;
            dist[i][j] = Math.sqrt(dx * dx + dy * dy);
        }
    }
    
    console.log(`\nSolving TSP for ${n} random cities:`);
    const start = performance.now();
    const result = twoOptTSP(dist);
    const end = performance.now();
    
    console.log(`Time: ${(end - start).toFixed(2)} ms`);
    console.log(`Final cost: ${result.cost.toFixed(2)}`);
}
 
// solveRandomTSP(100);  // Fast
// solveRandomTSP(500);  // Still reasonable
// solveRandomTSP(1000); // May take a few seconds

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

/**
 * Warehouse Pick Path Optimization
 * 
 * A picker must collect items from various locations.
 * Minimize total walking distance.
 */
 
interface Location {
    aisle: number;
    position: number;  // Position along the aisle
}
 
interface PickOrder {
    itemId: string;
    location: Location;
}
 
/**
 * Calculate distance between two warehouse locations
 * Simplified model: aisles are parallel, travel at ends
 */
function warehouseDistance(a: Location, b: Location): number {
    if (a.aisle === b.aisle) {
        // Same aisle: direct distance
        return Math.abs(a.position - b.position);
    } else {
        // Different aisles: go to end, cross, go to position
        const aisleWidth = 3;  // meters between aisles
        const aisleLength = 50;  // meters per aisle
        
        // Strategy: go to nearest end of aisle
        const crossingCost = Math.abs(b.aisle - a.aisle) * aisleWidth;
        
        // Either go to front (position 0) or back (position 50)
        const viaFront = (a.position) + crossingCost + (b.position);
        const viaBack = (aisleLength - a.position) + crossingCost + 
                        (aisleLength - b.position);
        
        return Math.min(viaFront, viaBack);
    }
}
 
/**
 * Optimize pick path using TSP
 */
function optimizePickPath(
    orders: PickOrder[],
    startLocation: Location
): {
    sequence: PickOrder[];
    totalDistance: number;
} {
    const n = orders.length + 1;  // +1 for start location
    
    // Build distance matrix
    const locations: Location[] = [startLocation, ...orders.map(o => o.location)];
    const distances: number[][] = Array.from(
        { length: n },
        (_, i) => Array.from(
            { length: n },
            (_, j) => warehouseDistance(locations[i], locations[j])
        )
    );
    
    // Solve TSP (for small orders, exact; for large, heuristic)
    let result: { tour: number[], cost: number };
    
    if (n <= 12) {
        result = tspHeldKarp(distances);
    } else {
        // Use nearest neighbor + 2-opt for larger orders
        const nn = nearestNeighborTSP(distances);
        result = twoOptImprove(nn.tour, distances);
    }
    
    // Remove start/end from tour, map back to orders
    const sequence = result.tour
        .slice(1, -1)  // Remove start and end (both are location 0)
        .map(i => orders[i - 1]);
    
    return { sequence, totalDistance: result.cost };
}
 
// Example usage
const pickList: PickOrder[] = [
    { itemId: "SKU001", location: { aisle: 1, position: 10 } },
    { itemId: "SKU002", location: { aisle: 3, position: 45 } },
    { itemId: "SKU003", location: { aisle: 1, position: 40 } },
    { itemId: "SKU004", location: { aisle: 5, position: 20 } },
    { itemId: "SKU005", location: { aisle: 2, position: 5 } },
];
 
const start = { aisle: 0, position: 0 };  // Dispatch area
 
const optimized = optimizePickPath(pickList, start);
console.log("Optimal pick sequence:");
optimized.sequence.forEach((item, i) => {
    console.log(`  ${i + 1}. ${item.itemId} at aisle ${item.location.aisle}, pos ${item.location.position}`);
});
console.log(`Total walking distance: ${optimized.totalDistance.toFixed(1)} meters`);