Question

You are in charge of transportation of a product for company A. The company has three production facilities across the state of Georgia, and two cross-docks that receive product from each of the production facilities and then distribute it to three retail stores. Every production facility can send their product to either cross-dock, but cross-dock 1 can only satisfy the demand of retailers 1 and 2, while cross-dock 2 can satisfy the demand of retailers 2 and 3. Table 1 shows the production capacity of each production facility over the planning horizon of four weeks, and Table 2 shows the demand of each retailer for the planning horizon. Retailers demand must be met on time without backlogging.

Period Facility Facility 4. 2 4 P1500 420 470 450 P2850 780 740 820 P3400 450 430 480 R1 420 490 420 470 R2710 820 720 790 R3620 340 500 490 Table 1: Production Capacity Table 2: Retailer Demand

The figure below shows the layout of the company’s network:

  

     

Product is sent by truck between facilities with each pair of facilities having different capacities and transportation cost per unit of product. Table 3 show the capacity and cost for each facility pair in the network; these are the same for each week in the planning horizon.

Model this problem as a minimum cost network flow problem. In your network, nodes should represent facility-week combinations so you can track flows at different points in the horizon.

Answer 1

Cost As A Priority

Jocelyn would like to apply at MGM Manufacturing to become their transportation manager. She's heard that they prefer to use the minimum cost method for solving their transportation problems, but she hasn't had an opportunity to use that method at her current position. She seeks help from Bill a former colleague who she knows has used it. Let's listen in:

Bill says: Well, Jocelyn, the minimum cost method, sometimes called the minimum cell cost method or least cost method is used when the priority is to reduce costs for distribution of materials. As you know, you can use other methods if the priority is time savings rather than cost savings. But it looks like MGM Manufacturing wants to distribute their product for as little cost as possible, thus reducing the overall cost of the product. Let's look at a problem I had just last week.

Constraints

In the case of the recent problem I had, there were six constraints, three from the supplier and three from the destination. Constraints are the limitations of the distribution such as how much a factory can supply and how much of the product a given facility needs. Let's take a look at the constraints for my transportation problem:

Supply constraints:

• Orlando supplier can produce fifteen truckloads of the product.
• Baltimore supplier can produce thirty truckloads of the product.
• Boston supplier can produce twenty truckloads of the product.

Destination constraints:

• Las Vegas needs five truckloads
• Seattle needs twenty truckloads
• St. Louis needs forty truckloads

I created a transportation matrix which is just a simple table that shows all constraints:

Destinations Las Vegas Seattle St. Louis Supply Orlando Baltimore Boston 15 30 20 Demand 5 20 40

Cost Information

Once I knew my constraints, I gathered information on the cost for delivery from each supplier to each destination and added that to my matrix (in red):

Destinations 15 45 30 Las Vegas Seattle St. Louis Supply 35 60 20 15 30 20 n Orlando Baltimore Boston 60 30 90 Demand 20 40

Now that I have all the information in my matrix, I can solve the transportation problem using the least cost or minimum cost method.

Solve the Problem

I start out by looking for the cell with the lowest cost for transportation. In this case, it's the route from Orlando to Las Vegas at a cost of fifteen, so I want to fill as much of the Las Vegas demand with my supply from Orlando. Orlando can supply fifteen but Las Vegas only needs five, so I fill that in (in blue) and cross out the demand for Las Vegas:

Destinations Las Vegas Seattle St. Louis Supply Orlando 15 5 60 30 90 35 60 20 15 30 20 Baltimore 45 Boston 30 Demand 5 20 40

Now I go on to the next lowest cost which is the Boston to St. Louis route for a cost of twenty. Boston can supply twenty but St. Louis needs forty, so I will assign all of Boston's supply to St. Louis which crosses out Boston's supply:

Destinations Las Vegas Seattle St. Louis Supply Orlando15 5 60 35 Batimore 45 Boston 15 30 60 30 30 90 20 20 20 Demand s 20 40

I continue in the same manner, looking for each cell that is the least expensive and assign as much as I can from the supplier to meet the demand of the destination.

Both the Boston to Las Vegas and the Baltimore to Seattle routes have a cost of thirty, but the Las Vegas demand has already been filled, so I can move directly to the Baltimore/Seattle route. Seattle needs twenty and Baltimore has thirty so I fill the Seattle demand from Baltimore and cross out the Seattle demand: