Transp&Supply Chain Sys
Transp&Supply Chain Sys ISYE 6203
Popular in Course
Popular in Industrial Engineering
This 0 page Class Notes was uploaded by Maryse Thiel on Monday November 2, 2015. The Class Notes belongs to ISYE 6203 at Georgia Institute of Technology - Main Campus taught by Alan Erera in Fall. Since its upload, it has received 14 views. For similar materials see /class/234191/isye-6203-georgia-institute-of-technology-main-campus in Industrial Engineering at Georgia Institute of Technology - Main Campus.
Reviews for Transp&Supply Chain Sys
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/02/15
Vehicle Routing ln transportation and logistics problems we are often concerned with the routing of transport vehicles which is quite distinct from the problem of path nding In many problems instead of simply nding an optimizing path from s to t we are instead inter ested in departing from s and visiting a number of locations say 1 2 p we would like to determine the visitation sequence with minimum total cost Such sequence determination problems are known as routing problems When routing vehicles we are often interested in moving a vehicle back to where it starts following a visitation sequence Suppose 0 is some current vehicle location like a depot or a yard where vehicles are kept Then we often wish to nd a route from 0 that visits 1 2 p and returns to 0 with minimum total cost time distance let V represent this set of locations nodes Such a visitation sequence is called a tour Thought Question Since minimum cost path models and algorithm typically nd paths from a start node 5 to all other nodes why are such solutions insuf cient for routing problems Application LTL and Package Empress PickupDelivery Both LTL and package express companies operate hub and spoke networks where pack ages are collected and consolidated initially at satellite terminals and then distributed from such terminals at the other end oftheir trip Since ef cient collection or distribution operations will typically have multiple customers served by each vehicle and different assignments of customers to vehicles and visitation sequences will require different costs ef cient determination of such sequences are routing problems Application Distribution using milk runs from a local distribution center A supplier may serve customers typically plants or retail outlets in a region surrounding its distribution centers with so called milk runs In a milk run the supplier will load the orders for several customers into a truck and then visit those customers in some order making delivery If the company is using a private eet after the run is complete the truck may return to the DC for use again in a later period However if the company has contracted a truckload common carrier for the task the truck may move on to a different location for a different client or back to a trucking depot Setting up cost ef cient milk runs is another routing problem Minimum spanning tree models First we start with some technical information Recall the de nition of a network model G N A Suppose there are n nodes and m arcs General Path A general path P in G is a sequence of nodes i1i2 ip such that ik E N ik are all unique and either ikik1 E A or ik1ik E A for all k 12 p7 1 note that such a de nition does not necessarily identify a directed path as de ned earlier and thus may not be a feasible sequence of decisions for a network user The cost of a directed path is 2 cim In our study of MCP problems we identi ed methods for determining the minimum cost paths in G for i1 s Cycle A cycle is a set of arcs that forms a closed loop in G you can begin walking at some node7 follow only arcs in the cycle regardless of their direction7 and then return to that node Thus7 a cycle 0 is a sequence of nodes 2391723927 z39pz391 where 2 6 N7 2 are unique7 and either aha E A or z k17 k E A for all k 17 27 quot710 71 and either 2391772391 E A or 2391723917 E A In an undirected network7 a cycle clearly is a permitted sequence In a directed network7 it may or not be permitted Trees 1 A tree T in G is a collection of arcs such that all n nodes are connected7 and no cycles exist All nodes connected implies the existence of a general path between all pairs of nodes on T 2 A tree T in G is a set of n 7 1 arcs such that all nodes are connected An important property of a tree is that it de nes7 for each pair of nodes7 a unique not necessarily directed path between them On an undirected network7 of course7 any tree de nes a set of unique paths that can be followed from a node to any other node Minimum spanning tree A minimum spanning tree MST in a network where each arc 2397j has a cost 017 is a tree such that the total cost sum of all the arcs in the tree is minimized MST argminT G 2 CH ijeT Thought Question Why is the minimum spanning tree not the same as a minimum cost path tree Finding the minimum spanning tree Two algorithms that you can use to nd the MST are now presented Both of them are of polynomial complexity7 and easy to understand Kruskal s algorithm Initialization MST Q Iterations 1 Sort the arcs in order of non decreasing 07 into the LIST 2 while lMSTl lt n 71 a Remove ij from the top of the LIST b Add ij to MST if so doing does not create a cycle Generic Kruskal7s Complexity Kruskal7s algorithm consists of two primary steps rst we need to sort the arcs then at each iteration we need to search for cycles To sort in arcs with arbitrarily large arc costs requires 0m log in time Since in S n2 0m log in 0m log n2 02m log n 0m log To search for cycles each iteration it is useful to store the arcs currently in MST in a forest data structure where each element in the forest is a subtree a tree on a subset of the nodes Elements in the forest can be stored as a number of linked lists of nodes with each list representing a different subtree in the forest When we look to add ij to MST we simply scan each subtree list in the forest and ifi and j are already both in the same subtree then we don7t add ij to MST since it would create a cycle For each of the in potential arcs we consider adding to the current MST in Kruskal7s this scan of the forest requires 0n time Therefore Kruskal7s algorithm requires 0mn in log n 0mn run time There exist slightly more ef cient implementations of Kruskal7s algorithm requiring 0m log n n log n time Cuts To explain the next algorithm it necessary to understand the concept of a cut in a network Suppose the nodes in N are partitioned into two independent subsets S and T That is S U T N and S T Q The cut set S T is given by all arcs ij such that i E S andjEToriETandjES Prim s algorithm Initialization MST 0 S 1 T N S In English the set S contains node 1 while the set T contains all nodes except node 1 Iterations while lMSTl lt n 71 1 Find the arc ij in S T with minimum cost 07 2 Add i j to MST 3 Remove j from T and addj to S Generic Prim7s Complexity Prim7s algorithm requires n 7 1 iterations in which a single arc is identi ed in S T and moved into the MST Each iteration we could scan each arc to determine whether it is in S T and if so if it has cost less than the current minimum Such an implementation would scan Om arcs each iteration for a total complexity of However we can improve the complexity with a heap implementation just like we did with Dijkstra7s algorithm Suppose that for each node j E T we keep around a label d where dj minc ij E S T this label represents the minimum inbound cost to j E T from a node k E S and let predj Is It is easy to update these labels each iteration after adding a new node to i to S simply scan all the arcs ij E iT and if dj gt c then dj 07 and predj i Each iteration then we can add the node p with the minimum label dp into S and remove it from T and add predpp to the MST If we did not store node labels in a heap this implementation would require complexity 0n2 which can be derived virtually identically to Dijkstra7s A binary heap implementation would require 0m log n time and a Fibonacci heap 0m n log Thus Prim7s is theoretically more ef cient than Kruskal7s Minimum cost spanning tree optimality conditions Similar to the case with minimum cost paths we can write down optimality conditions for minimum spanning trees that allow us to determine whether an arbitrary tree T is indeed a MST a Path optimality conditions a tree T is an MST on G if and only if for every nontree arc 166 E AT CM 2 07 for each arc ij on the unique path connecting k to Z using the arcs in T b Cut optimality conditions a tree T is a MST on G if and only if for every tree arc ij E T 07 3 CM for each arc 166 contained in the cut formed by removing ij from T A direct minimum spanning tree application in transportation Mini map paths A standard minimum cost path from s to t is often called a minisum path among all paths P connecting s to t we know that P argminP Zawep 07 In some applications we would prefer to identify a minimaco path de ned as follows PA argminP maxj6p 07 In words among all paths connecting s to t PX is one that encounters the smallest maximum cost There are some useful applications of these paths One type of arc cost that one might wish to minimize the maximum77 is elevation change Suppose that you are designing a railroad line through a mountainous region and you want to determine the alignment Since costs associated with traction power and the wear and tear associated with braking increase quickly with absolute elevation change you may wish to choose an alignment that minimizes the maximum elevation change In another application suppose you are transporting extremely hazardous materials such that any spill would cause great harm to surrounding populations Since any spill would be disastrous you might not wish to minimize the expected population exposed but rather the maximum population exposed Solving all pairs minimacv path Fortunately one can solve the all pairs minimax pathing problem on an undirected net work G in which you identify the minimax paths connecting all node pairs by simply solving a MST problem Suppose you have found MST Then the minimax path be tween any pair of nodes 5 and t is identi ed by the path on MST We can justify this claim using the cut optimality conditions Let PA be the path connecting s and t on MST and suppose 27 argmaxltwgtepf ckb Further let I J represent the cut cre ated by removing 27 from MST From cut optimality we know that CM 2 0 for all 166 E I J Since any path from s to It must use at least one arc k Z since 5 E I and t E J it follows that PITI has the minimum maximum value Single Vehicle Routing the Traveling Salesman Problem Let7s consider now the routing of a single vehicle that must make an optimal circuit of a set of locations Optimality will be de ned according to a single summation cost criterion Complete Undirected Network with AInequality To do so in most applications7 the rst step is to develop a complete undirected network satisfying the A inequality G N7 A7 where N is limited to the set of locations through which we would like to build the circuit In a complete network7 an arc exists connecting each node to every other node A complete undirected network with n nodes always contains 7271 0n2 arcs Furthermore7 suppose that the network satis es the A inequality with respect to a set of arc costs cij cji De nition 1 A inequality on Complete Networks A complete network G N7 A satis es the A inequality with respect to arc costs cij i for all i7j7k E N the following relationship holds cm 3 CH cjk As an aside7 there is also a notion of a A inequality for networks that are not complete De nition 2 Triangle Inequality on Arbitrary Networks A network G N7 A satis es the A inequality i for all arcs i7 k E A and intermediate nodesj E N the following relationship holds cm 3 G 0 where G represents the minimum path cost from nodei to node j A network satis es this assumption if the arc from i to j always has no greater cost than a path through a different node7 say k Generating Complete Undirected Network with AInequality Many transportation problems are associated with a fundamental underlying infrastruc ture network G NZA which is not complete7 nor does it satisfy the A inequality For example7 G may be a network of road segments However7 such a network may can be converted to a CUNDl through the use of a minimum cost path procedure Suppose N C N is the set of nodes of interest in a routing problem We can construct a CUNDl G N7 A where the arc set A includes an arc from each node in N to every other node in N7 and the cost on arc i7j is the cost of the minimum cost path from i7j in G Clearly7 in cases where the cost of the path from i to j differs from the cost from j to i7 this procedure will not work however7 this assumption is frequently valid Also7 there must exist some path between all nodes in N Traveling salesperson tours and subtours Let7s now de ne the traveling salesperson problem on some CUNDl G N7A7 where N n7 with arc costs cij cji TSP tour a visitation order7 or sequence7 of all the nodes in N T l17l27 7ln7l17 where ik E N and unique Subtour a sequence of nodes with a common start and end node7 such that not all nodes in N are visited l17l27 7lq7l17 ik E N and unique7 q a positive integer lt n Tour costs and optimal Traveling salesperson tours Tour cost the cost of a tour is simply the sum of all of the arc segments traversed in the tour CT CW cinil Optimal traveling salesman tour the traveling salesman TSP tour that requires the minimum total cost TSP argminTeaCT The problem of determining the optimal TSP tour in a network is in general a very dif cult problem and much more dif cult than nding a minimum cost path or tree on a network It is in the problem type NP hard which essentially means that no one has discovered an ef cient optimal algorithm to solve all instances of the problem In fact the TSP problem is perhaps the most studied of all operations research problems An enumeration algorithm One inef cient way to determine an optimal TSP tour is to simply enumerate each possible tour and pick the one with minimum total cost How many tours in a network with n nodes Why From a start node one can go to n l nodes next Then a choice of n 2 nodes and so on We divide by 2 since tours since in an undirected network half of these tours are just the reverse of other tours So the enumerative method is an 071 algorithm optimal but not ef cient Be quite con dent that an inef cient algorithm will not be aided by improvements in computation speed for large problem instances Consider the following chart 77 6 Since there are only about 315 million seconds in a year let7s consider the performance of the worlds fastest computer performing TSP enumeration on a problem with 100 nodes Currently the Earth Simulator performs a peak of 41000 giga ops billion operations per second this performance is not sustainable but suppose it was The Earth Simulator would require 9815 million years to complete 2100 operations and 72266 136 years to complete 100 operations Heuristic algorithms A heuristic or heuristic algorithm provides feasible solution to an optimization problem which may or may not be optimal Good heuristics give solutions that are close to the optimal solution and usually are ef cient in terms of theoretical or practical running time A desirable property of a heuristic is that the worst case quality of the solution provided can be guaranteed For example some heuristics guarantee that the solution they identify is at worst a optimal that is if the optimal cost is 0 the heuristic nds a solution no greater than aC for minimization problems Importance of Lower Bounds for Hard Minimization Problems When solving hard minimization problems like TSP problems we usually cannot know the cost of the optimal solution for a given instance Even if we were handed the optimal solution it is a dif cult problem to recognize it as such So how do we know if the cost of a feasible solution developed by a heuristic for a given instance is close to the optimal solution cost Suppose that TH is some feasible tour identi ed by a heuristic Clearly we know that CTH 2 CTSP But how close it Often we can compare our heuristic solution cost instead to an easily identi able lower bound on the optimal cost Suppose QTSP is a lower bound for the TSP cost for a given problem Then CTSP 2 QTSP If the bound is close to the optimal solution tight then comparing CTH to QTSP is a good proxy And if a heuristic solution is 04 percent higher than a lower bound it is clearly no greater than 04 higher than the true optimal cost Developing good lower bounds for hard minimization problems is often nearly as hard as developing the optimal solution However any reasonable lower bound is often a good start A simple lower bound for the TSP Often we generate lower bounds using a decomposition strategy For example suppose a feasible solution to a problem can be decomposed into two components If these two components are optimized separately the resulting solution may not be feasible for the original problem but the resulting cost is a lower bound on the optimal cost of the original problem Consider any feasible solution to the TSP that is a tour visiting all nodes in G Suppose TOUR is a set containing all of the arcs used in the tour clearly lTOURl 71 If one arc 27 from the tour is removed the remaining structure is a TREE on G all nodes are connected and the TREE contains 71 7 1 arcs ln set terminology we could write this decomposition as TOUR TREE Z39jlz39j E A TREE The cost of a tour could then be written as follows CTOUR CTREE 0 Now let7s minimize the decomposition Clearly the minimum cost tree in a network is given by the MST Therefore a lower bound on the optimal TSP cost is the following CTSP 2 CMST c where c is the cost of the minimum cost arc not in MST Heuristics for the TSP I An aapproximation heuristic MST 2approximation Steps 1 Generate a minimum spanning tree MST of the nodes N 2 Let LIST contain two copies of each arc in the minimum spanning tree MST 3 Generate a WALK of nodes of G using each arc in LIST exactly once 111112 112n111 Note that 1 are not unique 4 Create a heuristic tour TH by following the nodes in the order speci ed by WALK but skipping repeat visits to any node the taking shortcuts77 process a Let tz39 0 for all 239 E N TH 0 b for 239 1 to 2n 71 i if tm 0 then TH TH 1 and tm 1 5 TH lt TH 11 In this method recognize that WALK does not t with our de nition of a tour since it may contain nodes that are visited more than once So we simply eliminate repeat visits in our WALK to identify TH sometimes referred to as an embedded tour Generating a walk of the nodes Generating the walk of the nodes above is always possible since the arcs in LIST form what is known as an Eulerian graph Walks in such graphs can be identi ed using a simple recursive procedure Pick an arbitrary node 01 as a starting point and create a walk of some but possibly not all of the nodes WALK1 iii102030201 Now remove the arcs you just used from LIST and examine the remaining structure You now may have additional disconnected walks that may need to be attached to nodes in the main walk For example perhaps you nd a new walk attached to 113 U314151413 Again re move these arcs from LIST Then you update WALK2 111112Ug141514113112111 Keep proceeding recursively in this fashion until no arcs are left in LIST Figure 1 The dark black lines represent the minimum spanning tree For example in Figure 1 suppose a TSP tour is started at node 1 One example of a WALK that could be generated would be WALK 1213431 This tour contains unnecessary return visits to nodes and has a total cost of 12 2 gtk 3 2 1 Applying the shortcut procedure a tour would begin at 1 and move to 2 The walk speci es a return to 1 so we look ahead to the next unvisited node which is 3 The shortest path from 2 to 3 is along arc 23 so we add this arc to the tour T is now T 12 23 Next WALK tells us to visit node 4 and since it has not yet been visited we move along the MST T 1 2 23 34 Next the WALK speci es a 10 return to 3 Since it has already been visited7 we move ahead to the next unvisited node Since all nodes have been visited7 we return to the start node 1 along the shortest path7 which happens to be arc 471 The nal tour is T 1727271 0737474717 with a cost of 10 Proof of the 2approximation The MST 2 approximation heuristic will generate a TSP tour with a cost no greater than double the optimal cost for networks satisfying the triangle inequality This is not good7 but at least its a guarantee Proof First7 we know that the heuristic tour we generated has a cost less than twice the min imum spanning tree7 since we started with a walk with cost exactly equal to 20MST and then reduced its cost by taking shortcuts due to the A inequality CTH 20MST Now7 suppose that you were to remove a single arc from the optimal traveling salesman tour the result is a tree Let7s call it TSPTREE lt7s clear that the minimum spanning tree cost is always no greater than the cost of any TSPTREE CMST S CTSPTREE and of course7 the cost of any TSPTREE is no greater than the cost of the optimal TSP tour for problems with nonnegative arc costs CTSPTREE S CTSP The result now follows CTH 20MST 20TSPTREE 20TSP B Christo des7 Heuristic Christo des7 heuristic has the best known worst case performance bound for the traveling salesman problem on complete networks satisfying the triangle inequality Similar to the Twice Around MST heuristic Christo des7 heuristic utilizes the concept of minimum spanning trees In addition the heuristic relies on the idea of minimum cost perfect matchings MCPM Consider the following de nitions and facts De nition 3 Node Degree The degree of a node i E N with respect to a set of arcs T is the number of arcs in T that are adjacent or touching node i Lemma 1 An Euler Lemma Given a set of nodes N and a set of arcs representing a spanning tree T the number of nodes with odd degree with respect to the arc set T is even De nition 4 Perfect Node Matching Given a set of nodes S such that lSl is even a perfect node matching W is a set of l node pairings such that each node in S is in emactly one pairing In a complete network each node pairing ij ij E S represents an arc in the network The cost of matching W is given by CW Zawew cij Lemma 2 Another Lemma from Euler Suppose given a complete network you nd a spanning tree T Then you nd a perfect node matching W of the nodes in N with odd degree with respect to T Now consider the set of arcs R T U W Now the nodes in N each have an even degree with respect to R and are all connected Thus a traveling salesman tour of the nodes can always be constructed using only the arcs ofR with no duplicates The above de nitions and lemmas motivate Christo des7 heuristic Here is a sketch of the method Ghristo des Heuristic Steps H Given an undirected complete network G satisfying the A inequality nd a mini mum spanning tree MST on G P Let S be the nodes of G with odd degree with respect to MST 9 Find a perfect node matching W ofthe nodes in S with minimum total cost This problem can be solved in 0n3 time by the method of Lawler 7 Generate a tour of the nodes TC using arcs in the set MST U W exactly once T0 can again be improved by introducing shortcuts to avoid revisiting nodes