How to do best-match allocation of items to customers?
This is perhaps best explained by an illustrative example rather than in terms of coding requirements:
Imagine I'm running a lending library. Not quite a typical library, as you'll see.Customers have supplied lists of the books they'd like to borrow, and indicated how important each book is. I obviously have a list of what stock I have available, and stock is limited - there is never enough on hand to completely satisfy all customers. Customers can have two books at a time.
Tim's list contains, in his order of preference:
Book A
Book B
Book C
Book D
Book E
John's list contains:
Book A
Book B
And I have one copy of each book in stock. Obviously if I send Tim his top two choices, John won't get anything, but this is easily and visibly solvable in this example - send John his top two, and Tim gets C and D. Everybody got something, and where possible they got the best possible pick. Now add three more people and ten more books into the equation and it quickly gets a lot more complex.
How would I go about developing a reasonably intelligent best-match algorythm? The obvious solution would be to simply try every possible permutation and select the result set with the most books allocated and the highest choices from each list. But that soon becomes ridiculous as the numbers ramp up, as every person/book added doubles the number of possible outcomes.
Is there a standard way of doing something like this?
Imagine I'm running a lending library. Not quite a typical library, as you'll see.Customers have supplied lists of the books they'd like to borrow, and indicated how important each book is. I obviously have a list of what stock I have available, and stock is limited - there is never enough on hand to completely satisfy all customers. Customers can have two books at a time.
Tim's list contains, in his order of preference:
Book A
Book B
Book C
Book D
Book E
John's list contains:
Book A
Book B
And I have one copy of each book in stock. Obviously if I send Tim his top two choices, John won't get anything, but this is easily and visibly solvable in this example - send John his top two, and Tim gets C and D. Everybody got something, and where possible they got the best possible pick. Now add three more people and ten more books into the equation and it quickly gets a lot more complex.
How would I go about developing a reasonably intelligent best-match algorythm? The obvious solution would be to simply try every possible permutation and select the result set with the most books allocated and the highest choices from each list. But that soon becomes ridiculous as the numbers ramp up, as every person/book added doubles the number of possible outcomes.
Is there a standard way of doing something like this?
I don't know if it's the best one but it just poped-up in my head.
make a demand list in your case:
BookA - 2
BookB - 2
BookC - 1
BookD - 1
BookE - 1
and process is it ascending order, so first send books with demand 1, then demand 2 and so on, in same time keep track of number of books sent to customer so once you emptied list with demand 1 and start processing demand 2 take a look at their satisfaction ratio. in your case when processing demand 2 you have Tim and John, Tim's satisfaction ratio is 60% (you've already sent him 3 out of 5 books when processing demand 1) while John's ration is 0% so sent BookA to John, again BookB has demand 2 Tim's satisy ratio remains 60% while John's is 50% so once again send book to John.
of course at some point you'll have 2 or more clients with same satisfaction ratio then you can say for instance if I have to customers with same satisfaction ratio I'll pick the one who has longer whish list or he's my client for a longer period of time or maybe he has some priority ahead of others, etc.
ziolko.
make a demand list in your case:
BookA - 2
BookB - 2
BookC - 1
BookD - 1
BookE - 1
and process is it ascending order, so first send books with demand 1, then demand 2 and so on, in same time keep track of number of books sent to customer so once you emptied list with demand 1 and start processing demand 2 take a look at their satisfaction ratio. in your case when processing demand 2 you have Tim and John, Tim's satisfaction ratio is 60% (you've already sent him 3 out of 5 books when processing demand 1) while John's ration is 0% so sent BookA to John, again BookB has demand 2 Tim's satisy ratio remains 60% while John's is 50% so once again send book to John.
of course at some point you'll have 2 or more clients with same satisfaction ratio then you can say for instance if I have to customers with same satisfaction ratio I'll pick the one who has longer whish list or he's my client for a longer period of time or maybe he has some priority ahead of others, etc.
ziolko.
This is a disguised version of the Travelling Salesman problem.
Each person (salesman) has a thing they want (need to get to) with a metric to determine their needs.
There is no general purpose way to solve it; no elegant solution. You'll need to look at each person, and each person's entire list to determine what to do.
But this might work...
Sort the list of people in descending order on size of list...
Create another list of books, and add counts to each book for the number of times the book appears in somebody's want list.
Trivially assign books that have a needed count of 1 to the users that wanted them.
Then assign books that are in contention based on the number of unfilled slots for each user. In your example, Let's say both tim and john's lists ended at book B... john gets A... tim gets B if there was a third person, charley, he gets nothing.
Continue until the supply of requested books is exhausted.
-j
Each person (salesman) has a thing they want (need to get to) with a metric to determine their needs.
There is no general purpose way to solve it; no elegant solution. You'll need to look at each person, and each person's entire list to determine what to do.
But this might work...
Sort the list of people in descending order on size of list...
Create another list of books, and add counts to each book for the number of times the book appears in somebody's want list.
Trivially assign books that have a needed count of 1 to the users that wanted them.
Then assign books that are in contention based on the number of unfilled slots for each user. In your example, Let's say both tim and john's lists ended at book B... john gets A... tim gets B if there was a third person, charley, he gets nothing.
Continue until the supply of requested books is exhausted.
-j
to make it fair you still need to randomly pick equals
John
Book A
Tim
Book A
these are equal, but who will get Book A ?
John
Book A
Tim
Book A
these are equal, but who will get Book A ?
Yes, agreed. Pick one randomly.
-j
-j
I would try to look at it from a human aspect.. what seems "fairer" to people.
I would include an extra property to the list "Time I have Been Waiting For this Book..."
that way, if "A" has been on the waiting list for book "1" for 5 weeks, and person "B" comes along and wants book "1" also, then "A" should get preference.
if "A" has a list of 4 books, and "B" has a list of only 1 book, then it would be "fairer" for "B" to get the book
Finally, where there is a clash, I would go through the list, and try to get a book to everyone first, and then try to give them a second book, if there are any left
that way person "A" doesn't get all his books, and person "Z" finds that there are no books left because everyone before him has taken them all..
Include the "priority" of the book into the calculation. (i.e "A"'s first choice is book "1")
From these things, I would create a "percentage" for each person's desired book, and give the book to the highest value
When a person gets a book, their "percentage" for all their other books drops by say... 10%
(allowing hopefully for each person to get a book before people get a 2nd book)
I would include an extra property to the list "Time I have Been Waiting For this Book..."
that way, if "A" has been on the waiting list for book "1" for 5 weeks, and person "B" comes along and wants book "1" also, then "A" should get preference.
if "A" has a list of 4 books, and "B" has a list of only 1 book, then it would be "fairer" for "B" to get the book
Finally, where there is a clash, I would go through the list, and try to get a book to everyone first, and then try to give them a second book, if there are any left
that way person "A" doesn't get all his books, and person "Z" finds that there are no books left because everyone before him has taken them all..
Include the "priority" of the book into the calculation. (i.e "A"'s first choice is book "1")
From these things, I would create a "percentage" for each person's desired book, and give the book to the highest value
When a person gets a book, their "percentage" for all their other books drops by say... 10%
(allowing hopefully for each person to get a book before people get a 2nd book)
Do you need to cater for having more than 1 copy of the book?
I might whip up a small demo that all of us experts can use to illustrate different algorithms...
Then you can compare and choose the best method that suits your requirements
I might whip up a small demo that all of us experts can use to illustrate different algorithms...
Then you can compare and choose the best method that suits your requirements
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Thanks to all for the great ideas. Keep 'em coming. Many of these concepts are already in use, and I'm still looking for the "Holy Grail" ultimate answer. But, like the Holy Grail itself, that may remain beyond my grasp. I'll be happy to settle for pure genius ;o)
TheRealLoki: more than one copy of the book? Yes, I might have several copies. But a customer should never get more than one copy of the same book.
TheRealLoki: more than one copy of the book? Yes, I might have several copies. But a customer should never get more than one copy of the same book.
There is no Holy Grail here.
If you only have one copy of a book, and more than one person wants access to it, then you have "conflict".
"Oh! Come and see the violence inherent in the system! Help! Help! I'm being repressed!"
In other words, you can't solve the problem.
We could try, though, something from antiquity...
We could be like King Solomon, and we could cut the book in two!
-john
If you only have one copy of a book, and more than one person wants access to it, then you have "conflict".
"Oh! Come and see the violence inherent in the system! Help! Help! I'm being repressed!"
In other words, you can't solve the problem.
We could try, though, something from antiquity...
We could be like King Solomon, and we could cut the book in two!
-john
ASKER
I'm aware that there is no perfect solution where everybody gets exactly what they want. But there must be a way to find the optimum allocation so that as many people as possible (a) get something; and (b) get something they really wanted.
I have a feeling that some obscure mathematics will be involved somewhere, but this is over my head.
I have a feeling that some obscure mathematics will be involved somewhere, but this is over my head.
have you tried my solution? :-) based on human expectations
This seems to be an NP-Complete problem, which means that the exact solution would become ridiculously slow as the numbers ramp up
but this looks like an efficient approximation algorithm:
http://www.cs.technion.ac.il/~lirank/pubs/2006-IPL-Generalized-Assignment-Problem.pdf
but this looks like an efficient approximation algorithm:
http://www.cs.technion.ac.il/~lirank/pubs/2006-IPL-Generalized-Assignment-Problem.pdf
i suspect you are using a database for this
As i use oracle most of the time, the syntax will be oracle
tables
BOOKS
ID, SUBID, NAME, AVAILABLE
ID = number of book
SUBID = number of copy for this same book
NAME = title of book
BOOKORDERS
BOID, CUSTOMERID, DATEORDERED
BOID = BOOKORDERID
BOOKORDERDETAILS
BOID, BODID, BOOKID, RECEIVED
BODID = BOOKORDERDETAILID
this will give a little more substance as to how to solve this ...
SELECT BOD.BOOKID, RANK() OVER (ORDER BY BO.DATEORDERED DESC, BOD.BODID ASC) AS PRIO
FROM BOOKORDERS BO
JOIN BOOKORDERDETAILS BOD ON BO.BOID = BOD.BOID
JOIN BOOKS B ON BO.BOOKID = B.ID
WHERE BOD.RECEIVED = 0
AND B.AVAILABLE = 1
this should give a list as to what book is the one somebody has been waiting for the longest
anything among these lines ?
As i use oracle most of the time, the syntax will be oracle
tables
BOOKS
ID, SUBID, NAME, AVAILABLE
ID = number of book
SUBID = number of copy for this same book
NAME = title of book
BOOKORDERS
BOID, CUSTOMERID, DATEORDERED
BOID = BOOKORDERID
BOOKORDERDETAILS
BOID, BODID, BOOKID, RECEIVED
BODID = BOOKORDERDETAILID
this will give a little more substance as to how to solve this ...
SELECT BOD.BOOKID, RANK() OVER (ORDER BY BO.DATEORDERED DESC, BOD.BODID ASC) AS PRIO
FROM BOOKORDERS BO
JOIN BOOKORDERDETAILS BOD ON BO.BOID = BOD.BOID
JOIN BOOKS B ON BO.BOOKID = B.ID
WHERE BOD.RECEIVED = 0
AND B.AVAILABLE = 1
this should give a list as to what book is the one somebody has been waiting for the longest
anything among these lines ?
ASKER
Unfortunately I haven't had time to complete this project, but TheRealLoki put some solid work into finding a solution for me. Thanks to everyone who chipped in.
no need for algorithm ...