基于Shapley值分配原則的鐵路應(yīng)急資源調(diào)度研究

湯兆平,鄒 揚(yáng),劉鈺玲,孫劍萍

(1. 華東交通大學(xué) 交通運(yùn)輸工程學(xué)院,江西 南昌 330013;2. 寧波市軌道交通集團(tuán)有限公司,浙江 寧波 315101)

0 引 言

隨著我國鐵路路網(wǎng)密度的持續(xù)增大,列車運(yùn)行時速不斷提高,行車組織愈加復(fù)雜,路網(wǎng)之中出現(xiàn)多個地點(diǎn)同時發(fā)生事故的可能性也逐漸增大,如遇到特殊地形地質(zhì)或自然災(zāi)害時,更容易引發(fā)大規(guī)模的鐵路突發(fā)事故。由于事故發(fā)生存在不確定性,以及鐵路應(yīng)急資源的儲備成本高等特點(diǎn),各救援點(diǎn)的應(yīng)急資源不可能無限制配備[1]。因此,針對救援初期資源不足的情況,對多事故點(diǎn)多救援點(diǎn)的資源公平調(diào)配問題的研究顯得尤為重要。

在多事故點(diǎn)-多資源-多救援點(diǎn)的應(yīng)急資源分配調(diào)度方面,相關(guān)學(xué)者已進(jìn)行了一定的研究。如王東海等[2]通過TOPSIS模型來評估事故點(diǎn)的救援優(yōu)先權(quán),模型中以成本系數(shù)和時間系數(shù)的形式表示事故點(diǎn)的優(yōu)先權(quán),使救援優(yōu)先權(quán)較高的事故點(diǎn)優(yōu)先獲得其所需的資源。范雪琳[3]以應(yīng)急控制程度最大化和線路停運(yùn)損失最小化為目標(biāo),研究了鐵路接觸網(wǎng)多故障的資源調(diào)度問題;王旭坪等[4]以效用滿意度和需求滿意度為目標(biāo)來描述并求解救援初期的應(yīng)急物資分配問題;CHAI Gan等[5]提出了一種以救援路線行程時間估計為依據(jù)的應(yīng)急救援資源調(diào)度方法,根據(jù)應(yīng)急救援路徑的總長度與救援車輛排隊在時間上的延誤的對應(yīng)關(guān)系,計算出救援路徑行程的大致時間,并以此為據(jù)建立改進(jìn)的資源調(diào)度模型;湯兆平等[6]考慮事故點(diǎn)的需求為模糊需求,運(yùn)用塔木德公平分配理論對大規(guī)模鐵路突發(fā)事件下多事故點(diǎn)-多救援點(diǎn)-多種資源的資源分配問題,基于此分配原則進(jìn)行資源調(diào)度,可以較好地保持博弈規(guī)則的公正性;陳治亞等[7]通過AHP模糊綜合評價法對鐵路多事故點(diǎn)的受災(zāi)程度進(jìn)行評分,并以運(yùn)輸成本和懲罰成本最小化為目標(biāo)建立資源調(diào)度優(yōu)化模型。Shapley值分配原則能夠兼顧公平與效益,已有學(xué)者對其在收益分配機(jī)制方面進(jìn)行了研究。張宇翔等[8]通過考慮項目內(nèi)部成員的產(chǎn)權(quán)比例、風(fēng)險承擔(dān)和工作貢獻(xiàn),構(gòu)建了國際高鐵項目收益分配概念模型,并采用合作博弈理論和Shapley值法對收益分配方案進(jìn)行了修正;WANG Yuanhua等[9]研究了在n人合作對策下的對稱和加權(quán)Shapley值,利用博弈者定義的非對稱權(quán)重設(shè)計加權(quán)Shapley值的收益函數(shù),從而保證最優(yōu)分配是純Nash均衡;趙璇[10]針對產(chǎn)學(xué)研聯(lián)盟收益分配中存在收益值的不確定性以及聯(lián)盟的不穩(wěn)定性2個問題,使用估計值來衡量聯(lián)盟的收益,建立了基于H-Shapley值法的產(chǎn)學(xué)研聯(lián)盟收益分配模型,得出的H-Shapley分配解能夠使產(chǎn)學(xué)研聯(lián)盟合作保持長久穩(wěn)定;楊靛青等[11]利用Choquet積分定義模糊合作對策中局中人可能形成的多層級聯(lián)盟結(jié)構(gòu),在此基礎(chǔ)上提出Shapley值解概念及其解法,通過算例分析合作對策Shapley值和Banzhaf值的異同特性,結(jié)果表明Shapley值的聯(lián)盟結(jié)構(gòu)相對固定;武士超等[12]通過熵值法和Shapley值法對快遞行業(yè)組建末端配送聯(lián)盟利益進(jìn)行分配,最后對影響因素權(quán)重進(jìn)行修正,得到最終分配結(jié)果,結(jié)果符合個體理性和集體理性;K.M.CUBUKCU[13]證明了在合作博弈框架下發(fā)展起來的Shapley值公平分割方案,可以實(shí)現(xiàn)土地所有者之間剩余開發(fā)權(quán)的公平分割。

筆者將Shapley值分配原則引入鐵路應(yīng)急資源的分配中,通過計算出各事故點(diǎn)對不同資源的Shapley值以確定分配比例和分配量,再綜合考慮調(diào)度時間和調(diào)度成本等因素建立優(yōu)化模型,最后進(jìn)行模型求解。使調(diào)度方案實(shí)現(xiàn)公平與效益的統(tǒng)一,在減小系統(tǒng)綜合損失的同時,該種分配方案也更易被多方接受。

1 Shapley值分配理論

假設(shè)合作博弈系統(tǒng)內(nèi)有n個成員,由N={1,2,…,n}表示,不同成員之間互相排列組合成不同的聯(lián)盟S(S?N),特征函數(shù)w(S)為聯(lián)盟S的收益,w(S)具有超可加性,其性質(zhì)表示為:若聯(lián)盟S1和S2之間沒有交集,則S1和S2合并形成新聯(lián)盟的收益應(yīng)該不小于聯(lián)盟S1與S2的收益之和[14]。即:

(1)

聯(lián)盟內(nèi)成員i的收益為該成員i在所有聯(lián)盟的參與中創(chuàng)造的邊際貢獻(xiàn)均值,表示為φi(w):

(2)

式中:S為包含成員i的所有子聯(lián)盟;|S|為子聯(lián)盟S中成員的個數(shù);w(S{i})為子聯(lián)盟S除去成員i后的收益;w(S)-w(S{i})為成員i對子聯(lián)盟S的邊際貢獻(xiàn);θ(|S|)為聯(lián)盟S出現(xiàn)的概率,其計算公式為:

(3)

2 問題描述

3 多目標(biāo)優(yōu)化模型建立

為了方便計算,筆者只考慮由于事故造成的直接損失。由于鐵路應(yīng)急救援具有緊迫性,因此優(yōu)化模型目標(biāo)函數(shù)的主要考慮因素是資源調(diào)度的時間最短,其次還應(yīng)該盡可能使資源的調(diào)配成本最小。

根據(jù)上述分析,建立多目標(biāo)優(yōu)化模型如下:

(4)

(5)

(6)

(7)

(8)

(9)

(10)

模型中:式(4)為救援時間最短的目標(biāo)函數(shù);式(5)為總調(diào)度成本最小的目標(biāo)函數(shù);式(6)為事故點(diǎn)i和救援點(diǎn)j之間構(gòu)成事故點(diǎn)-救援點(diǎn)對;式(7)為事故點(diǎn)i和救援點(diǎn)j之間不構(gòu)成事故點(diǎn)-救援點(diǎn)對;式(8)為應(yīng)急救援點(diǎn)向事故點(diǎn)實(shí)際運(yùn)送應(yīng)急資源的量等于救援點(diǎn)對該事故點(diǎn)應(yīng)急資源的調(diào)運(yùn)量總和;式(9)為應(yīng)急救援點(diǎn)向事故點(diǎn)實(shí)際運(yùn)送應(yīng)急資源的量應(yīng)該小于或等于救援點(diǎn)j的資源儲備量;式(10)為救援點(diǎn)向事故點(diǎn)的實(shí)際運(yùn)送量應(yīng)該不小于0。

4 基于Shapley值分配原則的需求點(diǎn)資源分配數(shù)量的確定

將事故點(diǎn)的應(yīng)急救援工作類比于合作博弈問題,其中的事故點(diǎn)可看作博弈問題中的參與方,應(yīng)急資源的分配可看作參與項目的過程,各事故點(diǎn)由于應(yīng)急資源得到滿足所減少的損失可類比于參與到項目中獲得的收益。

1)列舉出所有包含事故點(diǎn)i的救援方案S,分別計算各個救援方案S下所減少的損失為:

(11)

2)計算在救援方案S中除去事故點(diǎn)i后所減少的損失為:

(12)

3)計算得到事故點(diǎn)i在救援方案S下的邊際收益為:

(13)

4)根據(jù)式(2)得出事故點(diǎn)i對資源k的Shapley值為:

(14)

5)重復(fù)上述步驟,分別計算得出各個事故點(diǎn)i(i=1,2,…,n)的Shapley值,從而得到在現(xiàn)有的資源k總儲備量條件下各個事故點(diǎn)的資源分配比例為:

(15)

6)設(shè)y為規(guī)模比例系數(shù),各個事故點(diǎn)對k資源需求量、分配比例與規(guī)模比例系數(shù)乘積之和應(yīng)該與k資源的總儲備量相等,即:

(16)

7)根據(jù)式(16),可以得到y(tǒng)的具體數(shù)值,進(jìn)而可以確定各個事故點(diǎn)i對k資源的具體分配數(shù)量為:

(17)

5 實(shí)例分析

5.1 實(shí)例概況

以中國鐵路某局集團(tuán)公司為例,其局內(nèi)設(shè)共有14個應(yīng)急救援基地(A1,A2,…,A14),為了便于計算,假設(shè)在某局的部分區(qū)域內(nèi)突發(fā)鐵路大規(guī)模事故,涉及的事故點(diǎn)有3處,分別用N1,N2,N3表示,參與救援的救援基地有5處,分別用M1,M2,…,M5表示。假設(shè)該事故中事故點(diǎn)需要的應(yīng)急資源有醫(yī)療救援設(shè)備k1和鐵路搶修設(shè)備k2兩種?？紤]到鐵路貨運(yùn)單位千米運(yùn)費(fèi)以及救援時間成本,將單位救援物資和單位千米的運(yùn)費(fèi)設(shè)為c=7元,通過參考相關(guān)實(shí)例并根據(jù)決策者的偏好合理假設(shè),將調(diào)運(yùn)時間、調(diào)運(yùn)成本的權(quán)重分別確定為ξ1=0.3,ξ2=0.7。各個救援點(diǎn)與事故點(diǎn)之間的信息如表1。

表1 各救援點(diǎn)和事故點(diǎn)信息

5.2 確定各需求點(diǎn)的實(shí)際分配數(shù)量

5.2.1 資源k1

表2 各事故點(diǎn)由于資源k1未能得到滿足引起的損失

計算各個事故點(diǎn)對資源k1的Shapley值。

設(shè)y1為資源 的規(guī)模比例系數(shù),已知資源k1的總儲備量為170,根據(jù)公式(16),有:(80×37%+40×24%+70×39%)×y1=170,從而得到y(tǒng)1=2.56。

最后根據(jù)式(17)計算得到資源k1的實(shí)際分配情況如表3。

5.2.2 資源k2

表4 各事故點(diǎn)由于資源k2未能得到滿足引起的損失

計算各個事故點(diǎn)對資源k2的Shapley值。

設(shè)y2為資源k2的規(guī)模比例系數(shù),已知資源k2的總儲備量為150,根據(jù)公式(16),有:(70×39%+40×26%+60×35%)×y2=150,從而得到y(tǒng)2=2.55。

最后根據(jù)式(17)計算得到資源k2的分配情況如表5。

表5 資源k2分配情況

5.3 調(diào)度方案的最優(yōu)解

表6 最優(yōu)調(diào)度方案

將優(yōu)化后的結(jié)果代入式(4)和式(5),并根據(jù)調(diào)運(yùn)時間以及調(diào)運(yùn)成本的權(quán)重ξ1=0.3,ξ2=0.7,計算得到本次救援的最小綜合成本為194 221.3元。

6 多種分配方法下的比較分析

在資源公平分配方面,主要有約翰·羅爾斯的公平分配理論、亞里士多德的分配正義理論、Shapley值分配理論以及塔木德公平分配理論。

為了體現(xiàn)Shapley值分配原則在鐵路應(yīng)急資源調(diào)度方面的良好適用性,下面以資源k1為例,對比分析比例分配理論和塔木德分配理論對上述案例的資源分配情況,計算得到具體分配情況見表7(不限定整數(shù))。

表7 不同分配方法下各事故點(diǎn)對資源k1的分配量

從資源需求量上看,事故點(diǎn)N1對資源k1的需求量最大,可以認(rèn)為該事故點(diǎn)受災(zāi)相對嚴(yán)重;N2的需求量最小,受災(zāi)相對較輕。從3種方式的分配結(jié)果可以看出,Shapley值分配法分配給受災(zāi)最嚴(yán)重的事故點(diǎn)N1的資源數(shù)量最多,其次是塔木德分配法,比例分配最少。該分配結(jié)果證明Shapley值分配法對受災(zāi)最為嚴(yán)重的事故點(diǎn)進(jìn)行了重點(diǎn)考慮N1,充分反映了在救援初期資源不足的情況下,Shapley值分配方法的天平是傾向于弱者的。對于受災(zāi)程度相對較輕的事故點(diǎn)N2,資源分配數(shù)量最多的是比例分配法,其次是塔木德分配法,Shapley值分配法最少。3種分配方法分派給各個事故點(diǎn)的資源數(shù)量雖互有差異,但它們的變化范圍處在同一數(shù)量級上,說明Shapley值分配法在優(yōu)待弱者的同時,依然保證了博弈的公平性原則。

3種分配方法對資源k1的最優(yōu)調(diào)度方案如表8。

表8 不同分配方法下資源k1的最優(yōu)調(diào)度方案

將表8得出的最優(yōu)調(diào)度方案代入式(4)和式(5),得到比例分配和塔木德分配對于資源k1的綜合成本分別為105 804.7元和105 480.3元,而Shapley值分配法的綜合成本為105 457.8元。由此可知,根據(jù)Shapley值分配原則進(jìn)行資源分配調(diào)度時所產(chǎn)生的綜合成本最小,能最大程度上減少事故造成的經(jīng)濟(jì)損失。

與比例分配原則相比,Shapley值分配原則基于公平分配理論,根據(jù)減少損失的程度對事故點(diǎn)所需資源進(jìn)行分配,考慮每種分配方法所減少的邊際損失,體現(xiàn)了“按勞分配”的原則,具有較強(qiáng)的合理性。相比于塔木德分配原則適用于應(yīng)急資源較為充足的情況,Shapley值法分配原則在大規(guī)模鐵路突發(fā)事件初期,應(yīng)急資源儲備量不足以滿足所有事故點(diǎn)的需求量的情況下更為適用。

7 結(jié) 論

針對鐵路突發(fā)事故初期多事故點(diǎn)多救援點(diǎn)的資源分配問題,通過綜合分析現(xiàn)有的資源公平分配方式,采用Shapley值分配法對各需求點(diǎn)進(jìn)行了資源分配,在此基礎(chǔ)上以救援時間最短、資源運(yùn)輸成本最小為目標(biāo)建立多目標(biāo)優(yōu)化模型,并借助Lingo軟件求解,得到的結(jié)論如下:

1)將Shapley值分配原則用于鐵路應(yīng)急資源調(diào)度工作中,為大規(guī)模鐵路突發(fā)事件下多事故點(diǎn)-多救援點(diǎn)-多種應(yīng)急資源的資源調(diào)配提供了新的思路和方法。通過Shapley值計算結(jié)果來衡量各個事故點(diǎn)應(yīng)急資源得到滿足時所減少損失的程度,并以此計算各事故點(diǎn)進(jìn)行資源分配的比例系數(shù),這個過程既考慮了分配的效益,又兼顧分配的公平性原則。

2)將Shapley值分配方法對資源k1的分配結(jié)果與比例分配和塔木德分配方法的分配結(jié)果進(jìn)行對比,結(jié)果表明Shapley值分配方法能更好地考慮受災(zāi)程度相對嚴(yán)重事故點(diǎn)。并且3種分配方法分派給各個事故點(diǎn)的資源數(shù)量雖互有差異,但它們的變化范圍處在同一數(shù)量級上,說明Shapley值分配法在優(yōu)待弱者的同時,依然保證了博弈的公平性原則。