University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

170

Pages:

2
Author:

SlexTRawlaxzp

Systems Optimization: Models and Computation Network Flow"Pup" Challenge. Background: As shown in the figure, a pup is a small truck-trailer. One tractor can pull 1or 2 pups. Goal Deliver 1 "Pup" to each of 15 destinations. A network of destination and routes is defined. Between the connected destinations, we must determine the number of truck drivers (the capacity) that we will pay to be available to run that route. Obviously, each driver can transport up to 2 pups. Line Example Suppose we had a line of 6 nodes and five edges and had to deliver one pub from one end of the line to each other node. Then we would require 3 trucks on the first edge, 2 on the second and third edges, and 1 on the fourth and fifth for a total of 9 trucks (drivers). The Challenge Example The grid models a transportation system with 16 intersections (nodes) and 24 edges (routes). Each long rectangular button represents a 2-way route. We have 15 pups starting in the lower left corner. Exactly one pup must be delivered to each "intersection". A truck driver can transport 1 or 2 pups at a time. Assuming that it cost $1 dollar to dispatch any driver (truck) on any edge, what is the smallest total cost required to deliver all the pups? The applet permits exploration of the network design problem. Drivers are added to an arc by clicking on the button. The buttons labels indicate the current number of Truck Drivers (capacity). The "increment" label indicates the value of each click, and is modified via the "+" and "-" buttons. Positive labels correspond to Pups travelling North or East. Negative labels correspond to Pups travelling South or West. The Calculate button computes the current Cost (1 unit of Cost per Truck Driver), and indicates if the driver distribution is sufficient to transport 1 pup to each destination. Note: 38 is not optimal! The number on each of these arcs is the number of Truck Drivers (capacity) that will drive from one node to the next. (sign indicates direction) 15 Destinations There are 15 Pups that start out at this Node