[發明專利]一種瓶裝液化氣車輛配送路徑優化方法

有效

• 申請號: 202111116863.1
• 申請日: 2021-09-23
• 公開（公告）號: CN113780676B
• 公開（公告）日: 2023-06-23
• 發明（設計）人: 吳慶濤;賈新宇;謝萍;冀治航;王琳;劉牧華;張明川;朱軍龍;邢玲
• 申請（專利權）人: 河南科技大學
• 主分類號: G06F17/00
• 分類號: G06F17/00;G06Q10/04;G06Q10/08;G06F30/15;G06F30/27;G06N3/12
• 代理公司: 洛陽華和知識產權代理事務所(普通合伙) 41203
• 代理人: 陳佳麗

1.一種瓶裝液化氣車輛配送路徑優化方法，其特征在于，包括：

步驟一、根據液化氣配送車輛路徑問題的描述，建立數學模型：定義完整圖G＝(N,A)，N＝{0,1,2,…,n}為配送中心和客戶點集，A＝{arc(i,j)|i,j∈N,i≠j}是路徑的集合，節點0為配送中心節點，C為不包含配送中心節點0的客戶點集，已知每個客戶點i的位置,其需求量及配送時間窗要求分別為g_i和[Ta_i,Tb_i]，配送中心最多用K輛車從配送中心到達所有的客戶點，每輛車從配送中心出發，最后返回到配送中心，每輛車的最大載貨量為Q，T_ik為車輛k到客戶i的時刻，w_ik為車輛k在客戶i的等待時間，A＝{arc(i,j)|i,j∈N,i≠j}是邊的集合，定義d_ij為arc(i,j)的距離，即客戶點i到客戶點j的距離，且d_ij＝d_ji，t_ij為客戶點i到客戶點j的運輸時間，車輛k從客戶i到客戶j的實時裝載量為al_ijk，路徑事故率為p_ij以及與其相關的暴露人口為液化氣配送共包含三個目標，風險低、成本低以及車輛冗余度低，建立目標函數如下：

決策變量：

該問題的可行解必須滿足的約束條件有：

其中k是運輸液化氣的車輛，C_V是單輛運輸車的發車成本，C_L是單位路程燃油成本，C_T是駕駛員單位時間費用，D_ij表示客戶i到客戶j路段的實際距離或運輸時間；約束(4)表示每個客戶點只有一輛車為其服務；約束(5)表示每位客戶被訪問一次，并返回到配送中心；約束(6)表示每輛車出發時最多只能訪問一位客戶；約束(7)表示每輛車到達時最多只能配送一位客戶；約束(8)表示車輛載貨量約束；約束(9)表示確保車輛到達某客戶節點完成配送后，必須離開該客戶前往下一個客戶；約束(10)表示車輛服務某客戶后所減少的載重必須等于該客戶的需求；約束(11)表示車輛到達客戶的時間；約束(12)對每個客戶施加硬時間窗約束，雖然要求車輛必須在客戶時間窗內開始配送，但允許較早到達的車輛等待客戶時間窗的開始；

步驟二、利用混合協同進化優化方法對上述模型進行求解，得出的最優解即為最優路線；

所述步驟二中利用混合協同進化優化方法對步驟一中的模型進行求解的方法為：

(1)使F₁表示步驟一中的模型，F₂表示步驟一中除去(3)、(11)和(12)的模型；

(2)編碼；

步驟2.1、設置參數：客戶點數目N，車輛最大載重量Q，客戶點的需求量列表T，交叉概率PC，變異概率PM，種群規模NP，迭代次數G；

步驟2.2、編碼：采用整數編碼的形式對染色體進行編碼，用數字0表示配送中心，1,2,3,…,N表示客戶點，則配送路徑可以編碼為(0,1,2,3,0,4,5,6,7,0,…,N,0)；

(3)初始化種群P₁和P₂：

步驟3.1、分別使用前向插入啟發式算法構造F₁和F₂的兩個可行個體；

步驟3.2、在步驟3.1中個體的鄰域內選擇部分個體，同隨機產生的其他個體一起形成規模均為初始種群P₁和P₂；

(4)基于序列交叉操作：

步驟4.1、分別從子代種群Off₁和Off₂中選擇一個染色體作為父代染色體，記為chrom1和chrom2，產生一個在[0,1]區間的隨機數r'，若r'＜PC，進行步驟4.2-步驟4.6的交叉操作，否則直接保留這兩條染色體至下一代；

步驟4.2、分別從父代染色體chrom1和chrom2中隨機選擇一條路徑，記為L1和L2；

步驟4.3、從每條路徑中隨機選取一個斷點，記為Node1和Node2；

步驟4.4、將L1中Node1之前的部分與L2中Node2之后的部分鏈接為一條新的路徑，如果出現兩個重復的客戶，刪除其中一個，并檢查該條新路徑是否滿足約束，若滿足約束，則進行步驟4.5，如不滿足則返回步驟4.3，若返回步驟4.3次數達到L1與L2中客戶數的乘積，則放棄交叉進行步驟(5)；

步驟4.5、將步驟4.4中新路徑添加到chrom1中，如果有客戶在新路徑中出現一次，在其他舊路徑中出現一次，則刪除舊路徑中的重復客戶；

步驟4.6、如果L1中后半部分有客戶沒有被分配路徑，則將該客戶插入到chrom1中其他路徑的可行插入位置，如果沒有可行插入位置，則放棄交叉進行步驟(5)，如果全部可行，則chrom1更新為chrom1'，可以通過顛倒父母角色來生成第二個后代chrom2'；

(5)變異操作：在Off₁和Off₂分別產生一個在[0,1]區間的隨機數r”，若r”＜PM，隨機選擇染色體中的兩個客戶點編碼，進行位置互換；否則，直接保留當前染色體至下一代；遍歷完所有染色體更新子代種群Off₁和Off₂；

(6)從更新后的Off₂中選擇能夠解決原始液化氣配送問題即滿足時間窗約束的可行解形成Off₂_feasible；

(7)種群合并：合并種群P₁，Off₂_feasible和更新后的子代種群Off₁成為新的P₁；合并種群P₂，更新后的子代種群Off₁和Off₂成為新的P₂；

(8)計算適應度值：分別計算種群P₁和P₂中各個染色體在各維目標的適應度；

(9)非支配排序：將種群P₁中所有個體對于各維適應度值按支配關系分為若干層，第一層為R₀的非支配個體集合F₁，第二層為在R₀中去掉第一層個體后所求得的非支配個體集合F₂，依此類推，產生所有分類排序子集F＝(F₁,F₂,…)，種群P₂同理；

(10)計算P₁個體的擁擠距離：設P[x]_distance為個體x的擁擠距離，P[x].m為個體x在子目標m上的函數值f_k，則計算種群P₁中所有個體的擁擠距離：種群P₂同理；

(11)計算P₂個體的違反約束值：對于P₂的每個個體x計算其違反原始液化氣配送問題的時間窗約束值，即CV(x)；

(12)對P₁和P₂進行精英選擇操作：定義每個個體的的分類序號x_rank，x_rank＝k當且僅當x∈F_k；當兩個個體屬于不同的分類排序子集時，優先選取序號x_rank小的個體進入P_t+1；在P₁中，當x_rank相同時，則優先選取聚集距離P[x]_distance大的個體進入P_t+1；在P₂中，當x_rank相同時，則優先選取違反約束值CV(x)小的個體進入P_t+1；直至P_t+1的規模為N；

(13)迭代步驟4至步驟11，最大迭代次數G，得到種群P₁的一組最優解，根據決策者對各目標的優先考慮度選擇其中的一個解進行決策，即得到瓶裝液化氣車輛配送最優路線。