[發(fā)明專利]一種基于路網(wǎng)可達(dá)性的車輛路徑優(yōu)化方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201910805004.X
• 申請(qǐng)日: 2019-08-29
• 公開（公告）號(hào): CN110689165A
• 公開（公告）日: 2020-01-14
• 發(fā)明（設(shè)計(jì)）人: 張貴軍;陳馳;劉俊;武楚雄;李亭;周曉根
• 申請(qǐng)（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06N3/12
• 代理公司: 33241 杭州斯可睿專利事務(wù)所有限公司
• 代理人: 王利強(qiáng)

1.一種基于路網(wǎng)可達(dá)性的車輛路徑優(yōu)化方法，其特征在于，所述車輛路徑優(yōu)化方法包括以下步驟：

1)以所有配送車輛的總路程最短為目標(biāo)建立如下目標(biāo)函數(shù)：其中K為配送車輛數(shù)量，V為配送中心和所有客戶點(diǎn)的集合，i,j表示集合V中的元素，x_ijk為決策變量，取值為0和1，即當(dāng)?shù)趉輛車從客戶點(diǎn)i到客戶點(diǎn)j時(shí)取值為1，否則為0，d_ij為客戶點(diǎn)i到客戶點(diǎn)j之間的真實(shí)道路距離；約束條件為：只有一個(gè)配送中心，且其所有的配送車輛均以配送中心為起點(diǎn)和終點(diǎn)，每個(gè)客戶點(diǎn)的需求量已知且均小于車輛的最大承載量Q，每輛車可以配送多個(gè)客戶點(diǎn)，但是每個(gè)客戶點(diǎn)只能由單個(gè)車輛配送；

2)設(shè)置參數(shù)：客戶點(diǎn)數(shù)目N，車輛最大載重量Q，客戶點(diǎn)的需求量列表T，交叉概率PC，變異概率PM，種群規(guī)模NP，迭代次數(shù)G；

3)通過ArcGIS Pro加載目標(biāo)區(qū)域的地理信息地圖，根據(jù)真實(shí)道路創(chuàng)建對(duì)應(yīng)的道路線圖層，并完成目標(biāo)區(qū)域的路網(wǎng)矢量化以及地理配準(zhǔn)操作；

4)基于創(chuàng)建的道路線圖層來構(gòu)建目標(biāo)區(qū)域的網(wǎng)絡(luò)數(shù)據(jù)集，在網(wǎng)絡(luò)數(shù)據(jù)中新建點(diǎn)特征圖層來表征配送中心和客戶點(diǎn)地理位置；

5)創(chuàng)建“起始點(diǎn)-目的地”距離成本分析矩陣D，獲取配送中心以及客戶點(diǎn)之間基于路網(wǎng)可達(dá)性的真實(shí)道路距離，其中如d₀₁表示配送中心0到客戶點(diǎn)1之間的真實(shí)道路距離，d₂₅表示客戶點(diǎn)2到客戶點(diǎn)5之間的真實(shí)道路距離；

6)確定所需的配送車輛數(shù)量K＝[∑q_i/(αQ)]，其中q_i表示第i個(gè)客戶點(diǎn)的貨物需求量，α為[0,1]的隨機(jī)約束因子，[]表示向下取整；

7)編碼：采用自然數(shù)的編碼方式；

8)種群初始化，過程如下：

8.1)首先將按自然數(shù)編碼的所有客戶點(diǎn)隨機(jī)排成一列；

8.2)q_i表示第i個(gè)客戶點(diǎn)的貨物需求量，如果滿足且則在染色體第a位后面插入0，隨后開始重復(fù)計(jì)算直至插入K-1個(gè)0，形成K條車輛路徑；

8.3)在染色體首位和最后一位分別插入一個(gè)0，最終形成一條初始染色體；

8.4)迭代步驟8.1至步驟8.3)，生成NP條染色體構(gòu)成的初始種群；

9)交叉操作，過程如下：

9.1)從種群中隨機(jī)不重復(fù)選取兩個(gè)染色體作為父代染色體，記為chrom1和chrom2，產(chǎn)生一個(gè)在[0,1]區(qū)間的隨機(jī)數(shù)r′，若r′＜PC，進(jìn)行下面的交叉操作，否則直接保留這兩條染色體至下一代；

9.2)分別從父代染色體chrom1和chrom2中隨機(jī)選取其中一輛車的路徑記為L(zhǎng)1和L2；

9.3)將L1作為子代染色體chrom1′的一部分并放置于首部，同時(shí)將父代染色體chrom2中不包括子徑路徑L1的客戶點(diǎn)編碼，順序添加到子路徑L1的后面，并在尾部添加編碼0，同理，對(duì)L2進(jìn)行相同的操作后，得到chrom1′和chrom2′；

9.4)在子代染色體chrom1′中的第二編碼0和尾部編碼0之間的片段中，隨機(jī)插入K-2個(gè)0后，形成子代染色體chrom1″，同理可以生成子代染色體chrom2″；

9.4)染色體合法性檢驗(yàn)：計(jì)算子代染色體chrom1″和chrom2″中每輛車路徑包含客戶點(diǎn)的需求量總和，若需求量綜合超過車輛載重量Q，則轉(zhuǎn)至步驟9.3)，重新執(zhí)行插0操作；

9.5)迭代步驟9.1)至9.4)，直至遍歷完所有染色體；

10)變異操作：產(chǎn)生一個(gè)在[0,1]區(qū)間的隨機(jī)數(shù)r″；若r″＜PM，隨機(jī)選擇染色體中的兩個(gè)客戶點(diǎn)編碼，進(jìn)行位置互換，再檢查該染色體的合法性，即每條線路的需求量不能超過車輛的載重，若不合法，重新隨機(jī)選擇兩個(gè)客戶進(jìn)行編碼互換；若r″≤PM，直接保留當(dāng)前染色體至下一代；

11)選擇操作，過程如下：

11.1)將父代種群和子代種群組成一個(gè)大小為2NP的種群；

11.2)計(jì)算種群中各個(gè)染色體的適應(yīng)度fit(i)＝1/z，z為目標(biāo)函數(shù)；

11.3)計(jì)算種群中所有染色體的適應(yīng)度之和sumFit＝∑fit(i),i＝1,2,…,2NP；

11.4)計(jì)算當(dāng)前種群中各個(gè)染色體的選擇概率p(i)＝fit(i)/sumFit和累積概率ps(i)＝∑p(i),i＝1,2,…,2NP；

11.5)產(chǎn)生一個(gè)[0,1]區(qū)域內(nèi)的隨機(jī)數(shù)r，若滿足ps(i)＞r，選擇第一條染色體進(jìn)入新種群，否則選擇使得ps(i-1)＜r＜ps(i)成立的第i條染色體進(jìn)入新種群；

11.6)重復(fù)步驟11.5)NP次，得到種群規(guī)模大小為NP新種群；

12)迭代步驟9)至步驟11)至最大迭代次數(shù)G，選擇當(dāng)前種群中適應(yīng)度最高的染色體作為最優(yōu)路徑。