Tell me more ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.
up vote 1 down vote favorite
2

I've asked this over on Stack Overflow but thought that someone may have a GI point of view that may help:

As an over-simplified example I have a list of events that have a maximum attendance:

 event    | places
===================
 event_A  |   1
 event_B  |   2
 event_C  |   1

And a list of attendees with the distance to the events:

 attendee    | event_A dist | event_B dist | event_C dist
==========================================================
 attendee_1  |      12      |      15      |      12      
 attendee_2  |      11      |      15      |      11
 attendee_3  |      10      |      11      |      12

Can anyone suggest a (hopefully) simple method to produce a set of options providing the best case allocations based on shortest total distance and also on shortest mean distance?

I currently have the data held in Oracle Spatial database, but I'm open to suggestions.

In my actual data there will be more places than attendees, so the events do not have to be full, but they cannot be "over-full". For the possible solutions I'd like 2; one showing the lowest total distance (i.e. sum of all attendees' distances), the other showing the mean distance (i.e. sum of all attendees' distances / No. of attendees)

Update:

  • Each atendee should be assigned to exactly one event
  • Each event has a limit as to how many atendees are assigned to it
  • Underfull or even empty events are no problem
  • Each assignment between an event and an atendee corresponds to a given distance
  • I want to minimize the overall distance for all assignments
share|improve this question
Here is the Stack Overflow question. There has been 1 answer so far but it is more than a little over my head, but it may help someone along the way. – Rob Feb 21 at 12:43
The answer on stack overflow from @MvG is a good one. This is an optimization problem, and the tools of optimization (graphs, matrix math) will provide the solution. It's not a trivial problem. This is better suited for an algorithm than a SQL query. – katahdin Feb 21 at 15:03
It is unclear what this question is asking. If an "allocation" is a unique choice of event for each attendee, and if "total distance" is the sum of associated distances found in the list, then the problem is trivial: the smallest number in each attendee row determines the associated event (with some disambiguation for ties, such as a randomized choice). Otherwise, what really is the question and what does it have to do with GIS, given that there is no locational information at all? Since SE discourages cross-posting, I vote to close this copy of the question. – whuber♦ Feb 21 at 15:19
Apologies, I should have been clearer. I initially have the data in two Oracle spatial tables where the events and the attendees have a geographic co-ordinates; I skipped that part of the problem on Stack Overflow. As my GIS knowledge is much better than my math knowledge, I entered it here in case there was a solution using GIS/Spatial Databases. Willing to delete this post if that is the consensus. – Rob Feb 21 at 15:30
If you can give us some more detail (in particular show the where the spatial components fit) then we can provide better help. A picture showing where events and attendees are located, and how attendees match up to events, would be a big help. – katahdin Feb 21 at 15:49
show 2 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.