Optimisation de séjour en gite ou hotel

Version imprimable

10/02/2019, 22h28
Louprouge

1 pièce(s) jointe(s)

Optimisation de séjour en gite ou hotel

Bonjour à tous,

J'aimerais mettre au point une méthode me permettant d'optimiser l'occupation d'une chambre pendant une période donnée ( par exemple sur un mois) avec comme but de laisser les chambres inoccupées libres un maximum de temps consécutif.
Ceci permettrait de les occuper pour un long séjour le cas échéant.

Par exemple, dans mon hôtel de 13 chambres, où l'on considère que toutes les chambres sont absolument identiques, si j'ai les réservations suivantes :

- du 1 au 7
- du 1 au 16
- du 2 au 18
- du 8 au 14
- du 15 au 23
- du 15 au 27
- du 19 au 27
- du 21 au 29
- du 24 au 28
- du 28 au 31
- du 28 au 30
- du 29 au 31
- du 30 au 31

Je peux placer ces réservations sur les 13 chambres différentes. Mais si on veut me réserver un séjour d'un mois, ce ne sera plus possible.

Par contre, je peux placer dans la 1ere chambre les séjours du 1 au 7, du 8 au 14, du 15 au 27 et du 28 au 31
Dans une seconde chambre, je peux placer les séjours du 1 au 16, du 19 au 27 et du 28 au 30
Dans la 3eme chambre, je mettrai le séjour du 2 au 18 , du 21 au 29 et du 30 au 31
Dans la 4eme je mettrai enfin les séjours du 15 au 23, du 24 au 28 et du 29 au 31

La chambre 1 sera occupée les 31 jours du mois
La chambre 2 n'aura que 3 nuitées sans occupation
La chambre 3 aura également 3 nuitées inoccupées
La chambre 4 aura 14 nuitées consécutives libres
et les chambres de 5 à 13 seront entièrement libres.

Cette optimisation me permet potentiellement d'accepter 8 séjours d'un mois, ce qui n'était pas possible dans la première version des réservations.

Comment puis-je automatiser cette optimisation ?
Pour ne pas ré-inventer la roue, un algorithme réutilisable de ce type existe-t-il déjà ?

En annexe, je joint un fichier avec mes essais.

J'ai tenté, avec un hôtel de 15 chambres et 32 séjours à caser, de remplir la grille d'occupation dans l'ordre de réception des réservations, en plaçant celles-ci dans un endroit libre.
Cela laisse apparaître beaucoup de nuit libres dans chaque chambre, ce qui empêche de d'accepter des réservations pour certains long séjours.

Ensuite j'ai essayé de remplir les chambres en plaçant d'abord les séjours les plus long, puis en complétant les "trous" avec des séjours plus court. Cette méthode permet déjà un meilleur taux d'occupation des premières chambres, mais un examen attentif des attributions permet de voir que certains séjours plus court ne sont pas idéalement placés car les dates sont déjà occupées par des séjours plus long. Pourtant, avec certaines permutations, on pourrait allonger certaines périodes "libres".

J'ai donc modifié ma méthode de remplissage en combinant d'abord les séjours qui s'enchaînent pour les placer dans la même chambre (par exemple, du 1 au 7, du 8 au 14, du 15 au 27 et du 28 au 31.
La première chambre est ainsi complète tout le mois, ce qui est idéal.

Mais si vous regardez la pièce jointe plus attentivement, dans le 3eme tableau, une permutation du séjour 20 avec les séjours 17 et 29 ainsi qu'une permutation entre les séjours 23 et 28 avec le séjour 24 , 2 chambres peuvent accepter des séjours plus long qu'avant.

Dans la pièce jointe, la colonne de gauche indique le numéro de la chambre , celle de droite indique le nombre de nuitées libres par chambre.
Les cases rouges numérotées indiquent le numéro de séjour.

Quelle serait la meilleure méthode pour combiner ces réservations ?
11/02/2019, 00h08
tbc92

Voici la démarche que je vois pour optimiser la disposition.
Tu classes toutes les réservations, en fonction de la date de début ; peu importe la date de fin de chaque réservation.
Tu prends la 1ère réservation, et tu la mets dans la 1ère chambre où elle peut aller, la chambre n°1 donc.
Et ainsi de suite. Pour chaque réservation, tu la cases dans la 1ère chambre compatible.
Ainsi, tu as l'assurance que l'occupation sera optimisée.

Si certains clients demandent à avoir une chambre bien précise pour leur séjour, c'est plus compliqué.
11/02/2019, 00h12
bstjean

Ce que tu recherches en fait est un algorithme qui s'appelle "Best Fit" souvent utilisé dans les problématiques d'allocation de blocs de mémoire. Tu devrais trouver sans problème en googlant un peu!
11/02/2019, 02h16
Flodelarab

Bonjour :coucou:

@tbc92 : 2 chambres et 3 réservations.
Du 1 au 2.
Du 2 au 29
Du 30 au 31.
Si tu fais par disponibilité, la chambre 1 va recevoir la première et la troisième réservations, cassant la grande plage, alors que mettre les 2 dernières réservations pour la chambre 2 est optimal.

@bstjean: Un programme peut être à n'importe quelle place dans la mémoire. Pas les jours de réservation.

@Louprouge:
Je verrais bien un système de calcul de score égal à la somme du carré des longueurs des espaces disponibles.
Tu pars du plus grand possible putatif, et tu diminues.
Quand tu trouves une disposition possible, tu t'arrêtes car c'est un maximum.
11/02/2019, 02h30
bstjean

Citation:

Envoyé par Flodelarab

@bstjean: Un programme peut être à n'importe quelle place dans la mémoire. Pas les jours de réservation.

Il s'agit exactement du même algorithme. Le programme demande une plage mémoire (ou de jours) et l'algorithme Best Fit trouve le bloc le plus petit satisfaisant la demande. Des variantes existent (notamment les algorithmes de "garbage collection" avec de multiple zones d'allocation ("new space"). Suffit de transposer le problème de blocs de mémoire en blocs de disponibilité.
11/02/2019, 14h07
Louprouge

Merci pour vos interventions et conseils.

@tbc92 : Je pense que c'est la seconde méthode que je décris. Si il y a déjà une belle optimisation, elle n'est pas maximale dans tous les cas de figure: 2 séjours courts peuvent occuper partiellement une chambre alors que combinés avec 2 autres séjour courts ils auraient pu compléter complètement une autre chambre.

@Flodelarab : Je suis (très) mauvais en mathématiques, mais je fais des efforts: si je suis ta suggestion, je ne comprend pas pourquoi je dois passer par le carré des jours libres ? Peux-tu développer un peu ta suggestion ?

@bstjean : j'ai trouvé un code source avec l'algorithme best-fit. https://www.thecrazyprogrammer.com/2...rithm-c-c.html
il y a effectivement une recherche de capacité correspondante mais cela ne tient compte que de la possibilité de faire entrer un process dans un block, mais pas d'optimiser le remplissage. En effet, dès qu'un process entre dans un blcok, il y est placé. Même si le block est trop grand et qu'un autre block plus loin aurait mieux convenu. De plus, cet algorithme ne tiens pas compte des combinaisons de séjours qui pourraient mieux remplir une chambre qu'en les considérant séparément.
11/02/2019, 17h37
tbc92

Corrigeons mon algorithme.

- Je classe les réservations selon la date de début (comme dans ma 1ère proposition)
- Je vais traiter les réservations, séquentiellement, selon cet ordre.
- Pour chaque réservation, je la case dans la chambre qui convient le mieux.... Ca veut dire quoi ? J'ai la date de début de ma réservation DATE0.
--- Pour chaque chambre, je sais dire si elle est compatible ou non ( libre sur la période , ou non). J'élimine les chambres non compatibles.
--- Pour chaque chambre restante, je peux calculer la dernière date à laquelle cette chambre est occupée. Par construction cette date DATE1 est inférieure à DATE0.
--- Je prends la chambre pour laquelle DATE1 est maximum.
--- Si plusieurs chambres ont la même date DATE1, on en choisit une au hasard.
- Et on boucle, on passe à la réservation suivante.
11/02/2019, 19h02
anapurna

salut

pourquoi ne pas créer un arbre et sélection les branches max ?
11/02/2019, 22h29
Louprouge

1 pièce(s) jointe(s)

@anapurna : comme dit plus haut, je ne suis pas bon en math (y compris en vocabulaire). Pourrais-tu développer un peu ta suggestion svp ?

@tbc92 : Je viens de simuler ta proposition: Dans l'ordre des dates de réservation, on place le séjour dans la première chambre libre ayant sa date de fin d'occupation la plus proche du début du séjour que je considère. Dans le fichier joint, le second tableau affiche ton résultat.
Le premier tableau affiche le meilleur résultat précédent.
En dessous , on a la liste des séjours à caser.

L'agencement semble meilleur que mes précédents essais car j'ai seulement 4 séjours limités à une nuit maximum alors qu'avant j'en avais 7 dans le cas.
Ensuite, j'ai refais le même exercice en classant les séjours par date de début identique ET par durée décroissante.
Il me semble que le résultat est légèrement meilleurs car je réduis aussi le nombre de séjours limités à 3 nuits.

Excellent algorithme de tbc92. :bravo:

A noter : même quantité de trous de taille égale, si on prend l'algorithme dans l'autre sens (en partant de la fin), mais pas la même configuration

Entrée :

Code:

Sortie par le début :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
01 01 01 08 08 08 08 08 08 08 00 10 10 10 10 10 10 10 18 18 18 18 18 18 18 18 18 31 31 31 31
02 02 02 02 02 00 00 00 00 00 00 13 13 13 13 00 00 00 00 00 21 21 21 21 21 21 30 30 30 30 30
03 03 03 03 03 03 03 09 09 09 09 09 09 09 14 14 14 14 14 14 14 14 14 14 14 14 14 32 32 32 00
04 04 04 04 04 04 04 04 04 00 00 11 00 00 15 15 15 15 15 15 15 15 15 26 26 26 26 33 33 00 00
05 05 05 05 05 05 05 05 00 00 00 12 12 12 12 12 12 12 00 00 19 19 19 19 19 19 19 19 19 00 00
07 07 07 07 07 07 07 07 07 07 07 07 07 07 07 07 00 16 16 17 17 17 17 17 17 28 28 28 28 28 00
00 00 06 06 06 06 06 06 06 06 06 06 06 06 06 06 00 00 00 00 20 20 20 20 20 20 20 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 22 22 22 27 27 27 27 27 27 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 23 23 23 23 23 29 29 29 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 24 24 24 24 24 24 24 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 25 25 25 25 25 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Sortie par la fin :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
01 01 01 08 08 08 08 08 08 08 00 10 10 10 10 10 10 10 00 00 22 22 22 26 26 26 26 31 31 31 31
00 00 06 06 06 06 06 06 06 06 06 06 06 06 06 06 00 00 00 00 21 21 21 21 21 21 30 30 30 30 30
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 25 25 25 25 25 32 32 32 00
04 04 04 04 04 04 04 04 04 00 00 13 13 13 13 00 00 00 00 00 23 23 23 23 23 28 28 28 28 28 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 20 20 20 20 20 20 20 33 33 00 00
03 03 03 03 03 03 03 09 09 09 09 09 09 09 15 15 15 15 15 15 15 15 15 27 27 27 27 27 27 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 19 19 19 19 19 19 19 19 19 00 00
07 07 07 07 07 07 07 07 07 07 07 07 07 07 07 07 00 16 16 17 17 17 17 17 17 29 29 29 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 24 24 24 24 24 24 24 00 00 00
05 05 05 05 05 05 05 05 00 00 00 12 12 12 12 12 12 12 18 18 18 18 18 18 18 18 18 00 00 00 00
02 02 02 02 02 00 00 00 00 00 00 11 00 00 14 14 14 14 14 14 14 14 14 14 14 14 14 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Et les trous : (identiques donc)

Code:

1
2
3
4
5
6
7
8
9
10
4 trous de taille 1
7 trous de taille 2
3 trous de taille 3
3 trous de taille 4
1 trou de taille 5
1 trou de taille 6
2 trous de taille 20
1 trou de taille 21
1 trou de taille 22
4 trous de taille 31

13/02/2019, 09h46
Louprouge

Merci à tous pour votre aide. Je pars sur l'algorithme de tbc92.
Merci à Flodelarab pour la vérification poussée en ordre inverse: Je l'avais simuler mais sans arriver à déterminer si la différence était en faveur d'une méthode ou de l'autre. Maintenant, je sais que cela revient au même :)

Je clôturerai le sujet ce jeudi pour le cas ou quelqu'un voudrait ajouter un commentaire.
23/09/2019, 00h54
Louprouge

fixer ou non les chambres

Bonsoir,

Je ré-ouvre ce topic parce que je n'arrive pas à trancher :
Dois-je associer le séjour que j'ajoute à une chambre, ou dois-je faire mes attribution dynamiquement ?

Imaginons que j'ai 2 séjours :
- Du 1 au 5
- Du 15 au 20

j'ai donc 10 jours libres pour ma chambre. Si je les assignes à la chambre 1, et que j'ai ensuite un séjour du 7 au 12, je peux également l'assigner dans cette chambre 1.
Mais si le lendemain on me demande un séjour du 6 au 14 je serai obligé de le placer dans la chambre 2.

Par contre, si je fais les assignations dynamiquement, j'aurai dans la chambre 1 les séjours du 1 au 5 , du 6 au 14 et du 15 au 20 , le séjour du 7 au 12 passant dans la chambre 2 et libérant un maximum de jours libres dans celle-ci.

Mais cette assignation dynamique va poser problème si un séjour est en cours: je vais changer les clients de chambre, et ça c'est à éviter.

Pouvez-vous me suggérer une méthode cohérente ?

Merci d'avance pour vos idées.
23/09/2019, 09h56
tbc92

Il faut le refaire dynamiquement, idéalement après chaque nouvelle réservation.
Mais quand tu fais tourner le process, il faut ajouter une contrainte : un séjour qui est commencé ne peut pas être modifié. Ca ne changera rien sur la vue d'ensemble des disponibilités, ça revient juste à permuter des chambres 2 à 2.
Ce serait un peu plus délicat si on devait gérer des cas comme : le client X a demandé spécifiquement une chambre au 1er étage, le client Y a demandé spécifiquement une chambre tout près de l'ascenseur ... mais c'est hors-sujet pour l'instant.
23/09/2019, 10h05
Louprouge

Merci Tbc92.

Je suppose que le cas du client qui a des desiderata doit être considéré comme si son séjour était commencé ?
23/09/2019, 18h14
anapurna

salut

tu as deux cas possible mobile et non mobile
donc ceux qui ont une exigence et les séjour déjà entamé
a moins que tu joue sur des surclassement mais ceci est une autre histoire
23/09/2019, 22h49
Louprouge

ok. Merci à tbc92 et anapurna pour leurs réponses, je vois mieux ou je vais.
je passerai le sujet en résolu demain, pour le cas ou quelqu'un voudrait ajouter quelque chose.

Encore merci.