[發(fā)明專利]求解單車場(chǎng)時(shí)變關(guān)聯(lián)物流運(yùn)輸車輛路徑問題的算法

在審

• 申請(qǐng)?zhí)枺?/td>: 201410291092.3
• 申請(qǐng)日: 2014-06-26
• 公開（公告）號(hào): CN104036333A
• 公開（公告）日: 2014-09-10
• 發(fā)明（設(shè)計(jì)）人: 蔡延光;郭帥;蔡顥;湯雅蓮
• 申請(qǐng)（專利權(quán)）人: 廣東工業(yè)大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q10/08;G06Q50/28
• 代理公司: 廣州市南鋒專利事務(wù)所有限公司 44228
• 代理人: 劉媖

技術(shù)領(lǐng)域

本發(fā)明屬于工程技術(shù)領(lǐng)域，涉及一種單車場(chǎng)時(shí)變關(guān)聯(lián)物流運(yùn)輸車輛路徑問題的混沌禁忌搜索算。

背景技術(shù)

配送是物流系統(tǒng)的核心環(huán)節(jié)，是伴隨著市場(chǎng)而誕生的一種必然的市場(chǎng)行為，隨著市場(chǎng)競(jìng)爭(zhēng)的日益激烈以及客戶要求的不斷提高，配送在未來的市場(chǎng)競(jìng)爭(zhēng)中將起到舉足輕重的作用。在配送業(yè)務(wù)中，配送車輛優(yōu)化調(diào)度問題的涉及面較廣，需要考慮的因素也很多，對(duì)配送企業(yè)提高服務(wù)質(zhì)量、降低經(jīng)營(yíng)成本、增加經(jīng)濟(jì)效益的影響也很大。國(guó)內(nèi)外學(xué)者著力于研究車輛路徑問題，主要因?yàn)樗俏锪髋渌秃徒煌ㄟ\(yùn)輸?shù)暮诵膯栴}，只有解決了調(diào)度問題才能使配送有效合理。

目前，國(guó)內(nèi)車輛路徑問題的研究主要使用的方法主要有以下幾個(gè)問題：所有車輛貨物的裝載沒有考慮貨物之間的具有的關(guān)聯(lián)約束。

因此，現(xiàn)有的物流配送方法存在缺陷，需要改進(jìn)。

單車場(chǎng)時(shí)變關(guān)聯(lián)物流運(yùn)輸車輛路徑問題同時(shí)考慮具有速度時(shí)變情況，以及貨物性質(zhì)關(guān)聯(lián)約束的情況，以懲罰成本的形式將貨物關(guān)聯(lián)加入目標(biāo)函數(shù)中。單車場(chǎng)時(shí)變關(guān)聯(lián)物流運(yùn)輸車輛路徑問題是車輛路徑的一個(gè)擴(kuò)展，車輛路徑問題已經(jīng)是一個(gè)NP-完全難題，再加入速度時(shí)變、貨物關(guān)聯(lián)，則該問題也是一個(gè)NP-Hard?問題，這意味著在問題規(guī)模增大到一定數(shù)量時(shí)將很難或者根本無法求得問題的全局最優(yōu)解。采用精確算法雖然可以對(duì)小規(guī)模的單車場(chǎng)時(shí)變關(guān)聯(lián)物流運(yùn)輸車輛路徑問題得到最優(yōu)解，但卻不適用于求解現(xiàn)實(shí)中的大規(guī)模的單車場(chǎng)時(shí)變關(guān)聯(lián)物流運(yùn)輸車輛路徑問題。有些學(xué)者運(yùn)用序列插入啟發(fā)式算法求解過單車場(chǎng)車輛路徑問題，但對(duì)于有多重約束的單車場(chǎng)時(shí)變關(guān)聯(lián)物流運(yùn)輸調(diào)度問題難以適用。

發(fā)明內(nèi)容

本發(fā)明的目的在于針對(duì)上述已有技術(shù)的不足，提出了一種求解單車場(chǎng)時(shí)變關(guān)聯(lián)物流運(yùn)輸車輛路徑問題的算法，該算法采用混沌禁忌搜索算法，以對(duì)具有多重約束的車輛路徑問題進(jìn)行求解。

本發(fā)的單車場(chǎng)時(shí)變關(guān)聯(lián)物流運(yùn)輸車輛路徑問題的方法包括兩部分的內(nèi)容，（1）建立單車場(chǎng)時(shí)變關(guān)聯(lián)物流運(yùn)輸車輛路徑問題的數(shù)學(xué)模型，以總的運(yùn)輸成本最低為目標(biāo)函數(shù)，將貨物間的關(guān)聯(lián)以關(guān)聯(lián)懲罰成本的形式加入到目標(biāo)函數(shù)當(dāng)中去，在考慮最大載重約束和最大距離約束的同時(shí)考慮速度時(shí)變的影響，（2）針對(duì)標(biāo)準(zhǔn)禁忌搜索算法尋優(yōu)依賴初始解以及鄰域解的問題，使用混沌優(yōu)化技術(shù)生成初始解，使用多種方式生成鄰域解，改善算法的尋優(yōu)能力。其主要步驟如下：

求解單車場(chǎng)時(shí)變關(guān)聯(lián)物流運(yùn)輸車輛路徑問題的算法,該算法采用混沌禁忌搜索算法，它包括以下步驟：

1）考慮速度時(shí)變的影響，將貨物關(guān)聯(lián)性質(zhì)以關(guān)聯(lián)成本的形式加入到目標(biāo)函數(shù)當(dāng)中去，建立數(shù)學(xué)模型：

步驟1）考慮速度時(shí)變的影響，將貨物關(guān)聯(lián)性質(zhì)以關(guān)聯(lián)成本的形式加入到目標(biāo)函數(shù)當(dāng)中去，建立數(shù)學(xué)模型，具體步驟如下：

步驟1.1：車場(chǎng)有????????????????????????????????????????????????名要服務(wù)的客戶，其中第個(gè)客戶的貨運(yùn)量為（=1，2，…，），需要將貨物從車場(chǎng)配送給客戶，車輛的最大載重量已知為，已知<，我們提前對(duì)需要調(diào)用的車輛數(shù)按照公式（1）進(jìn)行估計(jì)：

???????????????????????????????????????????????????（1）

其中，[?]代表不大于括號(hào)內(nèi)的數(shù)字的最大正整數(shù)；是對(duì)裝車和卸車的困難程度以及約束的估計(jì)，；

步驟1.2：?定義如下變量：

???????????????????????????????????????????（2）

?????????????????????????????????????（3）

建立目標(biāo)函數(shù)：

+，以最小配送費(fèi)為目標(biāo)，用表示從客戶到客戶的運(yùn)輸成本，=，考慮速度時(shí)變因素，關(guān)聯(lián)成本，第一項(xiàng)為運(yùn)輸成本，第二項(xiàng)為關(guān)聯(lián)成本，表示裝載在第臺(tái)車上的貨物間的關(guān)聯(lián)系數(shù)，其值越大，則表示貨物之間的兼容性就越好，貨物不兼容所產(chǎn)生的費(fèi)用就越低，越小，則表示貨物之間的兼容性就越差，貨物不兼容所產(chǎn)生的費(fèi)用就越高，第三項(xiàng)為車輛固定使用成本，為單臺(tái)車固定使用成本；

步驟1.3：建立不等式約束：

???????????????????????????????????????（4）

????????????????????????????（5）

?????????????????????????????（6）

?????????????????????????????????（7）