[發(fā)明專利]一種雙目標(biāo)交通網(wǎng)絡(luò)規(guī)劃模型優(yōu)化計(jì)算方法

在審

• 申請?zhí)枺?/td>: 201710512480.3
• 申請日: 2017-06-29
• 公開（公告）號: CN107274032A
• 公開（公告）日: 2017-10-20
• 發(fā)明（設(shè)計(jì)）人: 謝馳;米陽;劉海洋
• 申請（專利權(quán)）人: 上海交通大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G08G1/01
• 代理公司: 上海伯瑞杰知識產(chǎn)權(quán)代理有限公司31227
• 代理人: 孟旭彤

1.一種雙目標(biāo)交通網(wǎng)絡(luò)規(guī)劃模型優(yōu)化計(jì)算方法，其特征在于，采用二分解決計(jì)算方法，即，先設(shè)定雙目標(biāo)交通網(wǎng)絡(luò)規(guī)劃模型是一個(gè)雙目標(biāo)離散優(yōu)化問題min_x{(f¹(x)，f²(x))|x∈X}，(f¹，f²)是目標(biāo)向量，x和X是決策變量集和可行變量區(qū)域，具體步驟如下：

步驟一，是初始化，分別解決兩個(gè)標(biāo)量化問題min_x{f¹(x)|x∈X}和min_x{f²(x)|x∈X}，并設(shè)置解向量為和其各自的目標(biāo)函數(shù)向量設(shè)為和

如果那么該雙目標(biāo)問題只有一個(gè)最優(yōu)解并且所有的非劣解已經(jīng)被找到；否則，將目標(biāo)函數(shù)向量對放入先進(jìn)先出列表(FIFO)；

步驟二，參數(shù)產(chǎn)生，從先進(jìn)先出列表中選擇第一個(gè)目標(biāo)函數(shù)向量對(f_a，f_b)，其中并且產(chǎn)生一個(gè)新的參數(shù)集并構(gòu)造一個(gè)標(biāo)量化的單目標(biāo)問題；

步驟三，問題求解，如果該標(biāo)量化問題存在最優(yōu)解，那么這就是原問題的一個(gè)非劣解；使用得到的目標(biāo)函數(shù)向量f^*與f_a和f_b結(jié)合來構(gòu)造兩個(gè)新的目標(biāo)函數(shù)向量對(f_a，f^*)和(f^*，f_b)，并把它們放入先進(jìn)先出列表，

如果該表量化問題不存在可行解，那么在(f_a，f_b)所構(gòu)成的限制區(qū)域內(nèi)，非劣解不存在；

步驟四，終止條件，如果先進(jìn)先出列表是空的，那么停止搜索，所有的非劣解已經(jīng)得到；否則，轉(zhuǎn)入步驟二；

通過先進(jìn)先出列表中既定的目標(biāo)函數(shù)向量(f_a，f_b)構(gòu)造單目標(biāo)問題，其中并且

(f_a，f_b):目標(biāo)函數(shù)向量對，

w:目標(biāo)函數(shù)系數(shù)的參數(shù)集，

在第n次迭代的系數(shù)，

在第n次迭代的系數(shù)，

雙目標(biāo)約束，帶權(quán)重的目標(biāo)函數(shù)方法有如下構(gòu)造：

minxf=w1(n)fn1+w2(n)fn2]]>

滿足于：

fn1≤fmax1-∈and fn2≤fmax2-∈]]>

where fmax1=max(fn-11,fn1)and fmax2=max(fn-12,fn2)]]>

w1(n+1)=fn2-fn-12(fn-11-fn1)+(fn2-fn-12)and w2(n+1)=fn-11-fn1(fn-11-fn1)+(fn2-fn-12)]]>

使用正交法產(chǎn)生參數(shù)集添加對于每個(gè)目標(biāo)函數(shù)添加額外約束：

2.如權(quán)利要求1所述的雙目標(biāo)交通網(wǎng)絡(luò)規(guī)劃模型優(yōu)化計(jì)算方法，其特征在于，采用分解法來解決該單目標(biāo)混合整數(shù)規(guī)劃問題，步驟如下：

步驟1，初始化，設(shè)迭代次數(shù)n＝1，并且確立一個(gè)合適的初始解zⁿ，如果沒有可行解存在，那么停止運(yùn)算；

步驟2，子問題求解，當(dāng)給定z＝zⁿ時(shí)，解子問題P^s，如果P^s不存在可行解，那么進(jìn)入步驟0；否則，我們可以得到交通流xⁿ，Lagrangian乘數(shù)λⁿ，和上界f^U＝min f(x^λ，z^λ)；

步驟3，主問題求解，對所有的i＝1，...，n，給定λⁱ，求解主問題P^r，更新解zⁿ，并得到目標(biāo)函數(shù)的下界f^U＝max μ^λ，其中μ^λ是主問題的目標(biāo)函數(shù)值；

步驟4，收斂性檢查，如果f^U-f^L≤ε，其中ε是提前預(yù)設(shè)的差值，那么運(yùn)算停止，否則，令n：＝n+1，并進(jìn)入步驟2；

如果該標(biāo)量化問題存在最優(yōu)解，則該最優(yōu)解是原問題的一個(gè)非劣解，使用得到的目標(biāo)函數(shù)向量f^*與f_a和f_b結(jié)合來構(gòu)造兩個(gè)新的目標(biāo)函數(shù)向量對(f_a，f^*)和(f^*，f_b)，并把它們放入先入先出列表，

如果該表量化問題不存在可行解，那么在(f_a，f_b)所構(gòu)成的限制區(qū)域內(nèi)，非劣解不存在。