[發(fā)明專(zhuān)利]快捷貨物運(yùn)輸路徑確定方法和裝置

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 200910086795.1
• 申請(qǐng)日: 2009-06-30
• 公開(kāi)（公告）號(hào): CN101592956A
• 公開(kāi)（公告）日: 2009-12-02
• 發(fā)明（設(shè)計(jì)）人: 郭玉華;賀振歡;王偉;任斌;蔣熙
• 申請(qǐng)（專(zhuān)利權(quán)）人: 北京交通大學(xué)
• 主分類(lèi)號(hào): G05D1/02
• 分類(lèi)號(hào): G05D1/02;G08G1/00
• 代理公司: 北京同達(dá)信恒知識(shí)產(chǎn)權(quán)代理有限公司
• 代理人: 李 娟

1.一種快捷貨物運(yùn)輸路徑確定方法，其特征在于，包括：

對(duì)于要從主干運(yùn)輸網(wǎng)絡(luò)中的第一節(jié)點(diǎn)運(yùn)送到第二節(jié)點(diǎn)的快捷貨物，確定一個(gè)節(jié)點(diǎn)集合，所述節(jié)點(diǎn)集合中包括所述第一節(jié)點(diǎn)、第二節(jié)點(diǎn)以及第一節(jié)點(diǎn)與第二節(jié)點(diǎn)之間的中轉(zhuǎn)節(jié)點(diǎn)；

將所述節(jié)點(diǎn)集合中的各中轉(zhuǎn)節(jié)點(diǎn)的剩余裝卸能力與所述快捷貨物所需的裝卸能力進(jìn)行比較；若比較的中轉(zhuǎn)節(jié)點(diǎn)的剩余裝卸能力小于所述快捷貨物所需的裝卸能力，則將該中轉(zhuǎn)節(jié)點(diǎn)從所述節(jié)點(diǎn)集合中刪除；

根據(jù)所述節(jié)點(diǎn)集合中的節(jié)點(diǎn)確定設(shè)定條數(shù)的備選路徑；所述備選路徑滿(mǎn)足以下條件：所述備選路徑由所述節(jié)點(diǎn)集合中某些具有連接關(guān)系的節(jié)點(diǎn)依次連接構(gòu)成，所述備選路徑的起始節(jié)點(diǎn)與終止節(jié)點(diǎn)分別為第一節(jié)點(diǎn)、第二節(jié)點(diǎn)；所述備選路徑中的各中轉(zhuǎn)節(jié)點(diǎn)滿(mǎn)足所述快捷貨物所需的中轉(zhuǎn)時(shí)間要求；以及所述備選路徑的全程運(yùn)輸時(shí)間小于由所述節(jié)點(diǎn)集合中的節(jié)點(diǎn)連接構(gòu)成的、以第一節(jié)點(diǎn)與第二節(jié)點(diǎn)分別為起始節(jié)點(diǎn)與終止節(jié)點(diǎn)的其它路徑的全程運(yùn)輸時(shí)間；

根據(jù)所述備選路徑確定所述快捷貨物在主干運(yùn)輸網(wǎng)絡(luò)中的運(yùn)輸路徑。

2.如權(quán)利要求1所述的方法，其特征在于，所述設(shè)定條數(shù)為一條，所述根據(jù)所述節(jié)點(diǎn)集合中的節(jié)點(diǎn)確定設(shè)定條數(shù)的備選路徑，具體包括：

根據(jù)所述節(jié)點(diǎn)集合中的節(jié)點(diǎn)之間的連接關(guān)系確定路徑集合，所述路徑集合中包含所有的由節(jié)點(diǎn)集合中的節(jié)點(diǎn)所構(gòu)成的以第一節(jié)點(diǎn)為起始節(jié)點(diǎn)、第二節(jié)點(diǎn)為終止節(jié)點(diǎn)的路徑；

對(duì)于路徑集合中的每條路徑，若確定該路徑的中轉(zhuǎn)節(jié)點(diǎn)不滿(mǎn)足所述快捷貨物所需的中轉(zhuǎn)時(shí)間要求，則將該路徑從路徑集合中刪除；

在將所有的不滿(mǎn)足中轉(zhuǎn)時(shí)間要求的路徑從路徑集合中刪除后，確定路徑集合中的每個(gè)路徑的全程運(yùn)輸時(shí)間，從中選擇全程運(yùn)輸時(shí)間最短的路徑作為所述備選路徑。

3.如權(quán)利要求1所述的方法，其特征在于，所述設(shè)定條數(shù)為一條，所述根據(jù)所述節(jié)點(diǎn)集合中的節(jié)點(diǎn)確定設(shè)定條數(shù)的備選路徑，具體包括以下步驟：

A1、令k＝1，集合S_k＝{s}，其中，s為所述第一節(jié)點(diǎn)；

A2、根據(jù)集合S_k確定集合S_k+1具體為：

若k＝1，則對(duì)于每個(gè)與起始節(jié)點(diǎn)s具有連接關(guān)系、且不屬于S_k的節(jié)點(diǎn)v_r，如果T{v_r}＞P{s}+w_sr，則令T{v_r}＝P{s}+w_sr、λ(v_r)＝s；其中，w_sr為節(jié)點(diǎn)s到節(jié)點(diǎn)v_r之間的運(yùn)輸時(shí)間；記屬于集合S，但不屬于集合S_k的節(jié)點(diǎn)為v_q，設(shè)集合R包含節(jié)點(diǎn)v_q；確定集合R中的各節(jié)點(diǎn)的T值中的最小值T{v′}，其中，v_q為不屬于集合S_k的節(jié)點(diǎn)，若T{v′}＜+∞，將該最小值T{v′}所對(duì)應(yīng)的節(jié)點(diǎn)v′以及S_k中的節(jié)點(diǎn)組合為集合S_k+1，并令P{v′}＝T{v′}，所述節(jié)點(diǎn)v_r的T值為T(mén){v_r}，表示從起始節(jié)點(diǎn)到節(jié)點(diǎn)v_r的最短時(shí)間上界，所述P{v′}為節(jié)點(diǎn)v_r的P值，表示從起始節(jié)點(diǎn)到節(jié)點(diǎn)v′的最短時(shí)間，所述λ(v_r)表示從起始節(jié)點(diǎn)到節(jié)點(diǎn)v_r的最短路徑上，與節(jié)點(diǎn)v_r具有連接關(guān)系的在前節(jié)點(diǎn)；

若k＞1，假設(shè)v_j滿(mǎn)足條件：v_j∈S_k；則對(duì)于每個(gè)與v_j具有連接關(guān)系、且不屬于S_k的節(jié)點(diǎn)v_u，如果在由節(jié)點(diǎn)v_g、v_j、v_u所構(gòu)成的路徑上，節(jié)點(diǎn)v_j滿(mǎn)足所述快捷貨物所需的中轉(zhuǎn)時(shí)間要求、并且T{v_u}＞P{v_j}+w_ju，則令T{v_u}＝P{v_j}+w_ju，λ(v_u)＝v_j；其中，w_ju為節(jié)點(diǎn)v_j到節(jié)點(diǎn)v_u之間的運(yùn)輸時(shí)間；記屬于集合S，但不屬于集合S_k的節(jié)點(diǎn)為v_x，設(shè)集合R′包含節(jié)點(diǎn)v_x；確定集合R中的各節(jié)點(diǎn)的T值中的最小值T{v″}，其中，v_x為不屬于集合S_k的節(jié)點(diǎn)，如果確定的T{v″}＜+∞，將該最小值T{v″}所對(duì)應(yīng)的節(jié)點(diǎn)v″以及S_k中的節(jié)點(diǎn)組合為集合S_k+1，并令P{v″}＝T{v″}；

A3、令k＝k+1；

A4、判斷節(jié)點(diǎn)v″′是否為所述第二節(jié)點(diǎn)；如果不是，跳轉(zhuǎn)到A2；如果是，根據(jù)以下步驟B1～B4，確定所述備選路徑；其中，v″′∈S_k，

B1、令v_p為終止節(jié)點(diǎn)t；

B2、令v_q＝λ(v_p)；則確定v_q為滿(mǎn)足貨物A的中轉(zhuǎn)要求的運(yùn)輸時(shí)間最短的路徑中的一個(gè)節(jié)點(diǎn)；若v_q為起始節(jié)點(diǎn)s，則跳轉(zhuǎn)到步驟B4；否則，執(zhí)行步驟B3；

B3、令v_p＝v_q；跳轉(zhuǎn)到步驟B2；

B4、結(jié)束。