[發(fā)明專利]一種用于物流配送領(lǐng)域的路徑優(yōu)化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201510066971.0
• 申請(qǐng)日: 2015-02-09
• 公開(kāi)（公告）號(hào): CN104573880B
• 公開(kāi)（公告）日: 2017-12-05
• 發(fā)明（設(shè)計(jì)）人: 杜磊;郭利平;耿彥峰;李雪蓮;王晉平
• 申請(qǐng)（專利權(quán)）人: 山西大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q10/08
• 代理公司: 太原科衛(wèi)專利事務(wù)所(普通合伙)14100
• 代理人: 朱源

1.一種應(yīng)用于物流配送領(lǐng)域的路徑優(yōu)化方法,用以解決物流配送中大規(guī)模目的地路徑優(yōu)化問(wèn)題，其特征在于，將這類問(wèn)題的計(jì)算分為三個(gè)階段，稱為三級(jí)過(guò)程算法：

a)第一階段，首先通過(guò)路口、路口屬性的描述，應(yīng)用堆優(yōu)化Dijkstra算法，將出發(fā)點(diǎn)與所有目的地點(diǎn)、任意兩個(gè)目的地點(diǎn)之間的距離實(shí)現(xiàn)表格化，然后通過(guò)預(yù)先計(jì)算各點(diǎn)的距離并存儲(chǔ)；

b)第二階段，采用一種啟發(fā)式的模擬退火網(wǎng)格算法，結(jié)合約束條件，將大量的目的地點(diǎn)進(jìn)行劃分或分組，形成一系列滿足約束條件的團(tuán)簇；

c)第三階段，利用中國(guó)郵遞員問(wèn)題算法，確定團(tuán)簇內(nèi)行走時(shí)的最短路徑和行走次序，最終計(jì)算得到面向所有目的地點(diǎn)的最優(yōu)化路徑解；(1)在第一階段中，結(jié)合路口點(diǎn)的約束條件，構(gòu)造各點(diǎn)間距離的鄰接矩陣

①路口、出發(fā)點(diǎn)、目的地的連通性處理

在物流配送問(wèn)題中，無(wú)論出發(fā)點(diǎn)、目的地點(diǎn)總是由許多路徑連接構(gòu)成，而路徑是由最基本的路口這一元素構(gòu)成；為了準(zhǔn)確的計(jì)算路徑，考慮到路口的約束條件，首先構(gòu)建描述路口連通性的體系；

所述路口屬性信息的表示方式，可以準(zhǔn)確的表示單連通、雙連通、三聯(lián)通、四聯(lián)通、…直到n連通的路口信息；以下都用0來(lái)表示路口，依次用1、2、3…n表示與其直接連接的其它路口，分別有以下幾種情況：

a)路口不能有孤立的，即沒(méi)有零連通的路口點(diǎn)；

b)單連通的路口點(diǎn)的表示：路口點(diǎn)的單連通相當(dāng)于1條路的終點(diǎn)，設(shè)0為需描述的該路口點(diǎn)，1表示與其相連接的另一路口點(diǎn)；單連通的點(diǎn)僅能與另外的一個(gè)點(diǎn)連通，即單連通的點(diǎn)可以表示為：1→0→1；

c)雙連通的路口點(diǎn)的表示：雙連通的路口點(diǎn)可以與其它一共2個(gè)路口點(diǎn)連通，設(shè)0表示需描述的該路口點(diǎn)，1、2表示與其相連的另兩個(gè)路口點(diǎn)，則其通過(guò)性可描述為：1→0→1，1→0→2，2→0→1，2→0→2這四種情況，則使用一個(gè)長(zhǎng)度為4的字符串可以表示該路口的通過(guò)性信息，字符串中1表示通，0表示不通；

d)三連通的路口點(diǎn)的表示：三連通的路口點(diǎn)可以與其它一共3個(gè)路口點(diǎn)連通，用0表示需描述的該路口點(diǎn)，1、2、3表示與其相連的另兩個(gè)路口點(diǎn)，則其通過(guò)性可描述為：1→0→1，1→0→2，1→0→3；2→0→1，2→0→2，2→0→3；3→0→1，3→0→2，3→0→3；則使用一個(gè)長(zhǎng)度為9的字符串可以表示該路口的通過(guò)性信息；

e)四連通的路口點(diǎn)的表示：四連通的路口點(diǎn)可以與其它一共4個(gè)路口點(diǎn)連通，用0表示需描述的該路口點(diǎn)，1、2、3、4表示與其相連的另兩個(gè)路口點(diǎn)，則其通過(guò)性可描述為：1→0→1，1→0→2，1→0→3，1→0→4；2→0→1，2→0→2，2→0→3，2→0→4；3→0→1，3→0→2，3→0→3，3→0→4；4→0→1，4→0→2，4→0→3，4→0→4；則使用一個(gè)長(zhǎng)度為16的字符串可以表示該路口的通過(guò)性信息；

f)依此類推，對(duì)應(yīng)n連通的點(diǎn)，點(diǎn)本身標(biāo)記為0，與其相連通的n個(gè)點(diǎn)，分別標(biāo)記為1、2、3、4、5……n，則其通過(guò)性可以用一個(gè)n×n的矩陣表示；用長(zhǎng)度為n²的字符串即可描述其通過(guò)性；字符串的排列方式為由左向右開(kāi)始排列，如下所示：

n×n矩陣：

矩陣中的每個(gè)位置的元素分別為0、1、2、3、4、5…n；采用不同的數(shù)字表示不同的通過(guò)性，先排列矩陣的第一行對(duì)應(yīng)的字符，再排第二行字符，一直繼續(xù)，直到排列矩陣的第n行，得到一個(gè)由n²字符構(gòu)成的一個(gè)字符串來(lái)描述該路口的連通性；

②路口數(shù)據(jù)屬性描述

所述路口信息的數(shù)據(jù)存儲(chǔ)方式，包括數(shù)據(jù)表，數(shù)據(jù)表中有以下幾項(xiàng)：唯一ID；X；Y；Z；Connection；Describe；唯一ID表示路口的唯一編號(hào)；X；Y；Z；分別表示路口的X坐標(biāo)、Y坐標(biāo)、Z坐標(biāo)；Connection表示與路口相連接的其它路口的ID；Describe表示連通性描述字符串；

③出發(fā)點(diǎn)、目的地距離表的計(jì)算與生成

計(jì)算過(guò)程中，關(guān)鍵是要得到路口與路口之間的距離，通過(guò)第一階段路口的連通性處理及路口的自身屬性，借助堆優(yōu)化Dijkstra算法，可以快速計(jì)算出兩點(diǎn)之間的最短路徑距離，最終可以求得出發(fā)點(diǎn)到每個(gè)目的地點(diǎn)的距離、各個(gè)目的地點(diǎn)之間的距離，構(gòu)成一個(gè)出發(fā)地、目的地距離表；

(2)模擬退火計(jì)算團(tuán)簇

第二階段，采用一種啟發(fā)式的模擬退火網(wǎng)格算法，結(jié)合約束條件，將大量的目的地點(diǎn)進(jìn)行劃分或分組，形成一系列滿足約束條件的團(tuán)簇；

①定義目標(biāo)函數(shù)與約束條件

不同的路徑優(yōu)化計(jì)算過(guò)程，目標(biāo)函數(shù)與約束條件都不一樣，根據(jù)具體的問(wèn)題設(shè)定具體的目標(biāo)函數(shù)與約束條件都可以進(jìn)行計(jì)算；

②隨機(jī)構(gòu)建初始隨機(jī)解

根據(jù)具體的約束條件和目標(biāo)函數(shù)構(gòu)建一個(gè)隨機(jī)的初始解：先將目標(biāo)團(tuán)簇分為多個(gè)組，然后將任意目的地分到各個(gè)組中；顯然初始解的效果是不理想的，下一步開(kāi)始用模擬退火進(jìn)行交換，以求得滿意解；具體如下：設(shè)有具體的路徑優(yōu)化計(jì)算為，從起始點(diǎn)S出發(fā)，一共有N個(gè)配送目的地，分別是D1、D2、D3、…、DN；

約束條件為：每次配送，從S出發(fā)最多只能經(jīng)過(guò)n個(gè)點(diǎn)；

目標(biāo)函數(shù)為：配送總路徑最短，即：式中S₁表示從出發(fā)點(diǎn)到本次行走第一個(gè)目的地點(diǎn)的距離，S₂表示從最后一個(gè)目的地點(diǎn)返回出發(fā)點(diǎn)的距離，L_ij表示從第i個(gè)目的地點(diǎn)到第j個(gè)目的地點(diǎn)的距離；用α描述這是第α次行走；

于是構(gòu)建一個(gè)隨機(jī)的初始解：先將目標(biāo)團(tuán)簇分為η組：η＝INT(N/n)+1，然后將任意目的地分到各個(gè)組中；顯然初始解的效果是不理想的，下一步開(kāi)始用模擬退火進(jìn)行交換，以求得滿意解；

③采用模擬退火法進(jìn)行降溫計(jì)算，在每個(gè)溫度下，進(jìn)行目的地交換計(jì)算，計(jì)算規(guī)則如下:

a)先確定團(tuán)簇內(nèi)交換和團(tuán)簇間交換的份額β，β＝0.8，產(chǎn)生一個(gè)隨機(jī)數(shù)rnd，若rnd≤β，則進(jìn)行團(tuán)簇內(nèi)交換；若rnd＞β，則進(jìn)行團(tuán)簇間交換；

b)采用Metropolis判據(jù)e^{-|tagetValueDelta|/T}＞rnd判斷上述交換是否接受，其中targetValueDelta為上一輪目標(biāo)值和本輪目標(biāo)值的差，T為本輪溫度，rnd是0-1間的隨機(jī)數(shù)；

c)通過(guò)設(shè)定改進(jìn)迭代和非改進(jìn)迭代的次數(shù)，來(lái)限制上述過(guò)程中的交換；在某一溫度下隨機(jī)進(jìn)行組內(nèi)交換或組間交換后，可能導(dǎo)致目標(biāo)值降低，那么本次交換叫做一次改進(jìn)迭代，否則叫非改進(jìn)迭代；

(3)第三階段，利用中國(guó)郵遞員問(wèn)題算法，確定團(tuán)簇內(nèi)行走時(shí)的最短路徑和行走次序

通過(guò)第二階段交換的完成，可以形成一定量相對(duì)最優(yōu)解的團(tuán)簇；然后，在團(tuán)簇內(nèi)部進(jìn)行郵遞員問(wèn)題計(jì)算行走，以求得團(tuán)簇內(nèi)的最優(yōu)行走順序；因?yàn)榇藭r(shí)滿足約束條件和目標(biāo)解的團(tuán)簇內(nèi)部目的地點(diǎn)已經(jīng)比較少，可以通過(guò)貪心算法，用郵遞員問(wèn)題算法最終計(jì)算得到面向所有目的地點(diǎn)的最優(yōu)化路徑解；所述目的地為實(shí)體商店，每個(gè)商店的訂貨量不同，但每次配送車輛的裝載量是固定的，故約束條件為：其中X_i為各個(gè)商店的訂貨量，σ為車輛的最大裝載量。