Need simple advice for graph solving problem

Question

Hi there,

a collegue of mine proposed to me an exercise from an online judge website, which is basically a graph solving problem of an evacuation plan on a small town.

i dont need the answer (nor do i want it) i just need an advice on which is the best approach to solving it since im kinda new to these kind of problems.

the problem consists of town buildings with workers and fallout shelters in case of a nuclear attack. i have to build an algorithm that will assign the workers of each building to one or more fallout shelters but in a way that some shelters wont became too overcrowded while others remain almost empty (else i would just make the workers go to the nearest one).

the problem is this: http://acm.timus.ru/problem.aspx?space=1&num=1237

in case its offline heres the google cached version of it: http://webcache.googleusercontent.com/search?q=cache:t2EPCzezs7AJ:acm.timus.ru/problem.aspx%3Fspace%3D1%26num%3D1237+vladimir+kotov+evacuation+problem&cd=1&hl=pt-PT&ct=clnk&gl=pt

what i've done so far is for each building get the nearest shelter and move the number of workers from that build equal to the shelter capacity. then move to the next building. but sometimes the number of workers is greater than the shelter capacity, in that case after i iterate through every building, ill just iterate then again apllying the same algorithm until every building has 0 workers in it, problem is this is hardly the best way to solve it.

any tip is welcome, please dont feel like im asking for the answer, i just want an advice in the right direction of solving it.

thanks in advance.

Answer 1

This looks like a standard Min-cost max flow problem. A bipartite graph with ~200 vertices should run easily in time.

To create the vertex constraint (each node can only handle k people), you just need to create a second graph G_1 where you add an additional vertex u_i for each v_i - and having the flow v_i to u_i be whatever your constraint be, in this case, k+1, with the cost 0. So basically if there is an edge (a,b) in the original graph G, then in G_1, there will be an edge (u_a,v_b) for each of these edges. In effect, you're creating a second layer of vertices that constraints the flow to k for each vertex.

Answer 2

This looks exactly like the Transhipment Problem which can (apparently) be solved using Linear Programming. (I say apparently, because this looks to be an instance of Integer Linear programming).

From the site:

The standard scenario where a transportation problem arises is that of sending units of a product across a network of highways that connect a given set of cities. Each city is considered either as a "source," in that units are to be shipped out from there, or as a "sink," in that units are demanded there. Each source has a given supply, each sink has a given demand, and each highway that connects a source-sink pair has a given transportation cost per unit of shipment. This can be visualized in the form of a network, as depicted in Figure TP-1 below.

Given such a network, the problem of interest is to determine an optimal transportation scheme that minimizes the total cost of shipments, subject to supply and demand constraints.

Hope that helps.