Moją pierwszą myślą było
select
<best solution>
from
<all possible combinations>
Część „najlepszego rozwiązania” została zdefiniowana w pytaniu - najmniejsza różnica między najbardziej obciążonymi i najmniej obciążonymi ciężarówkami. Druga część - wszystkie kombinacje - spowodowała, że zastanowiłem się.
Rozważmy sytuację, w której mamy trzy zamówienia A, B i C oraz trzy ciężarówki. Możliwości są
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.
Wiele z nich jest symetrycznych. Na przykład pierwsze sześć rzędów różni się tylko tym, w jakiej ciężarówce jest składane każde zamówienie. Ponieważ ciężarówki można zamieniać, te aranżacje przyniosą ten sam rezultat. Na razie zignoruję to.
Znane są zapytania dotyczące tworzenia permutacji i kombinacji. Powodują one jednak ustalenia w ramach jednego segmentu. W przypadku tego problemu potrzebuję uzgodnień między wieloma segmentami.
Patrząc na wynik standardowego zapytania „wszystkie kombinacje”
;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
<snip>
3 2 3
3 3 1
3 3 2
3 3 3
Table B: cross join of three values.
Zauważyłem, że wyniki uformowały taki sam wzór jak w Tabeli A. Dokonując sprytnego skoku biorąc pod uwagę każdą kolumnę jako Zamówienie 1 , wartości określające, która ciężarówka będzie utrzymywać to Zamówienie, a rząd jako układ Zamówień w ciężarówkach. Zapytanie staje się następnie
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
<snip>
Query C: Orders in trucks.
Rozwijając to, aby objąć czternaście zamówień w przykładowych danych, i upraszczając nazwy, otrzymujemy to:
;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.
Dla wygody wybieram przechowywanie wyników pośrednich w tabelach tymczasowych.
Kolejne kroki będą znacznie łatwiejsze, jeśli dane zostaną po raz pierwszy 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.
Wagi można wprowadzić, łącząc się z tabelą Zamówienia.
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
Można teraz odpowiedzieć na pytanie, znajdując układy, które mają najmniejszą różnicę między najczęściej załadowanymi i najmniej załadowanymi ciężarówkami
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
Dyskusja
Jest z tym bardzo wiele problemów. Po pierwsze, jest to algorytm brutalnej siły. Liczba wierszy w tabelach roboczych jest wykładnicza pod względem liczby ciężarówek i zamówień. Liczba wierszy w #Arrangements to (liczba ciężarówek) ^ (liczba zamówień). To nie będzie dobrze skalować.
Po drugie, zapytania SQL mają osadzoną liczbę zamówień. Jedynym sposobem na obejście tego jest użycie dynamicznego SQL, który ma własne problemy. Jeśli liczba zamówień jest w tysiącach, może przyjść czas, kiedy wygenerowany SQL stanie się zbyt długi.
Trzecia to nadmiarowość w ustaleniach. Powoduje to nadmierne powiększanie tabel pośrednich, zwiększając znacznie czas działania.
Po czwarte, wiele wierszy w #Arrangements pozostawia jedną lub więcej ciężarówek pustych. Nie może to być optymalna konfiguracja. Łatwo byłoby odfiltrować te wiersze podczas tworzenia. Zdecydowałem się tego nie robić, aby kod był prostszy i bardziej skoncentrowany.
Z drugiej strony ma to wpływ na ujemne ciężary, jeśli Twoje przedsiębiorstwo zacznie kiedykolwiek wysyłać wypełnione balony z helem!
Myśli
Gdyby istniał sposób na wypełnienie #FilledTrucks bezpośrednio z listy ciężarówek i zamówień, myślę, że najgorszym z tych problemów można by zaradzić. Niestety moja wyobraźnia natknęła się na tę przeszkodę. Mam nadzieję, że jakiś przyszły współpracownik może być w stanie dostarczyć to, co mi umknęło.
1 Mówisz, że wszystkie elementy zamówienia muszą znajdować się w tej samej ciężarówce. Oznacza to, że atomem przypisania jest Zamówienie, a nie Zamówienie Szczegóły. Wygenerowałem je z danych testowych w ten sposób:
select
OrderId,
Size = sum(OrderDetailSize)
into #Order
from #OrderDetail
group by OrderId;
Nie ma jednak znaczenia, czy oznaczymy przedmiotowe pozycje „Zamów”, czy „Szczegóły zamówienia”, rozwiązanie pozostaje takie samo.