關(guān)于列車時(shí)刻表效用值優(yōu)化問題的求解研究

沈 潔，祖天琪，宋雨徽，太文芳

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院，遼寧 大連 116029)

0 引言

優(yōu)化問題是基于現(xiàn)有資源使效益最大或?yàn)閷?shí)現(xiàn)某目標(biāo)使成本最低的問題[1].本文研究的列車時(shí)刻表效用值問題是非光滑優(yōu)化問題[2]，求解方法通常包括最速下降法、黑盒子方法、束方法等[3].最速下降法需要對次微分有整體地全面了解，黑盒子方法無法保證目標(biāo)函數(shù)的下降，二者的不足較明顯，而束方法結(jié)合了最速下降法的下降性和黑盒子方法的穩(wěn)定性[3]，效果較好.常規(guī)的束方法有水平束方法、信賴域束方法、懲罰束方法等[3].在實(shí)際運(yùn)算中，目標(biāo)函數(shù)值往往不能被精確算出，通常得到的是近似值，故近幾年有多名學(xué)者利用目標(biāo)函數(shù)近似值對束方法展開研究，如：張清葉等[4]提出了一種求解非光滑凸規(guī)劃問題的混合束方法；董小霞等[5-7]利用目標(biāo)函數(shù)的近似信息研究非精確束方法；沈潔等[8-9]利用懲罰束方法解決通信數(shù)據(jù)網(wǎng)絡(luò)優(yōu)化問題近似模型的相關(guān)問題并研究了非光滑無約束凸規(guī)劃的混合束方法；U.Brannlund等[10]介紹了一種針對列車時(shí)刻表優(yōu)化問題的拉格朗日松弛方法；A.A.Abderrahman等[11]介紹了一種針對列車時(shí)刻表優(yōu)化問題的聚集束方法.列車時(shí)刻表效用值優(yōu)化問題是指尋找一個(gè)科學(xué)可執(zhí)行的列車時(shí)刻表來使軌道運(yùn)輸產(chǎn)生的效用值達(dá)到最大的問題.本文針對列車時(shí)刻表效用值優(yōu)化問題提出了一種改進(jìn)的束方法，即通過使用指示函數(shù)將約束問題轉(zhuǎn)換成無約束問題，利用束方法基本思想構(gòu)建了切平面近似模型，在此基礎(chǔ)上以對偶理論為基礎(chǔ)，給出了原規(guī)劃與對偶規(guī)劃最優(yōu)解的顯式表達(dá)，并得到了近似優(yōu)化模型的一些相關(guān)結(jié)論，為后續(xù)算法構(gòu)造奠定了基礎(chǔ)，對于軌道交通運(yùn)營效率的提高具有重要的客觀參考價(jià)值.

1 預(yù)備知識與模型構(gòu)建

首先給出非光滑優(yōu)化基本概念、束方法相關(guān)理論和列車時(shí)刻表優(yōu)化效用值優(yōu)化問題的近似模型.

定義1(次微分) 設(shè)f(x)是Rn上的凸函數(shù)，f(x)在x點(diǎn)處的次微分定義為

?f(x)={s∈Rn|f(y)≥f(x)+sT(y-x)，?y∈Rn}.

定義2(εk次微分) 設(shè)f(x)是Rn上的凸函數(shù)，εk>0為常數(shù)，f(x)在x點(diǎn)處的εk次微分定義為

?εkf(x)={s∈Rn|f(y)≥f(x)+sT(y-x)-εk，?y∈Rn}.

定義3(法錐) 設(shè)S?Rn非空，集合S在點(diǎn)x∈S處的法錐NS(x)定義為

NS(x)={d∈Rn|dT(y-x)≤0，?y∈S}.

列車時(shí)刻表效用值問題(TTP)是指尋找一個(gè)科學(xué)可執(zhí)行的列車時(shí)刻表來使軌道運(yùn)輸產(chǎn)生的效用值達(dá)到最大的問題.科學(xué)可執(zhí)行意味著既要滿足每列列車在特定的時(shí)間段內(nèi)不發(fā)生沖突，又不能超出鐵路系統(tǒng)的基礎(chǔ)設(shè)施與軌道容量的限制.優(yōu)化列車時(shí)刻表主要考慮的效用值規(guī)劃問題是[9]：

(1)

只考慮問題(1)中的第一個(gè)約束，引入對偶變量y∈Rn，則問題(1)的拉格朗日函數(shù)為

(2)

引入指示函數(shù)

其中D={y|y≥0}，y≥0表示y的每個(gè)坐標(biāo)都大于或等于零，文中類似情形不再說明.則問題(2)可改寫為一個(gè)無約束優(yōu)化問題，具體為

(3)

為避免步長較大，問題(3)中增加二次項(xiàng)，引入控制參數(shù)uk調(diào)整步長，相應(yīng)效用值子問題為

(4)

定義額定下降為

(5)

2 基于近似模型對偶問題最優(yōu)解的表達(dá)及相關(guān)性質(zhì)研究

定理2.1設(shè)yk+1是列車時(shí)刻表近似模型子問題(4)的最優(yōu)解，那么

(6)

證明將問題(4)寫成一個(gè)帶有額外標(biāo)量r的二次規(guī)劃問題，具體為

(7)

整理后得到

其中

因此

(8)

定理2.2對于時(shí)刻列車表效用值優(yōu)化模型近似問題(4)，有以下結(jié)論成立：

證明(ⅰ) 根據(jù)問題(4)的最優(yōu)性條件和k的定義，有

故

(ⅱ) 由于沒有對偶間隙，原規(guī)劃(4)與對偶規(guī)劃(8)最優(yōu)值等價(jià)，即

由式(4)和式(5)有

由于μk為穩(wěn)定中心，yk+1為最優(yōu)解，則iD(μk)=0，iD(yk+1)=0.應(yīng)用式(5)額定下降的定義和(ⅱ)的結(jié)論，有

因此

φ(y)+iD(y)≥φ(μk)+iD(μk)+k*(y-μk)-εk.

故

k∈?εkφ(μk)+?εkiD(μk).

3 結(jié)語

本文采用傳統(tǒng)懲罰束方法對列車時(shí)刻表效用值優(yōu)化問題展開了研究.通過增加指示函數(shù)構(gòu)建目標(biāo)函數(shù)的近似模型，利用束方法基本思想構(gòu)建了切平面近似模型，以對偶理論為基礎(chǔ)，給出了原規(guī)劃與對偶規(guī)劃最優(yōu)解的顯式表達(dá)以及近似優(yōu)化模型的一些相關(guān)結(jié)論，為后續(xù)算法構(gòu)造奠定了基礎(chǔ).