[發(fā)明專利]城市物流中兩階段選址-路線問題的優(yōu)化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010045042.2
• 申請(qǐng)日: 2020-01-16
• 公開（公告）號(hào): CN111275379B
• 公開（公告）日: 2020-11-03
• 發(fā)明（設(shè)計(jì)）人: 湯希峰;吳建濤;楊帥
• 申請(qǐng)（專利權(quán)）人: 河海大學(xué)
• 主分類號(hào): G06Q10/08
• 分類號(hào): G06Q10/08;G06Q10/06;G06Q10/04
• 代理公司: 南京蘇高專利商標(biāo)事務(wù)所(普通合伙) 32204
• 代理人: 徐紅梅

1.城市物流中兩階段選址-路線問題優(yōu)化方法，其特征在于，包括以下步驟：

(1)根據(jù)兩階段選址-路線問題的結(jié)構(gòu)特征，將其拆分成相對(duì)獨(dú)立的兩個(gè)層次和相互聯(lián)系且易于解決的四個(gè)子問題；

(2)針對(duì)小規(guī)模兩階段選址-路線問題，將第一層次的轉(zhuǎn)運(yùn)中心選址和客戶分配兩個(gè)子問題單獨(dú)考慮、分別處理；具體為：

(21)轉(zhuǎn)運(yùn)中心選址：

首先賦予每個(gè)備選轉(zhuǎn)運(yùn)中心一個(gè)初始的信息素濃度，然后安排第一組由若干螞蟻組成的蟻群負(fù)責(zé)選址，每只螞蟻選擇轉(zhuǎn)運(yùn)中心的個(gè)數(shù)是在考慮客戶貨運(yùn)總需求與備選轉(zhuǎn)運(yùn)中心平均服務(wù)能力基礎(chǔ)上隨機(jī)產(chǎn)生，相應(yīng)個(gè)數(shù)的轉(zhuǎn)運(yùn)中心在考慮其信息素濃度和啟發(fā)式信息的基礎(chǔ)上按照偽比例選擇的規(guī)則進(jìn)行選擇；

(22)客戶分配：

首先賦予客戶到所有選定轉(zhuǎn)運(yùn)中心之間的每條路線一個(gè)初始的信息素濃度，然后再安排第二組由若干螞蟻組成的蟻群負(fù)責(zé)分配，客戶分配在考慮客戶與轉(zhuǎn)運(yùn)中心連接路線上的信息素濃度和路線長(zhǎng)度的基礎(chǔ)上同樣按照偽比例選擇的規(guī)則進(jìn)行選擇，每個(gè)選址方案對(duì)應(yīng)一個(gè)客戶分配方案；

(23)第一階段車輛路線安排：

在給定轉(zhuǎn)運(yùn)中心選址方案和客戶分配方案的情況下，每個(gè)轉(zhuǎn)運(yùn)中心的貨運(yùn)需求變?yōu)橐阎?，即等于其服?wù)的所有客戶的貨運(yùn)需求之和；第一階段的車輛路線問題就轉(zhuǎn)化為經(jīng)典的具有能力約束的單配送中心車輛路線問題，采用經(jīng)典的蟻群算法進(jìn)行路線構(gòu)建，首先賦予配送中心與轉(zhuǎn)運(yùn)中心之間以及轉(zhuǎn)運(yùn)中心與轉(zhuǎn)運(yùn)中心之間每條路線一個(gè)初始的信息素濃度，然后安排第三組蟻群負(fù)責(zé)路線構(gòu)建；下一個(gè)節(jié)點(diǎn)在考慮當(dāng)前節(jié)點(diǎn)與下一節(jié)點(diǎn)之間路線上的信息素濃度與啟發(fā)式信息的基礎(chǔ)上進(jìn)行選擇；考慮到車輛的裝載容量限制，每當(dāng)螞蟻服務(wù)的節(jié)點(diǎn)需求達(dá)到車輛的裝載容量時(shí)返回配送中心，然后重新出發(fā)構(gòu)建路線，如此重復(fù)，直至服務(wù)完所有轉(zhuǎn)運(yùn)中心；每只螞蟻構(gòu)建一個(gè)可行的車輛路線安排方案，相應(yīng)地對(duì)經(jīng)過路線上的信息素濃度做局部更新處理以擴(kuò)大隨后螞蟻的搜索范圍；當(dāng)蟻群中每只螞蟻都完成一個(gè)路線安排方案后，從已有路線安排方案中選擇一個(gè)費(fèi)用最低的作為當(dāng)前最優(yōu)方案，然后對(duì)當(dāng)前最優(yōu)方案中的每條路線的信息素濃度再進(jìn)行全局更新處理以保證后面的每次迭代都是對(duì)當(dāng)前最優(yōu)方案的改進(jìn)；

(24)第二階段車輛路線安排：

在給定轉(zhuǎn)運(yùn)中心選址方案和客戶分配方案的情況下，第二階段的車輛路線問題由一個(gè)具有能力約束的多配送中心車輛路線問題拆分成若干個(gè)具有能力約束的單配送中心車輛路線問題，然后安排第四組由若干螞蟻組成的蟻群采用與步驟(23)相同的方法構(gòu)建車輛路線；考慮到客戶數(shù)量遠(yuǎn)多于轉(zhuǎn)運(yùn)中心的數(shù)量，需要對(duì)每組蟻群生成的最優(yōu)方案采用一些局部搜索算法進(jìn)行改進(jìn)，再?gòu)囊延新肪€安排方案中選擇一個(gè)最優(yōu)的作為當(dāng)前最優(yōu)方案再對(duì)其進(jìn)行相應(yīng)的信息素全局更新處理；

(25)步驟(21)至步驟(24)中，每當(dāng)?shù)谝唤M蟻群中的一只螞蟻生成一個(gè)轉(zhuǎn)運(yùn)中心選址方案，第二組蟻群就相應(yīng)地生成一個(gè)客戶分配方案，第三個(gè)蟻群就會(huì)生成一個(gè)第一階段車輛路線安排方案，第四個(gè)蟻群就會(huì)生成一個(gè)第二階段車輛路線安排方案，這樣就得到一個(gè)轉(zhuǎn)運(yùn)中心選址和兩個(gè)階段車輛路線安排的整體解決方案；首先對(duì)其中轉(zhuǎn)運(yùn)中心選址方案中所選轉(zhuǎn)運(yùn)中心以及客戶分配方案中客戶與轉(zhuǎn)運(yùn)中連接路線上的信息素濃度進(jìn)行局部更新處理，然后對(duì)蟻群中每只螞蟻提供的整體解決方案進(jìn)行比較，將費(fèi)用最小的作為該組蟻群產(chǎn)生的最優(yōu)整體解決方案，并對(duì)該整體解決方案中的第二階段車輛路線安排方案采用局部搜索算法進(jìn)行進(jìn)一步改進(jìn)；最后從已有的整體解決方案中選擇一個(gè)費(fèi)用最小的作為當(dāng)前最優(yōu)整體解決方案，再對(duì)其轉(zhuǎn)運(yùn)中心選址方案中所選轉(zhuǎn)運(yùn)中心以及客戶分配方案中客戶與轉(zhuǎn)運(yùn)中連接路線上的信息素濃度進(jìn)行全局更新處理；如此，通過若干次迭代后，即得到最終的最優(yōu)整體解決方案；

(3)針對(duì)大規(guī)模兩階段選址-路線問題，將第一層次的轉(zhuǎn)運(yùn)中心選址和客戶分配兩個(gè)子問題一并考慮、整體優(yōu)化。

2.根據(jù)權(quán)利要求1所述的城市物流中兩階段選址-路線問題優(yōu)化方法，其特征在于，步驟(1)中第一層次包括轉(zhuǎn)運(yùn)中心選址和客戶分配兩個(gè)子問題，第二個(gè)層次包括第一階段車輛路線安排和第二階段路線安排兩個(gè)子問題。