[發(fā)明專利]一種基于電子地圖的物流路徑優(yōu)化方法

無效

• 申請(qǐng)?zhí)枺?/td>: 201310115538.2
• 申請(qǐng)日: 2013-04-03
• 公開（公告）號(hào): CN103440524A
• 公開（公告）日: 2013-12-11
• 發(fā)明（設(shè)計(jì)）人: 李波;徐傳超;唐熠;李慶華;屈小龍
• 申請(qǐng)（專利權(quán)）人: 天津大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q10/08;G06Q50/28
• 代理公司: 天津市北洋有限責(zé)任專利代理事務(wù)所 12201
• 代理人: 李素蘭

1.一種基于電子地圖的物流路徑優(yōu)化方法，其特征在于，該方法包括以下步驟：?

首先，確定理論最優(yōu)需求點(diǎn)的坐標(biāo)，同一個(gè)區(qū)域集合內(nèi)的所有需求點(diǎn)的坐標(biāo)值是基于同一個(gè)坐標(biāo)系，坐標(biāo)系的位置可以任意選擇，不同區(qū)域集合的坐標(biāo)可以不同；根據(jù)重心法公式公式中各物理參數(shù)分別為：X_i表示第i個(gè)點(diǎn)在X軸的坐標(biāo)值，Y_i表示第i個(gè)點(diǎn)在Y軸的坐標(biāo)值，T_i表示運(yùn)輸?shù)降趇個(gè)點(diǎn)或從第i個(gè)點(diǎn)運(yùn)出的貨運(yùn)量，表示所有運(yùn)輸點(diǎn)的總貨運(yùn)量，X₀是重心法最優(yōu)X軸的坐標(biāo)值，Y₀是重心法最優(yōu)Y軸的坐標(biāo)值；所包含若干個(gè)物流點(diǎn)的區(qū)域集合，在每個(gè)區(qū)域集合內(nèi)通過重心法理論公式確定理論最優(yōu)需求點(diǎn)的坐標(biāo)(X₀,Y₀)；?

然后，確定實(shí)際最優(yōu)需求點(diǎn)的坐標(biāo)，通過蟻群算法或禁忌搜索等優(yōu)化算法在電子地圖尋找最接近于理論需求點(diǎn)的坐標(biāo)值作為實(shí)際最優(yōu)需求點(diǎn)的坐標(biāo)，如果一次優(yōu)化算法尋求到的理論最優(yōu)需求點(diǎn)的坐標(biāo)值在實(shí)際需求點(diǎn)的坐標(biāo)并不存在，則再次通過蟻群算法或禁忌搜索等優(yōu)化算法繼續(xù)尋找實(shí)際最優(yōu)需求點(diǎn)，至到尋找到實(shí)際最優(yōu)坐標(biāo)值為止；?

其次，求解出過實(shí)際最優(yōu)需求點(diǎn)的最短直線距離；根據(jù)SDVRP公式求解出通過實(shí)際最優(yōu)需求點(diǎn)處的理論上的最短直線行駛距離（SDVRP公式及其公式中所有參數(shù)含義如下所示），即圖1所示的L₀₁和L₀₄兩條路徑；但理論上的最短行駛距離并非一定是實(shí)際的最優(yōu)的運(yùn)輸路徑，也就是說實(shí)際路線中不一定存在這條理論上的最短路徑，但一定存在與理論最短路徑最接近的一條路徑；再次通過蟻群算法、禁忌搜索等優(yōu)化算法在電子地圖上尋找與理論最優(yōu)路徑最接近的一條實(shí)際路線L₀₂和L₀₅作為最終的物流實(shí)際運(yùn)輸路徑，具體計(jì)算流程如下：?

SDVRP公式詳解及其公式中所有參數(shù)代表的含義為：?

f_ik≤d_iy_ik?k＝1,....m;i＝1,.....n（1-7）?

上式公式中，Q_k表示第k輛車的車輛容量；V表示無向圖G=（V，E）中的n+1個(gè)需求節(jié)點(diǎn)，V={0，1，2，……，n}；V′表示需求點(diǎn)集合，V′={1，2，……，n}；c_ij表示非負(fù)的時(shí)間與費(fèi)用的矩陣，與邊（i，j）一一對(duì)應(yīng)；車隊(duì)M={1，2，……，m}；E＝{(i,j):i,j∈V,i＜j}代表對(duì)應(yīng)邊；節(jié)點(diǎn)0表示起始點(diǎn)坐標(biāo)位置；任一需求點(diǎn)i∈V′的需求為d_i單位；S表示V中任意點(diǎn)所形成的閉合回路的集合，包括起始位置坐標(biāo)0在內(nèi)；MA為一個(gè)充分大的常數(shù)；是頂點(diǎn)集合的一個(gè)子集；是相對(duì)于s的補(bǔ)集；d(s)為s中所有頂點(diǎn)集合需求之和；δ(s)為所有滿足構(gòu)成的弧集；為第k輛車被派出經(jīng)過邊（i，j）的次數(shù)；f_ik為需求點(diǎn)在車輛k上被滿足的需求；?

目標(biāo)函數(shù)式（1-1）表示整個(gè)車隊(duì)行駛的總距離最短；式（1-2）表示每個(gè)需求點(diǎn)至少有車輛經(jīng)過一次；式（1-3）保證每輛車至少訪問一個(gè)需求點(diǎn)，這就要求所有車輛都投入使用；式（1-4）規(guī)定了路徑開始位置坐標(biāo)；式（1-5）是為了防止出現(xiàn)不必要的弧，即當(dāng)任何一輛車都沒有訪問此路徑對(duì)應(yīng)的需求點(diǎn)的時(shí)候，相應(yīng)的有第k輛車不經(jīng)過邊（i，?j）；式（1-6）確保了車輛的容量限制，還避免了支路出現(xiàn)回路的情況，其中表示向上取整數(shù)；式（1-7）要求車輛不能供應(yīng)其沒有訪問的需求點(diǎn)；（1-8）規(guī)定必須滿足所有的需求量；式（1-9）保證不超出車輛容量限制；式（1-10）～（1-11）為非負(fù)約束以及布爾約束；?

再次，在電子地圖確定通過最優(yōu)需求點(diǎn)的一條或多條實(shí)際物流路徑，由SDVRP求解的路徑為理論上的最短行駛距離，但理論上的最短行駛距離并非一定是實(shí)際的最優(yōu)的運(yùn)輸路徑，所以需要尋找最優(yōu)的路徑；目前，最常用的兩種電子地圖形式是矢量地圖和柵格地圖；現(xiàn)僅對(duì)矢量化電子地圖的路徑進(jìn)行最優(yōu)的選擇，在矢量化電子地圖中，道路網(wǎng)可以看成為帶權(quán)有向不完全稀疏圖；帶權(quán)有向不完全稀疏圖的求解為：?

RoadWork=(N，R)；?

N={XX∈Nodeset}；?

R={NR}；?

NR={〈X，Y〉L(X，Y)∩(X，Y)∈N}；?

其中N表示道路的節(jié)點(diǎn)集，NR表示電子地圖上兩個(gè)節(jié)點(diǎn)的拓?fù)潢P(guān)系集合，無序?qū)Α碭，Y〉表示需求點(diǎn)X和Y之間的一條實(shí)際路徑，謂詞L(X，Y)表示節(jié)點(diǎn)X到Y(jié)的實(shí)際路徑，需求點(diǎn)和需求點(diǎn)之間連接的權(quán)可以用需求點(diǎn)之間的幾何長(zhǎng)度或者長(zhǎng)度和其他因素的加權(quán)和表示；由于存在轉(zhuǎn)向限制和道路行駛方向限制，所以它是有向圖；電子地圖覆蓋區(qū)域是有限的，區(qū)域內(nèi)的需求點(diǎn)和需求點(diǎn)之間的聯(lián)系也是有限的，因此這種圖是有向的，也是強(qiáng)連接的；對(duì)于電子地圖上的一對(duì)需求點(diǎn)（X，Y）總存在多條X與Y之間的實(shí)際路徑；?

最后，在電子地圖上確定最優(yōu)實(shí)際物流路徑，在矢量化優(yōu)化選擇后的多條實(shí)際路徑，用Dijkstra算法進(jìn)行最后的實(shí)際物流路徑確定，該算法包括以下處理：?

假如每一點(diǎn)都有一對(duì)標(biāo)號(hào)(d_f,p_j)，其中d_j是從起源點(diǎn)s到點(diǎn)j的最短路徑的長(zhǎng)度（從一個(gè)點(diǎn)到其本身的長(zhǎng)度為0，兩個(gè)互不相通的點(diǎn)的距離為無窮），求解從起源點(diǎn)s到j(luò)的最短路徑算法基本過程如下：?

步驟（1）、初始化，起始點(diǎn)設(shè)置為：（11）、d_s＝0，p_s為空；（12）、所有其他點(diǎn)：d_f＝∞，對(duì)不同的點(diǎn)尋找最短路徑時(shí)，p_f不同；（13）、標(biāo)記起源點(diǎn)s，記k=s，其他所有點(diǎn)設(shè)置為未標(biāo)記的；?

步驟2、檢查從所有已標(biāo)記的點(diǎn)k到其直接連接的未標(biāo)記的點(diǎn)j的距離，并設(shè)置：?

d_f＝min{d_j,d_k+l_kj};?

式中：l_kj是從k到j(luò)的直接連接距離；?

步驟3，選取下一個(gè)點(diǎn)，從所有為標(biāo)記的節(jié)點(diǎn)中，選取d_j中最小的一個(gè)i值：?

d_f＝min，d_j是所有未標(biāo)記出的點(diǎn)j；?

式中，d_f為對(duì)應(yīng)點(diǎn)i最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)定的；?

步驟（4）找到點(diǎn)i的前一點(diǎn)，從已標(biāo)記的點(diǎn)中找到直接連接點(diǎn)i的點(diǎn)u作為前一點(diǎn)，設(shè)置：i=u；?

步驟（5）標(biāo)記點(diǎn)i，如果所有點(diǎn)已標(biāo)記，則實(shí)際最短物流路徑已找到，算法退出，否則k=i，轉(zhuǎn)到步驟（2）再繼續(xù)；?

在按標(biāo)記法實(shí)現(xiàn)Dijkstra算法的過程中，核心步驟就是從未標(biāo)記的點(diǎn)中選擇一個(gè)權(quán)值最小的弧段，這是與SDVRP求解出的最短直線距離循環(huán)比較的過程。?