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).
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>