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

在審

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

一種基于路網(wǎng)可達(dá)性的車(chē)輛路徑優(yōu)化方法，首先，創(chuàng)建研究區(qū)域的網(wǎng)絡(luò)數(shù)據(jù)集，獲取研究對(duì)象點(diǎn)之間的真實(shí)道路距離；然后，在滿(mǎn)足車(chē)輛載重約束的條件下，將配送中心和客戶(hù)點(diǎn)采用自然數(shù)編碼方式進(jìn)行編碼操作，并完成種群的初始化；對(duì)種群進(jìn)行交叉、變異操作后，采用輪盤(pán)賭的方式對(duì)當(dāng)前種群進(jìn)行選擇操作，篩選出適應(yīng)度較高的染色體構(gòu)成新的種群，重復(fù)交叉、變異和選擇操作，直到滿(mǎn)足迭代的終止條件；最終，輸出種群中適應(yīng)度最高的染色體，即為車(chē)輛配送的最優(yōu)路徑方案。本發(fā)明提供一種更加貼合實(shí)際應(yīng)用的基于路網(wǎng)可達(dá)性的車(chē)輛路徑優(yōu)化方法。

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

本發(fā)明涉及GIS技術(shù)、物流配送、智能計(jì)算、計(jì)算機(jī)應(yīng)用領(lǐng)域，尤其涉及的是一種基于路網(wǎng)可達(dá)性的車(chē)輛路徑優(yōu)化方法。

背景技術(shù)

隨著經(jīng)濟(jì)全球化和信息化程度的提高，我國(guó)的經(jīng)濟(jì)發(fā)展取得了豐碩的成果，許多新興行業(yè)發(fā)展生機(jī)勃勃。近年來(lái)，尤其是電子商務(wù)的高速發(fā)展，推動(dòng)了整個(gè)物流行業(yè)的巨大進(jìn)步，物流業(yè)作為聯(lián)系產(chǎn)品供應(yīng)方和需求方的關(guān)鍵環(huán)節(jié)，越來(lái)越體現(xiàn)其關(guān)鍵性作用，作為現(xiàn)代企業(yè)“第三方利潤(rùn)來(lái)源”的地位也已深入人心。同時(shí)，物流業(yè)對(duì)于社會(huì)的發(fā)展、工作效率的提高、優(yōu)化資源結(jié)構(gòu)等，都發(fā)揮著巨大的作用。在這樣的背景下，政府出臺(tái)了一系列支持促進(jìn)第三方物流發(fā)展的政策措施，來(lái)促進(jìn)整個(gè)物流行業(yè)健康穩(wěn)定的發(fā)展。物流配送在第三方物流系統(tǒng)中處于非常重要的位置，多于一半甚至更高的成本來(lái)自于配送環(huán)節(jié)。物流配送路線的合理規(guī)劃，即車(chē)輛路徑問(wèn)題，已經(jīng)引起了學(xué)術(shù)界的廣泛關(guān)注。

車(chē)輛路徑問(wèn)題，也稱(chēng)為車(chē)輛調(diào)度問(wèn)題，是運(yùn)輸組織優(yōu)化中的核心問(wèn)題之一，它通過(guò)對(duì)車(chē)輛的運(yùn)輸路線進(jìn)行優(yōu)化，在滿(mǎn)足客戶(hù)需求的前提下，盡量以最低的運(yùn)輸成本與費(fèi)用將貨物送達(dá)目的地。在實(shí)踐中，該問(wèn)題的應(yīng)用不僅僅局限于物流配送領(lǐng)域，在航空、遠(yuǎn)洋航運(yùn)、工業(yè)管理等領(lǐng)域也有一定的應(yīng)用，其研究成果已用于輪船公司運(yùn)送貨物經(jīng)過(guò)港口與貨物安排的優(yōu)化設(shè)計(jì)、交通車(chē)輛線路安排、垃圾收集線路安排和生產(chǎn)系統(tǒng)中的計(jì)劃與控制等多種組合優(yōu)化問(wèn)題。車(chē)輛路徑問(wèn)題的研究影響了物流、供應(yīng)鏈管理、企業(yè)資源計(jì)劃等多個(gè)應(yīng)用領(lǐng)域的發(fā)展，至今仍然吸引著廣大學(xué)者的關(guān)注。

目前，針對(duì)車(chē)輛路徑問(wèn)題的研究，大多數(shù)研究人員都是通過(guò)圖論簡(jiǎn)單建模的方式，將客戶(hù)點(diǎn)的位置和道路抽象成為圖論中的點(diǎn)和線，基于這種拓?fù)潢P(guān)系來(lái)進(jìn)行研究。在計(jì)算每個(gè)客戶(hù)點(diǎn)之間的距離時(shí)，是基于客戶(hù)點(diǎn)的地位置坐標(biāo)的轉(zhuǎn)換，運(yùn)用兩點(diǎn)間距離公式來(lái)開(kāi)展的。這樣的數(shù)據(jù)處理方式，完全忽略了真實(shí)道路下客戶(hù)點(diǎn)之間的路網(wǎng)可達(dá)性，兩點(diǎn)間的歐氏距離并不等同于真實(shí)道路下兩個(gè)客戶(hù)點(diǎn)之間的實(shí)際道路距離，回歸到實(shí)際應(yīng)用，精準(zhǔn)度損失較大。

因此，現(xiàn)有的車(chē)輛路徑優(yōu)化方法在真實(shí)道路下配送方案應(yīng)用研究的精準(zhǔn)性上存在缺陷，需要改進(jìn)。

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

為了解決現(xiàn)有的車(chē)輛路徑優(yōu)化方法對(duì)真實(shí)道路下的配送問(wèn)題解決方案精確度不高的缺陷，本發(fā)明提出了一種基于路網(wǎng)可達(dá)性的車(chē)輛路徑優(yōu)化方法，利用GIS技術(shù)，將配送區(qū)域的實(shí)際地理信息，進(jìn)行矢量化建模，創(chuàng)建特征網(wǎng)絡(luò)數(shù)據(jù)集，針對(duì)網(wǎng)絡(luò)數(shù)據(jù)集上的客戶(hù)點(diǎn)位置，建立“起始點(diǎn)-目的地”成本距離分析矩陣，獲取每個(gè)客戶(hù)點(diǎn)之間的實(shí)際路網(wǎng)距離，再采用改進(jìn)的遺傳算法來(lái)解決車(chē)輛路徑問(wèn)題。

本發(fā)明解決的技術(shù)問(wèn)題所采用的技術(shù)方案是：

一種基于路網(wǎng)可達(dá)性的車(chē)輛路徑優(yōu)化方法，包括以下步驟：

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

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