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

龍圖騰網恭喜北京工業大學申請的專利一種基于自適應多約束差分進化算法的車輛路徑優化方法獲國家發明授權專利權，本發明授權專利權由國家知識產權局授予，授權公告號為：CN114330810B 。

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

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

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

如需購買、轉讓、實施、許可或投資類似專利技術，可聯系本專利的申請人或專利權人北京工業大學，其通訊地址為：100124 北京市朝陽區平樂園100號；或者聯系龍圖騰網官方客服，聯系龍圖騰網可撥打電話0551-65771310或微信搜索“龍圖騰網”。