How to pick items from warehouse to minimise travel in TSQL?

Question

I am looking at this problem from a TSQL point of view, however any advice would be appreciated.

Scenario

I have 2 sets of criteria which identify items in a warehouse to be selected.

Query 1 returns 100 items
Query 2 returns 100 items

I need to pick any 25 of the 100 items returned in query 1.
I need to pick any 25 of the 100 items returned in query 2.
- The items in query 1/2 will not be the same, ever.

Each item is stored in a segment of the warehouse.
A segment of the warehouse may contain numerous items.

I wish to select the 50 items (25 from each query) in a way as to reduce the number of segments I must visit to select the items.

Suggested Approach

My initial idea has been to combined the 2 result sets and produce a list of

Segment ID, NumberOfItemsRequiredInSegment

I would then select 25 items from each query, giving preference to those in a segments with the most NumberOfItemsRequiredInSegment.

I know this would not be optimal but would be an easy to implement heuristic.

Questions

1) I suspect this is a standard combinational problem, but I don't recognise it.. perhaps multiple knapsack, does anyone recognise it?

2) Is there a better (easy-ish to impliment) heuristic or solution - ideally in TSQL?

Many thanks.

Answer 1

This might also not be optimal but i think would at least perform fairly well.

Calculate this set for query 1.

Segment ID, NumberOfItemsRequiredInSegment

take the top 25, Just by sorting by NumberOfItemsRequiredInSegment. call this subset A.

take the top 25 from query 2, by joining to A and sorting by "case when A.segmentID is not null then 1 else 0, NumberOfItemsRequiredInSegmentFromQuery2".

repeat this but take the top 25 from query 2 first. return the better performing of the 2 sets.

The one scenario where i think this fails would be if you got something like this.

Segment   Count Query 1    Count Query 2
A         10               1
B         5                1
C         5                1
D         5                4
E         5                4
F         4                4
G         4                5
H         1                5
J         1                5
K         1                10

You need to make sure you choose A, D, E, from when choosing the best segments from query 1. To deal with this you'd almost still need to join to query two, so you can get the count from there to use as a tie breaker.