asked on # Optimization Problem (via Excel Solver)

I have an optimization problem that I'd like to solve.

Please see attached JPG and two (2) spreadsheets for more details/illustration.

Basically, here's the concept:

- For disaster relief I need to transport 752,000 lbs from a ship to any region ashore

- The means for transportation are unmanned aircraft (UAC)

- I have up to 41 UAC available... each of them can carry a load of 4,000 lbs.

- Thus, to accomplish the transportation of all material, I need 188 flights (752,000 / 4,000)

- All transportation must be completed within a 72 hour time window (or 4,320 minutes)

Optimization Goals:

- The objective is to MINIMIZE the number of UAC while achieving to transport all material (752k lbs) within the given time (4,320 minutes)

Other Information:

o Attached XLS (v01) indicates that I need at least 27 UAC. However, I kinda "cheated" by having hard-coded the constraint of <=7 flights per UAC... but that's ok for right now.

Additional Information that must be considered:

- There's an additional time factor of 15 minutes of "loading time" each time when the UAC returns to the ship.

- Currently, it is estimated that each trip will take 10 hours (600 minutes) per UAC. Adding the 15 minutes makes it 615 min. per trip per UAC. So, in XLS (v02), I tried to account for that by adding the time. However, the Excel Solver solution did NOT take into account that the UAC fly simultaneously.... one after each other in 15 minute increments

My questions:

1. On a piece of paper, I estimate that I need 31 UAC (vs. 27 UAC) in order to account for the 15 minutes of loading time. How can I achieve this solution given the two provided concept in the spreadsheets?

2. How can I remove the hard-coded constraint of <=7 flights per UAC? Ideally, the optimization problem will tell me that's what I need.

Optimization-Problem-v01.xls

Optimization-Problem-v02.xls

Visualization.jpg

Please see attached JPG and two (2) spreadsheets for more details/illustration.

Basically, here's the concept:

- For disaster relief I need to transport 752,000 lbs from a ship to any region ashore

- The means for transportation are unmanned aircraft (UAC)

- I have up to 41 UAC available... each of them can carry a load of 4,000 lbs.

- Thus, to accomplish the transportation of all material, I need 188 flights (752,000 / 4,000)

- All transportation must be completed within a 72 hour time window (or 4,320 minutes)

Optimization Goals:

- The objective is to MINIMIZE the number of UAC while achieving to transport all material (752k lbs) within the given time (4,320 minutes)

Other Information:

o Attached XLS (v01) indicates that I need at least 27 UAC. However, I kinda "cheated" by having hard-coded the constraint of <=7 flights per UAC... but that's ok for right now.

Additional Information that must be considered:

- There's an additional time factor of 15 minutes of "loading time" each time when the UAC returns to the ship.

- Currently, it is estimated that each trip will take 10 hours (600 minutes) per UAC. Adding the 15 minutes makes it 615 min. per trip per UAC. So, in XLS (v02), I tried to account for that by adding the time. However, the Excel Solver solution did NOT take into account that the UAC fly simultaneously.... one after each other in 15 minute increments

My questions:

1. On a piece of paper, I estimate that I need 31 UAC (vs. 27 UAC) in order to account for the 15 minutes of loading time. How can I achieve this solution given the two provided concept in the spreadsheets?

2. How can I remove the hard-coded constraint of <=7 flights per UAC? Ideally, the optimization problem will tell me that's what I need.

Optimization-Problem-v01.xls

Optimization-Problem-v02.xls

Visualization.jpg

Microsoft ExcelMath / SciencePuzzles / Riddles

If you need to schedule take-off times every 15 minutes, then that would require a modification of the array formula in column D:

=IF(COUNTIF(C$4:C4,C4)=1,MAX(-15,D$3:D3)+15,MAX(MAX(D$3:D3)+15,LOOKUP(2,1/(C$3:C3=C4),D$3:D3)+615))

I found that 31 UAC were required

I also found that I could double-click the little square at bottom right of selection marquee in step 2 rather than dragging it down to row 191. The little spreadsheet icon of step 3 is still presented. This let me do an iteration in about 10 seconds.

Brad

=IF(COUNTIF(C$4:C4,C4)=1,M

I found that 31 UAC were required

I also found that I could double-click the little square at bottom right of selection marquee in step 2 rather than dragging it down to row 191. The little spreadsheet icon of step 3 is still presented. This let me do an iteration in about 10 seconds.

Brad

Hi

assuming you start loading the first plane at 0 minutes and they fly every 15 mins your 1st plane will be back about the time your 41st leaves so youve got the right number of planes for the quickest possible drop. The last plane should be back at the ship at 3420 minutes

To minimise planes used by taking longer on the job. Lets say you want the last plane back by 4320 minutes.

Start loading at 0 mins.

First plane goes at 15 mins.

Last plane must go at 3720 mins (4320-600)

You need a plane to leave every 19.7 mins (3720-15)/188

The 31st plane leaves at 606 mins (15 + 30x19.7)

The first plane gets back at 615 mins

so you will still need to use plane 32

Thats just plain maths. Unless you have similar problems happening often do you need a spreadsheet to work it out?

Rowan

PS Curious to know if this is a real life thing.

assuming you start loading the first plane at 0 minutes and they fly every 15 mins your 1st plane will be back about the time your 41st leaves so youve got the right number of planes for the quickest possible drop. The last plane should be back at the ship at 3420 minutes

To minimise planes used by taking longer on the job. Lets say you want the last plane back by 4320 minutes.

Start loading at 0 mins.

First plane goes at 15 mins.

Last plane must go at 3720 mins (4320-600)

You need a plane to leave every 19.7 mins (3720-15)/188

The 31st plane leaves at 606 mins (15 + 30x19.7)

The first plane gets back at 615 mins

so you will still need to use plane 32

Thats just plain maths. Unless you have similar problems happening often do you need a spreadsheet to work it out?

Rowan

PS Curious to know if this is a real life thing.

All of life is about relationships, and EE has made a viirtual community a real community. It lifts everyone's boat

William Peck

Woah sorry. I should have read your question to the end!

Rowan

Rowan

byundt:

I think this is definitely on the right track... I also (manually) determined that I needed 31 UAC.

So, to update the array formula, I copied/pasted it from the 2nd posting. Now when I execute it, I get 28... but not 31.

What am I missing to get to the 31?

EEH

I think this is definitely on the right track... I also (manually) determined that I needed 31 UAC.

So, to update the array formula, I copied/pasted it from the 2nd posting. Now when I execute it, I get 28... but not 31.

What am I missing to get to the 31?

EEH

byundt:

Quick follow-up question... there's one constraint that's currently being violated.

The whole mission must be completed within 72 hours or 4,320 minutes. So, although I'm not coming up with 31 UACs now (which I think is btw the correct answer), the last flight cannot return @ 4,665.

Thoughts?

EEH

Quick follow-up question... there's one constraint that's currently being violated.

The whole mission must be completed within 72 hours or 4,320 minutes. So, although I'm not coming up with 31 UACs now (which I think is btw the correct answer), the last flight cannot return @ 4,665.

Thoughts?

EEH

Get an unlimited membership to EE for less than $4 a week.

Unlimited question asking, solutions, articles and more.

rowanscott:

Thanks for the input... I will admit that byundt has (more than likely) solved the problem completely. There's one small piece missing..

Anyhow, yes, this is for a real disaster relief project.

EEH

Thanks for the input... I will admit that byundt has (more than likely) solved the problem completely. There's one small piece missing..

Anyhow, yes, this is for a real disaster relief project.

EEH

Hi again.

Give him the points because i have no use for them but ill just attach this just in case its of any use.

Best regards

Flight-Calculator.xlsx

Give him the points because i have no use for them but ill just attach this just in case its of any use.

Best regards

rowanscott:

Thanks... your solution seems to be interesting as well. Is it based on mere computations/formulas? Or do you use VBA code?

EEH

Thanks... your solution seems to be interesting as well. Is it based on mere computations/formulas? Or do you use VBA code?

EEH

Experts Exchange is like having an extremely knowledgeable team sitting and waiting for your call. Couldn't do my job half as well as I do without it!

James Murphy

rowanscott:

Could you please "walk me" through the process... particular how you arrived at 31?

EEH

Could you please "walk me" through the process... particular how you arrived at 31?

EEH

Yes sure. It is Formula only in the spreadsheet. No Macros

First of all down the left in the white cells are the variables you can change

Trips required is unit load/total load

Last plane return is (hours x 60)

Last plane departure is return time - flight time

Flight interval is minutes between the last plane departure and the first plane departure devided by number of flights -1 (youve got a fixed time for first plane and last plane so we know the time interval)

First Plane Return is flight time + the time it left

Then the final calculation

The first plane leaves at 15min (Load Time) lets call it s

Lets call the interval p

the second plane leaves at s+p

the 3nd plane leaves at s+2p

the nth plane leaves at s+(n-1)p

so if we call the departure time of the nth plane m

we have m= s+(n-1)p

using algebra we can change that to

n=((m-s)/p)+1

which is the formula in the cell only i see i typed in 15 instead of referenceing G5.

The integer part of n is the last plane that left before the first plane got back. So we have to round it up to get the number of planes needed.

Hope that makes sense.

Rowan

First of all down the left in the white cells are the variables you can change

Trips required is unit load/total load

Last plane return is (hours x 60)

Last plane departure is return time - flight time

Flight interval is minutes between the last plane departure and the first plane departure devided by number of flights -1 (youve got a fixed time for first plane and last plane so we know the time interval)

First Plane Return is flight time + the time it left

Then the final calculation

The first plane leaves at 15min (Load Time) lets call it s

Lets call the interval p

the second plane leaves at s+p

the 3nd plane leaves at s+2p

the nth plane leaves at s+(n-1)p

so if we call the departure time of the nth plane m

we have m= s+(n-1)p

using algebra we can change that to

n=((m-s)/p)+1

which is the formula in the cell only i see i typed in 15 instead of referenceing G5.

The integer part of n is the last plane that left before the first plane got back. So we have to round it up to get the number of planes needed.

Hope that makes sense.

Rowan

Log in or sign up to see answer

Become an EE member today7-DAY FREE TRIAL

Members can start a 7-Day Free trial then enjoy unlimited access to the platform

or

Learn why we charge membership fees

We get it - no one likes a content blocker. Take one extra minute and find out why we block content.

Not exactly the question you had in mind?

Sign up for an EE membership and get your own personalized solution. With an EE membership, you can ask unlimited troubleshooting, research, or opinion questions.

ask a question
EEH

Im not sure ive got it exactly right. We would be spacing out the planes more than the necessary 15 mins to minimise the number of planes and using the plane thats just returned to go out next but at the end when each plane is on its last flight it would be silly to delay sending it out. So it may actually be less than 31. I will give that more thought.

How much is at stake here? You could make this quite advanced.

Best regards

Rowan

Im not sure ive got it exactly right. We would be spacing out the planes more than the necessary 15 mins to minimise the number of planes and using the plane thats just returned to go out next but at the end when each plane is on its last flight it would be silly to delay sending it out. So it may actually be less than 31. I will give that more thought.

How much is at stake here? You could make this quite advanced.

Best regards

Rowan

Get an unlimited membership to EE for less than $4 a week.

Unlimited question asking, solutions, articles and more.

No sorry ignore my last comment. It works out the same.

The maths gets you the 31 planes then you would send them all out at 15 min intervals then have a break from loading while you waited for the 1st one to return.

The maths gets you the 31 planes then you would send them all out at 15 min intervals then have a break from loading while you waited for the 1st one to return.

Hi EEH

Ive done another example using macros. Fills in a table showing flight numbers, plane numbers and departure times in minutes.

Uses class modules.

Hope it helps somebody

Rowan

Flight-Calculator.xlsm

Ive done another example using macros. Fills in a table showing flight numbers, plane numbers and departure times in minutes.

Uses class modules.

Hope it helps somebody

Rowan

rowanscott:

Rowan... thanks for the additional XLS with macros... if I needed to tweak my variables (e.g., have less than 41 aircraft available, the macro blows up... presume it would be the same if I had more).

Thoughts?

Btw, given this is an actual work problem that will be helped for determining disaster relief, the model will potentially help some peoples' lives.

EEH

Rowan... thanks for the additional XLS with macros... if I needed to tweak my variables (e.g., have less than 41 aircraft available, the macro blows up... presume it would be the same if I had more).

Thoughts?

Btw, given this is an actual work problem that will be helped for determining disaster relief, the model will potentially help some peoples' lives.

EEH

This is the best money I have ever spent. I cannot not tell you how many times these folks have saved my bacon. I learn so much from the contributors.

rwheeler23

Thanks, byundt!!

rowanscott -- thanks for your contributions.

Hi EEH

You are welcome

Yes i havent done any error handling and the variables have to be within a certain range for the maths to work. It should work down to 31 planes though if the other variables are the same. If it cant be completed in the given time frame it will give a macro error but this can be handled of course.

Im willing to volunteer to work with someone to develop it to whatever is required if they feel its worth it.

Best regards

You are welcome

Yes i havent done any error handling and the variables have to be within a certain range for the maths to work. It should work down to 31 planes though if the other variables are the same. If it cant be completed in the given time frame it will give a macro error but this can be handled of course.

Im willing to volunteer to work with someone to develop it to whatever is required if they feel its worth it.

Best regards

Get an unlimited membership to EE for less than $4 a week.

Unlimited question asking, solutions, articles and more.

I listed flight numbers 1 through 188 in B4:B191, UAC#1 through 41 in column C and departure time in column D. The departure time used the array formula in cell D4 (copied down):

=IF(COUNTIF(C$4:C4,C4)=1,0

The trick to copying down UAC numbers in repeating groups of 1 through xx is:

1) Select cells C4:C44 (the numbers 1 through 41)

2) Drag the little square at bottom right corner of selection marquee down through row 191

3) Click on the little icon (looks like a spreadsheet with + sign) to right of selection marquee, and choose option to Copy

The brute force technique is to follow steps 1-3 for ever smaller blocks of UAC numbers. When the maximum value in column D exceeds your 4320 minute allowable time (I used a MAX formula in cell E7), then you need at least one more UAC.

FWIW, I used Solver and tried to minimize the number of UAC--but the answer was always the starting point.