Optimiser planning de réservations de chambres

[SwimCoachNico79]

Bonsoir à tous,

Afin d’optimiser un planning de réservations de chambres, je cherche une formule ou un code vba qui me permette de réduire au maximum le nombre de chambres louées en optimisant les réservations

Exemple : la personne 1 loue la chambre 1 du 1er au 18 mais, la chambre 4 est louée par la personne 4 du 19 au 27 mai et pour finir la chambre 20 est louée par la personne 20 du 28 au 30 mai.
Comment faire pour optimiser la chambre 1 et permettre de la louer du 1er au 18 mai à la personne 1 puis du 19 au 27 mai à la personne 4 puis du 28 au 30 mai à la personne 20.

J'ai conscience que cela est simple à traiter manuellement quand on a quelques lignes, mais quid quand il y en a 250 ou plus ?

Quelqu'un a t il une idée.

En vous remerciant par avance.

SCN79

 

[ODVJ]

Re : Optimiser planning de réservations de chambres

Bonsoir,

Quand tu auras installé GLPK, utilise la commande glpsol.exe --minisat -m "xld_color.mod" -o "xld_color.out" au lieu de celle de mon précédent message.
470 fois plus rapide.....Ça décoiffe!

cordialement

 

[Si...]

Re : Optimiser planning de réservations de chambres

salut

J’ai suivi de loin cet échange en étayant un fichier commencé il y a quelques temps.
Il n’est pas complet pour un usage professionnel mais il peut s’enrichir de fonctions supplémentaires.
Voir si cela peut donner des idées pour ce type de gestion.

Nota : pas trop testé après les nouvelles modifications.

 

[SwimCoachNico79]

Re : Optimiser planning de réservations de chambres

Bonjour à tous,

Merci Si... pour ta solution.

ADVJ, je viens de faire un test avec 320 chambres (j'ai fait le graph puis j'ai modifié le fichier xld_color.mod). J’exécute le solveur mais j'obtiens le message d'erreur suivant :

C:\Users\XXX\Downloads\glpk-4.60\w32>glpsol.exe --minisat -m "xld_co
lor.mod" -o "xld_color.out"
GLPSOL: GLPK LP/MIP Solver, v4.60
Parameter(s) specified in the command line:
--minisat -m xld_color.mod -o xld_color.out
Reading model section from xld_color.mod...
Reading data section from xld_color.mod...
89245 lines were read
Checking (line 21)...
Checking (line 57)...
Display statement at line 64
nc = 235
Generating map...
Generating arc...
glp_alloc: no memory available
Error detected in file ..\src\env\alloc.c at line 91

Je n'arrive pas à comprendre pourquoi...

Je joins le fichier xld_color.mod que j'ai modifié.

Bonne fin de journée

 

[ODVJ]

Re : Optimiser planning de réservations de chambres

Bonsoir,

ce message est censé indiquer un problème de mémoire insuffisante.
Je l'ai testé sur un PC avec 12Go de RAM et j'ai eu le même message vers les 6Go utilisés.
edit : il suffit de passer en glpk 64 bits pour ne plus avoir ce message.
en revanche, il remplit les 12Go à toute vitesse et, après, il doit swapper.
il vaut mieux le lancer la nuit...... Parce que le modèle SAT a 20 millions de lignes et 75000 colonnes.fin edit

Donc il doit y avoir un problème ailleurs.

Il existe, je crois, une possibilité de découper le problème en tranche mais je ne sais plus où j'ai vu ça....

En tout cas, j'ai mis l'instance sur Cplex et après 2s j'ai obtenu une solution. (pas mal pour un modèle de 90 000 lignes !)
Solution que j'ai trièe par chambre.

Il suffirait donc de 235 chambres pour loger ces 320 clients.
Je ne garantis pas qu'il s'agit de l'optimum mais c'est la seule solution que Cplex a trouvée.

cdlt

 

[SwimCoachNico79]

Re : Optimiser planning de réservations de chambres

Bonjour ODVJ
Bonjour le forum,

Je n'avais pas vi ta dernière modif (passer en 64 bits).
Hier j'ai laissé tourner mon ordi pendant plus de 12h et il a planté de la mème manière...

C:\Users\XXX\Downloads\glpk-4.60\w64>glpsol.exe --minisat -m "xld_co
lor.mod" -o "xld_color.out"
GLPSOL: GLPK LP/MIP Solver, v4.60
Parameter(s) specified in the command line:
--minisat -m xld_color.mod -o xld_color.out
Reading model section from xld_color.mod...
Reading data section from xld_color.mod...
89245 lines were read
Checking (line 21)...
Checking (line 57)...
Display statement at line 64
nc = 235
Generating map...
Generating arc...
Generating obj...
Model has been successfully generated
Will search for ANY feasible solution
Translating to CNF-SAT...
Original problem has 20951041 rows, 75435 columns, and 62927595 non-zeros
20950720 packing inequalities
320 partitioning equalities
glp_alloc: no memory available
Error detected in file ..\src\env\alloc.c at line 91

De plus "minisat" ne fonctionne pas avec le 64 bits (j'ai fais un test avec un fichier bcp plus petit).

Bref, je ne sais plus trop quoi faire...

Bonne journée.
SCN79

 

[mapomme]

Re : Optimiser planning de réservations de chambres

Bonjour à tous,

• un essai en VBA avec une méthode perso plus qu'empirique
• aucune garantie d'avoir une solution optimale
• bien que la durée de traitement n'aie pas été optimisée, c'est assez rapide
• une contrainte: chaque séjour doit être repéré par un identifiant unique
• le traitement porte sur l'ensemble des réservations
• les tests ont été assez succincts de ma part

 

[mapomme]

Re : Optimiser planning de réservations de chambres

re,

Le même en couleur.

 

[mapomme]

Re : Optimiser planning de réservations de chambres

re,

Une version future pourrait figer tout séjour en cours à la date du jour (on ne change pas de chambre un client ayant commencé son séjour) et abandonner tout séjour terminé à la veille de la date du jour (l'optimisation des séjours terminés ayant très peu d’intérêt). Cela permettrait d'appliquer la réduction à n’importe quel stade des réservations.
Si quelqu'un y voit une utilité, m'en informer afin que je m'y attelle.

 

[CBernardT]

Re : Optimiser planning de réservations de chambres

Bonjour SwimCoachNico79, ODVJ et le forum

Salut mapomme

Un classeur ancien retouché pour exemple.

1- tout d'abord, les réservations fond l'objet d'un tri croissant selon les dates d'arrivée et le nombre de nuits du séjour au moment de leur saisie et de leur enregistrement à partir d'un formulaire simplifié.

2- L'optimisation de la planification est réalisée depuis la feuille réservation.

 

[SwimCoachNico79]

Re : Optimiser planning de réservations de chambres

Bonjour mapomme
Bonjour CBernardT

Merci à tous les deux pour vos fichiers.

SCN79

 

[mapomme]

Re : Optimiser planning de réservations de chambres

Bonsoir SwimCoachNico79,

Suite à votre demande de limiter le nombre de clients par chambre à trois au maximum, voici un essai bricolé à partir de la v1.

Dans le module de la feuille feuil1 se trouvent deux constantes qu'on peut modifier :
.

• ClientsParChambre -> qui le nombre maximum de clients par ligne (correspond à une chambre)
• xFois qui est le nombre d'itérations qu'on effectue pour trouver un résultat.
• Dans le fichier v2 publié, ClientsParChambre = 3 et xFois =500
• chaque fois qu'on trouve une meilleure solution, un bip retentit
• la progression de l'exécution est affichée dans la barre d'état

Si le nombre de clients par chambre est indifférent, préférer la v1.

 

[SwimCoachNico79]

Re : Optimiser planning de réservations de chambres

Bonsoir le forum,
Bonsoir ODJV,

Est-il envisageable de tester avec votre logiciel cplex le fichier .mod joint et me transmettre le fichier .out ?

Dans l'attente de votre retour, je vous souhaite une très bonne fin de journée.

SCN

 

[ODVJ]

Re : Optimiser planning de réservations de chambres

Bonsoir,

La variable 207 n'est pas renseignée dans la liste des incompatibilités.

Avec cette absence de variable 207, Cplex trouve 219 chambres, mais il a mis la personne 207 avec la personne 256 dans la chambre 1 alors que la personne 256 semble occuper une chambre sur toute la période, non?.

Cordialement

edit : le code Cplex étant différent de celui de GLPK, il faut "reconditionner" ce dernier. J'en ai profité pour faire sortir un résultat formaté à l'écran puis j'ai fait un copier/coller dans une feuille excel.
Pas besoin d'extraire des "X[i,j,k] à 1" d'un fichier ".out"

 

[JM27]

Re : Optimiser planning de réservations de chambres

Bonjour
Un solution qui permettrai d'optimiser les chambres à la réservation.
Dès la saisie la liste t'indiques quelles sont les chambres disponibles.
A toi de réserver par ordre de priorité les premières de la list box.
A tester pour voir si cela peut le faire.
Il peut y avoir plusieurs fichiers différents en fonction de la qualité des chambres et de leurs capacités.
Nota : je me suis limité à 15 chambres pour des pb de capacité d'envoi des fichiers.

 

[SwimCoachNico79]

Re : Optimiser planning de réservations de chambres

Bonjour à tous,
Bonjour ODVJ,
Bonjour JM27,

A ODVJ, je vais vérifier l'intégralité de mon fichier.
A JM27, merci pour tes fichiers, je via les explorer au plus vite.

Bonne journée,
SCN79