R
My first thought was
select
from
The "best solution" part is defined in the question - the smallest difference between the most loaded and least loaded trucks. The other bit - all combinations - caused me pause for thought.
Consider a situation where we have three orders A, B and C and three trucks. The possibilities are
Truck 1 Truck 2 Truck 3
------- ------- -------
A B C
A C B
B A C
B C A
C A B
C B A
AB C -
AB - C
C AB -
- AB C
C - AB
- C AB
AC B -
AC - B
B AC -
- AC B
B - AC
- B AC
BC A -
BC - A
A BC -
- BC A
A - BC
- A BC
ABC - -
- ABC -
- - ABC
Table A: all permutations.
Many of these are symmetric. The first six rows, for example, differ only in which truck each order is placed. Since the trucks are fungible these arrangemets will produce the same outcome. I shall ignore this for now.
There are known queries for producing permutations and combinations. However, these will produce arrangements within a single bucket. For this problem I need arrangements across multiple buckets.
Looking at the output from the standard "all combinations" query
;with Numbers as
(
select n = 1
union
select 2
union
select 3
)
select
a.n,
b.n,
c.n
from Numbers as a
cross join Numbers as b
cross join Numbers as c
order by 1, 2, 3;
n n n
--- --- ---
1 1 1
1 1 2
1 1 3
1 2 1
3 2 3
3 3 1
3 3 2
3 3 3
Table B: cross join of three values.
I noted the results formed the same pattern as Table A. By making the congnitive leap of considering each column to be an Order1, the values to say which truck will hold that Order, and a row to be an arrangement of Orders within trucks. The query then becomes
select
Arrangement = ROW_NUMBER() over(order by (select null)),
First_order_goes_in = a.TruckNumber,
Second_order_goes_in = b.TruckNumber,
Third_order_goes_in = c.TruckNumber
from Trucks a -- aka Numbers in Table B
cross join Trucks b
cross join Trucks c
Arrangement First_order_goes_in Second_order_goes_in Third_order_goes_in
----------- ------------------- -------------------- -------------------
1 1 1 1
2 1 1 2
3 1 1 3
4 1 2 1
Query C: Orders in trucks.
Expaning this to cover the fourteen Orders in the example data, and simplifying the names we get this:
;with Trucks as
(
select *
from (values (1), (2), (3)) as T(TruckNumber)
)
select
arrangement = ROW_NUMBER() over(order by (select null)),
First = a.TruckNumber,
Second = b.TruckNumber,
Third = c.TruckNumber,
Fourth = d.TruckNumber,
Fifth = e.TruckNumber,
Sixth = f.TruckNumber,
Seventh = g.TruckNumber,
Eigth = h.TruckNumber,
Ninth = i.TruckNumber,
Tenth = j.TruckNumber,
Eleventh = k.TruckNumber,
Twelth = l.TruckNumber,
Thirteenth = m.TruckNumber,
Fourteenth = n.TruckNumber
into #Arrangements
from Trucks a
cross join Trucks b
cross join Trucks c
cross join Trucks d
cross join Trucks e
cross join Trucks f
cross join Trucks g
cross join Trucks h
cross join Trucks i
cross join Trucks j
cross join Trucks k
cross join Trucks l
cross join Trucks m
cross join Trucks n;
Query D: Orders spread over trucks.
I choose to hold the intermediate results in temporary tables for convenience.
Subsequent steps will be much easier if the data is first UNPIVOTED.
select
Arrangement,
TruckNumber,
ItemNumber = case NewColumn
when 'First' then 1
when 'Second' then 2
when 'Third' then 3
when 'Fourth' then 4
when 'Fifth' then 5
when 'Sixth' then 6
when 'Seventh' then 7
when 'Eigth' then 8
when 'Ninth' then 9
when 'Tenth' then 10
when 'Eleventh' then 11
when 'Twelth' then 12
when 'Thirteenth' then 13
when 'Fourteenth' then 14
else -1
end
into #FilledTrucks
from #Arrangements
unpivot
(
TruckNumber
for NewColumn IN
(
First,
Second,
Third,
Fourth,
Fifth,
Sixth,
Seventh,
Eigth,
Ninth,
Tenth,
Eleventh,
Twelth,
Thirteenth,
Fourteenth
)
) as q;
Query E: Filled trucks, unpivoted.
Weights can be introduced by joining to the Orders table.
select
ft.arrangement,
ft.TruckNumber,
TruckWeight = sum(i.Size)
into #TruckWeights
from #FilledTrucks as ft
inner join #Order as i
on i.OrderId = ft.ItemNumber
group by
ft.arrangement,
ft.TruckNumber;
Query F: truck weights
The question can now be answered by finding the arrangement(s) which have the smallest difference between most-loaded and least-loaded trucks
select
Arrangement,
LightestTruck = MIN(TruckWeight),
HeaviestTruck = MAX(TruckWeight),
Delta = MAX(TruckWeight) - MIN(TruckWeight)
from #TruckWeights
group by
arrangement
order by
4 ASC;
Query G: most balanced arrangements
Discussion
There are a great many problems with this. First it is a brute-force algorithm. The number of rows in the working tables is exponential in the number of trucks and orders. The number of rows in #Arrangements is (number of trucks)^(number of orders). This will not scale well.
Second is that the SQL queries have the number of Orders embedded in them. The only way around this is to use dynamic SQL, which has problems of its own. If the number of orders is in the thousands there may come a time when the generated SQL becomes too long.
Third is the redundancy in the arrangements. This bloats the intermediate tables increasing runtime hugely.
Fourth, many rows in #Arrangements leave one or more trucks empty. This cannot possibly be the optimum configuration. It would be easy to filter out these rows upon creation. I've chosen not to do so to keep the code simpler and focused.
On the up side this handles negative weights, should your enterprise ever start shipping filled helium baloons!
Thoughts
If there were a way to populate #FilledTrucks directly from the list of trucks and Orders I think the worst of these concerns would be managable. Sadly my immagination stumbled on that hurdle. My hope is some future contributor may be able to supply that which eluded me.
1 You say all items for an order must be on the same truck. This means the atom of assignment is the Order, not the OrderDetail. I have generated these from your test data thus:
select
OrderId,
Size = sum(OrderDetailSize)
into #Order
from #OrderDetail
group by OrderId;
It makes no difference, though, whether we label the items in question 'Order' or 'OrderDetail', the solution remains the same.
