Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase 12»»

Grouping and Sorting challenge Expand / Collapse
Author
Message
Posted Friday, August 15, 2014 1:27 PM
SSC Journeyman

SSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC Journeyman

Group: General Forum Members
Last Login: Monday, August 25, 2014 11:46 AM
Points: 98, Visits: 241
Hello all -

I have an interesting challenge. Imagine I own a pizza restaurant and I have delivery drivers (4). I also have a fixed number of delivery Routes for my restaurant and these routes have varying number of households on the them. I want to sort and assign the routes as evenly as I can to the drivers.

My route data my look like this:

[RouteID]_[RouteName]_[HouseHolds]___[DriverID]
-----------------------------------------------------
1________Route01_____700__________0
2________Route02_____210__________0
3________Route03_____111__________0
4________Route04_____452__________0
5________Route05_____236__________0
6________Route06_____111__________0
7________Route07_____300__________0
8________Route08_____421__________0
9________Route09_____1200_________0
10_______Route10______525_________0


Drivers:
-------------------------
1 - Bob
2 - John
3 - Ricky Bobby
4 - Batman


What I'm TRYING to is write a Stored Proc to loop though the records (routes) and assign them to the drivers as evenly as possible based on households (staying with whole integers). Make sense?

I've tried a couple of different concepts but keep hitting 'writers block'.

Any suggestions?


Post #1603852
Posted Saturday, August 16, 2014 12:02 AM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 4:20 PM
Points: 37,106, Visits: 31,663
This is a classic "Bin Stacking" problem. So far as I know, there's not a set based way to pull one of these off in T-SQL. You have to use some form of RBAR to do this.

As a bit of a sidebar, take a look at the first link in my signature line below under "Helpful Links". That'll tell you how to post "readily consumable data" to make it a bit easier on folks trying to help you. Not doing it that way is probably one of the big reasons why no one responded to your post any more quickly.

Here's another way to post such example data. It's what I used to test this and I'm posting it so if someone has a better idea on this problem, it's easier for them to test with.

One thing that you need to be made aware of is that I added a column to the Driver table. You should make such a change to your real table and make sure that both tables have an appropriate PK.

--=====================================================================================================================
-- Setup and populate the test tables
--=====================================================================================================================
--===== If the test tables already exist, drop them to make reruns easier in SSMS
IF OBJECT_ID('tempdb..#Route' ,'U') IS NOT NULL DROP TABLE #Route;
IF OBJECT_ID('tempdb..#Driver','U') IS NOT NULL DROP TABLE #Driver;

--===== Build the test tables with the data provided.
-- Note that a column has been added to the Drivers table.
SELECT *
INTO #Route
FROM (
SELECT 1 ,'Route01',700 ,0 UNION ALL
SELECT 2 ,'Route02',210 ,0 UNION ALL
SELECT 3 ,'Route03',111 ,0 UNION ALL
SELECT 4 ,'Route04',452 ,0 UNION ALL
SELECT 5 ,'Route05',236 ,0 UNION ALL
SELECT 6 ,'Route06',111 ,0 UNION ALL
SELECT 7 ,'Route07',300 ,0 UNION ALL
SELECT 8 ,'Route08',421 ,0 UNION ALL
SELECT 9 ,'Route09',1200,0 UNION ALL
SELECT 10,'Route10',525 ,0
) d (RouteID, RouteName, HouseHolds, DriverID)
;
SELECT *
INTO #Driver
FROM (
SELECT 1,'Bob' ,0 UNION ALL
SELECT 2,'John' ,0 UNION ALL
SELECT 3,'Ricky Bobby' ,0 UNION ALL
SELECT 4,'Batman' ,0
) d (DriverID, Name, TotalHouseholds) --<<< Added the TotalHouseholds column
;
--===== Add the required PK's to the tables
ALTER TABLE #Route ADD PRIMARY KEY CLUSTERED (RouteID);
ALTER TABLE #Driver ADD PRIMARY KEY CLUSTERED (DriverID);


Here's a classic cursor solution for a classic RBAR-only problem. As always, details are in the comments in the code. Of course, you'll need to change the table names for your implementation.

--=====================================================================================================================
-- Distribute the routes using a classic "Bin Fill".
-- The basic premise is to cycle through the routes in descending order according to the number of households in
-- the routes and assign the next value to the driver with the fewest number of households. That driver will
-- change on every iteration until we run out of routes.
-- What we end up with is the route assignments by driver in the route table and a total number of households
-- for each driver in the driver table.
--=====================================================================================================================
--===== Environmental presets for performance of RBAR.
SET NOCOUNT ON;

--===== Reset the Route and Driver tables to make reruns possible.
UPDATE #Route SET DriverID = 0;
UPDATE #Driver SET TotalHouseholds = 0;

--===== Declare the necessary obviously named variables.
-- Because we're using a cursor instead of temp tables, we don't need any counters.
DECLARE @Households INT
,@DriverID INT
;
--===== Define the cursor from the Route table.
-- Note that the number of households are in descending order.
DECLARE BinFill CURSOR LOCAL FORWARD_ONLY
FOR SELECT Households --This is all we need from the table. The cursor keeps track of everything else.
FROM #Route
ORDER BY HouseHolds DESC, RouteID ASC --TieBreaker
FOR UPDATE OF DriverID --This is key to updating the table where the cursor is currently positioned "WHERE CURRENT OF"
;
--===== Open the cursor so that we can use it.
OPEN BinFill
;
--===== Get the first row from the cursor
FETCH NEXT FROM BinFill
INTO @Households
;
--===== Loop through the rows in the cursor
WHILE @@FETCH_STATUS = 0
BEGIN
--===== Identify the driver with the fewest households for this iteration.
-- The DriverID is the tie breaker just to be pedantic.
SELECT TOP 1 @DriverID = DriverID FROM #Driver ORDER BY TotalHouseholds ASC, DriverID ASC
;
--===== Add the # of Households value from the cursor row to the designated driver
UPDATE d
SET d.TotalHouseholds = d.TotalHouseholds + @Households --@Households came from the cursor row,
FROM #Driver d
WHERE d.DriverID = @DriverID
;
--===== Update the Route table with the current DriverID according to the current position of the cursor.
-- It's freakin' magic.
UPDATE #Route
SET DriverID = @DriverID
WHERE CURRENT OF BinFill
;
--===== Get the next row. If we're out of rows, the fetch status will change to -1 auto-magically
FETCH NEXT FROM BinFill
INTO @Households
;
END
;
--======== Properly close the cursor
CLOSE BinFill;
DEALLOCATE BinFill;
GO
--===== All done. Let's see the results
SELECT * FROM #Driver;
SELECT * FROM #Route;


Last but not least, here are the results...

DriverID    Name        TotalHouseholds
----------- ----------- ---------------
1 Bob 1200
2 John 1047
3 Ricky Bobby 1035
4 Batman 984

(4 row(s) affected)

RouteID RouteName HouseHolds DriverID
----------- --------- ----------- -----------
1 Route01 700 2
2 Route02 210 3
3 Route03 111 4
4 Route04 452 4
5 Route05 236 2
6 Route06 111 2
7 Route07 300 3
8 Route08 421 4
9 Route09 1200 1
10 Route10 525 3

(10 row(s) affected)



--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1604016
Posted Tuesday, August 19, 2014 9:10 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 4:20 PM
Points: 37,106, Visits: 31,663
Any feedback? Is there something missing?

--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1605272
Posted Wednesday, August 20, 2014 7:46 AM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Today @ 11:16 AM
Points: 1,945, Visits: 3,007
Google “bin packing” and “knapsack” problems. Ther is also a classic book availalbre as a PDF download. http://www.or.deis.unibo.it/knapsack.html. It has heavy math and awful FORTRAN.

The bottom line is that you are screwed for the general case. This is an NP Complete problem.

Also your specs need to be more precise as to how you determine the sizes; would 3 identical sized bags and 1 outlier be better than 4 near-matches? Etc.

Since you have a limited problem of 4 knapsacks and 10 items. My best guess is first partition the 10 items into 2 subset of approximately equal weight. Whatever that means and assuming it is possible. Then partition each of those recursively and hand them out to the 4 drivers.

This will require a table of 2^10 rows (1024) with all possible combinations of the weights and 0 in each column.

CREATE TABLE Routes
(partition_nbr INTEGER NOT NULL PRIMARY KEY,
r01 INTEGER NOT NULL
CHECK(r01 IN 0, 700),
r02 INTEGER NOT NULL
CHECK(r02 IN 0, 210)

r10 INTEGER NOT NULL
CHECK(r10 IN 0, 525));

Load the routes (exercise for the student) then

SELECT partition_nbr, (r01+r02+ ..+r10) AS wgt
FROM Routes;

Pick partitions closest to the mid point.


Books in Celko Series for Morgan-Kaufmann Publishing
Analytics and OLAP in SQL
Data and Databases: Concepts in Practice
Data, Measurements and Standards in SQL
SQL for Smarties
SQL Programming Style
SQL Puzzles and Answers
Thinking in Sets
Trees and Hierarchies in SQL
Post #1605443
Posted Wednesday, August 20, 2014 8:53 AM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 4:20 PM
Points: 37,106, Visits: 31,663
CELKO (8/20/2014)
Google “bin packing” and “knapsack” problems. Ther is also a classic book availalbre as a PDF download. http://www.or.deis.unibo.it/knapsack.html. It has heavy math and awful FORTRAN.

The bottom line is that you are screwed for the general case. This is an NP Complete problem.

Also your specs need to be more precise as to how you determine the sizes; would 3 identical sized bags and 1 outlier be better than 4 near-matches? Etc.

Since you have a limited problem of 4 knapsacks and 10 items. My best guess is first partition the 10 items into 2 subset of approximately equal weight. Whatever that means and assuming it is possible. Then partition each of those recursively and hand them out to the 4 drivers.

This will require a table of 2^10 rows (1024) with all possible combinations of the weights and 0 in each column.

CREATE TABLE Routes
(partition_nbr INTEGER NOT NULL PRIMARY KEY,
r01 INTEGER NOT NULL
CHECK(r01 IN 0, 700),
r02 INTEGER NOT NULL
CHECK(r02 IN 0, 210)

r10 INTEGER NOT NULL
CHECK(r10 IN 0, 525));

Load the routes (exercise for the student) then

SELECT partition_nbr, (r01+r02+ ..+r10) AS wgt
FROM Routes;

Pick partitions closest to the mid point.


Table with 2^10 rows? "Screwed in the general case"? I don't believe any of that is necessary. This is one of those places where a loop (please see the solution I posted above) actually does work quite well and it's self correcting based on the number of rows in the two tables. And, remember... I'm one of those that hates loops!


--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1605478
Posted Thursday, August 21, 2014 11:04 AM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Today @ 11:16 AM
Points: 1,945, Visits: 3,007
This is one of those places where a loop (please see the solution I posted above) actually does work quite well and it's self correcting based on the number of rows in the two tables. And, remember... I'm one of those that hates loops!


We are getting into an example of why "set-oriented programming can stink" that us RDBMS (functional, declarative, whatever) do not want to admit. By its nature, set-oriented programming must produce all valid answers.

That can be a very large set An unusably large set. And it the real world we need only one answer to move forward. It does not matter which one, really.

Remember stable marriages problem? At least one solution must exist. Solutions can favor men or women various degrees. So pick one





Books in Celko Series for Morgan-Kaufmann Publishing
Analytics and OLAP in SQL
Data and Databases: Concepts in Practice
Data, Measurements and Standards in SQL
SQL for Smarties
SQL Programming Style
SQL Puzzles and Answers
Thinking in Sets
Trees and Hierarchies in SQL
Post #1605929
Posted Thursday, August 21, 2014 2:50 PM
SSC-Addicted

SSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-Addicted

Group: General Forum Members
Last Login: Today @ 6:24 AM
Points: 418, Visits: 2,451
CELKO (8/21/2014)
This is one of those places where a loop (please see the solution I posted above) actually does work quite well and it's self correcting based on the number of rows in the two tables. And, remember... I'm one of those that hates loops!


We are getting into an example of why "set-oriented programming can stink" that us RDBMS (functional, declarative, whatever) do not want to admit. By its nature, set-oriented programming must produce all valid answers.


Well there goes my set oriented chess program idea.
Post #1606019
Posted Thursday, August 21, 2014 5:24 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 4:20 PM
Points: 37,106, Visits: 31,663
CELKO (8/21/2014)
This is one of those places where a loop (please see the solution I posted above) actually does work quite well and it's self correcting based on the number of rows in the two tables. And, remember... I'm one of those that hates loops!


We are getting into an example of why "set-oriented programming can stink" that us RDBMS (functional, declarative, whatever) do not want to admit. By its nature, set-oriented programming must produce all valid answers.

That can be a very large set An unusably large set. And it the real world we need only one answer to move forward. It does not matter which one, really.

Remember stable marriages problem? At least one solution must exist. Solutions can favor men or women various degrees. So pick one




--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1606075
Posted Monday, August 25, 2014 6:49 AM
SSC Journeyman

SSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC Journeyman

Group: General Forum Members
Last Login: Monday, August 25, 2014 11:46 AM
Points: 98, Visits: 241
Jeff -

I just wanted to jump in and say Thanks! I went out of town last week so I was never able to follow up on this. I look forward to trying your solution in the next day or so! THANKS for the time!
Post #1607046
Posted Monday, August 25, 2014 6:52 AM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 4:20 PM
Points: 37,106, Visits: 31,663
patrickmcginnis59 10839 (8/21/2014)
CELKO (8/21/2014)
This is one of those places where a loop (please see the solution I posted above) actually does work quite well and it's self correcting based on the number of rows in the two tables. And, remember... I'm one of those that hates loops!


We are getting into an example of why "set-oriented programming can stink" that us RDBMS (functional, declarative, whatever) do not want to admit. By its nature, set-oriented programming must produce all valid answers.


Well there goes my set oriented chess program idea.


Heh... it IS called a "Chess Set".


--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1607049
« Prev Topic | Next Topic »

Add to briefcase 12»»

Permissions Expand / Collapse