Avatar of ExpExchHelp
ExpExchHelp
Flag for United States of America 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
Microsoft ExcelMath / SciencePuzzles / Riddles

Avatar of undefined
Last Comment
Rowan Scott

8/22/2022 - Mon
byundt

I'm not sure that you need Solver for this problem. Brute force is pretty quick.

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,LOOKUP(2,1/(C$3:C3=C4),D$3:D3)+615)                 'Returns 615 minutes after last departure of this UAC

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.
Optimization-Problem-v01Q2725110.xlsx
byundt

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
Rowan Scott

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.
All of life is about relationships, and EE has made a viirtual community a real community. It lifts everyone's boat
William Peck
Rowan Scott

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

ASKER
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
ExpExchHelp

ASKER
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
Get an unlimited membership to EE for less than $4 a week.
Unlimited question asking, solutions, articles and more.
ExpExchHelp

ASKER
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
Rowan Scott

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
ExpExchHelp

ASKER
rowanscott:

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
ExpExchHelp

ASKER
rowanscott:

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

EEH
Rowan Scott

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
ASKER CERTIFIED SOLUTION
byundt

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
Sign up - Free for 7 days
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
Rowan Scott

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
Get an unlimited membership to EE for less than $4 a week.
Unlimited question asking, solutions, articles and more.
Rowan Scott

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.
Rowan Scott

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
ExpExchHelp

ASKER
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
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
ExpExchHelp

ASKER
Thanks, byundt!!
ExpExchHelp

ASKER
rowanscott -- thanks for your contributions.
Rowan Scott

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
Get an unlimited membership to EE for less than $4 a week.
Unlimited question asking, solutions, articles and more.