Optimalisatie kavelverdeling in woonwijk

Woeka

Ik zit in een Collectief (particulier) opdrachtgeverschap waarmee we met een groep een woonwijk gaan neerzetten. Nu willen we de kavels gaan toewijzen aan huishoudens. Dat leek me nu echt een wiskundig probleem wat gewoon op te lossen moet zijn. Alleen hoe .. iemand die me daar verder mee kan helpen? Een simplex algoritme dacht ik eerst aan .. maar dat lijkt het toch niet helemaal te kunnen vatten.

Probleem 1

Het zo optimaal mogelijk toewijzen van 20 kavels in een woonwijk. Twintig huishoudens moeten geplaatst worden op 20 kavels. Ieder huishouden geeft een ranking aan ieder kavel van 1 tot 20 waarbij 1 de hoogste is. Daarmee zou de wijk zo optimaal mogelijk in gedeeld moeten kunnen worden. Volgens mij zijn de mogelijkheden 20! dus iets van

2,4 * 10^18 beetje te veel om brute force alles af te gaan.

Hieronder wat ik denk dat het zou moeten zijn:

Optimalisatie:

x1 + x2 + x3 + ... + x20 -> min

Waarbij x1, x2, ... , x20 de waarde heeft van de ranking van het huishouden dat geplaatst is op een bepaald kavel.

a1, a2, a3, .. , a20 = willekeurige volgorde van (1+2+3+4+..+20) waarbij ieder getal eenmaal voorkomt = 210

b1, b2, b3, .. , b20 = idem

.

.

t1, t2, t3, .. , t20 = idem

Waarbij a1-20 de ranking is van een huishouden voor de kavels dat voor 20 huishoudens kom je op a-t uit.

Waarbij:

x1 element uit (a1, b1, c1, .. , t1)

x2 element uit (a2, b2, c2, .. , t2)

.

.

x20 element uit (a20, b20, c20, .. , t20)

en

0 < x1 + x2 + x3 + ... + x20 < 21

Vraag 1

Hoe is het bovenstaande probleem op te lossen?

Probleem 2

Zo simpel als het probleem hierboven is geschetst is het natuurlijk niet, maar wel een goed begin als dat iig duidelijk is. Naast de ranking die huishoudens kunnen geven aan een kavel heeft een huishouden zelf ook een ranking op basis van binnenkomst in de groep.

Vraag 2

Hoe is de ranking van binnenkomst mee te nemen en hoe is het bovenstaande probleem dan op te lossen?

Iemand die met hierbij kan helpen?

317070

Woeka schreef:Vraag 1

Hoe is het bovenstaande probleem op te lossen?

Dit is een niet-triviaal probleem, en het is op te lossen met

Probleem 2

Zo simpel als het probleem hierboven is geschetst is het natuurlijk niet, maar wel een goed begin als dat iig duidelijk is. Naast de ranking die huishoudens kunnen geven aan een kavel heeft een huishouden zelf ook een ranking op basis van binnenkomst in de groep.

Hoe is de ranking van binnenkomst mee te nemen en hoe is het bovenstaande probleem dan op te lossen?

Gebruik:

c1*x1 + c2*x2 + c3*x3 + ... + c20*x20 -> min

Met c als het gewicht voor hoe belangrijk die familie is. 1-> heel belangrijk. 0->irrelevant.

Na wat opzoekwerk heb ik het algoritme gevonden. Je probleem is een "weighted matching problem in a bipartite graph".

In a weighted bipartite graph, each edge has an associated value. A maximum weighted bipartite matching[2] is defined as a perfect matching where the sum of the values of the edges in the matching have a maximal value. If the graph is not complete bipartite, missing edges are inserted with value zero. Finding such a matching is known as the assignment problem. It can be solved by using a modified shortest path search in the augmenting path algorithm. If the Bellman-Ford algorithm is used, the running time becomes O(V2E), or the edge cost can be shifted with a potential to achieve O(V2log(V) + VE) running time with the Dijkstra algorithm and Fibonacci heap. The remarkable Hungarian algorithm solves the assignment problem and it was one of the beginnings of combinatorial optimization algorithms. The original approach of this algorithm need O(V2E) running time, but it could be improved to O(V2log(V) + VE) time with extensive use of priority queues.

Kaspace

Ik begrijp dat dit een praktijksituatie is. Niet elk huishouden is hetzelfde. Je hebt er van 1, 2 en nog meer personen. Wellicht kan het probleem vereenvoudigd worden door die variatie mee te nemen. Het aantal willekeurige mogelijkheden vermindert én je houdt toch meer rekening met individuele behoeftes.

Woeka

Bedankt voor de tips,

Het geheel kon iets worden versimpeld tot een 16x16 probleem door huishoudens voor een hoekhuis en een tussenwoningen te scheiden. De tussenwoningen is een 4x4 probleem dus die is makkelijk op te lossen met Matlab of zelfs met de hand, 4! = 24 oplossingen. Die 16! zijn er echter nog steeds te veel

Als ik eruit ben zal ik het resultaat posten, maar laat je dat niet weerhouden te reageren als je nog tips hebt

Wetenschapsforum

Laatste berichten

Nieuwsberichten

Optimalisatie kavelverdeling in woonwijk

Optimalisatie kavelverdeling in woonwijk

Re: Optimalisatie kavelverdeling in woonwijk

Re: Optimalisatie kavelverdeling in woonwijk

Re: Optimalisatie kavelverdeling in woonwijk