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
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,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
=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.
Woah sorry. I should have read your question to the end!
Rowan
Rowan
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
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
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
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
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
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
Flight-Calculator.xlsx
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
Thanks... your solution seems to be interesting as well. Is it based on mere computations/formulas? Or do you use VBA code?
EEH
ASKER
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
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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
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
Flight-Calculator.xlsm
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
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
ASKER
Thanks, byundt!!
ASKER
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
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.
Optimization-Problem-v01Q2725110.xlsx