一種航班座位分配算法

王琨琨（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京100044）

一種航班座位分配算法

王琨琨
（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京100044）

研究航班旅客座位分配算法問(wèn)題，提出一種綜合考慮旅客個(gè)體偏好和旅客關(guān)系的座位分配算法。利用旅客歷史出行記錄推導(dǎo)出旅客共同出行網(wǎng)絡(luò)；構(gòu)建旅客座位偏好模型；采用先來(lái)先服務(wù)算法給航班旅客分配座位。在客運(yùn)領(lǐng)域的一個(gè)真實(shí)的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)表明與值機(jī)時(shí)生成的座位情況相比，采用先來(lái)先服務(wù)算法進(jìn)行座位分配提高旅客的滿意度。

人工智能；社會(huì)網(wǎng)絡(luò)；座位分配

1　問(wèn)題的提出

電子商務(wù)等領(lǐng)域[1]已經(jīng)廣泛地應(yīng)用個(gè)性化推薦系統(tǒng)[2]，為用戶帶來(lái)優(yōu)質(zhì)服務(wù)[3]的同時(shí)并獲得了豐碩的商業(yè)利潤(rùn)[4]?？瓦\(yùn)領(lǐng)域同樣存在著個(gè)性化推薦問(wèn)題，客運(yùn)領(lǐng)域下旅客座位分配問(wèn)題是非常有意義且有應(yīng)用價(jià)值的研究問(wèn)題之一。在經(jīng)濟(jì)全球化、航空聯(lián)盟化的趨勢(shì)下，客運(yùn)面臨著激烈的競(jìng)爭(zhēng)，客運(yùn)企業(yè)千方百計(jì)地提高效率進(jìn)而提高競(jìng)爭(zhēng)力。對(duì)于客運(yùn)企業(yè)來(lái)說(shuō)，提升對(duì)旅客的理解，進(jìn)而給旅客提供針對(duì)性的個(gè)性化服務(wù)成為其客戶關(guān)系管理[5]的一項(xiàng)重要舉措；尤其是，根據(jù)旅客的偏好給航班上的旅客預(yù)分配座位、提升絕大部分旅客的出行滿意度，成為航空公司競(jìng)相追求的目標(biāo)。

現(xiàn)存客運(yùn)領(lǐng)域中座位分配算法簡(jiǎn)單，座位無(wú)差異分配，沒(méi)有很好地考慮旅客個(gè)體偏好和旅客間社會(huì)關(guān)系對(duì)旅客選擇座位產(chǎn)生的影響，因而不能很好地提供個(gè)性化、差異化的服務(wù)。

客運(yùn)旅客座位分配問(wèn)題致力于研究和解決航班中基于旅客個(gè)體和關(guān)系的座位偏好的差異化分配問(wèn)題，達(dá)到旅客和客運(yùn)公司雙贏的目的。一方面，通過(guò)識(shí)別旅客個(gè)體及關(guān)系的偏好，滿足旅客座位的個(gè)性化需求；另一方面，按照客運(yùn)公司的戰(zhàn)略合理地分配座位，提高座位附加收益。

目前大多數(shù)研究學(xué)者研究的是學(xué)生座位安排問(wèn)題[6]和歐洲議會(huì)成員座位安排問(wèn)題[7]，很少有學(xué)者進(jìn)行客運(yùn)領(lǐng)域下的座位安排研究。本文首先介紹一種構(gòu)建旅客社會(huì)網(wǎng)絡(luò)的算法。然后提出一種考慮個(gè)體偏好和關(guān)系的旅客偏好模型，不僅考慮旅客自身的偏好，同時(shí)會(huì)考慮旅客間的社會(huì)關(guān)系對(duì)座位選擇產(chǎn)生的影響，更加符合現(xiàn)實(shí)生活中共同出行的旅客選擇座位的心理。基于旅客偏好模型[8]，本文提出一種可以基本模擬現(xiàn)實(shí)生活中座位分配情況的先來(lái)先服務(wù)算法。

2　構(gòu)建旅客共同出行網(wǎng)絡(luò)

我們首先根據(jù)合作的一個(gè)公司提供的旅客歷史出行記錄構(gòu)建旅客共同出行網(wǎng)絡(luò)[9]，然后從社會(huì)網(wǎng)絡(luò)的視角去構(gòu)建旅客座位偏好模型。旅客歷史出行記錄是構(gòu)建旅客共同出行網(wǎng)絡(luò)的重要依據(jù)。

構(gòu)建旅客共同出行網(wǎng)絡(luò)的方法如下：將有過(guò)出行記錄的旅客當(dāng)作網(wǎng)絡(luò)中的節(jié)點(diǎn)；若任意兩名旅客曾經(jīng)一起共同出行過(guò)（即曾經(jīng)共同出現(xiàn)在同一個(gè)機(jī)票訂單上），則在這兩個(gè)旅客之間建立一條邊；邊上的權(quán)重代表這兩名旅客共同出行的次數(shù)。共同出行次數(shù)越多，旅客之間的關(guān)系強(qiáng)度越大。以上方法構(gòu)建的旅客共同出行網(wǎng)絡(luò)是一個(gè)有權(quán)無(wú)向網(wǎng)絡(luò)。

3　構(gòu)建旅客偏好模型

3.1旅客個(gè)體偏好建模

旅客個(gè)體偏好衡量旅客個(gè)體對(duì)座位具有的某個(gè)屬性的偏好程度，我們?cè)诼每凸餐鲂芯W(wǎng)絡(luò)的基礎(chǔ)上，構(gòu)建旅客個(gè)體偏好模型。

定義旅客選擇具有某種屬性（以靠窗屬性為例）的座位的概率為旅客對(duì)座位靠窗屬性的偏好，計(jì)算公式如下：

3.2旅客關(guān)系偏好建模

旅客關(guān)系偏好衡量旅客關(guān)系對(duì)座位位置關(guān)系的偏好程度，我們?cè)诼每凸餐鲂芯W(wǎng)絡(luò)的基礎(chǔ)上，探索旅客關(guān)系之間的親密程度與座位距離之間的關(guān)系，進(jìn)而構(gòu)建旅客關(guān)系偏好模型。

我們將利用座位間的距離推導(dǎo)旅客間的關(guān)系偏好。兩個(gè)座位間的距離為行差和列差的加權(quán)和。計(jì)算公式如下：

其中，ri和ci分別表示第i個(gè)旅客的座位的行號(hào)和列號(hào)，rj和cj分別表示第j個(gè)旅客的座位的行號(hào)和列號(hào)，α和β分別表示行差和列差所占的權(quán)重。

定義旅客關(guān)系的親密度為旅客關(guān)系偏好，是座位距離的函數(shù)，計(jì)算公式如下：

其中，δij表示第i個(gè)旅客和第j個(gè)旅客的關(guān)系偏好。

4　先來(lái)先服務(wù)座位分配算法

在旅客偏好模型的基礎(chǔ)上，采用先來(lái)先服務(wù)（FCFS）算法給航班旅客分配座位。

采用先來(lái)先服務(wù)算法之前，首先進(jìn)行預(yù)處理過(guò)程，生成待分配旅客的可選座位集合，然后在旅客的可選座位集合中選擇座位分配給旅客。鑒于座位分配算法的約束條件為航空公司制定的一些業(yè)務(wù)規(guī)則，例如，訂頭等艙的票的旅客只能坐在頭等艙，不能任意跨艙。所以為每個(gè)旅客生成滿足業(yè)務(wù)規(guī)則限制的可選座位集合。生成旅客可選座位集合的算法思想是如果分配某個(gè)座位給旅客不違反業(yè)務(wù)規(guī)則，則將該座位加入該旅客的可選座位集合中。由生成旅客可選座位集合算法可知，不同旅客的可選座位集合會(huì)存在互相重疊的座位，但是這并不意味著座位沖突，因?yàn)槁每椭禉C(jī)有先后順序，先到先得，值機(jī)較晚的旅客只能在自己可選座位集合的空閑座位中選擇較滿意的座位。

生成航班每位旅客的可選座位集合后，采用先來(lái)先服務(wù)算法模擬航班旅客值機(jī)過(guò)程中的座位分配情況。先來(lái)先服務(wù)算法即根據(jù)航班旅客的值機(jī)順序依次給旅客分配座位，為每位旅客分配當(dāng)前空閑座位中滿意度最大的座位。即對(duì)于一名待分配座位的旅客，首先找出航班上剩余空閑座位與該旅客可選座位集合中的重疊座位，然后在重疊座位中分配滿意度最大的座位給該旅客。根據(jù)先來(lái)先服務(wù)算法的思想易知，靠前值機(jī)的旅客可以選擇的座位更多，更容易被分配符合旅客偏好的座位；靠后值機(jī)則選擇變少，有很大概率被分配不符合個(gè)人偏好的座位。

下面給出具體的算法描述：

輸入：旅客集合P，座位集合S，可選座位集合T

輸出：旅客到座位的一一映射M

根據(jù)值機(jī)序號(hào)對(duì)旅客進(jìn)行排序；

如果該座位沒(méi)有被占用，同時(shí)是該旅客最滿意的座位

將該座位分配給該旅客；

更新座位的占有情況；

輸出旅客到座位的一一映射M。

5　實(shí)驗(yàn)

我們利用合作的公司提供的數(shù)據(jù)構(gòu)建了一個(gè)共有十幾萬(wàn)名旅客、二十萬(wàn)條關(guān)系的旅客社會(huì)網(wǎng)絡(luò)。同時(shí)我們從兩年的歷史乘行航班中篩選出1000個(gè)上座率高于90%的航班，進(jìn)行座位分配算法的實(shí)驗(yàn)。將歷史分配座位結(jié)果History與算法分配座位結(jié)果FCFS進(jìn)行對(duì)比。如圖1示。其中，縱坐標(biāo)代表整體平均滿意度。

圖1　歷史分配平均滿意度、算法分配后整體平均滿意度對(duì)比

從圖中可以看出：整體平均滿意度指標(biāo)方面，先來(lái)先服務(wù)算法分配結(jié)果FCFS優(yōu)于歷史分配結(jié)果History。由此可知，相比于現(xiàn)實(shí)生活航班旅客值機(jī)過(guò)程的生成的座位分配情況，采用先來(lái)先服務(wù)座位分配算法可以提高旅客的整體平均滿意度。該實(shí)驗(yàn)也從另一個(gè)方面驗(yàn)證了旅客出行時(shí)會(huì)兼顧考慮個(gè)體偏好和關(guān)系偏好的結(jié)論，進(jìn)一步表明本文提出的旅客偏好模型是合理的。

6　結(jié)語(yǔ)

本文給出了一種先來(lái)先服務(wù)的座位分配算法。該算法不僅考慮旅客自身的偏好，同時(shí)考慮了旅客關(guān)系的偏好。采用先來(lái)先服務(wù)算法進(jìn)行航班座位分配，與現(xiàn)實(shí)生活中航班旅客值機(jī)時(shí)生成的座位分配相比，提高了旅客的滿意度。

[1]崔春生.電子商務(wù)推薦系統(tǒng)的理論與應(yīng)用研究[M].北京：經(jīng)濟(jì)科學(xué)出版社，2013

[2]Lee B K,Lee W N.The Effect of Information Overload on Consumer Choice Quality in an Online Environment[J].Psychology& Marketing，2004,21（3）:159～183

[3]Park Y J,Chang K N.Individual and Group Behavior-Based Consumer Profile Model for Personalized Product Recommendation[J]. Expert Systems with Applications,2009,36（2）:1932～1939

[4]Pazzani M J,Billsus D.Content-Based Recommendation Systems[M].New York:Springer Berlin Heidelberg Press,2007:325～341

[5]Schafer J B,Frankowski D,Herlocker J,et al.Collaborative Filtering Recommender Systems[M].New York:Springer Berlin Heidelberg Press,2007:291～324

[6]Burke R.Knowledge-Based Recommender Systems[J].Encyclopedia of Library and Information Systems,2000,69（32）:175～186

[7]Sarwar B,Karypis G,Konstan J,et al.Item-based Collaborative Filtering Recommendation Algorithms[C].Proceedings of the 10th International Conference on World Wide Web,Hong Kong,2001.New York:ACM,2001:285～295

[8]Mooney R J,Roy L.Content-Based Book Recommending Using Learning for Text Categorization[C].Proceedings of the fifth ACM Conference on Digital Libraries,San Antonio,2000.New York:ACM,2000:195～204

[9]Pazzani M J.A Framework for Collaborative,Content-Based and Demographic Filtering[J].Artificial Intelligence Review,1999,13（5-6）:393～408

Artificial Intelligence;Social Networks;Seat Allocation

Flight Seat Allocation Algorithm

WANG Kun-kun
（School of Computer and Information Technology，Beijing Jiaotong University，Beijing 100044）

Studies the issue of allocating seats for passengers in a flight and proposes an algorithm considering passengers'individual preference and social preference.Constructs passenger social networks based on their co-travel behaviors extracted from the historical travel records; models the individual preference and social preference of passengers;employs First-Come-First-Served（FCFS）algorithm to allocate seats for passengers in a flight.Experimental results on a real data set of passenger travel records in the field of passenger transport demonstrate that the seat allocation results employing algorithm can improve passengers'satisfaction.

1007-1423（2015）14-0037-04

10.3969/j.issn.1007-1423.2015.14.009

王琨琨（1991-），女，安徽蕪湖人，在讀研究碩士生，研究方向?yàn)閿?shù)據(jù)挖掘

2015-03-19

2015-04-29