---

Hej,

Jeg har en lille opgave som jeg håber at nogle af jer måske har lidt input
til.

Jeg har et program, hvor der kan laves reservationer af enheder i en given
periode. Det kunne f.eks. være til at booke hotelværelser.

Når man reserverer disse værelser over tid så er det mere eller mindre
tilfældigt hvilket værelse der lige bliver reserveret til en kunde. Det
betyder, at efterhånden som antallet af ledige værelser bliver mindre, så
vil der typisk opstå en del "spild", fordi reservationerne ikke ligger lige
efter hinanden. Der kan være huller på nogle dage mellem reservationerne af
et værelse.

Jeg har nu brug for en algoritme, der kan løbe alle reservationerne igennem
i en given periode, og flytte rundt på dem (dog ikke med datoen, kun med
værelset så der bliver mindst muligt spild. Dvs. et værelse skal være
booket så meget som muligt før man tager det næste i brug.

Jeg ved ikke lige hvordan jeg skal strikke denne algoritme sammen, har I
nogle forslag?

Algoritmen skal tage hensyn til, om en reservation MÅ flyttes, samt
naturligvis om den enhed der flyttes til er ledig i den periode man vil
reservere. Endvidere ville det være kanon hvis algoritmen også tager hensyn
til, at værelser kan være af forskellig type, dvs. en kategori 2 reservation
må ikke flyttes til et kategori 3 værelse osv.

Hilsen
Lars

---

> Jeg ved ikke lige hvordan jeg skal strikke denne algoritme sammen, har I
> nogle forslag?

Da du nok kender systemet bedre end vi andre (og da det er din opgave), så
vil jeg foreslå dig at tage papir og blyant frem, lave et hotel på papir og
se hvordan du ville håndtere disse reservationer. Prøv at opstil et eksempel
med en stak værelsesbestillinger som ligger helt skidt, og arranger dem nu
skridt for skridt som du synes det er bedst. bemærk undervejs præcis hvad du
gør i hvilke situationer. Vær klar over hvorfor du tager værelse A og
flytter istedet for værelse B ect.

Når du kan gøre det manuelt, så er du meget langt fremme i udredningen af
algoritmen.

Det lyder måske banalt, men det giver nu god mening. Hvis du kan udføre
opgaven selv, så kan du fortælle computeren hvordan den gør. Man skal
endelig ikke starte med at kode løs.

Håber du på en eller anden måde kan bruge mit råd

---

> Når du kan gøre det manuelt, så er du meget langt fremme i udredningen af
> algoritmen.

Tak for dit svar.

Grunden til at jeg stiller spørgsmålet i dette forum er dog, at jeg har en
formodning om, at der findes en standardalgoritme til det. Langt de fleste
programmer der f.eks. anvender et Gant diagram kan komprimere Gant'en. Det
et noget i den stil jeg har behov for.

/Lars

---

> Langt de fleste programmer der f.eks. anvender et Gant diagram kan
komprimere
> Gant'en. Det et noget i den stil jeg har behov for.

Ok. Det vidste jeg så ikke. Troede det var mere specifikt end som så.

---

On Sat, 07 Jun 2003 10:13:39 +0200, Lars wrote:
> Jeg har et program, hvor der kan laves reservationer af enheder i en given
> periode. Det kunne f.eks. være til at booke hotelværelser.

Resevertions/booking algoritmer er svære at lave.. AFAIK der findes nogle
algoritmer, men de er meget komplekse. Jeg tror faktisk mere der er tale
om hele reservertionssystemer (mon der er nogen opensource?) ..

Desværre er det ikke nogen *lille* opgave du har påtaget dig.

--
Simon Strandgaard

---

"Lars" <x@x.com> wrote in message
news:3ee190a6$0$15297$ba624c82@nntp03.dk.telia.net...

> Jeg har et program, hvor der kan laves reservationer af enheder i en given
> periode. Det kunne f.eks. være til at booke hotelværelser.
>
> Når man reserverer disse værelser over tid så er det mere eller mindre
> tilfældigt hvilket værelse der lige bliver reserveret til en kunde. Det
> betyder, at efterhånden som antallet af ledige værelser bliver mindre, så
> vil der typisk opstå en del "spild", fordi reservationerne ikke ligger
lige
> efter hinanden. Der kan være huller på nogle dage mellem reservationerne
af
> et værelse.
>
> Jeg har nu brug for en algoritme, der kan løbe alle reservationerne
igennem
> i en given periode, og flytte rundt på dem (dog ikke med datoen, kun med
> værelset så der bliver mindst muligt spild. Dvs. et værelse skal være
> booket så meget som muligt før man tager det næste i brug.
>
> Jeg ved ikke lige hvordan jeg skal strikke denne algoritme sammen, har I
> nogle forslag?
>
> Algoritmen skal tage hensyn til, om en reservation MÅ flyttes, samt
> naturligvis om den enhed der flyttes til er ledig i den periode man vil
> reservere. Endvidere ville det være kanon hvis algoritmen også tager
hensyn
> til, at værelser kan være af forskellig type, dvs. en kategori 2
reservation
> må ikke flyttes til et kategori 3 værelse osv.

Dette nemmeste du kan gøre er vel at lave alle legale kombinationer af
reservationer, og så måle hvilken der er optimal. I stedet for at bruge
kræfter på at finde sindrige regler for omgruppering, så bare bruge brutal
simpelhed.

Det giver naturligvis en eksponentiel algoritme som skalerer ufatteligt
dårligt - men hvis din løsning kun skal bruges på "hoteller" med et lille
antal "værelser" og med en kort "tidshorisont", så er det vel ok...

Det er da i al fald en start, og det burde være nemt at implementere.

Er problemet NP? Det er jeg lidt i tvivl om, det minder om Job Schedulering
problemet, som er NP. Og så bliver løsningen ikke bedre.

Alternativet er at bruge heurestikker, men så skal du til at tænke dig om


Mvh Lasse


--
<signature>
Lasse Westh-Nielsen
lasse@daimi.au.dk
</signature>

---

Lasse Westh-Nielsen wrote:

> Er problemet NP? Det er jeg lidt i tvivl om, det minder om Job Schedulering
> problemet, som er NP. Og så bliver løsningen ikke bedre.

Bare fordi problemet er NP-fuldstændigt er det meget muligt, at
der findes en bedre løsning end bare "prøv alle muligheder".
Jeg har dog væsentlige bedre forslag i det konkrete tilfælde.

--
Jens Axel Søgaard

---

Jens Axel Søgaard wrote:

> Jeg har dog væsentlige bedre forslag i det konkrete tilfælde.
Ups. Det retter vi straks til

Jeg har dog ingen væsentlige bedre forslag i det konkrete tilfælde.

--
Jens Axel Søgaard

---

> Jeg har dog væsentlige bedre forslag i det konkrete tilfælde.

Tak for dit svar.

Har du et forslag som jeg kan bruge, så vil jeg meget gerne høre det.

/Lars

---

Lars wrote:
>>Jeg har dog væsentlige bedre forslag i det konkrete tilfælde.

> Tak for dit svar.
>
> Har du et forslag som jeg kan bruge, så vil jeg meget gerne høre det.

Desværre, der var faldet et intet ud.

Mit bedste forslag er nok at kigge på CiteSeer.

--
Jens Axel Søgaard

---

"Jens Axel Søgaard" <usenet@jasoegaard.dk> wrote in message
news:3ee203f8$0$97222$edfadb0f@dread12.news.tele.dk...
>
> Bare fordi problemet er NP-fuldstændigt er det meget muligt, at
> der findes en bedre løsning end bare "prøv alle muligheder".


Det er rigtigt. Min fejl.

Så, en outline til algoritmen er:

<<R er en liste af reservationer>>
<<M er en matrix af værelser*dage>>
<<S er en liste af løsninger>>

[Program: find optimale reservationer]

Placer (R, M)
{
if (<<R er tom>>) <<tilføj M til de mulige løsninger og returner>>

for (<<i løber gennem værelserne>>)
{
M(i) = R[0];

Placer(R/R[0], M);
}
}

<<Søg gennem S og find den bedste>>

[program slut]



Og en optimeret udgave:

[snip]
M(i) = R[0];

if (M.valid()) Placer(R/R[0], M);
[snip]

hvor valid() afgør om denne kombination af værelser er gyldig, dvs om
reservationer overlapper på et værelse eller om andre constraints
(værelseskategori fx) forbyder den.

Dette kan givetvis gøres smartere - men det er da en start.

Mvh Lasse


--
<signature>
Lasse Westh-Nielsen
lasse@daimi.au.dk
</signature>

---

> Dette nemmeste du kan gøre er vel at lave alle legale kombinationer af
> reservationer, og så måle hvilken der er optimal. I stedet for at bruge
> kræfter på at finde sindrige regler for omgruppering, så bare bruge brutal
> simpelhed.

Hvis du taler om at prøve alle muligheder, burde man så ikke istedet lave
simuleret "udglødning" hvor man tager en tilfældig kombination, ser dens
værdi evt målt i spildtid på værelser. Ændrer den en smule ved at bytte
rundt på to og måler værdien igen. Hvis du finder en bedre værdi denne gang
så arbejd videre med den.. til du når et lokalt minimum og derfra forsøge
lidt kraftigere ændringer til du kan regne med at der er gode chancer for
globalt minimum eller noget med nogenlunde samme værdi.
Det burde vel være oplagt til denne situation... sådan som jeg forstår
værelserne altså.

---

Lars skrev:
> Jeg har nu brug for en algoritme, der kan løbe alle reservationerne
igennem
> i en given periode, og flytte rundt på dem (dog ikke med datoen, kun med
> værelset så der bliver mindst muligt spild. Dvs. et værelse skal være
> booket så meget som muligt før man tager det næste i brug.
....
> Algoritmen skal tage hensyn til, om en reservation MÅ flyttes, samt
> naturligvis om den enhed der flyttes til er ledig i den periode man vil
> reservere. Endvidere ville det være kanon hvis algoritmen også tager
hensyn
> til, at værelser kan være af forskellig type, dvs. en kategori 2
reservation
> må ikke flyttes til et kategori 3 værelse osv.

Umiddelbart lyder det som en opgave man ville bruge Prolog til, men nu er
dette jo en Visual Basic-gruppe, så jeg formoder at du har programmeret
systemet i Visual Basic?

Et lille spørgsmål: Er det nok at "en bedre" fordeling kan findes, eller
SKAL "den bedste" fordeling findes?

Jeg tænker lidt på om det kunne være op til brugeren at vurdere om det "er
godt nok" eller om systemet skal forsøge at finde en bedre fordeling. Evt.
kan man sætte en grænse der siger at hvis ingen bedre løsning er opnået
efter X iterationer eller Y sekunder, vises den indtil videre fundne bedste
løsning.

-------
Tomas

---

"Lars" <x@x.com> skrev i en meddelelse
news:3ee190a6$0$15297$ba624c82@nntp03.dk.telia.net...
> Hej,
>
> Jeg har en lille opgave som jeg håber at nogle af jer måske har lidt input
> til.
>
> Jeg har et program, hvor der kan laves reservationer af enheder i en given
> periode. Det kunne f.eks. være til at booke hotelværelser.
>
***KLIP***

Hej Lars
Det er bestemt ikke nogen lille opgave du har påtaget dig. Antallet af
mulige kombinationer
vil formentlig løbe op i mange milliarder selv ved et beskedent antal
hotelværelser.
Din problemstilling løses inden for operations analysen nærmere vha.
matematisk programmering
der er teorien om bestemmelse af en optimumsværdi for en funktion af mange
variable,
hvor de variable er underkastet visse betingelser.
Hvis du går denne vej må du nok søge støtte hos en prof. matematiker.
Alternativt kunne du forsøge dig med Monte Carlo modellen som nok ikke
finder det helt optimale
men du kan komme et pænt stykke ad vejen.
Du har f.eks alle dine reservationer "liggende løst" i en pulje, og herfra
anbringes de
tilfældigt i hotellet således at de hele tiden ligger inden for de regler du
har sat op.
Beregn nu spildtiden i hotellet og hvis den er mindre end dit forrige skud
gemmer du resultatet.
Du gentager nu det hele f.eks 10000 gange og hver gang der er fundet en
forbedring
erstattes det tidligere bedste resultat.
Det er forbavsende så tæt man kommer på det optimale, men det er som med en
opinionsundersøgelse
før et valg hvor en rundspørge til 1000 personer rammer det endelige
valgresultat indenfor nogle
få procent.
mvh
Yngve

---

"Yngve Damgaard" <ydamgaar@hotmail.com> skrev i en meddelelse
news:3ee27322$0$83050$edfadb0f@dtext01.news.tele.dk...
>
> "Lars" <x@x.com> skrev i en meddelelse
> news:3ee190a6$0$15297$ba624c82@nntp03.dk.telia.net...
> > Hej,
> >
> > Jeg har en lille opgave som jeg håber at nogle af jer måske har lidt
input
> > til.
> >
> > Jeg har et program, hvor der kan laves reservationer af enheder i en
given
> > periode. Det kunne f.eks. være til at booke hotelværelser.
> >
> ***KLIP***
>
> Hej Lars
> Det er bestemt ikke nogen lille opgave du har påtaget dig. Antallet af
> mulige kombinationer
> vil formentlig løbe op i mange milliarder selv ved et beskedent antal
> hotelværelser.
> Din problemstilling løses inden for operations analysen nærmere vha.
> matematisk programmering
> der er teorien om bestemmelse af en optimumsværdi for en funktion af mange
> variable,
> hvor de variable er underkastet visse betingelser.
> Hvis du går denne vej må du nok søge støtte hos en prof. matematiker.
> Alternativt kunne du forsøge dig med Monte Carlo modellen som nok ikke
> finder det helt optimale
> men du kan komme et pænt stykke ad vejen.
> Du har f.eks alle dine reservationer "liggende løst" i en pulje, og herfra
> anbringes de
> tilfældigt i hotellet således at de hele tiden ligger inden for de regler
du
> har sat op.
> Beregn nu spildtiden i hotellet og hvis den er mindre end dit forrige skud
> gemmer du resultatet.
> Du gentager nu det hele f.eks 10000 gange og hver gang der er fundet en
> forbedring
> erstattes det tidligere bedste resultat.
> Det er forbavsende så tæt man kommer på det optimale, men det er som med
en
> opinionsundersøgelse
> før et valg hvor en rundspørge til 1000 personer rammer det endelige
> valgresultat indenfor nogle
> få procent.
> mvh
> Yngve
>
>
Hej Lars

Hvis jeg var dig så ville jeg kigge lidt anderledes på dit problem. Sådan
som jeg læser det, så vælger du at tildele et værelsesnummer allerede ved
reservation. Hvis jeg var dig så ville jeg oprette forskellige værelsestyper
fx. enkelt tyger, enkelt ikke ryger dobbelt ikke ryger...

Du opretter så dit system med det antal værelser du har inden for hver
kategori. Når du så booker et værelse, så laver du bare en reservation på et
værelse. Hver aften der tildeler man så værelser. På den måde kommer der
ikke noget spild. Jeg tror aldrig man kan få et problem til at tildele
værelser automatisk, for problemet er, at der er mange forhold man skal tage
hensyn til. Hvis man fx. har stamkunder, så har disse som regl et stam
værelse som du forventer at få. Hvis du tildeler automatisk så kan man
heller ikke tage hensyn til inaktive værelser, som often opstår, da nogle
gæster laver sen check-out.

Klaus

---

"Klaus Egebjerg" <ke@brygladen.dk> wrote in message
news:bbvf8d$doc$1@news.net.uni-c.dk...
> Du opretter så dit system med det antal værelser du har inden for hver
> kategori. Når du så booker et værelse, så laver du bare en reservation
på et
> værelse.

Det duer ikke. Kunden (der f.eks. ringer) forventer med det samme at
kunne få at vide, om der er et ledigt værelse på det ønskede tidspunkt,
så hotellets database skal på et givet tidspunkt med kort varsel kunne
sige, om det kan lade sig gøre eller ej. Hvis den forrige kunde, der
ringede, afbestilte et værelse, kan det være det, der netop muliggør at
den nye kunde kan få et værelse.

Så der er faktisk behov for et ret dynamisk system, som løbende kan
afprøve om, en given ny reservation er mulig, evt. med en re-tildeling
først, hvorefter det så vil tage lidt længere tid at svare.

Hilsen
Uffe