[發(fā)明專利]一種物流配送車輛路徑優(yōu)化方法

在審

• 申請?zhí)枺?/td>: 201611057809.3
• 申請日: 2016-11-25
• 公開（公告）號: CN106779173A
• 公開（公告）日: 2017-05-31
• 發(fā)明（設計）人: 張貴軍;周曉根;王柳靜;郝小虎;陳凱;李章維
• 申請（專利權）人: 浙江工業(yè)大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 杭州斯可睿專利事務所有限公司33241
• 代理人: 王利強

1.一種物流配送車輛路徑優(yōu)化方法，其特征在于：所述路徑優(yōu)化方法包括以下步驟：

1)以所有配送車輛的總路程最短為目標建立如下目標函數(shù)：

$\min F=\underset{k=1}{\overset{K}{\Σ}}\[\underset{i=1}{\overset{n_k}{\Σ}}{d}_{r_{k(i-1)}{r}_{ki}}+d_{r_{{\mathrm{kn}}_k}{r}_{k0}}sign\left(n_k\right)\]---\left(1\right)$

其中，K為配送車輛數(shù)量，n_k表示第k輛車配送的客戶數(shù)量，r_ki表示客戶點在第k輛車配送的客戶順序中為第i個，r_k0表示配送中心，表示第k輛車配送的第i個客戶和第i-1個客戶之間的距離，表第k輛車配送完n_k個客戶后返回配送中心的路程，sign(n_k)為決策變量，如果第k輛車沒有進行配送任務，則取0，反之均取1；約束條件為：每輛車的配送路程不得超過其最大可行駛路程D，且每輛車配送的貨物重量不得超過其最大載重Q，每輛車的配送客戶數(shù)量不得超過需要配送的總客戶數(shù)量L，每個客戶都要被配送，且每個客戶只能被配送一次；

2)確定所需的配送車輛數(shù)量其中q_i表示第i個客戶的所需貨物的重量，α∈[0,1]為，表示向下取整；

3)編碼：用數(shù)字1表示配送中心，2,3,…,L+1表示各客戶點，，則配送路徑可以編碼為(1,2,3,4,1,5,6,7,1,8,…,L+1,1)，其中1的數(shù)量為K+1，則(1,2,3,4,1)表示第一輛車的配送路徑為第1個客戶點到第2個客戶點，再到第3個客戶點，以此類推；

4)通過x_s表示(1,2,3,4,1,5,6,7,1,…,L+1,1)，即x_s＝(1,2,3,4,1,5,6,7,1,…,L+1,1)，其中通過x_sj,j＝1,2,...,L+K+1表示x_s的第j維元素；

5)種群初始化：對x_s的每一維元素進行NP次隨機排序，一次排序即為一種配送路線，如果滿足步驟1)中的約束條件，則記為一個個體x_m，直到生成NP個滿足條件的個體為止，則NP個個體組成種群P＝{x₁,x₂,...,x_NP}，根據(jù)公式(1)計算各個體對應的路線的目標函數(shù)值，其中NP表示種群規(guī)模；

6)根據(jù)各個體的目標函數(shù)值對當前種群中的個體進行排名，選出前N個個體記為計算這N個所選個體的中心個體x^center：

其中，是中心個體x^center的第j維元素，是根據(jù)排名所選的第t個個體的第j維元素，表示向上取整；

7)針對當前種群中的每一個目標個體x_m,m＝1,2,...,NP進行如下操作：

7.1)依次對每個個體中不為1的元素x_mj進行變異：

其中F為步長因子，v_mj表示與目標個體x_m對應的變異個體v_m的第j維元素，x_mj表示目標個體x_m的第j維元素，a、b和c為從{1,2,…,NP}中隨機選取的互不相同的且與m不同的數(shù)字，x_aj、x_bj和x_cj分別表示種群個體x_a、x_b和x_c的第j維元素，且x_aj、x_bj和x_cj均不等于1；

7.2)對變異個體v_m和目標個體x_m進行交叉生成測試個體u_m：

$u_{mj}=\left\{\begin{array}{cc}{v}_{mj},& ifrand(0,1)\≤CRorj=j_{rand}\\ x_{mj},& otherwise\end{array}\right.---\left(4\right)$

其中u_mj表示測試個體u_m的第j維元素，rand(0,1)表示0到1之間的隨機數(shù)，CR表示交叉概率，j_rand表示1到L+K+1之間的隨機整數(shù)；

7.3)如果測試個體u_m的各維元素中除了1以外的元素有小于2或者大于L+1的元素，則從2到L+1之間隨機生成一個數(shù)字進行替換，直到所有除了1以外的元素均在2和L+1之間為止；

7.4)如果測試個體u_m的各維元素中除了1以外的元素有相同的元素，則從2到L+1之間隨機生成一個與其他元素不同的數(shù)字進行替換，直到除了1以外的元素互不同為止；

8)根據(jù)公式(1)分別計算測試個體u_m所對應的路線的目標函數(shù)值，如果測試個體u_m的目標函數(shù)值小于目標個體x_m的目標函數(shù)值，且測試個體u_m滿足步驟1)中的約束條件，則測試個體u_m替換目標個體x_m；

9)如果種群中的每個個體都執(zhí)行完步驟7)和8)以后，則迭代次數(shù)g＝g+1；

10)如果滿足終止條件，則繼續(xù)步驟(11)，否則返回步驟6)；

11)選出當前種群中目標函數(shù)值最小的個體進行解碼，其中第1個1和第2個1之間的數(shù)字表示第1輛車的配送路線，第2個1和第3個1之間的數(shù)字表示第2輛車的配送路線，以此類推，則第K個1個第K+1個1之間的數(shù)字表示第K輛車的配送路線，其中1與1之間的數(shù)字表示配送點，1表示配送中心。

2.如權利要求1所述的一種物流配送車輛路徑優(yōu)化方法，其特征在于：所述步驟10)中，終止條件為迭代次數(shù)g達到預設最大迭代次數(shù)g_max。