[發(fā)明專利]基于集群旅行商問題的協(xié)同配送路徑優(yōu)化方法

在審

• 申請?zhí)枺?/td>: 202110390408.4
• 申請日: 2021-04-12
• 公開（公告）號: CN112862414A
• 公開（公告）日: 2021-05-28
• 發(fā)明（設(shè)計）人: 鐘萍;陳元明;杜志成;丁梓原;儲惠龍
• 申請（專利權(quán)）人: 中南大學(xué)
• 主分類號: G06Q10/08
• 分類號: G06Q10/08
• 代理公司: 長沙永星專利商標(biāo)事務(wù)所(普通合伙) 43001
• 代理人: 周詠;米中業(yè)

本發(fā)明公開了一種基于集群旅行商問題的協(xié)同配送路徑優(yōu)化方法，包括獲取待分析區(qū)域的區(qū)域參數(shù)；構(gòu)建具有覆蓋的多集群旅行商問題模型；進行分區(qū)平衡優(yōu)化；隨機構(gòu)建初始路徑；采用擾動機制對初始路徑進行優(yōu)化；對后續(xù)路徑進行再優(yōu)化；重復(fù)上述步驟到設(shè)定的條件得到最終的協(xié)同配送路徑優(yōu)化結(jié)果。本發(fā)明方法能夠有效平衡各配送員的工作量，并為他們提供最優(yōu)的路徑規(guī)劃，能夠有效的降低總配送成本，而且可靠性高，實用性好。

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

本發(fā)明屬于路徑規(guī)劃領(lǐng)域，具體涉及一種基于集群旅行商問題的協(xié)同配送路徑優(yōu)化方法。

背景技術(shù)

隨著移動互聯(lián)網(wǎng)的發(fā)展，電商平臺不斷涌現(xiàn)，網(wǎng)絡(luò)購物用戶規(guī)模持續(xù)擴大，也為人們的日常生活帶去了便利。同時，與網(wǎng)購密不可分的快遞業(yè)務(wù)也在迅猛增長?？爝f業(yè)務(wù)已經(jīng)逐漸滲透人們的日常生活，為各企業(yè)帶來了巨大的商機。最后一公里配送是指在網(wǎng)絡(luò)購物后，快遞公司將貨物從本地分揀中心交付到客戶手中，是整個快遞流程的最后一環(huán)。同時，最后一公里配送是城市智慧物流建設(shè)的重點，也是路徑優(yōu)化領(lǐng)域中很重要的研究場景。

路徑優(yōu)化問題經(jīng)常被轉(zhuǎn)換為求解旅行商問題(Traveling Salesman Problem，TSP)或其變體問題。其中，集群旅行商問題(Cluster Traveling Salesman Problem，CTSP)經(jīng)常被用來求解區(qū)域化的最后一公里配送優(yōu)化問題。Baniasadi P等人的研究中，其考慮了求解廣義的CTSP問題：主要思想是將廣義CTSP問題轉(zhuǎn)化為普通的TSP模型，在此基礎(chǔ)上采用啟發(fā)式算法進行求解；此外，文中還介紹了所提方案在最后一公里配送中的應(yīng)用，采用送貨卡車運載無人機的形式來完成包裹運送任務(wù)，即當(dāng)送貨卡車從一個客戶轉(zhuǎn)移到為另一客戶提供服務(wù)時，無人機會從卡車上取走包裹并為更多的近距離客戶提供服務(wù)，同時每架無人機在相應(yīng)的交付后返回卡車。在這種配送模式下，可以有效降低卡車的行駛時間，并能達到優(yōu)化無人機空載率的目的。然而，由于無人機配送包裹的局限性，這種模式所服務(wù)的客戶數(shù)量十分有限。此外，該模式忽略了現(xiàn)實生活中自提點的資源，導(dǎo)致整個配送過程與實際場景偏離。Phuong H N等人的研究，重點在于求解帶優(yōu)先級的CTSP：文中將各個客戶按照緊急程度設(shè)立優(yōu)先級，并根據(jù)優(yōu)先級對客戶節(jié)點分類。然而，嚴(yán)格的優(yōu)先級制度不但會造成的總配送成本增加，還會限制解空間，從而影響最優(yōu)解的求取。針對這一問題，Phuong H N等人為優(yōu)先級排序設(shè)立了d松弛機制，規(guī)定當(dāng)兩客戶節(jié)點優(yōu)先級差值大于d時，才會按照嚴(yán)格的順序被服務(wù)。實驗結(jié)果證明，最終獲得的路徑與TSP問題求解方案相近。

但是現(xiàn)存的研究中，依舊存在以下問題：(1)忽視已有的自提點資源，導(dǎo)致所建立的模型與實際配送場景存在偏差；(2)只針對一條配送路線，無法提供有效的大區(qū)域協(xié)同配送方案。這些問題導(dǎo)致已有方案很難運用到實際配送場景中，實用性較差。

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

本發(fā)明的目的在于提供一種貼合實際配送場景，而且可靠性高，實用性好的基于集群旅行商問題的協(xié)同配送路徑優(yōu)化方法。

本發(fā)明提供的這種基于集群旅行商問題的協(xié)同配送路徑優(yōu)化方法，包括如下步驟：

S1.獲取待分析區(qū)域的區(qū)域參數(shù)；

S2.根據(jù)步驟S1獲取的區(qū)域參數(shù)，構(gòu)建具有覆蓋的多集群旅行商問題模型；

S3.根據(jù)區(qū)域內(nèi)的總配送請求，進行分區(qū)平衡優(yōu)化；

S4.隨機構(gòu)建初始路徑；

S5.采用擾動機制對步驟S4的初始路徑進行優(yōu)化；

S6.對后續(xù)路徑進行再優(yōu)化；

S7.重復(fù)步驟S5和S6直至達到設(shè)定的條件，得到最終的協(xié)同配送路徑優(yōu)化結(jié)果。

步驟S2所述的構(gòu)建具有覆蓋的多集群旅行商問題模型，具體為以配送員個數(shù)，客戶遍歷次數(shù)，自提點遍歷次數(shù)，路徑連續(xù)性，子行程約束，自提點容量限制以及自提點服務(wù)范圍為限制條件，以最小化配送成本為目標(biāo)，構(gòu)建目標(biāo)函數(shù)：