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.

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.

Frontline (the programmers of Excel's solver) have several examples.
Here's one involving fuel trucks: https://www.solver.com/partial-loading-knapsack-problem
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.

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

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.

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.

Administrative Note:

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.

Please remove the link(s) from your workbook and post it again without it.

(Note: this change is not optional.)

i-nth, regarding your reporting of your post...

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.

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

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

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;

3- open a new thread with your request.

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

HTH,

Francesco