買專利賣專利找龍圖騰，真高效！ 查專利查商標用IPTOP,全免費！專利年費監(jiān)控用IP管家,真方便！

龍圖騰網(wǎng)恭喜北京工業(yè)大學(xué)申請的專利一種基于自適應(yīng)多約束差分進化算法的車輛路徑優(yōu)化方法獲國家發(fā)明授權(quán)專利權(quán)，本發(fā)明授權(quán)專利權(quán)由國家知識產(chǎn)權(quán)局授予，授權(quán)公告號為：CN114330810B 。

龍圖騰網(wǎng)通過國家知識產(chǎn)權(quán)局官網(wǎng)在2025-04-01發(fā)布的發(fā)明授權(quán)授權(quán)公告中獲悉：該發(fā)明授權(quán)的專利申請?zhí)?專利號為：202111237064.X，技術(shù)領(lǐng)域涉及：G06Q10/047；該發(fā)明授權(quán)一種基于自適應(yīng)多約束差分進化算法的車輛路徑優(yōu)化方法是由侯瑩;吳毅琳;張嘉成;肖福霞;韓紅桂設(shè)計研發(fā)完成，并于2021-10-24向國家知識產(chǎn)權(quán)局提交的專利申請。

本一種基于自適應(yīng)多約束差分進化算法的車輛路徑優(yōu)化方法在說明書摘要公布了：本發(fā)明針對多約束多目標車輛路徑優(yōu)化問題，設(shè)計了一種基于自適應(yīng)多約束差分進化算法的車輛路徑優(yōu)化方法，將車輛使用數(shù)目和總行駛距離作為優(yōu)化目標，采用多目標差分進化算法，自適應(yīng)調(diào)整多個進化機制，利用可行解引導(dǎo)的差分變異策略，提高解集的收斂性，設(shè)計基于約束支配準則的評估機制進行選擇操作，提高最優(yōu)解的多樣性，獲得最佳的車輛路徑優(yōu)化方案，降低了企業(yè)運輸成本，增加了物流配送效益。

本發(fā)明授權(quán)一種基于自適應(yīng)多約束差分進化算法的車輛路徑優(yōu)化方法在權(quán)利要求書中公布了：1.一種基于自適應(yīng)多約束差分進化算法的車輛路徑優(yōu)化方法，其特征在于，包括以下步驟：步驟1確定車輛路徑優(yōu)化問題的優(yōu)化目標：假設(shè)有Kmax臺同一車型的運輸車輛全部停在一個物流中心，準備向N個客戶提供單程配送服務(wù)，車輛限載為Q，物流中心開門時間L和物流中心關(guān)門時間E；每個客戶對應(yīng)一條訂單數(shù)據(jù)，包括客戶編號i、客戶位置坐標xi,yi、第i個客戶的貨物重量qi、第i個客戶的最早開始服務(wù)時間li、第i個客戶的最晚開始服務(wù)時間ei和第i個客戶的服務(wù)時長si，其中i＝0表示物流中心；0Kmax50，0N200，0Q300，0L200，0E200，i＝0,…,N，0xi100，0yi100，0qi300，0li1000，0ei1440，0si200；該車輛路徑優(yōu)化問題的優(yōu)化目標為最小化如下目標函數(shù)：f1＝K1 其中，f1為配送過程使用的車輛總數(shù)K，f2為車輛總行駛距離；0KKmax，dij為客戶i與客戶j之間的距離，xijk表示第k輛車是否從i行駛至j，xijk＝1為是，xijk＝0為否，j＝0,…,N,k＝1,…,K；每一輛車在配送過程中需滿足以下條件，每個客戶僅由一輛車完成配送服務(wù)： 每輛車從物流中心出發(fā)，按相應(yīng)的客戶服務(wù)順序完成配送任務(wù)后返回物流中心： 第k輛車的客戶總需求量應(yīng)不超過Q： 車輛到達客戶i所在位置的時間ai應(yīng)在其服務(wù)時間窗內(nèi)，并且車輛應(yīng)在物流中心關(guān)門前回到物流中心：li≤ai≤ei8L≤a0≤E9車輛經(jīng)過j到達i所在位置的時間ai為： 其中，wj為車輛等待客戶j的時間，wj≥0，t0i為從物流中心行駛至客戶i花費的時間，tji表示從客戶j行駛至客戶i花費的時間，tj0表示從客戶j行駛至物流中心花費的時間；步驟2獲取車輛路徑優(yōu)化問題的距離和時間數(shù)據(jù)：計算客戶i與客戶j之間的距離： 其中，xi和yi分別表示客戶i位置的橫坐標和縱坐標，xj和yj分別表示客戶j位置的橫坐標和縱坐標；根據(jù)車輛平均行駛速度v，計算對應(yīng)于dij的行駛時間tij： 步驟3設(shè)計自適應(yīng)多約束差分進化算法：步驟3.1參數(shù)設(shè)置及種群初始化：設(shè)定多目標差分進化算法的最大進化代數(shù)為T，T是[250,2000]范圍內(nèi)的整數(shù)，變異率為F，0≤F≤1，交叉率為Cr，0≤Cr≤1，種群規(guī)模為H，H是[10,500]范圍內(nèi)的整數(shù)，鄰域規(guī)模為c，c是[1,N]范圍內(nèi)的整數(shù)，每個解表示一個車輛調(diào)度方案，隨機產(chǎn)生初始種群P0： 其中，pb,0為初始種群的第b個解，b＝1,…,H；步驟3.2可行解數(shù)目的判斷：第t代種群Pt表示為： 其中，pb,t為第t代種群的第b個解，pbu,t為第t代種群第b個解的第u維分量；t＝0,…,T，pbu,t＝1,…,N+Kmax,u＝1,…,N+Kmax；pbu,t＝1,…,N時表示客戶，pbu,t＝N+1,…,N+Kmax時表示物流中心；在兩個物流中心之間，按照客戶開始服務(wù)的時間，對客戶順序進行升序排序，客戶開始服務(wù)的時間從數(shù)據(jù)庫中讀取，得到K條配送路線rk，k是路線編號，k＝1,…,K,K≤Kmax；計算每個解的約束違反度δ： 其中，qi為第i個客戶的貨物重量，K為路徑總數(shù)，即使用的車輛總數(shù)，Q為車輛限載，ai為第i個客戶的到達時間，此值由公式10計算得到，ei為第i個客戶的最晚開始服務(wù)時間，此值從數(shù)據(jù)庫中讀取；設(shè)定滿足δ＝0的解為可行解，δ0的解為不可行解，統(tǒng)計Pt中可行解的總數(shù)；設(shè)定Pt中所有可行解組成的集合為Ft，β表示可行解總數(shù)，是[0,H]范圍內(nèi)的整數(shù)，若β＝0，則執(zhí)行步驟3.3-3.4后，執(zhí)行步驟3.6，若β≥2，則執(zhí)行步驟3.4-3.5后，執(zhí)行步驟3.6，若β＝1，則直接執(zhí)行步驟3.5；步驟3.3基于DErand1變異策略的差分進化： 其中，vb,t為第t代種群的第b個變異解，prand1,t為第t代種群的第rand1個解，prand2,t為第t代種群的第rand2個解，rand1和rand2是在[1,H]中隨機選取的異于b的兩個互不相同的整數(shù)；pbu,t+1為第t+1代種群中第b個解的第u維分量，randbu是第b個解在第i維分量上取的隨機數(shù)，0≤randbu≤1；對pb,t+1每一維分量進行向下取整： 其中，表示pb,t+1第u維分量向下取整后的數(shù)值；若N+1≤pbu,t+1≤N+Kmax，N+1≤pbu+1,t+1≤N+Kmax，且滿足1≤pbu+2,t+1≤N，即pb,t+1存在空路線時，將pbu+1,t+1移出路線組，否則令u＝u+1，繼續(xù)檢查空路線，直至pb,t+1中的空路線全部刪除；步驟3.4適應(yīng)度值計算：計算候選解集中每一個解的支配強度：若p為可行解，q為不可行解，則p支配q，p的支配強度加1；若p和q均為可行解，f1p≤f1q，f2p≤f2q，則p支配q，p的支配強度加1；若p和q均為不可行解，δpδq，則p支配q，p的支配強度加1；其中，p和q是候選解集中兩個相異的解，f1p和f1q分別是p對應(yīng)的車輛總數(shù)和q對應(yīng)的車輛總數(shù)，f2p和f2q分別是p對應(yīng)的車輛總行駛距離和q對應(yīng)的車輛總行駛距離，δp和δq分別是p對應(yīng)的約束違反度和q對應(yīng)的約束違反度；計算Pt和Pt+1構(gòu)成的候選解集中每一個解的等級值：對于δ＝0的解，即可行解，其等級設(shè)定為1；對于δ0的解，即不可行解，根據(jù)δ大小對其進行升序排序，每一個不可行解的等級為可行解總數(shù)與其δ排序值之和；將每一個解的支配強度與等級值相加，得到每一個解的適應(yīng)度值；步驟3.5可行解引導(dǎo)的差分變異操作：①根據(jù)適應(yīng)度值對Ft進行升序排序，得到Ft＝p1,...,pβ；②計算p1和p2的相似度S： 其中，rp1,rand和rp2,rand分別表示從p1中隨機挑選的一條配送路線和從p2中隨機挑選的一條配送路線，1≤rand≤Kmax，|rp1,rand|和|rp2,rand|分別表示rp1,rand和rp2,rand的客戶數(shù)目，|rp1,rand∩rp2,rand|表示同時在rp1,rand和rp2,rand中出現(xiàn)的客戶數(shù)目，|rp1,rand∩rp2,rand|≥0；③調(diào)整Ft的順序：p2調(diào)整為pβ，并且p3,...,pβ調(diào)整為p2,...,pβ-1；④若S≤0.5，執(zhí)行步驟3.5⑤，若S0.5，返回步驟3.5②；⑤按路線編號順序選取p1的一條路線rp1,k1，k1是p1對應(yīng)的路線編號，1≤k1≤Kmax，設(shè)定c1,rp1,k1表示p1中第k1條配送路線的第一個客戶，在p2中找出c1,rp1,1所在路線rp2,k2，k2是p2對應(yīng)的路線編號，1≤k2≤Kmax，確定rp1,k1和rp2,k2的差分向量對： 其中，rp1,k1-rp1,k1∩rp2,k2表示在rp1,k1而不在rp2,k2上的配送路線補集，rp2,k2-rp1,k1∩rp2,k2表示在rp2,k1而不在rp1,k2上的配送路線補集，m和n分別表示rp1,k1-rp1,k1∩rp2,k2和rp2,k2-rp1,k1∩rp2,k2的第一個客戶；⑥令第t+1代種群的第b個解pb,t+1＝p1，在p1中找出n所在路線rp1,k3，k3是p1中異于k1的路線編號，1≤k3≤Kmax，k3≠k1，將m和n分別從rp1,k1和rp1,k3中移除：在滿足公式3-公式10的前提下，找出rp1,k3中可插入m的所有位置，使δpb,t+1＝0成立，計算所有插入位置相應(yīng)的路線增量，路線增量最小對應(yīng)的位置設(shè)定為m的插入位置，并將m插入該位置；在滿足公式3-公式10的前提下，找出rp1,k3中可插入n的所有位置，使δpb,t+1＝0成立，計算所有插入位置相應(yīng)的路線增量，路線增量最小對應(yīng)的位置設(shè)定為n的插入位置，并將n插入該位置；若不存在使δpb,t+1＝0成立的可插入位置，將m或n設(shè)定為rp1,k3或rp1,k1的第一個客戶，完成pb,t+1的構(gòu)建；⑦令k1＝k1+1，統(tǒng)計第t+1代種群規(guī)模|Pt+1|，若k1＝K1，K1是p1對應(yīng)的車輛數(shù)目，且|Pt+1|＝H，H是種群規(guī)模，則轉(zhuǎn)到步驟3.6，若k1＝K1，且|Pt+1|H，則返回步驟3.5②；若k1K1，且|Pt+1|H，則返回步驟3.5⑤；步驟3.6大規(guī)模鄰域搜索操作：在pb,w中隨機選取一維表示客戶的分量pbu,w，pbu,w＝i，w＝t或t+1，1pbu,wN，N是服務(wù)的客戶總數(shù)，根據(jù)客戶i與客戶j之間的距離dij選取與客戶i距離最近的c個客戶，c是鄰域規(guī)模，找出pb,w中對應(yīng)的c維分量pbv,w，1pbv,wN，v≠u，將pbv,w和選中的c維分量從pb,t中移除；在滿足公式3-公式10的前提下，找出pb,w中可插入pbu,w的所有位置，使δpb,w＝0成立，計算所有插入位置的路線增量，設(shè)定路線增量最小對應(yīng)的位置為pbu,w的插入位置，并將pbu,w插入該位置；在滿足公式3-公式10的前提下，找出pb,w中可插入pbv,w的所有位置，使δpb,w＝0成立，計算所有插入位置的路線增量，設(shè)定路線增量最小對應(yīng)的位置為pbv,w的插入位置，并將pbv,w插入該位置；步驟3.7選擇操作：若Pt+1為空，即不存在第t+1代種群，轉(zhuǎn)到步驟3.8，否則根據(jù)解的適應(yīng)度值對候選解集進行升序排序，選取前H個解構(gòu)建Pt+1，H是種群規(guī)模；步驟3.8判斷算法的終止條件：若tT，則令t＝t+1，重復(fù)步驟3.2至步驟3.7，若t＝T，則停止計算，輸出最優(yōu)的車輛調(diào)度方案。

如需購買、轉(zhuǎn)讓、實施、許可或投資類似專利技術(shù)，可聯(lián)系本專利的申請人或?qū)＠麢?quán)人北京工業(yè)大學(xué)，其通訊地址為：100124 北京市朝陽區(qū)平樂園100號；或者聯(lián)系龍圖騰網(wǎng)官方客服，聯(lián)系龍圖騰網(wǎng)可撥打電話0551-65771310或微信搜索“龍圖騰網(wǎng)”。