Algo de placement par rapport a des periodes donees

Bonjour le forum,

Dans un projet de Gestion de camping, je voudrais un algorithme permettant l'optimisation d'attributions d'emplacements par rapport aux periodes reservees par un camper.
Je m'explique avec un petit exemple tres simpliste:

Soit un camping a 2 emplacements.
Paul reserve du 2 au 8. => Emplacement 1 attribue
Marc reserve du 10 au 16. => Emplacement 2 attribue
Si Jean veut reserver du 7 au 12, aucun emplacement ne sera disponible !
(Alors qu'il aurait ete possible en attribuant a Marc l'emplacement 1)


Voila l'idee. J'ai cherche du cote d'un algorithme d'ordonnancement mais je n'arrive pas a trouver ce qui me convient.
Une idee d'un algorithme existant se rapprochant de mon probleme ?
Toute piste m'interesse

Merci de m'orienter !

Hello,

Intéressant comme question. Il me semble qu'en cherchant du côté des algorithmes de génération d'horaires, on trouve pas mal de choses.

A première vue (je n'ai pas lu les articles que je te propose, mais ça semble une base de départ interessante, mais en anglais), jette un oeil là dessus:
http://www.emo.org.tr/ekler/76e76856c7fea3b_ek.pdf (technique de coloration de graphe)
http://secretgeek.net/content/bambrilg.pdf (version génétique)
http://en.wikipedia.org/wiki/Hill_climbing (un algo d'optimisation locale, part d'une solution et essaie de l'améliorer)

Ca devrait te donner une base de départ.

Je n'ai encore rien lu sur la question, mais le problème m'interesse, on va donc creuser un peu ;-)

Salut,

Merci pour ta réponse et ton enthousiasme ! =)
J'ai lu tes 3 liens, je trouve cela intéressant mais le problème est que ça reste super flou. Je n'ai aucune expérience dans le domaine de ce genre d'algorithme, je ne fais que découvrir ce qui existe pour le moment, après pour les comprendre plus en profondeur c'est autre chose... =/

Effectivement, le Hill Climbing semble être une bonne piste, mais m'a l'air relativement compliqué au premier abord, j'ai du mal à y projeter les données de mon problème.

Je continue à regarder tout cela, si tu a d'autres idées n'hésite pas

Encore merci pour ton intérêt !!

Bon, au fil de mes recherches, je pense avoir trouvé quelque chose d'intéressant :
L'algorithme des noeuds-chapeaux (ou algorithme de Rayrole). Je pense que ça pourrait être une bonne base.

http://www.developpez.net/forums/d514050/c-cpp/c/contribuez/calendrier-dallocation-ressources-algorithme-rayrole/#post3078887

PErso j'ai un problème un poil différent à organiser (plutôt une question d'optimisation de ressources en fait), du coup je vais attaquer Hill Climbing et voir comment on peut essayer d'y projetter un problème du type "allocation de ressources"

Ok merci beaucoup !
De mon coté je cherche toujours d'autres pistes, j'ai du mal à attaquer quelque chose de concret =/ . Je vais tout de même essayer de comprendre plus en détail l'algo de Rayrole. Le problème avec cet algorithme est que je ne vois pas comment y intégrer le fait d'avoir plusieurs "Emplacements".

Voilà pour le moment ;-)

Je me suis posé la même question en le découvrant (Rayrole donc) sur wikipedia tout à l'heure... Bien pour planifier pour un seul emplacement, par contre plusieurs j'ai du mal à voir...

Bonjour,
Ce projet pourrait être un début d'inspiration:
http://www.codeproject.com/KB/recipes/GaClassSchedule.aspx


louis

Hello,
Je me rappelles quand j'étais étudiant la tonne d'erreurs qu'on retrouvait dans l'élaboration du planning de la semaine, avec les réservations de salles etc.
Du coup, je ne pense pas qu'il existe un algo vraiment efficace.
Bon courage en tout cas...

@+
Buno
----------------------------------------
L'urgent est fait, l'impossible est en cours. Pour les miracles, prévoir un délai...

Hmmm toujours étudiant, donc j'ai la joie d'avoir des planings automatiques. Chez nous ça marche pas trop mal. Il parrait (d'après le prof qui s'en occupe) qu'il y'a un soft d'optimisation derrière (un truc du genre Hill Climbing dans l'idée), et que les retouches sont faites à la main.