基于粒子群算法的鐵路客票預(yù)售期研究

王紅愛，呂曉艷，朱建生，周亮瑾

(中國鐵道科學(xué)研究院 電子計算技術(shù)研究所，北京 100081)

鐵路客票發(fā)售和預(yù)訂系統(tǒng) (以下簡稱客票系統(tǒng)) 自1996年開始應(yīng)用以來，實現(xiàn)了全路聯(lián)網(wǎng)售票，推出窗口售票、自動售票機售票、電話訂票、互聯(lián)網(wǎng)購票等多種方式，極大地方便了旅客購票。為避免鐵路客流高峰時期的購票擁擠，一般需要調(diào)整客票預(yù)售期。目前，主要依據(jù)歷史數(shù)據(jù)和專家經(jīng)驗制定客票預(yù)售期，人為因素較多。因此，提出基于粒子群算法的鐵路客票預(yù)售期計算模型，以預(yù)測售票量為基礎(chǔ)，通過調(diào)整客票發(fā)售期的適用度函數(shù)，達到每日均衡發(fā)售客票的目標(biāo)。

1 粒子群算法概述

粒子群優(yōu)化算法 (PSO) 是一種進化計算技術(shù)，1995年由 Eberhart 和 kennedy 提出[1]，源于對鳥群捕食行為的研究。PSO 是一種基于迭代的優(yōu)化算法，系統(tǒng)初始化為一組隨機解，通過迭代搜尋最優(yōu)值。在每一次迭代中，粒子通過跟蹤2個極值來更新自己，一個極值是粒子本身所找到的最優(yōu)解，稱為個體極值 pbest；另一個極值是整個種群當(dāng)前找到的最優(yōu)解，稱為全局極值 gbest。如果將部分粒子代替整個種群進行搜索，得到的極值是局部極值。粒子在搜索過程中，根據(jù)個體極值和全局極值，更新自己的速度和位置。

式中：vi為粒子速度；w 為慣性權(quán)重，用于平衡全局搜索和局部搜索，可以改善粒子群優(yōu)化算法，使群體勘探和開發(fā)能力在整個計算過程中合理分配；pi是當(dāng)前粒子位置；r是介于 (0，1) 之間的隨機數(shù)；c1、c2是學(xué)習(xí)因子，通常 c1＝c2＝2；每一維粒子的速度都會被限制在一個最大速度 vmax之內(nèi)，如果某一維更新后的速度超過用戶設(shè)定的 vmax，那么這一維的速度就被限定為 vmax。

每個粒子在解空間內(nèi)不斷搜索與更新其個體極值和全局極值，直到滿足條件后停止。基本粒子群算法如圖1所示。

具體實現(xiàn)過程如下。

第1步：初始化粒子群：初始化粒子群中所有粒子的特征，包括粒子個數(shù)、速度和位置。

第2步：使用根據(jù)優(yōu)化問題目標(biāo)定義的適應(yīng)度函數(shù)對所有粒子進行評價。

第3步：將種群中每個粒子的適應(yīng)度值與其個體極值比較，如果適應(yīng)度值大于個體極值，則更新該粒子的個體極值。

第4步：將種群中每個粒子的適應(yīng)度值與全局極值比較，如果適應(yīng)度值大于全局極值，則更新每個粒子所在種群的全局極值。

第5步：不斷迭代粒子速度及位置。

第6步：重復(fù)以上步驟，直到滿足算法的迭代停止條件 (達到一定誤差或者達到最大循環(huán)次數(shù))為止。

2 建立模型

2.1 客票預(yù)售期模型

基于 PSO 算法建立鐵路客票預(yù)售期調(diào)整優(yōu)化模型，如圖2所示。該模型的思想是：預(yù)測預(yù)售期售票量，基于粒子群算法計算售票量的平滑度，對預(yù)售期進行優(yōu)化，使得售票量的平滑度達到最優(yōu)。

2.2 平滑度目標(biāo)函數(shù)

為均衡系統(tǒng)資源，平滑預(yù)售期內(nèi)日售票量差異，設(shè)置目標(biāo)函數(shù)。

式中：xi為每日售票量；x均為預(yù)售期內(nèi)平均每日售票量。

2.3 參數(shù)設(shè)置

根據(jù)鐵路客票預(yù)售期的實際情況，設(shè)置模型參數(shù)。

圖1 基本粒子群算法

圖2 基本粒子群算法的應(yīng)用模型圖

（1）粒子數(shù)。一般取 20～40。一般情況下，取 10個粒子即可以得到較好的效果。對于比較難的問題或者特定問題，粒子數(shù)可以取到 100～200。鐵路普通票的最大預(yù)售期為 20 天，取 20個粒子。

（2）vmax。最大速度決定粒子在循環(huán)中的最大移動距離，通常設(shè)定為粒子的范圍寬度。例如，粒子 (x1，x2，…，xi) 屬于[-5，5]，則 vmax的大小為10。

（3）學(xué)習(xí)因子。c1和 c2通常等于 2。不過在文獻中也有其他的取值，但是一般 c1等于 c2，并且范圍在 0和4之間。在此，取c1＝c2＝2.5。

（4）停止條件。設(shè)置日售票量峰值與日售票量均值的差值占均值的百分比作為停止條件。

（5）慣性權(quán)重。慣性權(quán)重表示原來的速度在下一步迭代中所占的比重，通常取較大值時，算法具有較強的全局搜索能力；反之，算法具有較強的局部搜索能力。對于 Schaffer 的f6函數(shù)，當(dāng) vmax≤2時，使用接近于1的慣性權(quán)重；當(dāng)vmax≥3 時，取w＝0.8 較好[2]。如果沒有 vmax的信息，使用 0.8 作為權(quán)重也是一種很好的選擇。一般設(shè)置 w 隨著計算的進行而不斷減小，以使得算法在運行初期有較好的全局搜索能力，而在末期有比較好的局部搜索能力。根據(jù)經(jīng)驗，w 的取值范圍為 [0，1.4]比較合適，但是通常當(dāng) w 取值在 [0.8，1.2]之間時，算法收斂較快。基于此，取慣性權(quán)重值為 0.8 。

3 模型仿真

以2012年春運節(jié)前客票銷售數(shù)據(jù)為樣本數(shù)據(jù)集，進行平滑度仿真實驗，確定預(yù)售期調(diào)整優(yōu)化方案。初始數(shù)據(jù)集：{1 763 447，1 530 622，1 087 933，1 038 916，1 000 560，1 477 520}。粒子范圍為[1 000 560，1 763 447]，vmax的取值為 762 887。預(yù)售期內(nèi)售票量的平滑度仿真結(jié)果如圖3所示，實驗統(tǒng)計量如表1所示。從圖3可見，不同的預(yù)售期售票曲線的平滑度不同。從表1可見，設(shè)置預(yù)售期為 13d時，評價指標(biāo)綜合最佳，平滑度最優(yōu)。從減輕系統(tǒng)壓力方面考慮，建議調(diào)整預(yù)售期為 13 d。

圖3 預(yù)售期內(nèi)售票量的平滑度仿真圖

仿真實驗的結(jié)果表明，通過 PSO 算法調(diào)整預(yù)售期可以平滑日售票量，減輕系統(tǒng)壓力。但是在圖3中的最優(yōu)曲線表明，在優(yōu)化過程中，存在指定售票日預(yù)售期內(nèi)售票量高峰轉(zhuǎn)移的現(xiàn)象，因此該解為局部最優(yōu)解，這與權(quán)重參數(shù) w 的選取有關(guān)。

表1 仿真實驗統(tǒng)計量

4 結(jié)束語

基于粒子群算法建立鐵路客運預(yù)售期模型，研究結(jié)果表明，該模型能夠較好地優(yōu)化預(yù)售期內(nèi)日售票量的平滑度，對于均衡系統(tǒng)資源、制定合理的預(yù)售期具有一定指導(dǎo)意義。2011年開始全面實現(xiàn)互聯(lián)網(wǎng)售票及電話訂票業(yè)務(wù)，鐵路客運售票量在特定時期如春運、暑運、十一、五一等階段不同售票方式的歷史數(shù)據(jù)有限，因此，該仿真實驗存在局限性。在下一步的研究中，一方面可在歷史數(shù)據(jù)充足的條件下對適用度函數(shù)的參數(shù)進行優(yōu)化，另一方面可以根據(jù)不同的售票方式建立多層次應(yīng)用模型，完善算法。

[1]Kennedy J，Eberhart R C. Particle Swarm Optimization[M]//IEEE Service Center. Proceedings of IEEE International Conference on Neural Networks. Piscataway，New Jersey：IEEE Service Center，1995，4：1942-1948.

[2]Yuhui Shi，Russell Eberhart. A Modified Particle Swarm Optimizer[M]//IEEE Press. Proceedings of IEEE World Congress on Computational Intelligence in：Evolutionary Computation. Anchorage，AK USA：IEEE Press，1998：69-73.