Formulating and Solving a Capacity Allocation Problem of a Plane

The passenger transport industry faces the problem of determining how to efficiently allocate transportation capacity when offering different prices or fees to their customers for a specific route. This is why they must consider sales revenues associated with each type of rate, estimated customer demand for such fees and the capacity of the transport in terms of the number of seats simultaneously. The next problem considers the formulation and computational problem of the capacity of allocation an airplane for an airline company. The complexity of the problem and the level of detail of the information is simplified for academic purposes.

Capacity Allocation Problem

Let us consider an airline that flies the Santiago (Chile) route to Bogota (Colombia) with a layover in Lima (Peru). This route uses an airplane with a capacity of 200 passengers. The sales department has estimated market prices (in dollars) for combinations of source/destination of 3 types of rates currently offered by the company: “Fee Y” (first class), “Fee B” (standard) and “Fee C” (tourist).

ticket-prices-table

Additionally and according to historical information about this route, the airline has estimated the maximum number of passages seats that will be in demand for each combination of rate on a flight segment. For example the maximum demand expected for the Santiago (SCL) to Bogota (BOG) in Fee B is 35 tickets.

max-demand-per-ticket

With this information the airline wants to determine how to allocate the capacity of the aircraft in order to provide a certain number of tickets for each type of fee per flight segment. To do this we define the following linear programming model:

Decision Variables:

Xij: Number of tickets offered in the Fee i, for the Origin-Destination segment j

Where i=1,2,3 represent the various types of fees (Y, B and C, respectively) and j=1,2,3 combinations of source-destination (SCL-LIM, LIM-BOG and SCL-BOG, respectively).

Parameters:

Using a notation with parameters, we can represent an optimization model in a compact way.

Pij: Price in US$ (Dollars) for the ticket fee i from Origin-Destination j segment

Dij: Maximum demand of tickets fee i on the Origin-Destination j segment

Objective Function:
objetive-function-plane
Constraints:

We must offer for each fee in the source-destination combinations a number of tickets that does not exceed the market demand.

max-demand

For each flight segment you must respect the total capacity of 200 passenger per aircraft.

capacity-of-a-plane

When the plane takes off from Santiago to Lima, it takes passengers for both Lima and Bogota. Therefore independently of what fee each of these passengers paid (hence the sum in fees) may not exceed the total capacity of the aircraft. This is guaranteed by the first constraint of capacity. The second capacity restriction is for the stretch from Lima to Bogota, where passengers coming from Santiago are also considered.

Finally the non-negativity conditions are defined.

non-negativity-plane

By using Solver to solve the above problem with the following optimal solution which determines how many tickets the airline should offer for each combination of rate and source destination is reached.

optimal-solution-plane-prob

The optimal value of the problem of total income (in dollars) associated with the proposed optimal solution is US$ 158,340.

Do you want to have the Excel file with the solution of this problem with Solver? Recommend us on Facebook, Google or Twitter using the social network tool at the bottom of this article and then download the file.

How to Download and Install the Trial version of Premium Solver Pro in Excel 2010

Solver is definitely next What’sBest! The most popular tool for solving optimization models using Microsoft Excel as a platform. In fact the free version of Solver we use is developed by Frontline Systems Inc., which provides a number of tools and resolution engines that are very useful when addressing problems of real life situations that are applied in the industry.

In the following article we will show you how to download and install the trial version of Premium Solver which is available for free for a period of 15 days, which allows us to solve significantly higher operational research models when it comes to the number of decision variables and constraints than those which can be solved with the traditional version of Solver. Additionally, by having improved resolution algorithms reliability of the solutions found and the processing times are more reliable. Here are the detailed instructions on how to download and install the trial version of Premium Solver Pro on a computer with an Excel 2010 version.

Step 1: Sign in Frontline Systems Inc, fill out the information required in the subscription form.

download-frontline-solvers

Step 2: Download the trial version compatible with the version of Excel that you have. In this tutorial the 64-bit version installation is shown. Once you are sure of our choice select “Download Now”.

download-a-free-trial-solve

If you have Excel 2010 and want to know how many bits you use to run your version of Excel, go to menu and select the Help option. In the lower right corner the number of bits of your version is displayed under “About Microsoft Excel”.

bits-excel

Step 3: Check your email account (which you provided in the subscription form from Step 1) and write down the 2 passwords that you have been assigned (pictured below, these have been protected with blue and red).

email-solver

Step 4: Once the download is complete run the “SolverSetup64.exe” file (or the name that corresponds to the version of Excel you are using).

solversetup64exe

Then select “Next”.

frontline-excel-solvers-64-

Now we enter the password that we have received by email (Step 3) to continue the program activation:

password-activation-solver

Then we must accept the license agreements of the program and select “Next”.

license-agreement-solver

At the moment, the program license has been activated and we must continue the installation process by selecting “OK”.

activation-solver

You must select the folder where the program will be installed and you can at this point simply select the folder that the program has selected by default.

destination-folder-solver

It’s time to select the product you wish to activate. In this case we selected “Premium Solver Pro” which corresponds to the improved version of Solver which is generally used for academic purposes.

frontline-excel-solvers

The installation wizard will ask us to confirm that we have selected the installation (Press “Install”).

install-solver

Finally we have completed the installation of the Premium Solver Pro program and we are in a position to use it to solve optimization models using Microsoft Excel as a platform.

installation-complete-solve

Example of a Product Mix Problem in Linear Programming

One of the classic applications of Linear Programming models is the product mix problem. If the quality of a product that is processed through the mixture of certain inputs can be approximated reasonably through a proportion, then a linear model may be useful. The example below shows this situation:

An oil refinery produces two types of unleaded gasoline: regular and extra, which sells to distributors in $12 and $14 per barrel, respectively. Both types are made from a national refined oil and an imported refined oil stock, that the company owns (ie by blending them), which must comply with the specifications contained in the following table:

mix-problem-data

The inventory characteristics of the refined oils are:

oil-data

We need to formulate and solve a linear programming model to maximize the weekly income of the refinery, satisfying the requirements previously detailed.

Decision Variables:

  • Xnr: Barrels of national oil used in the production of regular gasoline
  • Xne: Barrels of national oil used in the production of extra gasoline
  • Xir: Barrels of imported oil used in the production of regular gasoline
  • Xie: Barrels of imported oil used in the production of extra gasoline

Objective Function: Maximize the weekly income received by the refinery for production of regular and premium gasoline.

Max 12*(Xnr + Xir) + 14*(Xne + Xie)

Constraints:

Steam Pressure: The weighted average of the steam pressure of the different types of oils which make up the mixture should not exceed 23 units (for each type of gas).

  • (25Xnr + 15Xir) / (Xnr + Xir) <= 23
  • (25Xne + 15Xie) / (Xne + Xie) <= 23

Minimum octane rating: The weighted average of the different types octane petroleum included in the mixture must be at least 88 and 93 units for regular and extra, gasoline respectively.

  • (87Xnr + 98Xir) / (Xnr + Xir) >= 88
  • (87Xne + 98Xie) / (Xne + Xie) >= 93

Minimum and Maximum Demand: For each weekly gasoline must produce a quantity of barrels between the minimum and the maximum must be produced weekly for each gasoline type.

  • 50,000 <= Xnr + Xir <= 100,000
  • 5,000 <= Xne + Xie <= 20,000

Inventory: The availability of national and imported barrels of oil must be respected for the production of regular and premium gasoline.

  • Xnr + Xne <= 40,000
  • Xir + Xie <= 60,000

Non Negativity: The decision variables must naturally take greater than or equal to zero values.

  • Xnr, Xne, Xir, Xie >= 0

The following optimal solution and optimal value result from implementing the above model of optimization with Excel Solver:

optimal-solution-mix-proble

30,909.09 barrels of national oil should be targeted to the production of regular gasoline,  9,090.91 barrels of national oil for the production of extra gasoline, 49,090.91 barrels of imported oil for the production of regular gasoline and 10,909.09 barrels of imported for the production of extra gasoline. The previous production policy allows to generate a weekly income of MUS$1,240.

One recommendation in the computational task is to rewrite the constraints including equivalent proportions, to avoid divisions between changing cells (decision variables) and also denominators that initially adopt a value equal to zero. For example this constraint: (25Xnr + 15Xir) / (Xnr + Xir) <= 23 can be represented in analogous manner as follows: (25Xnr + 15Xir) -23 (Xnr + Xir) <= 0. Thus, it may be corroborated, for example, that in the optimal solution the steam pressure reached by the production of barrels for regular gasoline is: (25*30.909,09 + 15*49.090,91) / (30.909,09 + 49.090,91)=18,8636 (approx) that is less than or equal to the limit of 23 units.

Do you want to have the Excel file with the solution of this problem with Solver? Recommend us on Facebook, Google or Twitter using the social network tool at the bottom of this article and then download the file.

Formulation and Resolution of a model of Linear Programming to reduce the duration of a Project (Crashing)

In Project Management one of the key aspects is determining the costs to complete the project in a given time. Likewise it is of particular interest to efficiently face the problem of how to reduce the duration of it in the most economical way, on the premise that certain activities could eventually be developed in fewer time than estimated initially after assigning a greater amount of resources.  In this context the following article discusses the above problems through the formulation and computational resolution of a linear optimization model. Consider the following project consisting of 12 strictly necessary tasks, where the relationship of predecessors, times (in weeks) and costs is summarized in the table below:

normal-time-and-crash

For example the activity I can begin once completed the activities F and H and its estimated time is 1.5 weeks at a normal cost of $75. However, the activity I can rush (what is commonly known as a “crash” or “crashing”) so that its length can be 0.5 weeks, but with a higher cost of $135. Consequently the maximum allowable reduction for the task is 1 week (1.5 – 0.5 weeks) with an additional cost of $60. We will also assume that there is proportionality between the time of reduction and the additional cost, for example, if we wanted to reduce the activity I in 0.5 weeks (i.e. going from 1.5 to 1.0 weeks) the cost of the activity would be $105 ($75 + 0, 5*$60) and the additional cost (over the normal cost) is $30.

Then we will determine the duration of the project using the Critical Path Method (CPM), considering the estimated normal times for each activity.

cpm

The project has an estimated duration of 15.5 weeks and there is a unique critical path: A-B-D-G-H-I-K-L (note that all activities on this path have zero slack). The project cost is $2,620 and it is obtained simply by summing the normal costs of each of the activities.

In this context, the following Linear Programming model allows you to optimally deal with the problem of how reduce the duration of the project in the cheapest way possible, by reducing the time of activities (in particular of the activities belonging to the critical route(s).

Decision Variables:
decision-variables-crashing
Parameters:
parameters-crashing

Objective Function: We pretend to minimize the additional cost associated with the project after the “crashing” needed to complete the project in a given time. Note that we could add the normal cost of the project ($2,620) to the objective function as constant) in this case the interpretation of the optimal value would be the total cost of the project which has the duration of K weeks.

objective-function-crashing
Constraints:

Each activity can be reduced (if possible) within the maximum permissible reduction limit:

max-crashing

Predecessors relations between activities and the start time and reduction:

predecessor constraints

For example altogether inequalities (3) and (4) represent that the starting week home for  activity D will be bigger than or equal to the ending week (after any reduction) of the one that finishes later among the predecessor activities (B and C). Additionally, we have defined a “fictitious” or ending activity called “M” which has those activities that end up a route for the project (not necessarily critical) as predecessors, and allow us to estimate the duration of the project.

Definition of the objective time for the project:

constraint time objective

The computational resolution with Excel Solver can simulate for different values of the K parameter as to see how the results change. The minimum duration of the project will be given by the lower value of K that allows to generate a feasible instance for the optimization model.

Non negativity of the decision variables:

non negativity crashing

The results are shown in the table below where the minimum duration of the project corresponds to 8.5 weeks with a total cost of $ 3,295 ($ 675 in addition to the normal cost of the project). We can be see the optimal solution explicit when the activity begins and how it is reduced from its normal time, in the yellow cells (decision variables). For example the G activity begins after 2.5 weeks (counting the beginning of the project) and the normal length is reduced by 1.5 weeks (ie from a normal period of 3 to 1.5 weeks).

crashing-with-solver

Do you want to have the Excel file with the solution of this problem with Solver? Recommend us on Facebook, Google or Twitter using the social network tool at the bottom of this article and then download the file.

Model of Transportation with Transshipment solved with Excel Solver

One of the classic uses of Operations Research and, in particular of Linear Programming is to propose optimum alternatives for the logistics or transport of inputs and products from a group of suppliers to a group receivers or petitioners. When we consider that, in this process of transportation, intermediaries can participate, this is an extension of the basic model of transport which is commonly known as a model of transportation with transshipment. We will then present an applied case of this model.

Example Transportation with Transshipment

20 million barrels of oil should be shipped from Dhahran in Saudi Arabia to the cities of Rotterdam, Marseille and Naples in Europe. The orders of these three cities are 4, 12 and 4 million barrels, respectively. Below is a diagram with the possible routes:

transportation-with-transshipment

Note that for each city there is the possibility of direct shipment, i.e., that the barrels are transported directly from Dhahran. However, because of certain trade agreements, they cannot ship more than 3 million barrels through the route between Dhahran and Marseille.

On the other hand, there is a possibility of a delay either in the port of Alexandria or Suez, where storage capacity is 8 and 10 million .

Finally, note that it is possible to send barrels of oil from Marseilles to Naples. However, in Naples it is forbidden to receive more oil from Marseille than directly from Dhahran. Formulate and solve a model of linear programming that allows you to find the optimal transportation policy to comply with the requirements of demand from all the harbors.

Decision Variables:

  • X1: Barrels shipped from Dhahran to Rotterdam
  • X2: Barrels shipped from Dhahran to Marseille
  • X3: Barrels shipped from Dhahran to Naples
  • X4: Barrels shipped from Dhahran to Alexandria
  • X5: Barrels shipped from Dhahran to Suez
  • X6: Barrels shipped from Alexandria to Rotterdam
  • X7: Barrels shipped from Alexandria to Marseille
  • X8: Barrels shipped from Suez to Marseille
  • X9: Barrels shipped from Suez to Naples
  • X10: Barrels shipped from Marseille to Naples

Objective Function:

Minimize the total costs of transport given by the following expression: 7X1 + 8X2 + 15X3 + 6X4 + 5X5 + 8X6 + 7X7 + 2X8 + 6X9 + 1X10

Constrains:
Satisfy the Demand of the Harbors:

  • X1 + X6 = 4.000.000   (Rotterdam)
  • X2 + X7 + X8 – X10 = 12.000.000   (Marseille)
  • X3 + X9 + X10 = 4.000.000   (Naples)

Note that Marseille could eventually receive more than 12 million barrels of oil (demand) since this port has the ability to cater to Naples.

Balance in Transshipment:

  • X4 = X6 + X7   (Alexandria)
  • X5 = X8 + X9   (Suez)

The number of barrels that Alexandria and Suez receive, must be equal to the number each of them ship to the ports, i.e., intermediaries do not accumulate inventory at the end of the planning period. At this point it is important to note that, if it is considered an extended model which seeks to satisfy the requirements of demand for various periods, it could be admissible to store inventory in Alexandria and Suez, by changing the shape of the optimization model in this case.

Processing capacity in the Transshipment:

  • X4 <= 8.000.000   (Alexandria)
  • X5 <= 10.000.000   (Suez)

Both Alexandria and Suez cannot receive a bigger amount of barrels than the one that they can process.

Capacity of the Route between Dhahran and Marseille:

  • X2 <= 3.000.000

Through the route between Dhahran and Marseille, more than 3 million barrels cannot be shipped because of trade agreements.

Amount received in Naples:

  • X3 >= X10

In Naples it is forbidden to receive more oil from Marseille than, directly from Dhahran.

Non Negativity:

  • Xi >= 0 For All i

When implementing the previous model with Solver of Excel, the following results are obtained:

solution-transportation-with-transshipment

The solution obtained has the following structure (the value of the optimal solution is outlined above the arches):

solution-transportation