Algorithme de réservation complexe

**shrell** · 30/12/2008, 11h05

Bonjour tout le monde
Je viens vous voir avec une question sur laquelle je m'arrache les cheveux, et je voudrais avoir votre avis pour savoir si je vais dans la bonne direction ou si je dois tout de suite essayer de trouver une autre solution.

Alors voici l'exposé de la situation :

Je cherche à faire un système de gestion de réservation d'appartements, jusque là aucun souci, j'en ai déjà fait. Le problème est que cette fois, les clients ne choisissent pas directement leur appartement, mais choisissent la "famille" d'appartements qu'ils veulent réserver, chaque famille comportant X appartements proposant tous les mêmes prestations.

Problème :
Pour être sûr de pouvoir prendre le maximum de réservations, je ne souhaite fixer les réservations sur un appartement qu'au tout dernier moment. Entre temps, je souhaite travailler sur l'ensemble des permutations possibles des réservations sur les appartements.
Or, j'arrive vite à des temps de traitement et des tailles de bases de données gigantesques.

La solution que j'ai explorée :
Découper les zones de permutations en tranches indépendantes : elles sont définies comme les intervalles entre deux dates sur lesquelles aucune réservation n'est en cours (elles peuvent commencer ou finir ce jour là, mais pas être à cheval).

Voici la structure de mes tables :

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
CREATE TABLE `apparts` (
  `id_appart` mediumint(8) unsigned NOT NULL auto_increment,
  `id_groupe_appart` mediumint(8) unsigned NOT NULL,
  `id_proprietaire` mediumint(8) unsigned NOT NULL,
  `titre_appart_admin` varchar(255) NOT NULL,
  PRIMARY KEY  (`id_appart`),
  KEY `id_groupe_appart` (`id_groupe_appart`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8
 
CREATE TABLE `elements_permutations` (
  `id_permutation` bigint(20) unsigned NOT NULL,
  `id_appart` mediumint(8) unsigned NOT NULL,
  `id_reservation` mediumint(8) unsigned NOT NULL,
  PRIMARY KEY  (`id_permutation`,`id_appart`,`id_reservation`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;
 
CREATE TABLE `groupes_apparts` (
  `id_groupe_appart` mediumint(8) unsigned NOT NULL auto_increment,
  `titre_groupe_appart_admin` varchar(255) NOT NULL,
  PRIMARY KEY  (`id_groupe_appart`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8;
 
CREATE TABLE `permutations` (
  `id_permutation` bigint(20) unsigned NOT NULL auto_increment,
  `id_tranche` mediumint(8) unsigned NOT NULL,
  PRIMARY KEY  (`id_permutation`),
  KEY `id_tranche` (`id_tranche`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8;
 
CREATE TABLE `reservations` (
  `id_reservation` mediumint(8) unsigned NOT NULL auto_increment,
  `id_client` mediumint(8) unsigned NOT NULL,
  `id_groupe_appart` mediumint(8) unsigned NOT NULL,
  `id_appart` mediumint(8) unsigned NOT NULL,
  `date_arrivee` date NOT NULL,
  `date_depart` date NOT NULL,
  `statut` enum('Y','N') NOT NULL default 'Y',
  PRIMARY KEY  (`id_reservation`),
  KEY `date_arrivee` (`date_arrivee`),
  KEY `date_depart` (`date_depart`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8;
 
CREATE TABLE `tranches` (
  `id_tranche` mediumint(8) unsigned NOT NULL auto_increment,
  `id_groupe_appart` mediumint(8) unsigned NOT NULL,
  `date_debut_tranche` date NOT NULL,
  `date_fin_tranche` date NOT NULL,
  PRIMARY KEY  (`id_tranche`),
  KEY `id_groupe_appart` (`id_groupe_appart`),
  KEY `date_debut_tranche` (`date_debut_tranche`),
  KEY `date_fin_tranche` (`date_fin_tranche`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8;

Algorithme d'ajout d'une réservation :

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
	Récupérer toutes les tranches existantes chevauchées par la résa.
	Créer une nouvelle tranche, la plus petite possible, qui aura pour bornes : min(min(dates de début des tranches chevauchées), date de début de la résa) ; max(max(dates de fin des tranches chevauchées), date de fin de la résa)
 
	pour chaque appart de la famille d'apparts {
		récupérer, pour chaque tranche chevauchée, les permutations qui sont OK pour le couple (réservation;appart) considéré. on récupère quelque chose du style :
 
		| TRANCHE 1			|	TRANCHE 2		|
		| Perm 1		OK	|	Perm 4		NON	|
		| Perm 2		OK	|	Perm 5		OK	|
		| Perm 3		NON	|	Perm 6		OK	|
 
		Fusionner les anciennes permutations dans la nouvelle tranche, en leur ajoutant un enregistrement (id_nouvelle_permutation, id_resa, id_appart)
 
		| TRANCHE 3						 	|
		| Perm 7 ( = Perm 1 * Perm 5 + nouveau)				|
		| Perm 8 ( = Perm 1 * Perm 6 + nouveau)				|
		| Perm 9 ( = Perm 2 * Perm 5 + nouveau)				|
		| Perm 10 ( = Perm 2 * Perm 6 + nouveau)			|
	}
 
	Supprimer les anciennes tranches, permutations et elements de permutation

J'ai un peu de mal pour aligner mes barres verticales, mais en théorie la largeur de la tranche 3 devrait être égale à tranche 1 + tranche 2...

Voilà, j'ai essayé de simplifier mais je vois que c'est encore pas forcément très clair... si vous pouviez me dire ce que vous en pensez, si vous avez besoin d'éclaircissements....
Merci beaucoup

**pseudocode** · 30/12/2008, 12h46

Envoyé par shrell

Problème :
Pour être sûr de pouvoir prendre le maximum de réservations, je ne souhaite fixer les réservations sur un appartement qu'au tout dernier moment. Entre temps, je souhaite travailler sur l'ensemble des permutations possibles des réservations sur les appartements.
Or, j'arrive vite à des temps de traitement et des tailles de bases de données gigantesques.

Quel genre de "travail" tu veux faire ?

Si tu ne veux pas fixer les réservations, ca va limiter les opérations possibles.

**shrell** · 30/12/2008, 13h04

merci pour ta réponse

par "travail" j'entends : pouvoir déterminer si une nouvelle réservation pour certaines dates est possible
exemple : 2 réservations d'une semaine, sur deux periodes différentes, pour une famille de deux appartements. Je me retrouve alors avec les permutations suivantes :

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
 
		periode 1		periode 2
app 1	*********		
app 2					*********		(1)
 
		periode 1		periode 2
app 1	*********		*********
app 2								(2)
 
		periode 1		periode 2
app 1					*********
app 2	*********						(3)
 
		periode 1		periode 2
app 1			
app 2	*********		*********			(4)

maintenant si je veux rajouter une réservation qui s'étend sur la periode 1 ET la periode 2, seules les permutations (2) et (4) fonctionnent. Si je ne garde pas ces permutations en mémoire jusqu'au dernier moment et que je place toutes les réservations directement, je risque de me retrouver dans le cas (1), et alors je refuserais de prendre la nouvelle réservation, alors que je peux en fait la prendre

je me fais mieux comprendre?

**pseudocode** · 30/12/2008, 13h48

Envoyé par shrell

par "travail" j'entends : pouvoir déterminer si une nouvelle réservation pour certaines dates est possible

une réservation est possible seulement si le nombre de chevauchement cumulé est toujours inférieur a ton nombre de ressources. Comme cela tu as juste besoin de stocker les dates de réservations:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
	periode1 periode2 periode3
res.1	*********
res.2	         *****************
res.3	****************** 
----------------------------------
cumul	22222222222222222211111111

Par contre, si tu as d'autres contraintes que la période ça n'est pas une condition suffisante.

**shrell** · 30/12/2008, 14h03

effectivement, j'ai un autre type de contrainte, qui est que certaines réservations sont fixes : dans ton exemple, si la réservation 1 est disons un blocage parce que le plombier doit passer réparer la salle de bains et que la réservation 2 est une réservation du propriétaire de l'appartement (dans ce cas là il n'est pas envisageable de le mettre dans un autre appartement que le sien), alors je ne suis plus en mesure de prendre une réservation qui s'étend de la période 1 à la 3, alors que le cumul du nombre de réservations est effectivement inférieur au nombre de ressources disponible pour toute la période considérée

je sais c'est un problème affreusement complexe

**pseudocode** · 30/12/2008, 14h34

Je te conseille tout de même de stocker dans ta BdD seulement les contraintes (c'est à dire les dates de réservations, les ressources, les disponibilités, ...).

Il sera toujours possible de calculer les affectations réservation/ressource à partir de ces données, dans un temps raisonnable. Et donc de savoir si une nouvelle réservation est possible.

Par contre, stocker l'intégralité des affectations possibles va prendre une place énorme, et être très lourd à gérer.

**shrell** · 30/12/2008, 14h46

justement c'est bien là mon problème, le simple fait de stocker les permutations possibles fait dépasser les 100Mo à ma base (et je ne suis que sur un set de réservations d'exemple, je n'ose même pas imaginer en prod...)
à ce propos, vu que je continue de lire des choses de ci de là, je suis tombé sur un article sur les problème de 8 dames qui me semble correspondre vaguement à ce que je cherche.
Dans cet article je lis ceci :

La programmation par contraintes est bien plus efficace pour ce problème. Un algorithme de « réparation itérative » commence typiquement à partir d'un placement de toutes les dames sur l'échiquier, par exemple avec une seule dame par colonne. Il compte alors le nombre de conflits entre dames, et utilise une méthode heuristique pour déterminer comment améliorer les placements des dames. La méthode heuristique de moindre conflit, qui consiste à déplacer la pièce ayant le plus grand nombre de conflits, dans la même colonne à une place où le nombre de conflits est le plus petit, est particulièrement efficace. Elle résout le problème des millions de dames (sur un échiquier de 1 000 000× 1 000 000 cases) en moins de 50 étapes en moyenne!

source
Si effectivement c'est le cas, je suis en train de penser à faire les calculs à chaque fois qu'une recherche est effectuée. La question que je me pose : en combien de temps se font chacune de ces 50 étapes?
même si dans mon cas je n'aurai jamais un million d'enregistrements pour une période donnée, je ne suis pas sur que le calcul à la demande soit viable (disons que je suis prêt à accepter un temps de calcul de l'ordre de la dizaine de secondes)

PS: merci pour l'interet que tu portes à mon problème

**pseudocode** · 30/12/2008, 15h07

Envoyé par shrell

La question que je me pose : en combien de temps se font chacune de ces 50 étapes?
même si dans mon cas je n'aurai jamais un million d'enregistrements pour une période donnée, je ne suis pas sur que le calcul à la demande soit viable (disons que je suis prêt à accepter un temps de calcul de l'ordre de la dizaine de secondes)

Sur un ordinateur recent, les calculs seront plutot de l'ordre de la centaine de millisecondes que de la dizaine de secondes.

Regardes du coté de l'algorithme de Rayrole, ou d'autres algos d'allocation de ressources du meme genre.

**shrell** · 31/12/2008, 18h07

Salut à tous

J'ai poursuivi mon exploration de la programmation par contraintes, et je retombe sur des temps de traitement tout à fait raisonnables

je ne stocke plus que les tranches, et je recalcule tout à chaque fois, résultat :
placement de 240 réservations sur 7 appartements = 14 secondes

merci pour ton aide pseudocode, t'es un chef

**pseudocode** · 31/12/2008, 18h16

Content d'avoir pu t'aider.

(14 secondes, je trouve que ça fait quand même beaucoup. Mais bon ca dépend du PC, du langage et des contraintes

)

**shrell** · 31/12/2008, 18h33

à vrai dire la détermination de la disponibilite ou non d'une réservation en particulier ne prend que 0,08 secondes.
Je l'ai codé un peu à la va vite, les traitements MySQL étant effectués en PHP qui ensuite fait appel à un process python pour la partie "contraintes" à proprement parler...
si en prod je vois que les temps augmentent dans des proportions trop importantes, je chercherai plus avant à optimiser ça, mais pour l'instant ça me convient amplement

Algorithme de réservation complexe

Algorithmes et structures de données

Discussions similaires

Partager

Partager