# maximize the mass yield of each truck

1. ## maximize the mass yield of each truck

I would consider my Excel skills as "average". I have not ventured into the world of Macro's yet, or any kind of special programming. So, the reason for my question might have something to do with a lack of knowledge. I am really hoping that I might be able to learn from this experience, and would greatly appreciate any assistance. I am trying to understand the concepts pertaining to the solution to the problem presented below and so I have grossly simplified the problem. But here it goes:

Problem:

I have a number of consignments that need to be delivered to customers across the country. The trucks to be used for shipping can handle a maximum of 30 tons. Each "JOB #" needs to be loaded onto a truck. Can Excel be used to tell me: Which jobs should be paired together with which truck, in order to maximize the mass yield (ie which combinations of "JOB #" will get me as close to 30 as possible)?

You might notice that some of the "JOB #'s" exceed the 30 ton limit - which means they will need to be split over more than 1 truck. In the logical solution, these split jobs are indicated by the percentage associated with the JOB. Eg: TRUCK 2, JOB 16 (46.37%) = 0.4637*64.7 = 30 (TONS)

Can excel be used to help me solve this problem, using formula's? Or does one have to solve this manually?

Any and all input will be greatly appreciated. Thank you for your time.

2. ## Re: maximize the mass yield of each truck

Welcome to the forum.

We would very much like to help you with your query, however the thread title does not really convey what your request is about. Tell us what you are trying to do, not how you think it should be done.

Please take a moment to amend your thread title. Make sure that the title properly explains your request. Your title should be explicit and not be generic (this includes function names used without an indication of what you are trying to achieve).

Please see Forum Rule #1 about proper thread titles and adjust accordingly. To edit the thread title, open the original post to edit and then click on Go Advanced (bottom right) to access the area where you can edit your title.

As you are new I did it for you. Please read forum rules

3. ## Re: maximize the mass yield of each truck

It's a variation of well known "Knapsack Problem"
But your case could be a bit less demanding (in terms of computing power) than the original one, as if one load could be served by single truck, it can be splitted into two or more trucks (Like Job 6). May be it could be well programmed in Solver or may be a custom made macro will be better suited to this task. Anyway, I don't think that using just formulas one could present an elegant solution to the problem.

4. ## Re: maximize the mass yield of each truck

Thank you for the replies! I have read through the list of rules. My apologies! I figured that a catchy title could draw attention. I'll be more concise in future posts I am not too familiar with the Knapsack problem, however - I am under no illusion that this problem is unique. I just lack the experience to formulate and implement the solution to the problem. My hope, is that an experienced Excel user might be familiar with the problem, might have a solution, and might be willing to amend the attached spreadsheet (maybe, just for one truck?), so that I can see how the solution works, and potentially allow me to ask questions, so that I may learn.

Thank you for the insight. Looking forward to hearing from you!

5. ## Re: maximize the mass yield of each truck

Frontline (the programmers of Excel's solver) have several examples.
Here are some other logistics examples: https://www.solver.com/optimization-...stics-examples
Solver can often be used for these. If it can be used to solve your problem, I would expect it to be designed and programmed similar to these.

6. ## Re: maximize the mass yield of each truck

As I have not really solved the OP's problem i.e. a maximum of 3 loads for each truck I've deleted the downloaded file. I'll have a rethink of the problem and see if I can find a solution that does what the OP wanted.

Alf

7. ## Re: maximize the mass yield of each truck

Hi Alf, Thanks very much for looking into this problem. Is there any chance that you've had time to think about the problem? Do you think that it has an Excel solution? Or will it have to be solved using logic?

8. ## Re: maximize the mass yield of each truck

Take a look at the attached solution. It uses OpenSolver, since there are too many variables.

The problem can be solved with Simplex algorithm, and you can change number of jobs, mass of transported goods and occupation percentage.

Actually, I have taken a shortcut in building the model: if you look carefully, you will realize that it is still possible to have more than 3 jobs per truck, even when the constraint is satisfied (anyhow this does not happen in the loaded solution).

If you want, you can devise a constraint in order to be sure that the number of jobs is correctly calculated. Please remember that it should always be expressed with linear formulas, if you want to stick to Simplex.

HTH

Francesco

P.S. OpenSolver is a free Excel add-in, you can download it here. Once installed and loaded through Excel's add-in interface, you will be able to run models already defined in the worksheet. The input mask closely resembles the original one, and there are no limits on the number of variables and constraints.

9. ## Re: maximize the mass yield of each truck

Here's a model that illustrates how we can solve the problem. That is:
- The model decides how many trucks are required.
- Each truck's capacity usage is at least 90%.
- Each job is split into no more than 3 parts.
- The model minimises both: the number of trucks required (primary objective) and the total number of job parts (secondary objective).

The model requires OpenSolver. The formulation is a mixed integer program, so an optimal solution is guaranteed (in theory).
If we allow the model a lot of freedom, then finding an optimal solution takes about 30 minutes. Given what we can learn from an initial attempt at finding a solution, we can constrain the model more tightly, so an optimal solution can be found in 5 seconds.

Workbook containing link to commercial site removed.

10. ## Re: maximize the mass yield of each truck

Welcome to the forum.

Unfortunately your attachment does not comply with Rule #10 of our Forum RULES:

Do not put links to commercial sites or services or to competing forums in signatures and posts.

We do not allow advertising, the promotion of your own commercial ventures or the deliberate promotion of other competing fora here. The sane applies to commercial links ‘hidden’ in workbooks.

(Note: this change is not optional.)

11. ## Re: maximize the mass yield of each truck

I would like to have the opinion of a Moderator regarding the attached worksheet, which contains a reference to a commercial site: url removed

Does this violate rule 10

10. Do not put links to commercial sites or services or to competing forums in signatures and posts.

or could I sponsor my services as well, if a I put the reference in the attachment?

Francesco
This is a public forum, offering free excel help. As such we do not allow advertising of other sites or of offers of commercial help to our members. You are actually quite fortunate that Ali did not issue an instant ban for blatantly ignoring our rules and posting links to other sites.

12. ## Re: maximize the mass yield of each truck

Francesco - Thank you for your proposed solution! If I may ask, it seems that OpenSolver can only have one objective cell. In your example - what is the object cell?

13. ## Re: maximize the mass yield of each truck

Originally Posted by SheldonNyce
If I may ask, it seems that OpenSolver can only have one objective cell. In your example - what is the object cell?
Both Solver and OpenSolver can have at most one cell containing the quantity that should be maximized/minimized/equalled to something.

But you can build (and solve) a model without an objective, that is, simply forcing Solver to find values for the variables that will satisfy all the constraints, as long as they define the problem properly. This is a not so well known trick that may sometimes come handy, if you know what you are doing.

However, a much better model would seek to maximize/minimize some quantity, and this is exactly what you will find in the attached solution.
I have arbitrarily decided that we should split JOB 13 and 16 in as few fractions as possible among the trucks. Just because your logistics company is a bit careless, you know.

First of all, in the previous workbook you could have, in one or more trucks, a small fraction of JOB 13 and 16 and two more full jobs, so that the true total number would be 4, but their sum still be less than 3. This is clearly not we are looking for, so we need to modify a little the model.
For this reason, there are now two more rows of binary variables: they will switch to 1 as soon as the respective continuous one is greater than zero, thanks to two more constraints. Luckily, these constraints can be still expressed with a linear formula, and we can use CBC engine, so that we are sure our solution is optimal (even though it may not be unique). With this setup, it is found in less than one second.

Let me know if you need more details.

HTH

Francesco

14. ## Re: maximize the mass yield of each truck

Thank you so much for the responses!

Hydraulics - you have come up with an extremely elegant solution, and I thank you for your time in helping me solve the problem.

I would like to propose an increase in complexity. Please see the attached workbook with the problem statement and description of the goals.

In essence; now that we are able to load the trucks in terms of the optimised yield, we would like to consider loading the truck in terms of job priority,
distance between job delivery sites, and in terms of the optimised yield for the trucks. Is there an Excel solution for this problem, as eloquent as the solution prepared
in the FREIGHT EXAMPLE (Hydr3).xlsx by Hydraulics?

I thank you for entertaining this thread, and look forward to hearing from you.

Kind Regards to all,

Sheldon

15. ## Re: maximize the mass yield of each truck

Originally Posted by SheldonNyce
I would like to propose an increase in complexity.

[...]

I thank you for entertaining this thread, and look forward to hearing from you.
If your original question has been addressed, you may (not necessarily in this order):

1- mark the thread as SOLVED;

2- add reputation to anyone who helped you in solving your problem;

Are you looking for an approximate solution to your Vehicle Routing Problem, or the best one?

HTH,

Francesco

16. ## Re: maximize the mass yield of each truck

1 - mark the thread as SOLVED; (DONE, I think?)

2- add reputation to anyone who helped you in solving your problem; (DONE)

Are you looking for an approximate solution to your Vehicle Routing Problem, or the best one? - An approximate solution would be very helpful. The best solution would, of coarse, be most favorable. But any/all assistance will be most appreciated. Thank you for your help.

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts

Search Engine Friendly URLs by vBSEO 3.6.0 RC 1