DSA/ISE 5113 Advanced Analytics and Metaheuristics Homework #5(SOLVED)

Question 1: Case Study: Boomer Sooner Air Services (28 points)

Background

Li Chase set about the task of preparing a fuel plan for her upcoming five-leg flight to Nantucket, MA; New York City, NY; Nashville, TN; Tulsa, OK; and back. Like the other corporate pilots she works with, Ms. Chase enjoys flying a lot more than doing paperwork. But unlike some of her colleagues she rather enjoys the challenge of constructing a fuel plan.

Boomer Sooner Air Services (BSAS) operates multiple aircraft to serve the transportation needs of the corporate headquarters of Boomer, Inc. Located in Cedar Rapids, IA, the headquarters houses the executive and administrative staff of Boomer’s divisions along with a wide array of company-wide functions. Company executives routinely visit BSAS to fly to company factories, marketing facilities, and customer locations throughout the world.















Figure 1: Cessna Citation X aircraft (CE750)



1

BSAS currently operates two Cessna Citation X aircraft (CE750), among others. The CE750 often flies from Cedar Rapids to as far as South America, Europe, and western Russia. Its fuel burn rate of 310 gallons per hour coupled with its 14,000 pound capacity tank meant that it requires a fuel stop to reach these more distant destinations. It carries up to eight passengers and two pilots.

Flight Plan

In two days, both the CEO and CFO of Boomer, Inc. have a trip scheduled together for Cedar Rapids to Nantucket, the New York City area, Nashville, Tulsa, and then back to Cedar Rapids. The purpose of the trip is to pick up some key analysts and mutual fund managers in Massachusetts and New York and show them the new factories in Nashville and Tulsa and the new distribution center in Cedar Rapids. They would be picking up two passengers in Nantucket and four in New York.

As usual, BSAS will use the airport in Morriston, New Jersey, as their destination for the New York City area. Each U.S. airport carries a four-letter identifier beginning with the letter K. The upcoming four-leg flight would go from KCID to KACK to KMMU to KBNA to KTUL and back to KCID. Pilots at BSAS were responsible for creating and filing their own flight plans with the U.S. Federal Aviation Administration (FAA).

One important element of the flight plan is the takeoff and landing weight of the aircraft. To calculate these, one starts with the basic operating weight (BOW) of the aircraft and added the weights of the passengers and fuel. The BOW includes the structure of the aircraft, a stocked galley, emergency equipment, and the crew. The only weight components that vary from flight to flight are passengers and fuel. The only component that varies from takeoff to landing on a given flight is fuel.

Fuel plan and tankering

This means that one of Chase’s first tasks is to determine a fueling plan for the upcoming flights. Coming up with a fuel plan is not a joyful task for pilots because there is no straightforward ways to calculate how much fuel to take on or “upload” at the beginning of each leg. One question is whether or not to “tanker.”

Tankering refers to a practice in which extra fuel is uploaded initially to avoid having to purchase higher-priced fuel at destination airports. BSAS operated its own fuel farm at Cedar Rapids’s KCID, which kept its fuel costs low. Fuel at KCID at the time cost $4.00 a gallon. In contrast, fuel purchased at KACK cost $8.32 a gallon. As a simple example of tankering, Chase could decide to upload enough fuel at KCID to carry him through both of the first two legs, thereby avoiding buying fuel at KACK. In essence, BSAS would carry or tanker from KCID the fuel needed to fly from KACK to KMMU.

One factor working against tankering is the airport ramp fee. Ramp fees are fixed fees charged to each landing jet by the destination airport’s general-aviation terminal; the fees cover the costs of operating the terminal. For example, the ramp fee at KACK is $800, but the fee is waived with the purchase of 600 or more gallons of fuel.

To begin the process of constructing a fuel plan, Ms. Chase assembled the information in Table 1. The fuel burn numbers were fairly easy to calculate based on flight miles and aircraft. (The burn numbers included the fuel used during taxiing at the departing airport.) Although the calculation is more complicated than just multiplying miles by average gallons per mile (because extra fuel is used at takeoff), most pilots could do the calculation in their heads. Fuel prices, ramp fees, and minimum gallons needed to waive the ramp fees could all be found on the Internet.

In addition to the cost of fuel and ramp fees, Chase needs to consider the limitation of the CE750 Table 2). The fuel tank capacity is a firm physical limit, and the departure ramp and lading weight limit are structural limits developed by the manufacturer and approved by the FAA during aircraft certification. To calculate departing ramp or arrival weight, Chase added BOW to the weight of the fuel and the weight of the passengers (passenger weight calculations are based on a company-mandated figure of 200 pounds per person, including luggage).




Page 2





Table 1: Flight Details







Duration
Fuel burn
Fuel price

Minimum
Leg
Depart
Arrive
Miles

incl. taxi

Ramp fee
gallons to




(hh:mm)

($/gallon)







(pounds)


waive fee
1
KCID
KACK
1,090
2:56
5,100
4.00


2
KACK
KMMU
196
0:59
2,200
8.32
800
600
3
KMMU
KBNA
814
2:35
4,700
8.99
750
500
4
KBNA
KTUL
550
1:57
3,800
6.48
600
650
5
KTUL
KCID
485
1:48
3,600
$9.27
$800
500











Table 2: Aircraft Limitations (in pounds)

Aircraft
CE750


Maximum Ramp Weight
36,400
Maximum Landing Weight
31,800
BOW
22,800
Fuel Tank Capacity
14,000





There are two final considerations. The company requires that aircraft always land with at least 2,500 pounds of fuel. Any valid fuel plan Chase could create would have to be one in which the weight of fuel at arrival met or exceeded 2,500 pounds. This “safety stock” is there to ensure jets had enough fuel to make it to an alternate airport should there be bad weather at the destination airport. The second consideration is that the company dictated immediately bringing the fuel level up to 7,000 pounds upon arrival back at KCID. The rationale for this is that the aircraft would always be ready to go at a moment’s notice. This meant the Chase’s fuel plan should begin with the CE750 containing 7,000 pounds of fuel.

As Chase prepared to put pencil to paper to create a fuel plan for the upcoming KCID to KACK to KMMU to KBNA to KTUL and back to KCID trip, she paused to ponder why aircraft gauges measured fuel in pounds and yet fuel is sold in gallons. Like every other pilot at BSAS, she knew the importance of the number 6.7 – the weight in pounds of a gallon of jet fuel.

    (a) (20 points) Formulate a model and solve for a minimum cost fuel plan for the upcoming trip. What is the optimal fueling plan and minimal cost? Compare your results with a no “tankering” solution.

    (b) (8 points) Suppose the BSAS department manager wished to modify the model to require that “if you buy any gas, you must buy at least 200 gallons”. Formulate and solve the problem with this modification. How does this change the solution and cost for Ms. Chase’s current optimal plan?

















Page 3

Question 2: OKC Zoo (20 points)

The OKC zoo is undergoing renovations this winter and it is taking this as an opportunity to consider improving the exhibits and house different animals living together in their natural habitats. Of course this will not work in many cases since some animals naturally prey on others. The table below summarizes the various restrictions: an “X” indicates pairs of animals that cannot be housed together. Determine the smallest number of enclosures needed to house all the animals safely.

Table 3: Animals that do not play well with each other


a
b
c
d
e
f
g
h
i
j











a

X


X




X





























b
X


X


X














c







X

X





























d

X



X
























e
X







X





















f



X





X











g

X



































h


X





X












i




X


X

X
























j

X

X

X

X


Hint: This problem can be modeled as a “graph coloring” problem (a.k.a., “vertex coloring”)


Question 3: We Got Gas! (20 points)

A local oil and gas refinery company, We Got Gas! (WGG), manufactures 5 types of gasoline (A, B, C, D, and E). WGG has several thousands liters of each which must be stored in 8 different storage tanks. Each storage tank can contain at most one type of gasoline. Associated with each gasoline type and storage tank combination is a pumping cost. Each tank has a finite capacity so some gasoline types may have to be split over several storage tanks. Table 4 provides the relevant data for each type of gasoline. Formulate and solve this problem to find a minimum cost storage plan.




Table 4: Storage data




Gas


Tank-Pumping Cost per 1,000 liters ($)

Gas
Type








(liters)

1
2
3
4
5
6
7
8





















A
1
2
2
1
4
4
5
3
75,000
B
2
3
3
3
1
4
5
2
50,000
C
3
4
1
2
1
4
5
1
25,000
D
1
1
2
2
3
4
5
2
80,000
E
1
1
1
1
1
1
5
5
20,000










Tank Capacity
25,000
25,000
30,000
60,000
80,000
85,000
100,000
50,000

(liters)

































Page 4

Question 4: Galaxy Industries revisited (20 points)

Reformulate the Galaxy Industries problem from class – this time with piecewise linear cost functions and integer solutions.

Galaxy manufactures two toy guns:
Space$ Rays:
    • 8 revenue per unit

Total per unit costs: $1.50 for 0 to 125 units; $1.05 for the next 100 units; $0.95 for the next 150 units; $0.75 for any more
Zappers:$

5 revenue per unit
Total per unit costs: $1.05 for 0 to 50 units; $0.75 for the next 75 units; $1.50 for any more units
Managementˆ is seeking a production schedule to maximize the company’s profit.

Resources are limited:

– 1000 pounds of special plastic

– 40 hours of production time per week

Space Rays requires 2 pounds of plastic and 3 minutes of labor per unit.

Zappers requires 1 pound of plastic and 4 minutes of labor per unit.
    • Total production cannot exceed 700 units.

Number of units of Space Rays cannot exceed Zappers by more than 350.


Question 5: Binary Programming (12 points)

Given the following BP,

maximize 90x1 + 55x2 + 63x3 + 47x4

s.t.

7x1 + 2x2 + 8x3 + 3x4 ≤ 10

x3 + x4 ≤ 1
    • x1 + x3 ≤ 0
    • x2 + x4 ≤ 0

xi ∈ {0, 1} ∀i = 1 . . . 4


    (a) Depict the branch-and-bound (B&B) search tree. For each node, denote the solution and objective value: use zLP for the LP relaxation objective values and z∗ to denote objective values associated with incumbent solutions. Label the branches in the tree according to the constraints added. An example (with fictitious values) is provided in Figure 2.










Page 5






































Figure 2: Example B&B search tree (numbers are fictitious, example of format only)


























Page 6