Calculate combinations that leads to max intake in VBA using one column

[Will_vanthek]

Dear people,

I have a question, hope you can help me. In enclosed image I have a column with number in them, lets say 10 items.
Further I have a cell with 1 number, this is the max to be loaded: 10.000

Now, I need to find the combinations that will bring me <=10.000.
This means it can be cargo as: 1+2+5+6 or 1 + 4 +5 Etc.

All outcome, all combinations should lead towards the 10000, on top the combinations that are closest to the 10.000.
I see many tutorials doing this with two list etc, but I want to do this in one column, if this possible.

I prefer VBA code, but if otherwise possible than I hope you can help me.

greets will

 

[Eric W]

As far as the question in post #10, here's what I get when I try those same parameters:

Book1 (version 1).xlsb
	A	B	C	D	E	F	G	H	I	J	K	L
1	Cargo:				Target:	12500
2
3	1=	1000	B
4	2=	1500	B		Result:	Total	Results
5	3=	2000	P		1	12500	1	2	3	4	10
6	4=	2500	B		2	12500	1	2	4	8	10
7	5=	3000	P		3	10500	1	2	4	10
8	6=	6500	P
9	7=	9500	P
10	8=	2000	P
11	9=	5000	P
12	10=	5500	B
13
Sheet15

3 combinations with 1, 2, 4 and 10, which is what you have marked in C3:C12. None of them correspond with your results. All I can suggest is that somehow in the course of testing, you mixed up the results from different runs. I'll see what I can do about adding the Distance/Costs/Revenue.

 

[Will_vanthek]

As far as the question in post #10, here's what I get when I try those same parameters:

Book1 (version 1).xlsb
	A	B	C	D	E	F	G	H	I	J	K	L
1	Cargo:				Target:	12500
2
3	1=	1000	B
4	2=	1500	B		Result:	Total	Results
5	3=	2000	P		1	12500	1	2	3	4	10
6	4=	2500	B		2	12500	1	2	4	8	10
7	5=	3000	P		3	10500	1	2	4	10
8	6=	6500	P
9	7=	9500	P
10	8=	2000	P
11	9=	5000	P
12	10=	5500	B
13
Sheet15

3 combinations with 1, 2, 4 and 10, which is what you have marked in C3:C12. None of them correspond with your results. All I can suggest is that somehow in the course of testing, you mixed up the results from different runs. I'll see what I can do about adding the Distance/Costs/Revenue.

Thanks Eric

 

[Eric W]

Starting with this layout:

Book1 (version 1).xlsb
	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O
1	Cargo:							Target:	12500			Criteria	Mmax	Distance	Profit
2		Quantity	Status	Distance	Costs	Revenue							0	0	1
3	1=	1000	P	423	676.8	761.4
4	2=	1500	P	380	608	684
5	3=	2000	P	1100	1760	1980
6	4=	2500	B	285	456	513
7	5=	3000	P	647	1035.2	1154.6
8	6=	6500	P	1145	1832	2061
9	7=	9500	P	785	1256	1413
10	8=	2000	P	954	1526.4	1717.2
11	9=	5000	P	478	764.8	860.4
12	10=	5500	B	852	1363.2	1533.6
Sheet15

Use this macro:

Sub Combos()
Dim vals As Variant, opc As Range, dic As Object, mmax As Double, op() As Variant
Dim i As Long, s As String, c As String, w As Variant, x As Variant
Dim SortLoc As Range, SortCol As Long

    vals = Range("B3:F12").Value
    Set opc = Range("H4")
    mmax = Range("I1").Value
    Set SortLoc = Range("M2:O2")
    
    Application.ScreenUpdating = False
    opc.Resize(2 ^ UBound(vals) + 5, UBound(vals) + 5).ClearContents
    
    Set dic = CreateObject("Scripting.Dictionary")
    For i = 1 To 2 ^ UBound(vals)
        s = WorksheetFunction.Base(i, 2, UBound(vals))
        c = ""
        w = Array(0, 0, 0, 0)
        For j = 1 To UBound(vals)
            If Mid(s, UBound(vals) - j + 1, 1) = "1" Then
                c = c & j & ","
                w(0) = w(0) + vals(j, 1)    ' quantity
                w(1) = w(1) + vals(j, 3)    ' distance
                w(2) = w(2) + vals(j, 4)    ' costs
                w(3) = w(3) + vals(j, 5)    ' revenue
            Else
                If vals(j, 2) = "B" Then GoTo NextI:
            End If
        Next j
        If w(0) <= mmax Then
            c = Left(c, Len(c) - 1)
            dic(c) = w
        End If
NextI:
    Next i
    
    ReDim op(0 To dic.Count, 1 To 5)
    i = 1
    For Each x In dic
        op(i, 1) = i
        op(i, 2) = dic(x)(0)    ' quantity
        op(i, 3) = dic(x)(1)    ' distance
        op(i, 4) = dic(x)(3) - dic(x)(2) ' profit
        op(i, 5) = x            ' loads
        i = i + 1
    Next x
    
    op(0, 1) = "Result:"
    op(0, 2) = "Total"
    op(0, 3) = "Distance"
    op(0, 4) = "Profit"
    op(0, 5) = "Cargo"
    
    opc.Resize(dic.Count + 1, 5) = op
    SortCol = 1
    If SortLoc.Offset(, 1).Resize(1, 1).Value = 1 Then SortCol = 2
    If SortLoc.Offset(, 2).Resize(1, 1).Value = 1 Then SortCol = 3
    
On Error GoTo NoResults:
    opc.Offset(1, 1).Resize(dic.Count, 4).Sort Key1:=opc.Offset(1, SortCol), order1:=xlDescending
    opc.Offset(1, 4).Resize(dic.Count).TextToColumns DataType:=xlDelimited, comma:=True
        
NoResults:
    Application.ScreenUpdating = True
    
End Sub

Be sure to update the ranges at the top of the macro to match your sheet. Profit and distance seem to be closely related, since the sort order for both of them is the same.

 

[Will_vanthek]

Starting with this layout:

Book1 (version 1).xlsb
	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O
1	Cargo:							Target:	12500			Criteria	Mmax	Distance	Profit
2		Quantity	Status	Distance	Costs	Revenue							0	0	1
3	1=	1000	P	423	676.8	761.4
4	2=	1500	P	380	608	684
5	3=	2000	P	1100	1760	1980
6	4=	2500	B	285	456	513
7	5=	3000	P	647	1035.2	1154.6
8	6=	6500	P	1145	1832	2061
9	7=	9500	P	785	1256	1413
10	8=	2000	P	954	1526.4	1717.2
11	9=	5000	P	478	764.8	860.4
12	10=	5500	B	852	1363.2	1533.6
Sheet15

Use this macro:

Sub Combos()
Dim vals As Variant, opc As Range, dic As Object, mmax As Double, op() As Variant
Dim i As Long, s As String, c As String, w As Variant, x As Variant
Dim SortLoc As Range, SortCol As Long

    vals = Range("B3:F12").Value
    Set opc = Range("H4")
    mmax = Range("I1").Value
    Set SortLoc = Range("M2:O2")
   
    Application.ScreenUpdating = False
    opc.Resize(2 ^ UBound(vals) + 5, UBound(vals) + 5).ClearContents
   
    Set dic = CreateObject("Scripting.Dictionary")
    For i = 1 To 2 ^ UBound(vals)
        s = WorksheetFunction.Base(i, 2, UBound(vals))
        c = ""
        w = Array(0, 0, 0, 0)
        For j = 1 To UBound(vals)
            If Mid(s, UBound(vals) - j + 1, 1) = "1" Then
                c = c & j & ","
                w(0) = w(0) + vals(j, 1)    ' quantity
                w(1) = w(1) + vals(j, 3)    ' distance
                w(2) = w(2) + vals(j, 4)    ' costs
                w(3) = w(3) + vals(j, 5)    ' revenue
            Else
                If vals(j, 2) = "B" Then GoTo NextI:
            End If
        Next j
        If w(0) <= mmax Then
            c = Left(c, Len(c) - 1)
            dic(c) = w
        End If
NextI:
    Next i
   
    ReDim op(0 To dic.Count, 1 To 5)
    i = 1
    For Each x In dic
        op(i, 1) = i
        op(i, 2) = dic(x)(0)    ' quantity
        op(i, 3) = dic(x)(1)    ' distance
        op(i, 4) = dic(x)(3) - dic(x)(2) ' profit
        op(i, 5) = x            ' loads
        i = i + 1
    Next x
   
    op(0, 1) = "Result:"
    op(0, 2) = "Total"
    op(0, 3) = "Distance"
    op(0, 4) = "Profit"
    op(0, 5) = "Cargo"
   
    opc.Resize(dic.Count + 1, 5) = op
    SortCol = 1
    If SortLoc.Offset(, 1).Resize(1, 1).Value = 1 Then SortCol = 2
    If SortLoc.Offset(, 2).Resize(1, 1).Value = 1 Then SortCol = 3
   
On Error GoTo NoResults:
    opc.Offset(1, 1).Resize(dic.Count, 4).Sort Key1:=opc.Offset(1, SortCol), order1:=xlDescending
    opc.Offset(1, 4).Resize(dic.Count).TextToColumns DataType:=xlDelimited, comma:=True
       
NoResults:
    Application.ScreenUpdating = True
   
End Sub

Be sure to update the ranges at the top of the macro to match your sheet. Profit and distance seem to be closely related, since the sort order for both of them is the same.

Eric, something went not okay, it showed following, but the last part did not work, listing the combinations..

when looking in the code i found this:

SortCol = 1
If SortLoc.Offset(, 1).Resize(1, 1).Value = 1 Then SortCol = 2
If SortLoc.Offset(, 2).Resize(1, 1).Value = 1 Then SortCol = 3

I thin SortCol should be SortLoc, but even after changing this, it still not show the results.

hope you can shed the light

 

[Will_vanthek]

It also changed the criteria to number 2 for all.

 

[Eric W]

Those 3 lines were correct as presented. When you changed them, that caused the Criteria numbers to change to 2s. Here's what I get when I ran the macro:

Book1 (version 1).xlsb
	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q
1	Cargo:							Target:	12500			Criteria	Mmax	Distance	Profit
2		Quantity	Status	Distance	Costs	Revenue							0	0	1
3	1=	1000	P	423	676.8	761.4
4	2=	1500	P	380	608	684		Result:	Total	Distance	Profit	Cargo
5	3=	2000	P	1100	1760	1980		1	12000	3191	638.2	3	4	8	10
6	4=	2500	B	285	456	513		2	12500	3040	608	1	2	3	4	10
7	5=	3000	P	647	1035.2	1154.6		3	12500	2894	578.8	1	2	4	8	10
8	6=	6500	P	1145	1832	2061		4	11000	2660	532	1	3	4	10
9	7=	9500	P	785	1256	1413		5	11500	2617	523.4	2	3	4	10
10	8=	2000	P	954	1526.4	1717.2		6	11000	2514	502.8	1	4	8	10
11	9=	5000	P	478	764.8	860.4		7	11500	2471	494.2	2	4	8	10
12	10=	5500	B	852	1363.2	1533.6		8	10000	2237	447.4	3	4	10
13								9	12000	2207	431.4	1	4	5	10
14								10	12500	2164	422.8	2	4	5	10
15								11	10000	2091	418.2	4	8	10
16								12	10500	1940	388	1	2	4	10
17								13	11000	1784	346.8	4	5	10
18								14	9000	1560	312	1	4	10
19								15	9500	1517	303.4	2	4	10
20								16	8000	1137	227.4	4	10
21
Sheet15

As I mentioned before, make sure that the ranges in the top 4 lines of the macro point to the right cells. When testing this, I had the target cell pointing to the wrong place, so it picked up a 0 for the max quantity, so it ended up with an empty list. That's probably what you're seeing.

 

[Will_vanthek]

Eric, it worked, i had to many B instead of P to create the list, thanks I have something for you to read:

Dear Eric,

I was hoping i can explain what the end goal of my questions is, maybe you can help me with that. I am willing to pay for your efforts, so hope you have time to read this.

A shipping Line is a company with ships. Each ships has it owns specs, such as Max quantity tob e loaded.For example.

If a job ( cargo) comes up, it always has a loading port and a discharge port, quantity and the period when it needs to be loaded. Based on the Mmax of the vessel we already can find out what cargo combination can be made. Let’s say I have three identical vessels, only the position of the vessels is different. So we create three columns of cargo options.

We match in the background what vessel can take what cargo. If the cargo is bigger than 10.000 tons, i twill not show up in the list of the vessel that can only take 10.000. So we create three column(one for each vessel) and show the cargo that can be loaded by that particular vessel.

Now we matched the cargo tot he vessel based on quanity, distance or profit. This gives the operator a good view what action to take. But it has to go one step up.

We need to find the sequence based on laycan period.

A laycan period, date, week is the periode where the vessel needs to be present for loading.

When looking at above image, you can see that the laycan period follows eachother, so these 4 cargoes would be executable one after another. POL is port of loading, POD is port of discharge.

If a selection would be made based on laycan period, quantity, one could get a sailing sequence.

With the sailing sequence we could calculate the distance between two ports and cumulate them at the end. Each cargo will have its expensens and revenu, so profit of the sequence can be calculated.

But what if another cargo was entered in the column, with a laycan date and location before Rotterdam. Then the sequence would become different and we have to calculate again and see what profit this would make. At the end we calculate a top 10 with seqences, quanities and profits. This for each vessel. In the beginning we have an empty ship, so the combinations are endless, but if a cargo is booked that means that it will limit the combinations, the more is booked the lesser the options.

One can see that the same cargo can be loaded on many different vessels, depending on the vessels criteria. Once the cargo is booked ( mean a contract between shipping line and cargo owner) the cargo has tob e shipped, but not necesarely by that vessel. When it is booked and connected to vessel no. 1, i twill dissapear from the other vessels list, a recalculation has to be done.

2500 1000 1500

So, when loading all, we can calculate when the vessel is full, for example after Rotterdam the vessel with a max intake of 5000 is full, but we have to discharge in Bremen the first parcel of 2500 and re-load another parcel of 2500, so vessel full again, until after discharge the remaining cargo.

So we calculated the best option from vessel number one and suddenly another cargo pops up in the same column Then the calculation has to be re-done.
Here we have again multiple options depending on the new cargo. The sequence can be different , the intake can be different. Everytime the best options will be on top.
Of course this depends on profit, quantiy or distance. Best op top.

Distance between two ports needs to be calculated. So everytime a sequence changes the new distance from A to B to c to d etc. needs to be calculatedFor now we can take fixed numbers but we calculate on the fly with an API.

Now the question arises, can you help me building such an application. And if you can how much would it costs to help me on this?

Thanks enjoy your day.

Best regards Will

 

[Eric W]

I read your entire last post, and I thought this was where you were heading. When you kept adding requirements, it seemed you had some goal in mind. Unfortunately, this may be where I need to bow out. The level of complexity has risen to above what you can expect from a free forum. I don't have the time to devote to something this big, nor am I set up to handle contract jobs at the present time.

A few thoughts though. What I've being doing so far is what's called a knapsack problem (see Wikipedia). Solving it for one ship with a maximum of 10 different loads is not hard. I used a brute force method, examining all 1024 possible combinations, saving the valid ones, and then sorting them. Now you're looking at multiple ships, in multiple locations, that have to be at different locations at specific times to be loaded, and it also seems clear that the order that the loads are delivered will make a difference. The number of combinations just skyrocketed, and I'm not sure a brute force algorithm will work anymore. There are several improvements to my code I can think of that I didn't include because they weren't needed for a mere 1024 combinations, but would certainly be needed for bigger problems.

It seems quite likely that this is a common situation, a lot of people probably have the same requirements. Given that, it's probable that there is already some existing software you can use. I just Googled "shipping scheduling software" and found a lot of options. You'll need to see if any of them will work for you.

If you're still interested in a custom solution, check the down arrow next to "MrExcel Publishing" in the menu bar at the top of this page and select "Excel Consulting Services". I've been pretty impressed with the consultants I've seen at this site. They will be much better equipped to evaluate the scope of your project, and give you some price/time estimates. By all means, point them to this thread to give them a starting point. (Although the last time I referred someone to them, they didn't like my code! Maybe I should clean it up a bit!)

Good luck!

 

[Will_vanthek]

Dear Eric / Will
Many thanks for your message, i really appriciated what you did for me. Allow me to explain why "This" line of thinking is not in day to day business. Currently i am working on a PoC ( Proof of Concept ), that means that we will not use many great datasets, millions of records, but just limited sets to show what is feasible or not. in your answer i found some ideas about how to work this question and I am aware that a complete application would be to much work. but you could help me maybe and hopefully with smaller parts wich would fit in your brilliant code already.

The idea is not to run all the code on the same time with all variables inside, just smaller parts. ideas that can be used. For example:
Can you create multiple dictionaries in one sub? If so how does that look? If this works we could calculate three columns and show the result below the column. In code it should be run one after another.
Once the array is formed can I jump to another function with a set of variables, perform a calculation and come back and continue, line normally in a function is possible?

I had an idea, of approaching my questionaires is to treat a cargo like a container. A container with different sets of values. One could slide ( using your calculation and sequence) them in a certain position asnd let cargo01 talk to cargo02.

Because the handshake and talk to eachother, different calculations and outcomes can be found and displayed.What do you think of my idea. Just keep in mind this is for a PoC and the Brute force you use is more than welcome. Hopefully you can wrap your mind about my questions. Sorry if I ruin your weekend

Enjoy your day Eric and thanks already for the good work you already did.

 

[Eric W]

Yes, you can have more than one dictionary in a module, just give it a different name, or even make an array of dictionaries. But the dictionary was merely a useful way to store the results. With your enlarged project, something else may be preferable.

You could possibly use Class Modules to make a "container" (object) to hold a load. It would take more analysis to figure out what you want.

But I'll reiterate: this project appears that it will take more time, work, and analysis than someone will do on a volunteer basis. At least it is for me. You may wish to open a new thread with your new requirements and see if it will catch someone's interest. You can pass on the code I've provided so far, but I fear that it may not scale well. In any case, I'm out, but I wish you well in your endeavors.