Sort a Table based on one column, then find the next row based on 2 other Columns

Question

OK guys.. I'm a little stumped on this one..

I have a table of items in locations that I am consolidating. The items are spread between different rows (like a warehouse). I have calculated what to send where, and the distance between the starting and ending position.

Now, I need to develop a report that starts with the shortest move, then from its FINISH location finds the next shortest move with a START location closest to the first moves FINISH location... so if I move obj A from warehouse row 20 to row 30, I want my next line to be the next closest move, probably in row 30, that is also the shortest distance.

item | start_loc | end_loc | distance
A    | 5         | 10      | 5
B    | 14        | 11      | 3
C    | 20        | 1       | 19
D    | 10        | 13      | 3
E    | 10        | 5       | 5
F    | 10        | 6       | 4

So the table above would be ordered

D, B, F, A, E, C

Basically I want to optimize the amount of trips and spend the least amount of time empty handed..

Using ColdFusion and SQL to do this..

Edit from comments below: I'll try to clarify further.. The table above would be ordered D, B, F, A, E, C because: D has the shortest distance - 3; B is the next closes to D's end (13 --> 14); F because move B ends at 11, 10 is the next closest row with a move, and F has the shortest move distance in that row; A bc F ends at 6, and A starts at 5; E bc A ends at 10 and E starts on 10; C because it is the most inconvenient (longest, nothing ends by it) so it's last

UPDATE: I adapted the selected answer below to work with my tables etc.. however, it is skipping one of the rows, and I'm not sure why?

    <!-- Add some columns to the working table for calculations -->
<cfquery name="updateWorking" datasource="planning" dbtype="obdc">

    ALTER TABLE working
    ADD move_distance FLOAT;

    ALTER TABLE working
    ADD start_loc FLOAT;

    ALTER TABLE working
    ADD finish_loc FLOAT;

    ALTER TABLE working
    ADD move_order INT;

</cfquery>
<cfquery name="updateWorking2" datasource="planning" dbtype="obdc">

    UPDATE working
    SET start_loc = LEFT(Storage_Bin, 5)
    WHERE marked_consolidate_loc IS NOT NULL;

    UPDATE working
    SET finish_loc = LEFT(marked_consolidate_loc, 5)
    WHERE marked_consolidate_loc IS NOT NULL;

    UPDATE working
    SET move_distance = finish_loc - start_loc
    WHERE marked_consolidate_loc IS NOT NULL;

    UPDATE working
    SET move_distance = ABS(move_distance)
    where move_distance < 0

</cfquery>


<!-- Query to show all the moves in order by distance, shortest first -->
<cfquery name="report" datasource="planning" dbtype="obdc">
    SELECT  id, Material, marked_consolidate, marked_consolidate_loc, marked_consolidate_su,
            max_pallet, mixed_skid, Storage_Bin, Storage_Unit, move_distance, finish_loc, start_loc
    FROM working
    WHERE marked_consolidate IS NOT NULL
    AND mixed_skid = 0
    ORDER BY move_distance ASC
</cfquery>
<!-- What is the shortest move? Do it first -->
<cfquery name="firstMove" datasource="planning" dbtype="obdc" maxRows="1">
    Select id, Material, marked_consolidate, marked_consolidate_loc, marked_consolidate_su,
            max_pallet, mixed_skid, Storage_Bin, Storage_Unit, move_distance, finish_loc, start_loc
    FROM working
    WHERE marked_consolidate IS NOT NULL
    AND mixed_skid = 0
    ORDER BY move_distance ASC, start_loc ASC
</cfquery>

<!--- set the Move Number --->
<cfset moveNumber = 1>
<!-- List to remember ID of moves that have been completed -->
<cfset tripSequence = ''>

<!-- Update the first selection as the first move -->
<cfquery name= "updateMove" datasource="planning" dbtype="obdc">
    UPDATE working
    SET move_order = #moveNumber#
    WHERE id = #firstMove.id#;
</cfquery>

<cfset moveNumber = moveNumber + 1>
<cfset tripSequence = ListAppend(tripSequence, "#firstMove.id#")>
<cfset lastMoveFinish = #firstMove.finish_loc#>

<!--- number of trips remaining --->
<cfset numberOfTrips = (report.recordCount) - 1>

<!-- Loop through the whole table -->
<cfloop from="1" to="#numberOfTrips#" index="i">
    <!--- determine next move to compare to --->
    <cfloop query="report">
        <!--- Has it been moved already?--->
        <cfif listContains(tripSequence, #report.id#)>
            <!-- If so, continue to next row -->
            <cfcontinue>
        </cfif>
        <!-- If not, remember this one -->
        <cfset nextLocationID = report.id>
        <cfset nextLocationFinishLoc = report.finish_loc>
        <cfset nextLocationDist = abs(lastMoveFinish - report.start_loc)>
    </cfloop>

    <!--- compare this move with other moves, if the next one is shorter remember it --->
    <cfloop query="report">
        <!--- Has it been moved already? --->
        <cfif listContains(tripSequence, #report.id#)>
            <cfcontinue>
        </cfif>
        <!-- How far is this move from your current location? -->
        <cfset nextLocationDistance = abs(lastMoveFinish - report.start_loc)>
        <!-- If this move is closer to you than the one you selected above, remember it instead -->
        <cfif nextLocationDistance LT nextLocationDist>
            <cfset nextLocationID = report.id>
            <cfset nextLocationFinishLoc = report.finish_loc>
            <cfset nextLocationDist = abs(lastMoveFinish - report.start_loc)>
        </cfif>
    </cfloop>

    <!-- once you have the closest move, remember it and update the column -->
    <cfset tripSequence = ListAppend(tripSequence, nextLocationID)>
    <!-- Update the move column -->
    <cfquery name= "updateMove" datasource="planning" dbtype="obdc">
        UPDATE working
        SET move_order = #moveNumber#
        WHERE id = #nextLocationID#;
    </cfquery>
    <!-- Increment the Move Number -->
    <cfset moveNumber = moveNumber + 1>

    <!--- set the ending of your last move --->
    <cfset lastMoveFinish = nextLocationFinishLoc>
</cfloop>

<!-- BELOW IS OUTPUT OF THE REPORT -->
<body>
    <!-- Build the report -->
    <table border='1'>
        <tr>
            <th colspan="7">
                <h2>Consolidation Report</h2>
            </th>
        </tr>
        <tr>
            <td>Move Order</td>
            <td>Current Loc</td>
            <td>Current SU</td>
            <td>Item Number</td>
            <td>Qty To Move</td>
            <td>Moved To Loc</td>
            <td>Moved To SU</td>
        </tr>

        <!-- Query to show all the moves in order by distance, shortest first -->
        <cfquery name="showReport" datasource="planning" dbtype="obdc">
                SELECT Material, marked_consolidate, marked_consolidate_loc, marked_consolidate_su,
                        Storage_Bin, Storage_Unit, move_order
                FROM working
                WHERE marked_consolidate IS NOT NULL
                AND mixed_skid = 0
                ORDER BY move_order
        </cfquery>

        <cfloop query="showReport">
            <tr>
                <cfoutput>
                    <td>#showReport.move_order#</td>
                    <td>#showReport.Storage_Bin#</td>
                    <td>#showReport.Storage_Unit#</td>
                    <td>#showReport.Material#</td>
                    <td>#showReport.marked_consolidate#</td>
                    <td>#showReport.marked_consolidate_loc#</td>
                    <td>#showReport.marked_consolidate_su#</td>
                </cfoutput>
            </tr>
        </cfloop>
    </table>
    <cfoutput>#tripSequence#</cfoutput>
<body>

The output is a table with 49 rows.. however one of the rows Move Number is empty, and it skips Move Number: 48. Thoughts?

All rows are logically correct, it's just skipping 48 and not putting the Null row where it should be (logically would be around move 30).

Answer 1

Fun question, sql and a logic puzzle. Obviously a job for recursion, went with a while loop to keep it simple:

create table #examplework (item varchar(1), start_Loc int, end_loc int, distance int)

insert into #examplework
select 'a', 5, 10, 5
union
select 'b', 14, 11, 3
union
select 'c', 20, 1, 19
union
select 'd', 10, 13, 3
union
select 'e', 10, 5, 5
union
select 'f', 10, 6, 4

create table #worktable (Workingpath varchar(900), Current_Step varchar(1))
declare @step varchar(1) = (select top 1 item from #examplework order by distance) 
declare @path varchar(900) = ''

while @step is not null
begin
insert into #worktable
select concat(@path, ',' , @step) as Workingpath, @step as CurrentStep

set @step = (select top 1 ew1.item 
             from #examplework ew
             join #examplework ew1 on ew.item != ew1.item
             where ew.item = @step
             and ew1.item not in (select Current_Step from #worktable)
             order by abs(ew.end_loc - ew1.start_Loc))
set @path = (select top 1 Workingpath from #worktable order by len(Workingpath) desc)

end

select top 1 * from #worktable
order by LEN(workingpath) desc

Thus the salesman paradox is solved in sql again (darn college homework). To step through it, I set the step variable, then grab the closest item that does not appear in the work table. Once all items are in the work table the while loop closes. Hope that helps.

edit whoops if this is the TSP, you can't simply pick a node and hope the nearest leads to the best route. You need to brute force the hell out of it, look at all possible combinations and pick the one that requires the least travel. Here is an example of that:

select CONCAT(a.item, ',', b.item, ',', c.item, ',', d.item, ',', e.item, ',', f.item) as route,
sum(abs(a.end_loc - b.start_Loc) + abs(b.end_loc - c.start_Loc) + abs(c.end_loc - d.start_Loc) + ABS(d.end_loc - e.start_Loc) + abs(e.end_loc - f.start_Loc)) as distance  
from
#examplework a
join #examplework b on b.item != a.item
join #examplework c on c.item != a.item and c.item != b.item
join #examplework d on d.item != a.item and d.item != b.item and d.item != c.item
join #examplework e on e.item != a.item and e.item != b.item and e.item != c.item and e.item != d.item
join #examplework f on f.item != a.item and f.item != b.item and f.item != c.item and f.item != d.item and f.item != e.item
group by CONCAT(a.item, ',', b.item, ',', c.item, ',', d.item, ',', e.item, ',', f.item)
order by distance

That is literally the only way to solve the TSP, the other method will get you a good route, the brute force method will get you the best route.

Answer 2

Tackling the TSP, eh? That's my solution for you and unless you run thousands of nodes, it should be fine performance wise.

<cfset data = queryNew(
    "item,start_loc,end_loc,distance",
    "VARCHAR,INTEGER,INTEGER,INTEGER",
    [
        [ "A", 5, 10, 5 ],
        [ "B", 14, 11, 3 ],
        [ "C", 20, 1, 19 ],
        [ "D", 10, 13, 3 ],
        [ "E", 10, 5, 5 ],
        [ "F", 10, 6, 4 ]
    ]
)>

<cfset tripSequence = []>

<!--- BEGIN: determine first item --->

    <cfquery name="closestLocation" dbType="query" maxRows="1">

        SELECT
            *

        FROM
            [data]

        ORDER BY
            [distance] ASC,
            [start_loc] ASC

    </cfquery>

    <!--- add item --->
    <cfset tripSequence.add(closestLocation.item)>

<!--- END: determine first item --->

<!--- number of trips remaining --->
<cfset numberOfTrips = (data.recordCount - 1)>

<cfloop from="1" to="#numberOfTrips#" index="i">

    <!--- BEGIN: determine next trip to compare to --->

        <cfloop query="data">

            <!--- must not have been done already --->
            <cfif arrayFind(tripSequence, data.item)>
                <cfcontinue>
            </cfif>

            <cfset nextLocation = {
                item:       data.item,
                end_loc:    data.end_loc,
                distance:   abs(closestLocation.end_loc - data.start_loc)
            }>

        </cfloop>

    <!--- END: determine next trip to compare to --->

    <!--- BEGIN: compare with remaining trips --->

        <cfloop query="data">

            <!--- must not have been done already --->
            <cfif arrayFind(tripSequence, data.item)>
                <cfcontinue>
            </cfif>

            <cfset nextLocationDistance = abs(closestLocation.end_loc - data.start_loc)>

            <cfif nextLocationDistance lt nextLocation.distance>

                <cfset nextLocation = {
                    item:       data.item,
                    end_loc:    data.end_loc,
                    distance:   nextLocationDistance
                }>

            </cfif>

        </cfloop>

    <!--- END: compare with remaining trips --->

    <!--- add item --->
    <cfset tripSequence.add(nextLocation.item)>

    <!--- take item as base for the next iteration --->
    <cfset closestLocation = nextLocation>

</cfloop>

<cfoutput>#arrayToList(tripSequence, ", ")#</cfoutput>