一種航班座位分配算法

王琨琨（北京交通大學計算機與信息技術學院，北京100044）

一種航班座位分配算法

王琨琨
（北京交通大學計算機與信息技術學院，北京100044）

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

人工智能；社會網絡；座位分配

1　問題的提出

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

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

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

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

2　構建旅客共同出行網絡

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

構建旅客共同出行網絡的方法如下：將有過出行記錄的旅客當作網絡中的節點；若任意兩名旅客曾經一起共同出行過（即曾經共同出現在同一個機票訂單上），則在這兩個旅客之間建立一條邊；邊上的權重代表這兩名旅客共同出行的次數。共同出行次數越多，旅客之間的關系強度越大。以上方法構建的旅客共同出行網絡是一個有權無向網絡。

3　構建旅客偏好模型

3.1旅客個體偏好建模

旅客個體偏好衡量旅客個體對座位具有的某個屬性的偏好程度，我們在旅客共同出行網絡的基礎上，構建旅客個體偏好模型。

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

3.2旅客關系偏好建模

旅客關系偏好衡量旅客關系對座位位置關系的偏好程度，我們在旅客共同出行網絡的基礎上，探索旅客關系之間的親密程度與座位距離之間的關系，進而構建旅客關系偏好模型。

我們將利用座位間的距離推導旅客間的關系偏好。兩個座位間的距離為行差和列差的加權和。計算公式如下：

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

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

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

4　先來先服務座位分配算法

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

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

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

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

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

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

根據值機序號對旅客進行排序；

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

將該座位分配給該旅客；

更新座位的占有情況；

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

5　實驗

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

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

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

6　結語

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

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

2015-03-19

2015-04-29