Fundamentals of supply chain theory by Larry Synder

Fundamentals of supply chain theory

1. Fundamentals of Supply Chain Theory Larry Snyder Z.-J. Max Shen Slides © 2014 Lawrence V. Snyder Chapter 10: The Traveling Salesman Problem

2. 10.2 Introduction to the TSP 2

3. The Traveling Salesman Problem Starting at a home location and given n – 1 other cities, in what sequence should we visit the cities in order to minimize total distance traveled? Problem is solved routinely to determine delivery vehicle routes 3

4. Hamiltonian Cycle 4 We typically begin with a graph G(N, A), where the nodes in N correspond to cities, and arc lengths for arcs in A correspond to distances between cities Given G(N,A), a Hamiltonian Cycle is a tour that begins at a node, visits each node exactly once, and returns to the start node The Hamiltonian Cycle Problem asks, for any given network G(N, A), does a Hamiltonian Cycle exist on the network?

5. Hamiltonian Cycle 5 This graph has no Hamiltonian Cycle:

6. Hamiltonian Cycle 6

7. Hamiltonian Cycle 7 Solving the TSP requires finding a Hamiltonian Cycle of shortest total distance Thus, the TSP is at least as hard as the Hamiltonian Cycle Problem The Hamiltonian Cycle Problem is NP-Complete Implies that the TSP is NP-Hard

8. Formulating the TSP The TSP considers a set of n cities that must be visited before returning to a starting point, where c ij denotes the distance from city i to city j Define x ij = 1 if and only if city i is visited immediately before city j, and x ij = 0 otherwise The objective is to visit all of the cities at minimum cost, i.e., min We exit each city exactly once: , i = 1, …, n We enter each city exactly once: , j = 1, …, n So far we have an assignment problem? Is this enough ?   8

9. Subtours 9 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 8 Assignment problem solution 1 8 5 2 4 3 6 7 Corresponding TSP solution We need additional constraints!

10. Subtour Elimination 10 Let S denote any non-empty strict subset of N (the set of n cities) Given a subset S and N\S, there must be at least one arc used going from S to N\S, i.e., , for any S  N, S   Another form of subtour elimination constraints (there are others): , for S  N, 3 ≤ |S| ≤ n – 1 Either of these forms will work The problem: How many choices of S do we have?  

11. Subtour Elimination Constraints 11 The number of subtour elimination constraints equals where This is O(2 n ) (e.g., 2 100 is more than 1.26 x 10 30 ) If G(N, A) is a complete graph, then the number of feasible solutions is (N – 1)! How long would it take to evaluate each possible solution?  

12. TSP Combinatorial Explosion 12 Because the TSP is NP-Hard, we may in the worst case, have to evaluate all possible solutions The world’s fastest computer currently can handle 148.6 petaflops, which is 1.486 x 10 15 operations per second N - 1 (N - 1)! Time required by world's fastest computer Units 5 120 8.07537E-16 seconds 10 3628800 2.44199E-11 seconds 15 1.31E+12 8.79996E-06 seconds 20 2.43E+18 16.37215349 seconds 25 1.55E+25 172.5897847 weeks 30 2.65E+32 567,579 centuries

13. 10.4 Construction Heuristics for the TSP 13 © 2014 Lawrence V. Snyder

14. Nearest Neighbor Greedy and myopic approach At any node, always choose the closest node as the next node in the sequence Consider the network below (Figure 10.5) For any arc not shown, take its distance as the shortest path between nodes (e.g., arc (1, 6) has length 15) 14 9 1 2 3 4 5 6 7 8 13 17 16 5 7 16 12 7 11 5 13 10 6 12

15. Nearest Neighbor 15 Starting at node 1 Nearest node is 2 Nearest to 2 (that hasn’t been visited) is 5 Nearest to 5 (that hasn’t been visited) is 6 Total distance is 83 9 1 2 3 4 5 6 7 8 13 17 16 5 7 16 12 7 11 5 13 10 6 12

16. Nearest Insertion 16 Start at an arbitrary node; at 1 st iteration insert nearest neighbor At each subsequent iteration, find the node k * not on the tour that is closest to a node on the tour For each edge ( i,j ) currently on the tour (including the edge that completes the current subtour ) compute For the edge ( i,j ) that minimizes this value (call this ( i * ,j * )), replace ( i * ,j * ) with ( i * ,k * ) and (k * ,j * )  

17. Nearest Insertion 17 Start at node 1 and its nearest neighbor 2 The closest node to either 1 or 2 is node 5; we only have one to compute ( ), and we insert node 5 between 1 and 2 Next nearest node to 1, 2, or 5 is 6   9 1 2 3 4 5 6 7 8 13 17 16 5 7 16 12 7 11 5 13 10 6 12

18. Nearest Insertion 18 We compute , Minimum is 14 so we replace (5,2) with (5,6) plus (6,2) Remaining iterations: (5,8) and (8,6) replace (5,6) (6,3) and (3,2) replace (6,2) (5,7) and (7,8) replace (5,8)   9 1 2 3 4 5 6 7 8 13 17 16 5 7 16 12 7 11 5 13 10 6 12 Tour length = 85

19. Nearest Insertion 19 When distances satisfy the triangle inequality, the Nearest Insertion gives a solution that is never more than twice the optimal solution value Triangle inequality: c ij + c jk  c ik Cheapest Insertion variant: Instead of first finding the closest node k to any node on the current subtour and only computing for that value of k, compute for all k not on the current subtour and choose the combination of i , j, and k that give the minimum for insertion  

20. Farthest Insertion 20 Minor variant of Nearest Insertion: choose the node k that has the farthest minimum distance to any node on the current tour (using shortest path as arc length for arcs not shown) Still choose the smallest for the farthest k! Sequence of moves for our example network:   9 1 2 3 4 5 6 7 8 13 17 16 5 7 16 12 7 11 5 13 10 6 12 Tour length = 81

21. Minimum Spanning Tree 21 A spanning tree on a network is a connected subnetwork that includes all nodes and a subset of edges such that a path exists between each pair of nodes and no cycles exist Greedy algorithm is optimal for minimum spanning tree (MST): Start with no edges, and at each step add the shortest edge that does not create a cycle Stop when a connected tree is obtained

22. Minimum Spanning Tree 22 The minimum spanning tree solution gives a lower bound on the optimal TSP solution value Why? Suppose we have the optimal TSP solution If we remove any edge from this solution, the remaining edges sum to a value less than or equal to the TSP solution value, and The remaining edges form a spanning tree (thus, their sum is at least as great as the minimum spanning tree solution value)

23. Minimum Spanning Tree Heuristic 23 We first find a minimum spanning tree Next, we create a duplicate of each edge on the spanning tree Next, walk a Eulerian Tour on the duplicated spanning tree network A Eulerian Tour is a walk on a graph that visits each edge exactly once and is possible if and only if each node in the network has even degree The duplicated spanning tree is guaranteed to have all nodes of even degree

24. Minimum Spanning Tree Heuristic 24 After taking the Eulerian walk, throw out duplicated nodes on the walk by shortcutting to the next node on the walk Below is the creation of a minimum spanning tree on the example network 9 1 2 3 4 5 6 7 8 13 17 16 5 7 16 12 7 11 5 13 10 6 12

25. Minimum Spanning Tree Heuristic 25 Eulerian Walk: That sequence was 4 – 1 – 2 – 1 – 5 – 6 – 3 – 6 – 8 – 6 – 7 – 6 – 5 – 1 – 4 Now go through that sequence and eliminate duplicates: 4 – 1 – 2 – 5 – 6 – 3 – 8 – 7 – 4 9 1 2 3 4 5 6 7 8 13 5 7 5 10 6 Tour length = 81

26. Minimum Spanning Tree Heuristic 26 If the triangle inequality holds for the edges in the graph, then the tour length we obtain is less than or equal to twice the minimum spanning tree length Because we know that the minimum spanning tree length is a lower bound for the TSP solution value, this means that the solution we obtain is less than or equal to twice the optimal TSP solution value

27. Christophides ’ Heuristic 27 Christophides ’ Heuristic also starts with a spanning tree, but does not necessarily duplicate every edge in the spanning tree It is possible to show that for any undirected graph, the number of odd-degree nodes is even To obtain a graph on which we can take a Eulerian walk from a minimum spanning tree graph, we only need to create edges between nodes of odd degree

28. Christophides ’ Heuristic 28 We solve a minimum weight perfect matching problem using only the nodes of odd degree and the edges between them in the original network The edges contained in the solution to the minimum weight perfect matching are then added to the minimum spanning tree We then walk a Eulerian tour on this graph and remove duplicated nodes like before

29. Christophides ’ Heuristic 29 The spanning tree is shown below for our example network Nodes 1, 2, 3, 4, 7, and 8 have odd degree Minimum weight perfect matching matches 1 to 2, 3 to 8, and 4 to 7 9 1 2 3 4 5 6 7 8 13 17 16 5 7 16 12 7 11 5 13 10 6 12

30. Christophides ’ Heuristic 30 An Eulerian tour can be constructed as 4 – 1 – 2 – 1 – 5 – 6 – 3 – 8 – 6 – 7 – 4 The corresponding TSP tour is then 4 – 1 – 2 – 5 – 6 – 3 – 8 – 7 – 4 with tour length 81 9 1 2 3 4 5 6 7 8 13 17 16 5 7 16 12 7 11 5 13 10 6 12

31. Christophides ’ Heuristic 31 Let Z H be the heuristic solution value Let Z PM be the objective function value of the perfect matching on the odd degree nodes of the MST Let Z MST be the value of the minimum spanning tree Note that Z H  Z PM + Z MST

32. Christophides ’ Heuristic 32 We know that Z MST  Z * We need a bound for Z PM Suppose we solve a TSP on the subset of odd-degree nodes in the MST Let Z( ') denote the TSP solution on this subset, and note that we must have Z( ')  Z * Next observe that this TSP solution consists of two alternating perfect matchings on the subset of odd-degree nodes, and that the smaller of these perfect matchings must be less or equal to 1/2 Z( ')

33. Christophides ’ Heuristic 33 This immediate implies Z PM  Z(  ')/2  Z * /2 Putting this all together gives Z H  Z PM + Z MST  Z * /2 + Z * = 3Z * /2 Thus, Christophides ’ Heuristic guarantees a solution with objective function value no more than 1.5 times the optimal solution value

34. 10.5 Improvement Heuristics for the TSP 34 © 2014 Lawrence V. Snyder

35. 2-Opt Given a feasible solution, suppose we cut two node disjoint edges and re-assemble tour In the example below, we eliminate (1, 2) and (4, 5) and reassemble using (1, 5) and (2, 4) 35 1 2 3 4 5 6 Distance = 54 1 2 3 4 5 6 Distance = 52

36. 2-Opt 36 For the 2-Opt search: When we cut two node disjoint edges, there is only one way to put the tour back together to form a complete tour We have choices of disjoint edges  

37. 2-Opt Example 37 Consider the tour below with distance 83 Consider cutting (3, 7) and (6, 8): Put back together with (3, 6) and (7, 8) Cost change is 7 + 13 – 17 – 5 = -2 (improves!) 9 1 2 3 4 5 6 7 8 13 17 16 5 7 16 12 7 11 5 13 10 6 12

38. 3-Opt 38 Given a feasible solution, suppose we cut three node disjoint edges and re-assemble tour We now have 7 ways to put the tour back together Need to determine which of the 7 is best We also have O(N 3 ) choices of three node disjoint edges More generally, we may consider cutting k node disjoint edges, resulting in the k -Opt heuristic