微分進化算法在高鐵票價雙層規(guī)劃模型求解中的應(yīng)用

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

關(guān)鍵詞：微分進化算法；高速鐵路票價；雙層規(guī)劃模型

中圖分類號：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 引 言

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

1 微分進化算法

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

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

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

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

2 雙層規(guī)劃模型

2.1 雙層規(guī)劃形式

雙層規(guī)劃的形式如下所示：

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

其中y=y（x）由下述規(guī)劃求得：

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

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

2.2 模型的建立

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

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

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

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

2.3 上層規(guī)劃構(gòu)建

對于高鐵運輸線路中的不同出發(fā)到達點，本文將其定義為單個OD組，為了簡化模型，定義在OD組ω之間鐵路運輸?shù)目推眱r格為 ，那么在整個客運網(wǎng)絡(luò)中，總收益為：

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

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

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

（4）

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

（5）

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

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

求解過程如下：

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

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

第二步，把上層規(guī)劃中的初始解，即票價代入下層函數(shù)：

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

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

（3）根據(jù)評價函數(shù)，將各個分量的F值進行比較，優(yōu)選出新的優(yōu)勢種群；

（4）如果達到預(yù)設(shè)迭代次數(shù)，或F值已經(jīng)不再明顯變化，則計算結(jié)束，得到最優(yōu)解u，否則轉(zhuǎn)入（1），繼續(xù)計算。

4 結(jié) 論

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

參考文獻：

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

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

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

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

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

[6] 程謙.雙層規(guī)劃模型在滬寧城際鐵路客票價格優(yōu)化中的應(yīng)用 [J].現(xiàn)代交通技術(shù)，2015，12（2）：77-80.

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

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

[9] 陳建華.鐵路旅客票價優(yōu)化問題的相關(guān)模型及算法 [D].北京：北京交通大學(xué)，2007.

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

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