一種航班座位分配算法

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

一種航班座位分配算法

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

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

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

1　問題的提出

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

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

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

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

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

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

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

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

3.1旅客個體偏好建模

旅客個體偏好衡量旅客個體對座位具有的某個屬性的偏好程度，我們在旅客共同出行網(wǎng)絡(luò)的基礎(chǔ)上，構(gòu)建旅客個體偏好模型。

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

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

旅客關(guān)系偏好衡量旅客關(guān)系對座位位置關(guān)系的偏好程度，我們在旅客共同出行網(wǎng)絡(luò)的基礎(chǔ)上，探索旅客關(guān)系之間的親密程度與座位距離之間的關(guān)系，進(jìn)而構(gòu)建旅客關(guān)系偏好模型。

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

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

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

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

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

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

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

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

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

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

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

根據(jù)值機序號對旅客進(jìn)行排序；

如果該座位沒有被占用，同時是該旅客最滿意的座位

將該座位分配給該旅客；

更新座位的占有情況；

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

5　實驗

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

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

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

6　結(jié)語

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

[1]崔春生.電子商務(wù)推薦系統(tǒng)的理論與應(yīng)用研究[M].北京：經(jīng)濟科學(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-），女，安徽蕪湖人，在讀研究碩士生，研究方向為數(shù)據(jù)挖掘

2015-03-19

2015-04-29