Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Membre à l'essai
    Homme Profil pro
    Astronaute pompier
    Inscrit en
    octobre 2015
    Messages
    20
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Astronaute pompier

    Informations forums :
    Inscription : octobre 2015
    Messages : 20
    Points : 18
    Points
    18

    Par défaut 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 ?
    Images attachées Images attachées  

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 384
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 384
    Points : 5 029
    Points
    5 029

    Par défaut

    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é.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Membre régulier
    Homme Profil pro
    Analyste-programmeur
    Inscrit en
    décembre 2014
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France

    Informations professionnelles :
    Activité : Analyste-programmeur
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2014
    Messages : 44
    Points : 86
    Points
    86

    Par défaut

    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!

  4. #4
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 608
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 608
    Points : 8 658
    Points
    8 658

    Par défaut

    Bonjour

    @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.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  5. #5
    Membre régulier
    Homme Profil pro
    Analyste-programmeur
    Inscrit en
    décembre 2014
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France

    Informations professionnelles :
    Activité : Analyste-programmeur
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2014
    Messages : 44
    Points : 86
    Points
    86

    Par défaut

    Citation Envoyé par Flodelarab Voir le message
    @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é.

  6. #6
    Membre à l'essai
    Homme Profil pro
    Astronaute pompier
    Inscrit en
    octobre 2015
    Messages
    20
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Astronaute pompier

    Informations forums :
    Inscription : octobre 2015
    Messages : 20
    Points : 18
    Points
    18

    Par défaut

    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.

  7. #7
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 384
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 384
    Points : 5 029
    Points
    5 029

    Par défaut

    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.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  8. #8
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 842
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 842
    Points : 4 674
    Points
    4 674

    Par défaut

    salut

    pourquoi ne pas créer un arbre et sélection les branches max ?
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  9. #9
    Membre à l'essai
    Homme Profil pro
    Astronaute pompier
    Inscrit en
    octobre 2015
    Messages
    20
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Astronaute pompier

    Informations forums :
    Inscription : octobre 2015
    Messages : 20
    Points : 18
    Points
    18

    Par défaut

    @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.
    Images attachées Images attachées  

  10. #10
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 608
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 608
    Points : 8 658
    Points
    8 658

    Par défaut

    Excellent algorithme de tbc92.

    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    1 3
    1 5
    1 7
    1 9
    1 8
    3 16
    1 16
    4 10
    8 14
    12 18
    12 12
    12 18
    12 15
    15 27
    15 23
    18 19
    20 25
    19 27
    21 29
    21 27
    21 26
    21 23
    21 25
    22 28
    23 27
    24 27
    24 29
    26 30
    26 28
    27 31
    28 31
    28 30
    28 29
    Sortie par le début :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  11. #11
    Membre à l'essai
    Homme Profil pro
    Astronaute pompier
    Inscrit en
    octobre 2015
    Messages
    20
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Astronaute pompier

    Informations forums :
    Inscription : octobre 2015
    Messages : 20
    Points : 18
    Points
    18

    Par défaut

    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.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Optimisation de votre SGBDR et de vos requêtes...
    Par SQLpro dans le forum Langage SQL
    Réponses: 35
    Dernier message: 11/01/2013, 11h49
  2. [langage] Optimiser la lecture d'un fichier
    Par And_the_problem_is dans le forum Langage
    Réponses: 4
    Dernier message: 05/02/2003, 08h54
  3. [VB6] [BDD] Optimisation de l'accès aux données
    Par LadyArwen dans le forum VB 6 et antérieur
    Réponses: 8
    Dernier message: 30/01/2003, 13h27
  4. [langage]Problème de temps de lecture, optimisation
    Par And_the_problem_is dans le forum Langage
    Réponses: 2
    Dernier message: 08/01/2003, 08h47
  5. [langage] Optimiser la lecture d'un fichier
    Par And_the_problem_is dans le forum Langage
    Réponses: 2
    Dernier message: 11/06/2002, 10h24

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo