[發(fā)明專利]一種基于大規(guī)模多中心問(wèn)題的路徑規(guī)劃方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202011102500.8
• 申請(qǐng)日: 2020-10-15
• 公開(kāi)（公告）號(hào): CN112067011A
• 公開(kāi)（公告）日: 2020-12-11
• 發(fā)明（設(shè)計(jì)）人: 張玉州;張海奇;張子為;梅一;陶朗
• 申請(qǐng)（專利權(quán)）人: 安慶師范大學(xué)
• 主分類號(hào): G01C21/34
• 分類號(hào): G01C21/34;G06Q10/04
• 代理公司: 溫州市品創(chuàng)專利商標(biāo)代理事務(wù)所(普通合伙) 33247
• 代理人: 洪中清

本發(fā)明提供了一種基于大規(guī)模多中心問(wèn)題的路徑規(guī)劃方法，首先對(duì)車輛服務(wù)對(duì)象，即街道，采用三標(biāo)準(zhǔn)問(wèn)題分解方法進(jìn)行分割，獲得分割結(jié)果；然后利用上述分割結(jié)果，對(duì)服務(wù)車輛的路徑進(jìn)行規(guī)劃以求得可行解；利用上述可行解得到所述三標(biāo)準(zhǔn)問(wèn)題分解方法對(duì)應(yīng)的服務(wù)路線。本發(fā)明通過(guò)將路徑規(guī)劃分割成若干個(gè)相對(duì)獨(dú)立的子問(wèn)題，然后分別對(duì)各子問(wèn)題求解，最后將各子問(wèn)題的解決方案匯總，從而得到整個(gè)問(wèn)題的解決方法，最終獲取良好的車輛路徑安排，能夠獲得好高的路徑規(guī)劃的滿意度，使得服務(wù)的總費(fèi)用得到更好的控制，具有較好的應(yīng)用前景。

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

本發(fā)明涉及路徑規(guī)劃領(lǐng)域，特別涉及一種基于大規(guī)模多中心問(wèn)題的路徑規(guī)劃方法，屬于智能優(yōu)化的實(shí)際應(yīng)用領(lǐng)域。

背景技術(shù)

容量受限的弧路由問(wèn)題(Capacitated Arc Routing Problem，CARP)是一類經(jīng)典而復(fù)雜的組合優(yōu)化問(wèn)題，其有著廣泛的應(yīng)用背景，如冬季路面除雪、路面撒鹽、郵遞、垃圾清掃等問(wèn)題；CARP的目標(biāo)就是為駐扎在駐車中心的一隊(duì)車輛尋找最優(yōu)路徑，使得所有需要服務(wù)的邊(路面)均被服務(wù)，且車輛的總耗費(fèi)最小化，并且行車過(guò)程中存在一定的約束，同時(shí)總耗費(fèi)包括行車費(fèi)用以及服務(wù)費(fèi)用等。

服務(wù)中存在一定條件的約束：(1)車輛由站點(diǎn)出發(fā)，最后回歸站點(diǎn)；(2)每輛車均有一定的車載容量限制；(3)一條道路通常只能被一輛車服務(wù)；由于各道路上的服務(wù)量存在差異，且道路分布情況往往較復(fù)雜，所以冬季路面除雪、路面撒鹽、郵遞、垃圾清掃等問(wèn)題是一種復(fù)雜的車輛路徑規(guī)劃問(wèn)題，其可歸屬于經(jīng)典的容量受限的弧路由問(wèn)題。

針對(duì)上述問(wèn)題模型，已經(jīng)存在大量的解決方案；然而，在現(xiàn)實(shí)生活中的一些問(wèn)題，基本CARP難以應(yīng)對(duì)，如對(duì)于較大區(qū)域內(nèi)的垃圾清掃問(wèn)題，往往存在多個(gè)駐車點(diǎn)或回收中心，而基本CARP則只涉及一個(gè)中心點(diǎn)；所以，針對(duì)具體問(wèn)題，我們需要對(duì)CARP模型進(jìn)行擴(kuò)展。

關(guān)于多中心點(diǎn)的容量受限的弧路由問(wèn)題(MDCARP)，已有學(xué)者提出了解決方案，如Kansou和Zhu等提出的MDMA以及HGA等；然而這些方法只關(guān)注較小規(guī)模的問(wèn)題，忽略對(duì)大規(guī)模問(wèn)題的考慮；現(xiàn)實(shí)中的MDCARP的應(yīng)用背景往往涉及的面積很廣，如垃圾清掃問(wèn)題，一個(gè)城市總需要服務(wù)路面或街道數(shù)很多，分布區(qū)已很廣；此時(shí)，已有方法則難以適應(yīng)了。大規(guī)模、多中心點(diǎn)的容量受限的弧路由問(wèn)題(Large Scale MDCARP，LSMDCARP)的難點(diǎn)是需要服務(wù)的路面或街道歸屬處理，同時(shí)由于問(wèn)題規(guī)模的上升，問(wèn)題解空間呈爆炸式增長(zhǎng)。所以，使用較早的方法應(yīng)對(duì)大面積垃圾清掃問(wèn)題的車輛路徑規(guī)劃，往往會(huì)出現(xiàn)的問(wèn)題有：(1)路徑規(guī)劃的滿意度下降，即總費(fèi)用沒(méi)有得到有效降低；(2)規(guī)劃過(guò)程中，消耗的時(shí)間會(huì)很長(zhǎng)。

現(xiàn)有技術(shù)中提出了一種迭代式結(jié)構(gòu)的車輛路徑規(guī)劃方法，但是現(xiàn)有技術(shù)的此種迭代式結(jié)構(gòu)在當(dāng)前代結(jié)束時(shí)，利用所得的最優(yōu)路徑進(jìn)行下一循環(huán)的問(wèn)題分解，分解的單位是路徑；然而，一條路徑包含的信息較復(fù)雜，任何兩個(gè)任務(wù)間的連接可能較好，也可能較差，無(wú)法確保獲得路徑任務(wù)的良好連接，這樣依然存在上述路徑規(guī)劃的滿意度下降，總費(fèi)用無(wú)法獲得更好的控制。

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

針對(duì)上述動(dòng)態(tài)車輛路徑優(yōu)化方法中存在的問(wèn)題，本發(fā)明公布了一種基于大規(guī)模多中心問(wèn)題的路徑規(guī)劃方法，通過(guò)將路徑規(guī)劃分割成若干個(gè)相對(duì)獨(dú)立的子問(wèn)題，然后分別對(duì)各子問(wèn)題求解，最后將各子問(wèn)題的解決方案匯總，從而得到整個(gè)問(wèn)題的解決方法，最終獲取良好的車輛路徑安排，能夠獲得好高的路徑規(guī)劃的滿意度，使得服務(wù)的總費(fèi)用得到更好的控制。

本發(fā)明提供的一種基于大規(guī)模多中心問(wèn)題的路徑規(guī)劃方法，該方法包括如下步驟：

服務(wù)車輛接收服務(wù)任務(wù)信息；其中，所述服務(wù)任務(wù)信息中包括服務(wù)區(qū)域地圖信息和服務(wù)規(guī)劃路徑信息；

獲取服務(wù)的約束條件信息；

根據(jù)未服務(wù)區(qū)域信息和服務(wù)規(guī)劃路徑信息計(jì)算預(yù)計(jì)條件信息；

當(dāng)所述預(yù)計(jì)條件信息滿足所述約束條件信息時(shí)，根據(jù)所述服務(wù)規(guī)劃路徑信息繼續(xù)進(jìn)行服務(wù)作業(yè)；