ISyE 6203 - Transportation and Supply Chain Systems
Spring 2022
Homework 6
Only the first 5 problems will be graded. Problems 6 and 7 are meant to be for practice
purposes and you do not need to submit your proposed solutions. Solutions will be provided
for the 7 exercises.
1. Two reservoirs are available to supply the water needs of three cities: Atlanta, Charlotte,
and Savannah. Each reservoir can supply up to 50 million gallons of water per day. Each
city would like to receive 40 million gallons per day. For every million gallons per day
of unmet demand there is a penalty. At Atlanta the penalty is $40; at Charlotte it is $30
and at Savannah the penalty is $35. The cost of transporting 1 million gallons of water from
Reservoir 1 to Atlanta is $17, to Charlotte $13 and to Savannah $20. The cost of transporting 1
million gallons of water from Reservoir 2 to Atlanta is $19, to Charlotte $15 and to Savannah
$14.
Additionally, the pipelines from each reservoir to each city have a capacity of 30 million gal-
lons of water per day and the pipeline operators require a minimum daily flow of 5 million
gallons.
(a) Draw the appropriate network of a minimum cost network flow model that can be
used to determine the least-cost policy to satisfy the daily water demands of the cities.
Clearly indicate the real-world decisions that your flows represent, describe the cost,
lower bound and upper bound of each arc and the net supply of each node.
(b) How would you modify your graph if additional water could be supplied from a third
reservoir and transferred to any of the two original reservoirs at an additional cost of
$38 per each million gallons of water per day? Draw the new network and specify all
costs, lower bounds, upper bounds and net supplies.
2. A sports tournament has teams 0, 1, . . . , n. At a midway point in the season, each team i has
wi ∈ Z+ wins, and each pair i, j has gi,j ∈ Z+ games left to play (we define the pairs as (i, j)
with i < j). A team wins the league if it finishes with the most wins (or tied for the most).
You’d like to know whether team 0 is already eliminated, i.e. if it cannot finish with the
most wins. Model this as a max flow problem. Your answer should clearly explain how to
construct the network and it also needs to explain what is the condition (i.e. objective value)
that certifies team 0 has already been eliminated. (Hint: Start with a bipartite graph having
nodes 1, . . . , n on the left and pairs i, j for 1 ≤ i < j ≤ n on the right. You may need more
nodes. Your flow should try to find a way to “spread” remaining games’ wins around so no
team finishes with more wins than team 0)
3. Consider the following restricted version of the TSP: Thinking of the route’s start at the
depot as position 0, suppose you have decided which customer you’ll visit in each of the
even stops on the route. To make things simple, well say customer 2 is second, 4 is fourth,
and so on. However, you can choose where in the tour you’ll place each of the odd-labeled
customers. In other words, you have a partial tour that looks like (0, ?, 2, ?, 4, ?, . . . , 0); for
example, for n = 5 it would be (0, ?, 2, ?, 4, ?, 0). If the number n of customers is even then the
partial tour ends with (. . . , n, 0), otherwise it ends with (. . . , n− 1, ?, 0). You want to choose
positions for the odd-labeled customers to complete the partial tour at minimum cost. You
can assume that we know the distances di,j between each pair of customers and between
the depot and the customers. Formulate this problem as a minimum cost network flow.
Clearly explain your node set, arc set, and network parameters, and justify your answer.
4. Table 1 that has nodes’ locations, where node 0 represents a depot and all other nodes rep-
resent the location of a customer. The goal is to construct a tour that starts at the depot and
serves all customers.
Node X-coordinate Y-coordinate
0 50 50
1 11 43
2 56 22
3 35 20
4 33 48
5 96 81
6 87 20
7 68 98
8 52 93
9 32 78
10 11 49
11 94 67
12 89 15
13 0 52
14 28 28
15 18 39
16 13 23
17 87 13
18 9 38
19 18 21
20 90 56
21 4 99
22 34 63
23 22 3
24 76 18
Table 1: Coordinates of the depot and the customers
(a) Suppose the cost to travel between any pair of locations is given by the Manhattan met-
ric, that is, the rectilinear distance between them (This is the sum of the horizontal and
vertical distances between the points, and is used in urban logistics to model travel time
between locations in a city). Run the Nearest Neighbor and Cheapest Insertion heuris-
tics using the depot as a starting point; report the heuristics’ partial solution after every
iteration, the final solutions, and compare their costs. (Hint: Use a programming lan-
guage that allows you to compute the distances and code the heuristic methods. That
way you can save time for (b). This is not required (i.e. you can solve the problem by
hand) but it would help you to save time and reduce the probability of small mistakes.)
(b) Repeat (a) using the Chebyshev metric instead. This metric, also called the max-norm,
measures the distance between two points as the maximum of the horizontal and ver-
tical distance, and has a variety of applications, including in manufacturing, material
handling, and other industrial logistics settings.
(c) For the four solutions that you obtained (the two heuristics for both (a) and (b)), identify
a 2-opt improvement step and list the improvement obtained (distance-wise) as well as
the new tour, or verify that none exists.
5. Assume we have a directed graph G = (N, A), where N = 0, 1, . . . , n and the depot corre-
sponds to node 0. For each arc a = (i → j) in A we have a distance da > 0. We aim to solve
the TSP for this problem.
(a) Model the TSP as a shortest path problem. You must create a modified directed graph
G′ = (N′, A′) with both the node set and arc set modified with respect to N and A
respectively. Specify the start and end of the shortest path that you need to compute in
G′ to get the TSP on G (Hint: Split each node in N into two nodes. All arcs in A have
a corresponding arc in A′. You also need to add more arcs, and some arcs may have
negative distances).
(b) Your answer in (a) models the TSP as a Shortest Path problem with a similar number of
nodes. From class we know that solving the TSP is harder than solving a network flow.
Do we have a contradiction?
6. A company manufactures backpacks for hikers. The demand for its products occurs from
April to June of each year. The company estimates the demand for the three months to
be 100, 180 and 300 units, respectively. The company uses part-time labor to manufacture
the backpacks and, as such, its production capacity varies monthly. It is estimated that the
company can manufacture 130, 290 and 180 units in April, May and June, respectively. Be-
cause the production capacity and demand for the different months do not match, a current
month’s demand may be satisfied in one of three ways:
• From current’s month production
• From prior’s month production (i.e. items kept in inventory)
• From future’s month production (i.e. backorders fulfilled at a later month)
The production cost per backpack is $40. The cost of holding backpacks in inventory is $0.5
per backpack per month. Backorder penalty costs are estimated to be $2 per backpack per
month of delay.
Our goal is to minimize the total costs to fulfill the customers’ demand. Model this as a
minimum cost network flow model and draw the appropriate network. Clearly indicate
the real-world decisions that your flows represent,plus also the costs, upper bounds, lower
bounds for each arc, and the appropriate net supplies of each node.
7. Chicken feed is transported by trucks from three silos to four chicken farms. Some of the
silos cannot ship directly to some of the farms. The capacities on the other routes are limited
by the number of trucks available and the number of trips made daily. Table 2 shows the
daily amounts of supply at the silos and demand at the farms (in thousand of pounds). The
cell entries specify the daily capacities of the associated routes.
Silos (S) / Farms (F) F1 F2 F3 F4 Silo Supply
S1 30 5 0 40 20
S2 0 0 5 90 20
S3 100 40 30 40 200
Farm Demand 200 10 60 20 —
Table 2: Silos’ and Farms’ information
Additionally, transshipping is allowed between silos 1 and 2 and silos 2 and 3. Furthermore,
transshipping is also allowed between farms 1 and 2, farms 2 and 3, farms 3 and 4. The
capacity of any of the transshipping routes is 50.
Draw the appropriate network of a maximum flow model that can be used to determine the
schedule that satisfies the most daily demand. Clearly indicate the real-world decisions that
your flows represent, label all arcs with capacities, and clearly identify your source and your
sink.