Algo de placement par rapport à des périodes données

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 ?
Tout piste m'interesse ;)

Merci de m'orienter ! :P

Citation:

---

Envoyé par romfret

Voila l'idee. J'ai cherche du cote d'un algorithme d'ordonnancement mais je n'arrive pas a trouver ce qui me convient.

---

Il te faut plutôt un algorithme de réservation/booking de ressources.

Citation:

---

Une idee d'un algorithme existant se rapprochant de mon probleme ?
Tout piste m'interesse ;)

---

Ca se rapproche des algos de type "système réducteur", avec du packing (vertical) :

Code:

---

1 2 3 4 5 6 7

date: 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 Paul : PPPPPPPPPPPPPPPPPPPP Marc : MMMMMMMMMMMMMMMMMMMM Jean : JJJJJJJJJJJJJJJJJ   Emplacement 1 : -------------------------------------------------- Emplacement 2 : --------------------------------------------------

---

Ok merci pour ces infos, je vais fouiller 8-)

Bon après des recherches, j'ai eu quelques pistes de base à adopter.

On m'a conseillé l'algorithme "Hill Climbing".

Sinon, que pensez-vous de l'algorithme des noeuds-chapeaux ?
http://www.developpez.net/forums/d51...e/#post3078887

Voilà je parcours un peu tous les algorithmes existant pour le moment, je n'ai pas vraiment de connaissances dans le domaine de ce genre d'algo, tout cela me parait encore flou.

Voilà où j'en suis pour le moment, des suggestions ? ^^

Citation:

---

Envoyé par romfret

Bon après des recherches, j'ai eu quelques pistes de base à adopter.

On m'a conseillé l'algorithme "Hill Climbing".

---

C'est plus une "technique générale" qu'un algorithme particulier, mais oui c'est une bonne approche

Citation:

---

Sinon, que pensez-vous de l'algorithme des noeuds-chapeaux ?
http://www.developpez.net/forums/d51...e/#post3078887

---

Hum... L'algo de rayrole n'est pas vraiment fait pour optimiser l'allocation des ressources.

On peut utiliser une approche qui consiste à attribuer un poids (coefficient de difficulté à chaque demande) puis à attribuer les emplacements en traitant en priorité les demandes les plus difficiles.

Pour calculer le coefficient de difficulté, on peut prendre l'ensemble des demandes et faire une attribution dans un ordre aléatoire en prenant le premier emplacement dispo. Une fois ces allocation faites, on atttribue à chaque demande un poids égal au nombre d'autres emplacements susceptibles de satisfaire la demande. Les demandes les plus difficiles auront un poids égal à 0 et les plus faciles (une canadienne en janvier) auront un poids élevé pour ). Pour départager les ex-aequo, on pourra refaire un calcul avec une allocation initiale réalisée avec seulement 80% des demandes.

Après calcul des coeff de difficulté, on attribue donc les emplacements en traitant en priorité les demandes les plus difficiles. Il reste des echecs que l'on peut "retraiter" en faisant des permutations. Une allocation par permutation consiste à trouver un emplacement qui pourrait être dispo à condition de bouger des demandes plus faciles vers d'autres emplacements pouvant convenir à ces demandes. On peut évidement améliorer le processus en cascadant plusieurs permutations (en veillant bien à ce que les mouvements portent sur demandes moins difficiles).

Citation:

---

Envoyé par Graffito

On peut utiliser une approche qui consiste à attribuer un poids (coefficient de difficulté à chaque demande) puis à attribuer les emplacements en traitant en priorité les demandes les plus difficiles.

Pour calculer le coefficient de difficulté, on peut prendre l'ensemble des demandes et faire une attribution dans un ordre aléatoire en prenant le premier emplacement dispo. Une fois ces allocation faites, on atttribue à chaque demande un poids égal au nombre d'autres emplacements susceptibles de satisfaire la demande. Les demandes les plus difficiles auront un poids égal à 0 et les plus faciles (une canadienne en janvier) auront un poids élevé pour ). Pour départager les ex-aequo, on pourra refaire un calcul avec une allocation initiale réalisée avec seulement 80% des demandes.

Après calcul des coeff de difficulté, on attribue donc les emplacements en traitant en priorité les demandes les plus difficiles. Il reste des echecs que l'on peut "retraiter" en faisant des permutations. Une allocation par permutation consiste à trouver un emplacement qui pourrait être dispo à condition de bouger des demandes plus faciles vers d'autres emplacements pouvant convenir à ces demandes. On peut évidement améliorer le processus en cascadant plusieurs permutations (en veillant bien à ce que les mouvements portent sur demandes moins difficiles).

---

Je trouve cette approche excellente. Mais, est-ce vraiment efficace pour un camping a 40 emplacements..? Les traitements peuvent etre longs ? (Je pense particulierement aux permutations)

J'ai trouvé une autre approche qui consisterait à réduire au maximum la durée entre chaque réservation.

Contrainte :
Impossible de modifier une réservation "en cours".

Soit un camping à 2 emplacements. Nous sommes le 5 (toutes réservation incluant le 5 sera donc "en cours").

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Réservations déjà fixées (car "en cours") : - Eplt1 : du 3 au 8. - Eplt2 : du 2 au 6.   Réservations susceptibles d'être modifiées (car pas "en cours") : - Eplt1 : rien. - Eplt2 : rien.   Réservations fixées (car aucun écart > 0 ; optimisation optimale) : - Eplt1 : rien. - Eplt2 : rien.

---

Paul veut réserver du 10 au 14.
- Eplt1 : 10 - 8 = 2 jours d'écart
- Eplt2 : 10 - 6 = 4 jours d'écart

Nous choisissons donc l'Eplt1 ( min(Eplt1, Eplt2) )

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Réservations déjà fixées (car "en cours") : - Eplt1 : du 3 au 8. - Eplt2 : du 2 au 6.   Réservations susceptibles d'être modifiées (car pas "en cours"): - Eplt1 : du 10 au 14. - Eplt2 : rien.   Réservations fixées (car aucun écart > 0 ; optimisation optimale) : - Eplt1 : rien. - Eplt2 : rien.

---

Maintenant, Marc veut réserver du 6 au 10. Seul l'Eplt2 est dispo, il lui est attribué.
On reteste les autres réservations aprés le 10 : L'écart pour Paul devient 0 sur l'Eplt2, on lui l'attribue (0 < 2).

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Réservations déjà fixées (car "en cours") : - Eplt1 : du 3 au 8. - Eplt2 : du 2 au 6.   Réservations susceptibles d'être modifiées (car pas "en cours"): - Eplt1 : rien. - Eplt2 : rien   Réservations fixées (car aucun écart > 0 ; optimisation optimale) : - Eplt1 : rien. - Eplt2 : du 6 au 10. du 10 au 14.

---

Voilà, je pense que ça pourrait être une bonne façon de voir les choses, et je pense pas si dur que ça à implémenter.

Citation:

---

Les traitements peuvent etre longs ? (Je pense particulierement aux permutations)

---

Avec 40 places et quelques milliers de réservations, les temps de calculs devraient être de l'ordre de la seconde, y compris les permutations.

Citation:

---

Envoyé par Graffito

Avec 40 places et quelques milliers de réservations, les temps de calculs devraient être de l'ordre de la seconde, y compris les permutations.

---

OK, que penses-tu de ce que je propose ?

Citation:

---

Envoyé par romfret

OK, que penses-tu de ce que je propose ?

---

C'est un algo glouton sur le taux maximum d'occupation d'un emplacement.

C'est une solution qui en vaut une autre, quoiqu'il paraitrait plus rentable de maximiser le taux "global" d'occupation plutôt que celui d'un seul emplacement. :D

Citation:

---

Envoyé par pseudocode

C'est un algo glouton sur le taux maximum d'occupation d'un emplacement.

C'est une solution qui en vaut une autre, quoiqu'il paraitrait plus rentable de maximiser le taux "global" d'occupation plutôt que celui d'un seul emplacement. :D

---

Le but est bien de toujours avoir un emplacement de libre (dans la mesure du possible bien sur).
Grace au fait de maximiser le taux d'UN emplacement, on maximise le taux "global", non ? ( 1 + 1 + 1 + 1....)
Je ne voit pas bien ce que tu veux dire.

Je vais analyser en détail la methode de Graffito et voir ce que ça donne.

Citation:

---

Envoyé par romfret

Le but est bien de toujours avoir un emplacement de libre (dans la mesure du possible bien sur).
Grace au fait de maximiser le taux d'UN emplacement, on maximise le taux "global", non ? ( 1 + 1 + 1 + 1....)
Je ne voit pas bien ce que tu veux dire.

---

Je voulais juste dire que même si cette stratégie est mathématiquement possible, elle n'est peut être pas la meilleure d'un point de vue marketing ou organisationnelle pour le camping.

Répartir uniformément les gens sur les emplacements, ou minimiser le turn-over sur un emplacement, ca peut être aussi une bonne chose. ;)

Citation:

---

Envoyé par pseudocode

Je voulais juste dire que même si cette stratégie est mathématiquement possible, elle n'est peut être pas la meilleure d'un point de vue marketing ou organisationnelle pour le camping.

Répartir uniformément les gens sur les emplacements, ou minimiser le turn-over sur un emplacement, ca peut être aussi une bonne chose. ;)

---

Oui ok, c'est bien vrai ^^

Citation:

---

OK, que penses-tu de ce que je propose ?

---

Ca me semble correspondre à ce que ferait à la main un gestionnaire de camping pour pendre successivement de nouvelles reservations, en traitant comme une suite de "nouvelles" reservations celles susceptibles d'être modifiées plus la dernière demande.

Juste une remarque : Quelque soit l'approche utilisée, il faut garder "en secours" l'allocation déjà effectuée, afin de ne pas devoir annuler des reservations confirmées.

Compte tenu de cette contrainte, on doit opérer une réallocation pour chaque reservation nouvelle.



Dans l'esprit de l'approche que je t'ai proposée, on cherchera un emplacement libre pour la durée de la nouvelle résa et, en cas d'echec :

• on opèrera le calcul de poids sur l'ensemble des résa,
• on essayera d'identifier les permutations enviseagables, c'est-à-dire celles impliquant le déplacement de reservations moins difficiles,
• on traitera chaque permutation envisageable en testant sa faisabilté, c'est-à-dire la possibilité de trouver un autre emplacement libre pour les réservations de l'emplacement concerné recouvertes par la nouvelle demande.

Pour optimiser, lorsque tu as le choix entre plusieurs emplacements libres, tu peux évidement choisir le plus pertinent à priori, soit celui minimisant le nombre de jours "vides" par rapport à la fin(au début) du séjour précédent(suivant) sur le même emplacement.

ok merci pour cette piste, je reviens après avoir traité ma GUI ;)

Il y a peut être un détail qui m’échappe mais il y a deux éléments qui font que ton problème d'affectation est grandement simplifié : tu ne peux pas faire glisser dans le temps les périodes d'occupation des campeurs, tu ne peux pas annuler une demande d'occupation déjà acceptée. La seule liberté est celle de permuter un campeur d'un emplacement à un autre. Mais a priori tout les emplacements libres sont équivalents, non ?

Donc il me semble qu'il suffit de prendre les demandes dans un ordre chronologique et de les affecter à un emplacement libre. S'il n'y a pas d'emplacement libre alors la demande n'est pas traitable, s'il y a plusieurs emplacements libres alors ils sont tous équivalents.

Si tu veux tu peux choisir de remplir en priorité certains emplacement mais cela n'aura pas d'impact (enfin il me semble) sur la faisabilité ou non.

Effectivement, l'algorithme est maintenant ecrit.

Les grandes lignes sont:
1. récupération des bookings concernés.
2. Pour chaque booking, je récupère le booking le plus proche a "gauche" et le booking le plus proche a "droite" (ça me fait donc des tableaux a 3 cases de bookings).
3. je produit des listes chaînées (= les emplacements en faite) avec les bookings les plus proches entre eux.

Voila, c'est très simplifie mais l’idée est la ;)