Discussion :

[lolotomik]

Bonjour à tous,

Je dois mettre en place un logiciel permettant de disposer au mieux des pièces dans un bâtiment, contenant des étages.

Chaque pièce a une dimension (un rectangle), et peut être obligée d'être assignée à un étage. Elle contient un nombre de personnes permanentes. On peut saisir les pièces favorites des personnes de celle-ci (déplacements).

Je souhaite trouver des informations sur des algorithmes existants, afin de maximiser l'espace disponible restant, ainsi que les flux dans les couloirs (le moins de monde possible).

Mon professeur m'a orienté vers l'algorithme du Knapsack Problem de Mr Karp, mas celui-ci ne répond pas à mes attentes.

Merci à ceux tous ceux qui me liront et pourront m'apporter quelques pistes de réflexions.

Bonne soirée à vous

[pseudocode]

C'est loin d'être évident de modéliser le problème pour y appliquer un algorithme d'optimisation.

Le contrainte la plus forte semble être celle du packing : il faut que toutes les pièces choisies soient positionnés sur le plan, sans recouvrement. Le choix des pièces doit être fait pour réduire les flux de circulation inter-étage.

Je commencerais par trouver le plus grand nombre de configurations possibles pour ce 1er problème, qui est déjà complexe. Dans un deuxième temps, on pourrait alors reprendre chaque configuration trouvée et chercher à réduire davantage les flux de circulation et augmenter l'espace libre, en faisant des micros optimisations (petits changements sur la configuration, sans changer les pièces d'étage).

Tout ca reste très général et ce n'est qu'une première idée, à froid.

[Branch]

Bonjour à tous,

Je dois mettre en place un logiciel permettant de disposer au mieux des pièces dans un bâtiment, contenant des étages.

Chaque pièce a une dimension (un rectangle), et peut être obligée d'être assignée à un étage. Elle contient un nombre de personnes permanentes. On peut saisir les pièces favorites des personnes de celle-ci (déplacements).

Je souhaite trouver des informations sur des algorithmes existants, afin de maximiser l'espace disponible restant, ainsi que les flux dans les couloirs (le moins de monde possible).

Mon professeur m'a orienté vers l'algorithme du Knapsack Problem de Mr Karp, mas celui-ci ne répond pas à mes attentes.

Merci à ceux tous ceux qui me liront et pourront m'apporter quelques pistes de réflexions.

Bonne soirée à vous

Je vais peut-être dire une bêtise, mais si chaque pièce à une dimension (fixé à l'avance) n'importe quelle solution respectant tes contraintes laissera le même espace disponible restant, non ?

Concernant les flux dans les couloirs tu peux peut-être modéliser ca par la sommes des distances entre la pièce à laquelle chacune de tes personnes est assigné et ses pièces préférés... Mais dans ce cas comment calcules-tu la distance entre 2 pièces (distance euclidienne entre les 2 points les plus proches des rectangles ou alors tu ne considere que tes usagers ne peuvent circuler que dans les espaces vide...)

[lolotomik]

Bonjour,

Merci beaucoup pour vos idées, qui m'aident à modéliser le problème.
Branch, l'espace disponible restant peut être variable car en effet certaines pièces ne sont définies que par leur surface, pas de dimensions données.

Il faut donc que je commence par définir le meilleur étage pour chaque pièce selon ses pièces destinataires favorites, et ensuite optimiser l'espace au sein de chaque étage.
Il faut que je réfléchisse maintenant à cette deuxième phase

Merci encore
Lolo.

[souviron34]

le base de ce que tu recherches est Le problème du sac à dos