OM 300 1nd Edition Lecture 14 Outline of Last Lecture I Locational Cost Volume Analysis II Center of Gravity Method III GIS Outline of Current Lecture I Transportation Operations II Traveling Salesman Problem III Vehicle Routing Problem Current Lecture Transportation Operations Managing the shipment of goods or people as well as the vehicles and operators Two common transportation problems o Traveling Salesman Problem TSP Find the best sequence shortest distance in which to visit a specific set of locations o Vehicle Routing Problem VRP Group shipments into delivery routes to minimize transportation cost or distance Traveling Salesman Problem Fine the sequence in which to visit a set of n locations that minimizes the total distance traveled A feasible TSP solution is called a tour Many different procedures for finding a TSP solutions Location 0 is the starting point Must visit locations 1 2 n dij distance between locations i and j Nearest Neighbor Procedure Heuristic o Start at location 0 o Travel next to the closest unvisited location until all locations have been visited o Finally return to the original starting location Vehicle Routing Problem Coordinate inbound LTL shipments from many suppliers automotive assemble plant These notes represent a detailed interpretation of the professor s lecture GradeBuddy is best used as a supplement to your own notes not as a substitute Coordinate outbound LTL shipments to many customers deliveries from a warehouse or plant out to customers Determine which shipments to combine on a common pick up or delivery route Determine sequence of pickups and deliveries on each route Difficult to find an optimal solution Many different heuristics available Central warehouse must make deliveries to n customers Shipment quantities are known Central warehouse has one or more delivery vehicles One or more constraints on the vehicle o Limit on the length of a route o Limit on vehicle capacity Volume cube out Weight weigh out Solving the VRP A Greedy Heuristic for the VRP Assume a single point from which all vehicles leave and return o Denote this point as location 0 Let 1 2 n denote the customer locations o d0j the length of a trip from 0 to j o d0j the length of a trip from i to j Assume symmetric distances Nearest Neighbor Heuristic for the VRP 1 Start at the central warehouse plant 2 Travel to the next closest unvisited customer until the next customer s shipment exceeds the vehicle capacity of all customers have been visited 3 Finally return to the central warehouse plant 4 If all customer orders have been delivered stop 5 Otherwise go back to step 1 and start another delivery route
View Full Document
Unlocking...