基于粒子群算法的大型賓館客房智能分配算法設(shè)計(jì)

甘肅機(jī)電職業(yè)技術(shù)學(xué)院 王鵬亮

中國農(nóng)業(yè)銀行天水分行 裴海瑞

基于粒子群算法的大型賓館客房智能分配算法設(shè)計(jì)

甘肅機(jī)電職業(yè)技術(shù)學(xué)院 王鵬亮

中國農(nóng)業(yè)銀行天水分行 裴海瑞

本文簡要的介紹了離子群算法的思想和數(shù)學(xué)模型，緊跟著闡述了現(xiàn)在大型賓館管理系統(tǒng)中存在的主要問題，重點(diǎn)論述了應(yīng)用離子群算法對(duì)原有賓館管理算法進(jìn)行改進(jìn)，簡化系統(tǒng)運(yùn)行，提高賓館運(yùn)營管理，提高經(jīng)濟(jì)效益。

組合規(guī)劃；笛卡爾積；解域空

1.引入

進(jìn)入21世紀(jì)，我國經(jīng)濟(jì)發(fā)展水平明顯加快，人們對(duì)生活的質(zhì)量有了更高的追求，外出旅游做為一種新型消費(fèi)模式促使旅游業(yè)高速發(fā)展，也促使酒店賓館等服務(wù)業(yè)蓬勃高速發(fā)展。而今很多大型賓館在系統(tǒng)管理中存在一些問題，如當(dāng)住店人過多或是賓館房間太多的情況下，給顧客分配房間需要很長的時(shí)間，這就給顧客帶來不便，更降低了賓館的收益和競爭能力。如何實(shí)現(xiàn)賓館管理智能化、現(xiàn)代化，提高客房資源的分配率，提升管理水平是當(dāng)前大型賓館發(fā)展急需解決的問題。

2.解決思路

賓館客房的分配是一個(gè)典型的NP完全問題，也是一個(gè)多目標(biāo)、多約束的空間調(diào)度分配問題。該問題會(huì)隨著住店顧客的人數(shù)增多或是賓館客房的增加，使客房的分配難度成倍的增加。其問題本身的難度決定了算法設(shè)計(jì)的困難性。粒子群（Particle Swarm Optimization，PSO）算法是一種群智能算法，它是一種適合求解多約束、多變量、多目標(biāo)問題的進(jìn)化算法，其原理簡單、收斂性好、搜索效率高易實(shí)現(xiàn)。本文將PSO算法應(yīng)用于客房分配問題算法的設(shè)計(jì)上，對(duì)客房分配算法進(jìn)行優(yōu)化。

3.PSO算法的原理和數(shù)學(xué)描述

下面給出粒子速度和粒子位置的更新迭代公式：

其中，參數(shù)ω（慣性權(quán)重ω∈(0，1)），r表示第 i個(gè)粒子在R維解域空間中對(duì)應(yīng)的維數(shù)，表示第i個(gè)粒子的速度，c1和c2表示學(xué)習(xí)因子(又叫做加速因子，通常 c1=c2=2)，1)的隨機(jī)數(shù)，表示第i個(gè)粒子搜索到的最優(yōu)值，表示整個(gè)群體在一次迭代中搜索到的最優(yōu)值，表示第i個(gè)粒子的當(dāng)前位

5.結(jié)束語

圖1為粒子群在解域空間中搜尋最優(yōu)解過程的示意圖，n1，n2表示粒子群中的任意兩個(gè)搜尋粒子。

圖1 粒子群搜尋最優(yōu)解移動(dòng)示意圖

4.客房分配問題中PSO算法設(shè)計(jì)

在客房分配問題中應(yīng)用PSO算法進(jìn)行排課算法設(shè)計(jì)，每個(gè)顧客為搜尋粒子，整個(gè)賓館的房間為解域空間，每個(gè)滿足要求的客房都代表了一個(gè)優(yōu)化問題的可行解，下面應(yīng)用PSO算法對(duì)排課問題進(jìn)行算法設(shè)計(jì)：

（1）客房分配問題種群初始化。根據(jù)顧客人數(shù)和顧客住房要求確定搜索粒子數(shù)量和客房類型、輸入客房數(shù)量，而后對(duì)顧客粒子均勻分散在解域空間中，等待搜索目標(biāo)信息。

（2）建立一個(gè)立體三維空間坐標(biāo)軸，應(yīng)用三維空間對(duì)客房分配問題建模，根據(jù)客房數(shù)目、時(shí)間段次數(shù)和客房價(jià)位多少對(duì)三維坐標(biāo)各坐標(biāo)軸進(jìn)行分割，則整個(gè)三維空間就被分割成了許多的小立方體，且把所有小立方體的初值設(shè)置為0，表示沒有入住。三維空間中的每個(gè)小立方體代表一個(gè)迭代的顧客粒子，而且顧客粒子采用三維編碼方式記錄自身所搜索到的信息值。

（3）根據(jù)顧客要求確定入住客房類型，并且確定各入住房價(jià)，客房分配從底層向高層逐層分配，客房入住類型相同則盡量連號(hào)分配。

（4）顧客粒子在解域空間中按照時(shí)間段T和優(yōu)先級(jí)選取相應(yīng)的客房M進(jìn)行分配。M一旦確定客房價(jià)位P也隨之確定。這樣一個(gè)顧客粒子就在解域空間中搜索到了的可行解G(T,M,P)，即完成了一位顧客的客房分配任務(wù)。凡是三維空間中被分配了的客房小立方體都用1（有顧客入住）標(biāo)注。然后繼續(xù)執(zhí)行步驟⑷直至所有顧客粒子都搜尋到可行解，然后比較可行解的相對(duì)最優(yōu)解。

經(jīng)過以上4個(gè)步驟，實(shí)現(xiàn)了客房分配問題中PSO算法設(shè)計(jì)和應(yīng)用，完成了初始的客房分配任務(wù)。根據(jù)三維空間坐標(biāo)中的立方體標(biāo)注圖如圖2所示，可以準(zhǔn)確獲取顧客粒子的初始狀態(tài)、分布情況及其規(guī)模大小。

圖2 客房分配標(biāo)注示

本文針對(duì)大型賓館查詢系統(tǒng)客房查詢存在的問題，引入PSO算法，對(duì)客房查詢算法進(jìn)行了設(shè)計(jì)，簡化系統(tǒng)運(yùn)行，提高賓館運(yùn)營管理，提高經(jīng)濟(jì)效益。

[1]江菱.賓館客房管理系統(tǒng)分析與設(shè)計(jì)[D].云南大學(xué),2013.

[2]代航陽.基VB的賓館客房管理系統(tǒng)設(shè)計(jì)[D].電子科技大學(xué),2006.

[3]鄭宇軍.C#語言程序設(shè)計(jì)基礎(chǔ)[M].清華大學(xué)出版社,2011.

王鵬亮（1979—），男，甘肅天水人，工學(xué)碩士，甘肅機(jī)電職業(yè)技術(shù)學(xué)院講師，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)教學(xué)。

裴海瑞（1982—），女，甘肅天水人，理學(xué)碩士，中國農(nóng)業(yè)銀行職員，中級(jí)職稱，主要研究方向數(shù)學(xué)應(yīng)用。