OM 300 Lecture Notes - Lecture 1: Travelling Salesman Problem, Greedy Algorithm, Operations Management
9 May 2017
School
Department
Course
Professor
Document Summary
Transportation operations: managing the shipment of goods or people as well as the vehicles and operators, two common transportation problems. Traveling salesman problem (tsp: finds the best sequence (short distance) in which to visit a specific set of locations. Vehicle routing problem (vrp: group shipments into delivery routes to minimize transportation cost or distance. Travel next to the closet, unvisited location until all locations have been visited. Finally, return to the original starting locations. 4: answer: 0-2-1-3-4-0, total distance = 12 + 5 + 8 + 4 + 15 = 44. Limit on the length of a route. Limit on vehicle capacity: volume (cid:523)(cid:498)cube-out(cid:499)(cid:524, weight (cid:523)(cid:498)weigh-out(cid:499)(cid:524) Whole grains bakery: a small bakery must deliver fresh bread to 5 major customers each morning, bakery located at origin of coordinate axis (0,0, each truck can carry no more than 300 loaves. That is, dij = dji, for all i and j. Otherwise, go back to step 1 and start another delivery route.
