Shortest Fulfillment Path Headache

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2000 Forums

SQL Server Development (2000)

Shortest Fulfillment Path Headache

Author

Topic

TurdSpatulaWarrior
Starting Member

36 Posts

Posted - 2004-03-23 : 13:42:58

Summary: The company has a network of warehouses in various cities. Each location has shuttle vans that ferry ordered items between locations back and forth on set routes. The less times an item has to be unloaded from one van then loaded onto another van, the cheaper the overall labor cost. Using code based on BOL topic "expanding networks", I am able to select a list of all possible fulfillment paths. However, my brain is just not functioning well today and I'm stumbling when trying to modify what I have so that it selects the option with the least amount of "hops".

Here's the code to create a sample table w/data:


CREATE TABLE Connections (Location varchar(20), ShipsTo varchar(20))

INSERT Connections VALUES('Springfield', 'Greenbrier')
INSERT Connections VALUES('Springfield', 'White House')
INSERT Connections VALUES('Joelton', 'Springfield')
INSERT Connections VALUES('Franklin', 'Springfield')
INSERT Connections VALUES('Franklin', 'Joelton')
INSERT Connections VALUES('Franklin', 'Murfreesboro')

And here is the aforementioned code I have thus far:


DECLARE @CurrentLocation varchar(20), @Destination varchar(20), @Hops int, @MaxHops int

SET @CurrentLocation = 'Franklin'
SET @Destination = 'Greenbrier'
SET @MaxHops = 5
SET @Hops = 1

DECLARE @Stack table (City varchar(20), Hops int)
DECLARE @List table (City varchar(20), Hops int)

INSERT @Stack(City, Hops) VALUES(@CurrentLocation, 1)

WHILE @Hops > 0
   BEGIN
      IF EXISTS (SELECT * FROM @Stack WHERE (Hops = @Hops))
         BEGIN
            SELECT @CurrentLocation = City FROM @Stack WHERE (Hops = @Hops)

            DELETE FROM @Stack WHERE (Hops = @Hops) AND (City = @CurrentLocation)

            DELETE FROM @List WHERE (Hops >= @Hops)

            INSERT @List VALUES(@CurrentLocation, @Hops)

            IF(@CurrentLocation = @Destination)
	       SELECT City FROM @List

            INSERT @Stack(City, Hops)
            SELECT ShipsTo, @Hops + 1
               FROM Connections
               WHERE (Location = @CurrentLocation) AND (@Hops < @MaxHops)

            IF @@ROWCOUNT > 0
               SELECT @Hops = @Hops + 1
         END
      ELSE
         SELECT @Hops = @Hops - 1
   END

... which when run, returns this:


Franklin
Joelton
Springfield
Greenbrier

and


Franklin
Springfield
Greenbrier

I need to figure out a solution that will return the latter result only and it needs to perform well, as the actual live tables are LARGE and have numerous concurrent users.

Any pointers? My brain <= a bowl of cold oatmeal today :-(

Jay

ehorn
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2004-03-23 : 13:57:43

[code]DECLARE @Current varchar(20), @Dest varchar(20), @Hops int, @Maxlevel int

SET @Current = 'Franklin'
SET @Dest = 'Greenbrier'
SET @Maxlevel = 5
SET @Hops = 1
DECLARE @level int
CREATE TABLE #stack (city char(20), level int)
CREATE TABLE #list (city char(20), level int)
INSERT #stack VALUES (@current, 1)
SELECT @level = 1

WHILE @level > 0
BEGIN
IF EXISTS (SELECT 1 FROM #stack WHERE level = @level)
BEGIN
SELECT @current = city
FROM #stack
WHERE level = @level
DELETE FROM #stack
WHERE level = @level
AND city = @current
DELETE FROM #list
WHERE level >= @level
IF EXISTS (SELECT 1 FROM #list WHERE city = @current)
CONTINUE
INSERT #list VALUES(@current, @level)

INSERT #stack
SELECT shipsto, @level + 1
FROM connections
WHERE location = @current
AND @level < @maxlevel
IF @@rowcount > 0
SELECT @level = @level + 1
END
ELSE
SELECT @level = @level - 1
END

--Result
SELECT City
FROM #List

DROP TABLE #stack, #list
[/code]

TurdSpatulaWarrior
Starting Member

36 Posts

Posted - 2004-03-23 : 15:09:38

Thanks for the reply 'horn. It works in this specific instance, however the physical ordering of the data will not always remain the same. For example, if you enter the same data in a different order (change table name to Connections2 instead of Connections):


CREATE TABLE Connections2 (Location varchar(20), ShipsTo varchar(20))

INSERT Connections2 VALUES('Franklin', 'Murfreesboro')
INSERT Connections2 VALUES('Franklin', 'Joelton')
INSERT Connections2 VALUES('Franklin', 'Springfield')
INSERT Connections2 VALUES('Joelton', 'Springfield')
INSERT Connections2 VALUES('Springfield', 'White House')
INSERT Connections2 VALUES('Springfield', 'Greenbrier')

... the result is different.

Perhaps I need to rethink the approach on this and maybe try a series of inner joins until one clicks.

xpandre
Posting Yak Master

212 Posts

Posted - 2004-03-24 : 05:16:52

Could you just check this out..

drop procedure route 


CREATE  PROCEDURE route 
(@current char(20), @dest char(20), @maxlevel1 int = 5) AS
SET NOCOUNT ON
DECLARE @level1 int, @routeno int
CREATE TABLE #stack (city char(20), level1 int)
CREATE TABLE #final (city char(20), routeno int)
CREATE TABLE #list (city char(20), level1 int)
INSERT #stack VALUES (@current, 1)
SELECT @level1 = 1
SELECT @routeno = 1

WHILE @level1 > 0
BEGIN
    IF EXISTS (SELECT * FROM #stack WHERE level1 = @level1)
        BEGIN
            SELECT @current = city
            FROM #stack
            WHERE level1 = @level1

	    DELETE FROM #stack 
            WHERE level1 = @level1 
            AND city = @current

            DELETE FROM #list 
            WHERE level1 >= @level1

            IF EXISTS (SELECT * FROM #list WHERE city = @current)
            CONTINUE

	    INSERT #list VALUES(@current, @level1)

            IF(@current = @dest)

		    BEGIN

			insert into #final
			SELECT city, @routeno
	                FROM #list
			set @routeno= @routeno+1
	                CONTINUE
	            END

  
            INSERT #stack
            SELECT  shipsto, @level1 + 1
            FROM connections
            WHERE location = @current
            AND @level1 < @maxlevel1

            IF @@rowcount > 0
                SELECT @level1 = @level1 + 1

        END
    ELSE
        SELECT @level1 = @level1 - 1
END 
select city from #final where routeno =
(
select routeno from
	(
		select top 1 routeno,count(routeno) c2 from #final 
		group by routeno order by c2
	) c
)

select * from connections

Location             ShipsTo              
-------------------- -------------------- 
Franklin             Murfreesboro
Franklin             Joelton
Franklin             Springfield
Joelton              Springfield
Springfield          White House
Springfield          Greenbrier

(6 row(s) affected)

exec route 'Franklin','Greenbrier'

city                 
-------------------- 
Franklin            
Springfield         
Greenbrier

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources