database - Allocate places according to distance -

database - Allocate places according to distance -

as over-simplified illustration have list of events have maximum attendance:

event | places =================== event_a | 1 event_b | 2 event_c | 1

and list of attendees distance 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 suggest simple method produce set of options providing best case allocations based on shortest total distance , on shortest mean distance?

i have info held in oracle spatial database, i'm open suggestions.

i understand problem follows:

each atendee should assigned 1 event each event has limit how many atendees assigned it underfull or empty events no problem each assignment between event , atendee corresponds given distance you want minimize overall distance assignments you might want print result not using sums using means

based on interpretation, suggest next algorithm:

create finish bipartite graph, nodes in partition a atendees , nodes in partition b places in events. every atendee corresponds 1 node, , every event corresponds many nodes has places. atendees connected event nodes distance border cost.

at point problem corresponds general assignment problem, “agents” corresponding event places, , “tasks” corresponding atendees. every atendee must covered, not every event place must used.

add dummy attendees allow perfect matching. sum places, subtract number of actual atendees. difference, create many atendee nodes, distance 0 event nodes.

by making both partitions equal in size, in domain of more mutual linear assignment problem.

use hungarian algorithm compute minimal cost assignment. perhaps can think of simplifications create utilize of fact have many equivalent nodes, i.e. places same event , dummy atendees.

all of should done in application code, not in info base. i'd rather tag algorithm. you'll need pull total cost matrix database provide costs edges.

database math