微分進化算法在高鐵票價雙層規劃模型求解中的應用

摘 要：微分進化算法（DE）是一種快速高效的智能進化算法，本文對其算法做了簡單的介紹，并針對高速鐵路票價問題，引入并構建了雙層規劃模型。模型中高鐵企業是領導者角色，出行乘客是跟隨者角色，二者相互作用。上層模型從高鐵企業收益最大化的角度出發，下層模型以各類出行方式的乘客廣義出行費用相同為基礎。針對該模型設定了一些參數，并介紹了如何應用微分進化算法對該模型進行求解，并對乘客福利及算法本身的優化工作做出了進一步設想。

關鍵詞：微分進化算法；高速鐵路票價；雙層規劃模型

中圖分類號：TP301.6 文獻標識碼：A 文章編號：2096-4706（2019）04-0020-03

Application of Differential Evolution Algorithms in Bi-level Programming Model of

High-speed Railway Ticket Price

CUI Wei

（School of Traffic and Transportation，Lanzhou Jiaotong University，Lanzhou 730070，China）

Abstract：Differential evolution （DE） is a fast and efficient intelligent evolutionary algorithm，and its algorithm is briefly introduced. Aiming at the problem of high-speed railway fare，a bi-level programming model is introduced and constructed. In the model，the high-speed railway enterprise is the leader role，and the traveling passenger is the follower role，which interact with each other. The upper model is based on maximizing the revenue of high-speed railway enterprises，and the lower model is based on the same generalized travel cost of passengers in different modes of travel. Some parameters are set for the model，and how to use differential evolution algorithm to solve the model is introduced. Further assumptions are made on passenger welfare and optimization of the algorithm itself.

Keywords：differential evolution algorithms；high-speed railway ticket price；bi-level programming model

0 引 言

高速鐵路是未來鐵路旅客運輸的發展方向，票價在運輸問題中至關，鐵路部門作為企業要考慮收益最大化，同時作為國企還要承擔相應的社會責任，保證票價能讓乘客接受，這是一個復雜的問題。低票價會使企業入不敷出，導致虧損，高票價既浪費社會資源，又會引發乘客不滿，導致低上座率。企業在盈利和社會福利間實現最優票價是非常重要的問題，在制定高速鐵路的票價過程中引入雙層規劃模型是非常合適的。微分進化算法（Differential Evolution Algorithm，簡稱DE）是一種啟發式算法，原理簡單、易實現、效率高，非常適合用于雙層規劃模型的求解[1]。

1 微分進化算法

DE算法在求解連續變量的函數優化問題時能快速、穩定地收斂到全局最優解[2]，迭代到預設次數，或者目標函數到達一定要求時結束運算。影響微分進化算法性能的主要控制參數有種群規模、縮放因子和交叉常量。

（1）種群規模：種群規模較大時，算法的搜索范圍也會大，但是計算的時間會變長，問題的維數較高時，算法的效率低。種群小則種群會變得單一，易落入局部最優的困局，從而錯失最優解。根據經驗，種群數量可以取在問題維數的5～10倍；

（2）縮放因子：向量之間差值的系數用F表示，F越小，計算的收斂速度越快，每次搜索的距離就越近，越易陷入局部最優。F越大，收斂的速度會慢，向量探索的距離就越遠，更容易取到全局最優解，它的初值可以在[0.5，0.6]；

（3）交叉常量：它的取值區間為[0，1]，取值小，子代從父代繼承的部分就少，變異較小，收斂速度低。實際計算中取值范圍為[0.6，0.9]，它初值可以為0.8，具體應用時根據不同的需要可以略微作調節[1，2]。

2 雙層規劃模型

2.1 雙層規劃形式

雙層規劃的形式如下所示：

s.t. G（x，y）≤0

其中y=y（x）由下述規劃求得：

s.t. g（x，y）≤0

雙層規劃模型由上層模型（p1）和下層模型（p2）組成，上下層問題分別由相應的公式組成。居于上層的領導者通過對x值的決策影響下層跟隨者，下層跟隨者通過它的目標函數對上層領導者產生反饋。下層跟隨者的變量x是上層領導者變量y的函數，就是y=y（x），反應函數[3，4]。

2.2 模型的建立

本模型中把高速鐵路客運部門的收益多少與旅客的廣義出行費用看成上下層領導者與跟隨者的關系問題，其中高鐵客運部門是領導者，旅客的出行需求是跟隨者。領導者通過調整票價、安排車次、安排到發時間、提供不同等級的列車和坐席等政策來調整某種交通方式的特征，跟隨者面對各種出行方式，根據自身需要做出決策。由此，用以下模型來描述[5]：

其中U為上層規劃，L為下層規劃，F為上層規劃的目標函數，x為上層規劃的決策變量，G為對變量x的約束條件，f為下層規劃的目標函數，y為下層規劃的決策變量，g為對變量的約束條件，y=f（x）為反應函數[6]。

上層規劃U：高鐵客運部門通過決策票價水平、制定列車開行速度、開行時長等方式最大化企業收益；下層規劃L：出行者面對多種運輸方式，根據自身的收入水平、實際出行需要或換乘方案等，選擇廣義出行費用最小的。

模型中的上層規劃和下層規劃是相互制約的，客運企業期望經濟效益最大化，以此作為出發點來制定票價，同時旅客期望出行的廣義費用最小。一般情況下，在其他影響因素（如旅行時長、服務水平）不變的情況下，若高鐵票價價格上升，則必會影響客流分擔率，由部分高鐵客流轉向其他運輸方式（普速列車、公路或航空）；反之，高鐵票價價格下降則會導致部分其他運輸方式的客流需求轉移而來。因此，鐵路客運部門要對高鐵票價的制定做出全面的考慮[7]。

2.3 上層規劃構建

對于高鐵運輸線路中的不同出發到達點，本文將其定義為單個OD組，為了簡化模型，定義在OD組ω之間鐵路運輸的客票價格為 ，那么在整個客運網絡中，總收益為：

其中，為在OD組ω之間高鐵客運的流量，是高鐵部門在OD組ω之間乘客的人均運輸成本，也能用列車運行速度及服務水平等因素的函數來表示[8]。

對于下層規劃來說，由于每個乘客都會盡力選擇廣義出行費用最小的出行方式，經過簡化得到每一個運輸方式的廣義出行費用都相等，這樣得到如下公式：

Qw為OD組ω的客運總需求量，設OD組ω之間存在n種運輸方式，則n1，n2=1，2，K，n分別代表其中一種。函數f是一個廣義費用函數，式（2）表示狀態平衡時，多種運輸方式的廣義費用相等，式（3）表示多種運輸方式的客流量之和等于總客流量[9]。此處采用對數形式表示廣義費用函數f[8]：

（4）

a、b是系數，表示OD組ω中第n（n∈N）種交通方式的效用值，它的值越高，則乘客乘坐這種運輸方式所獲得的益處越大，即廣義出行費用低，表示如下[8]：

（5）

為出行時長參數，為客運票價參數，為安全及服務等其他相關系數；ai（i=1，2，3）為待定參數[8]。

3 基于微分進化算法求解雙層規劃模型

求解過程如下：

第一步，初始化參數：種群規模Np取20，縮放因子F初始化為0.6，交叉常量CR初始化為0.8。

在企業的運營過程中，首要考慮的因素應該是利潤，在與其它運輸方式競爭的過程中，企業要追求利益的最大化，其次由于企業的所有制形式，還要承擔一部分社會責任。因此，上述模型的目標分為兩個部分，第一個部分實現利潤的最大化，第二部分考慮社會的需求和公共福利。因此，第一階段的上層模型中Np=20，F=0.6，CR=0.9，滿足下層規劃函數的初始解 隨機產生，是不同交通方式i的票價[10]。

第二步，把上層規劃中的初始解，即票價代入下層函數：

（1）利用Frank-Wolfe算法求得最優解y*，即各種類列車的客流量；

（2）把X和y*代入上層函數，計算出種群中各個分量對應的F；

（3）根據評價函數，將各個分量的F值進行比較，優選出新的優勢種群；

（4）如果達到預設迭代次數，或F值已經不再明顯變化，則計算結束，得到最優解u，否則轉入（1），繼續計算。

4 結 論

微分進化算法是一種較為年輕的算法，它的優點很明顯，但是目前來看，在單目標計算方面使用較多，多目標計算方面有待進一步深入研究。本文通過引入微分進化算法，通過求解相應的雙層規劃函數，可以解決高速鐵路票價的優化問題。進一步的工作也可以改變優化策略，不僅可以實現高鐵部門收益最大化的目標，還可以從企業收益與乘客公共福利的角度對票價優化問題進行研究，兼顧雙方的目標。針對微分進化算法在搜索過程前期對搜索速度要求較高，以及后期對搜索范圍有一定要求的特點，可以在兩個階段對縮放因子和交叉系數進行優化，必定會大大提高算法的效率與準確度。

參考文獻：

[1] 崔偉.高速鐵路客運定價理論與方法研究 [D].蘭州：蘭州交通大學，2013.

[2] 劉科.改進微分進化算法在LZ-AVC6000系統中的研究與應用 [D].保定：華北電力大學，2017.

[3] 韋凌翔，陳紅，蔣金亮，等.基于廣義費用函數的高鐵票價雙層規劃模型研究 [J].鐵道科學與工程學報，2015，12（2）：250-256.

[4] 徐冰.基于鐵路客運票價的定價模型及求解方法研究 [D].沈陽：沈陽工業大學，2007.

[5] 陳建華，高自友.基于雙層規劃模型的鐵路票價制定優化策略 [J].北方交通大學學報（社會科學版），2003（3）：38-41.

[6] 程謙.雙層規劃模型在滬寧城際鐵路客票價格優化中的應用 [J].現代交通技術，2015，12（2）：77-80.

[7] 四兵鋒，高自友.市場競爭條件下的客運價格優化策略模型及算法 [J].交通運輸系統工程與信息，2007（1）：73-79.

[8] 高自友，四兵鋒.市場競爭條件下鐵路旅客票價制定的模型與算法 [J].交通運輸系統工程與信息，2001（1）：50-55.

[9] 陳建華.鐵路旅客票價優化問題的相關模型及算法 [D].北京：北京交通大學，2007.

[10] 郝鵬海，程曉榮.粒子群算法在鐵路雙層規劃模型求解中的應用 [J].電腦知識與技術，2017，13（26）：238-239+242.

作者簡介：崔偉（1982-），男，漢族，新疆奎屯人，工程師，碩士，研究方向：交通運輸規劃與管理。