[發明專利]一種利潤最大化的集配一體化車輛路徑規劃方法

有效

• 申請號: 201911150537.5
• 申請日: 2019-11-21
• 公開（公告）號: CN110991665B
• 公開（公告）日: 2023-05-12
• 發明（設計）人: 魯建廈;李嘉豐;許麗麗;李豪
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06Q10/30
• 分類號: G06Q10/30;G06Q10/0835
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 胡紅娟

1.一種利潤最大化的集配一體化車輛路徑規劃方法，其特征在于，包括：

步驟1，以產品配送與回收的總利潤最大為目標建立目標函數，并對目標函數進行約束；

所述的目標函數為公式(1)所示：

公式(1)中，∑_i∈V∑_j∈V∑_k∈KX_ijkr_jP_j部分為銷售產品的總收益；∑_i∈V∑_j∈v∑_k∈KX_ijkY_ijkr′_jP′_j部分為廢舊品回收總成本；∑_i∈V∑_j∈c∑_k∈KX_ijkY_ijkr′_j(P_2j-z_j)為廢舊品再制造收益；∑_i∈V∑_j∈V∑_k∈KX_ijkY_ijkr′_js_j部分為政府補貼收益；∑_i∈V∑_j∈V∑_k∈KX_ijKα_K部分為車輛的固定使用成本；∑_i∈v∑_j∈V∑_k∈KX_ijKβ_Kd_ij部分為配送車輛的距離成本；

其中，Z表示產品配送與回收的總利潤；節點集V＝{C∪D}，C＝{1，2，…，N}表示客戶集；D＝{1，2，…，M}表示車場集；K＝{1，2，…，H}表示車輛集；x_ijk表示從節點i到節點j由車輛k進行配送時，其值為1，否則為0；y_ijk表示從節點i到節點j由車輛k進行回收時，其值為1，否則為0；r_j表示客戶j的需求量；p_j表示客戶j的需求產品的單位價格；r_j′表示客戶j的回收量；p′_j表示客戶j的回收產品的單位回收價格；p′_2j表示客戶j的回收產品的二次銷售價格；z_j表示客戶j回收產品的再制造成本；S_j表示回收客戶j產品的單位政府補貼；d_ij表示節點i到節點j之間的距離；α_k表示車輛k的固定使用成本；β_k表示車輛k的單位距離行駛成本；

所述的廢舊品回收總成本的定價規則，包括：

其中，p′表示廢舊產品的最優回收價格；q₀表示廢舊產品的再制造質量門檻，質量高于q₀的產品有進行再制造的價值，而等于或低于q₀的廢舊品則只能被處理掉，獲得處理回報C₀；θ表示質量價值系數，為大于0的實數；ε為0到1之間的回收補貼系數；h表示潛在顧客人群中有主動回收意識的客戶數量；k表示客戶對回收價格的敏感系數；

所述的質量高于q₀的回收產品經過再制造然后再次進行銷售，再制造成本主要與回收產品的質量有關，質量越高，則相應的再制造成本越低；所述的再制造成本為：

其中，z表示再制造成本；p表示該產品的初始價格；q表示回收產品的質量；τ為再制造系數；

再制造產品通常會以折扣的形式再次出售給消費者，再銷售價格為：

p₂＝μp????(14)

其中，p₂為二次銷售價格；μ為產品折扣系數；

所述的廢舊品回收的判斷標準，包括：

當回收產品的總收益大于回收產品的總支出時，企業才會進行回收，否則不進行回收，判別方式為：

其中，S表示政府補貼；d_e表示進行廢舊品回收而額外行駛的距離；β為車輛的單位距離行駛成本；p₂、p′、z、C₀所代表的含義與權利要求3中的含義一致；如果式(15)大于等于0，則對該客戶的廢舊品進行回收，否則，不回收；

步驟2，確定客戶、車輛的路徑規劃問題，分別對每輛車進行客戶分配，由客戶的分配順序組成車輛的基因鏈，車輛的基因鏈共同組成一只個體；

步驟3，多只個體組成了初始種群p，并確定種群數量規模F，族群數m，其中mF，每個族群內的局部搜索次數n，種群最大迭代次數G，生成F只個體；

所述的生成F只個體的步驟，包括：

步驟3.1，將N個客戶隨機進行排序，構成一個數組；

步驟3.2，隨機選擇一輛車，將數組的第一個客戶分配給這輛車，并判斷是否超載，如果沒有超載，則以配送中心為圓心，選擇與該客戶形成角度最小的客戶分配給該車輛，并驗證是否超載；依次類推，繼續為該車輛安排其它客戶，直至該車輛無法再服務額外客戶為止；如果該車超載，則隨機選擇另一輛車對該客戶進行服務，循環以往，直至將所有客戶都安排給對應的車輛服務；

步驟3.3，執行步驟3.1-3.2共F次，生成F只個體；

步驟4，對F只個體進行分配，計算每個個體對于步驟(1)目標函數的總利潤；所述的利潤值為每個個體對于目標函數的適應度f；按照適應度降序排列分別將F只個體分配到m個族群中，使每個族群包含n只個體；

所述的對個體進行分配，包括：

步驟4.1，分別計算F只個體的對于以公式(1)為目標函數的總利潤值的適應度，并按照適應度的降序進行排列；

步驟4.2，將適應度位列第一的個體為種群最優個體，命名為Pg，被分配給第一個族群，位列第二的個體被分配給第二個族群，以次類推，直至將前m只個分別分配到m個族群中；

步驟4.3，確定探索范圍b，在其余的個體中，分別計算前b只個體與m個族群內個體的差異度，公式為：

其中，f1、f2分別表示兩只個體；H表示車輛數量；cu表示客戶；r_i表示車輛i的服務路線；N表示總的客戶數量；

步驟4.4，將b只個體中與族群1差異度最大的個體分配到族群1中，將與族群2差異度最大的個體分配到族群2中，以此類推，直至m個族群中各被分配到一個差異度最大的個體；

步驟4.5，執行步驟4.3和4.4若干次，直至將所有個體分別分配到m個族群中，每個族群包含n只個體；

步驟5，對m個族群內部個體進行n次信息交流、進化，對適應度值最大的個體進行n次優化，完成一次個體的迭代；

所述的對m個族群內部n次信息交流、進化后的步驟，包括：

步驟5.1，在大小為n的族群中，選擇s只個體組成一個子群，其中，s＜n,選擇概率公式為：

其中，j表示客戶的適應度排序；p_j表示適應度排序為j的客戶被選中的概率；

步驟5.2，給子群中適應度值最大的個體命名為Pb，適應度最小的個體命名為Pw，Pb與Pw兩只個體進行信息交流；

步驟5.3，信息交流后的個體分別命名為P′_b和和P′_w，根據其適應度判斷，如果f(P′_b)f(P_b)，則用P′_b替換P_b，否則保持P_b不變；

步驟5.4，如果f(P′_w)f(P_w)，則用P′_w替換P_w；否則，將步驟5.2中的Pb用Pg進行替換，然后重新進行信息交流操作，并再次比較信息交流后的適應度；如果f(P′_w)f(P_w)，則用P′_w替換P_w，否則按照步驟3.1、步驟3.2所描述方式，重新生成一只新的個體代替P_w；

步驟5.5，根據鄰域搜索策略，對Pb進行優化；

步驟5.6，重復執行步驟5.1到步驟5.5共n次，進行n次信息交流，對適應度值最大的個體進行n次優化，完成一次個體的迭代；

步驟5.5中，所述的鄰域搜索策略，包括：

(1)車輛間單點轉移；隨機選擇兩條路徑，將一條路徑上的一個客戶按照最小成本法插入到另一條車輛路徑中；

(2)車輛間路徑兩點互換；隨機選擇兩條路徑，從兩條路徑中分別選擇一個客戶按照最小成本法插入到另一條路徑中；

(3)車輛間路徑路段互換；隨機選擇兩條路徑，從兩條路徑中分別選擇一段客戶隨機插入到另一條路徑中；

(4)車輛內路徑單點插入；隨機選擇一條路線上的一個客戶，然后按照最小成本法插入到路線上的其它位置；

(5)車輛內路徑路段互換；隨機選取一條路線上的兩段客戶，將兩段客戶的位置互換；

(6)車輛內路徑反轉；隨機選擇一條路徑上的兩個位置，然后將兩位置間的所有客戶進行反轉；步驟6，對F只個體進行混合重洗，返回執行步驟4～5，完成g次個體的迭代，迭代統計次數為g＝g+1；判斷迭代次數g是否達到最大迭代次數G；如果達到，則繼續執行步驟7；否則返回執行步驟4；

步驟7，輸出適應度最大的個體Pg，及其適應度f(P_g)；按照適應度最大的個體Pg中各車輛的基因鏈，安排具體車輛的配送服務路線。