基于最優(yōu)路徑算法的快餐配送路徑優(yōu)化問題研究

柯小波

摘 要：隨著快餐業(yè)的迅速發(fā)展，對快餐業(yè)中快餐配送問題的算法研究就愈發(fā)重要，快餐的配送問題，本質(zhì)上就是最優(yōu)路徑問題，現(xiàn)在分析一種最優(yōu)路徑算法的基礎(chǔ)上，結(jié)合快餐配送的諸多影響因子，對算法進行了優(yōu)化。

關(guān)鍵詞：最優(yōu)路徑算法，快餐配送；研究

1 引言

最優(yōu)路徑算法是GIS在路徑分析中最常用的算法之一。車載導(dǎo)航系統(tǒng)、智慧交通系統(tǒng)等都離不開最優(yōu)路徑算法的應(yīng)用。[1]而在快餐業(yè)配送過程中，由于行業(yè)的特殊性及配送物品的特殊性，使得其在具有一般配送的特點同時，又具有自身特點。涉及到配送路徑方面的問題主要體現(xiàn)在以下幾個方面：（1）快餐配送對時間極為敏感。由于客戶對快餐的需求都相對較急迫，且快餐本身的食物特性所帶來的保溫要求，使得快餐的配送要求非常迅速的將食物送達到；（2）點餐客戶位置的特殊性。如點餐客戶在某個小區(qū)的某樓層內(nèi)，這就要求不能將小區(qū)作為點餐點處理，而要以小區(qū)門作為關(guān)注點，考量從小區(qū)門到該客戶所在樓房及樓層的距離；（3）快餐配送受時間區(qū)段、配送工具、區(qū)域交通狀況、天氣狀況等情況的影響。

目前傳統(tǒng)的最優(yōu)路徑算法通常將路網(wǎng)模型理想化處理，實用性教差。較少考慮實際行駛過程中的道路屬性，如道路限速、紅綠燈、道路等級[2]、道路阻值、交通工具限制等?；蛘呖紤]不夠全面。

2 最優(yōu)路徑算法優(yōu)化研究

2.1 傳統(tǒng)最優(yōu)路徑算法的優(yōu)化

在按標(biāo)記法[3]實現(xiàn)Dijkstra 算法的過程中，核心步驟就是從未標(biāo)記的點中選擇一個權(quán)值最小的弧段。這是一個循環(huán)比較的過程， 如果不采用任何技巧，未標(biāo)記點將以無序的形式存放在一個鏈表或數(shù)組中。那么要選擇一個權(quán)值最小的弧段就必須把所有的點都掃描一遍，在大數(shù)據(jù)量的情況下，這無疑是一個制約計算速度的瓶頸。要解決這個問題，最有效的做法就是將這些要掃描的點按其所在邊的權(quán)值進行順序排列，這樣每循環(huán)一次即可取到符合條件的點，可大大提高算法的執(zhí)行效率。

2.2 在快餐配送過程中，影響最優(yōu)路徑算法的道路因子[1]

影響路徑分析的交通影響因子很多，但是各類因子對計算結(jié)果的影響程度是各不相同的，有的只是對道路權(quán)值的影響；有的則會改變路徑分析過程中路徑的行進方向，可分類如下：

2.2.1 影響道路阻值的影響因子。這類因子只會影響道路的權(quán)值屬性，不會改變路徑的連通性，也不會改變路徑分析過程中的物體的進行方向，如紅綠燈、道路等級、限速[4]、道路阻值等。這類信息可以直接在原始路網(wǎng)模型的基礎(chǔ)上進行考量。

若以實際行駛速度為考量單位，下面是只考慮道路等級因素和障礙物因素的算法：[3]

V，實際行駛速度；T，選擇使用的交通工具；g，經(jīng)過道路的等級；d，經(jīng)過道路的長度；t，N分鐘商圈（N分鐘商圈就是指乘坐某種交通工具，如電動車，以到達某地所需的某個具體時間為標(biāo)準(zhǔn)，這里取N分鐘，所形成的一個凸包多邊形）；t'，行駛中遇到障礙物的等待時間（如紅綠燈）。其中d值通過Dijkstra 算法算出。

2.2.2 影響路網(wǎng)連通性的影響因子。這類因子可直接改變原有路網(wǎng)模型的連通性，會改變路徑分析過程中 的進行方向，如單雙行線、交通工具限制、斑馬線天橋、道路轉(zhuǎn)向等。這些因子需要將其作為路網(wǎng)模型的一部分然后重新建立路網(wǎng)模型。

2.2.3 訂餐區(qū)域的影響因子。這些因子會影響到達目前大致區(qū)域后到達顧客手上這個過程的時間，以小區(qū)為例，需要考慮的小區(qū)參數(shù)：大門口到道路的距離、小區(qū)大門口到樓宇質(zhì)心點的距離，該距離可以預(yù)先分派到道路節(jié)點上、小區(qū)大門到道路的通行情況。

小區(qū)道路映射預(yù)處理過程：（a）以小區(qū)大門為圓心，半徑不斷迭代增大形成緩沖區(qū)，直至與路網(wǎng)相交；（b）搜索緩沖區(qū)與路網(wǎng)相交的道路，判斷小區(qū)大門到該道路是否可達；（c）對于可達的道路，計算其與小區(qū)大門距離，取其距離最短的連接點作為小區(qū)道路映射點。（d）計算的距離。

另外，為了提高系統(tǒng)的性能，對兩兩小區(qū)質(zhì)心點間的路徑、路徑距離、通行時間，調(diào)用路網(wǎng)分析算法進行預(yù)先計算，結(jié)果存儲在表中。

3 實際應(yīng)用分析

在快餐配送的實際應(yīng)用過程中，通常不單要求計算從店鋪到顧客點餐地點的最優(yōu)路徑，還需要根據(jù)該店的輻射范圍，提前計算出該店的多分鐘商圈的范圍，如某快餐店將自己所輻射的區(qū)域提前劃分為5分鐘商圈、10分鐘商圈，然后可自動根據(jù)顧客來電判斷處于哪個商圈范圍內(nèi)[5]，這樣可以方便統(tǒng)一分配配送任務(wù)并可及時準(zhǔn)確通知客戶所需等待的時間。

N分鐘商圈的算法步驟主要為：

（1）劃定理想商圈范圍。以該店面為圓心，以N分鐘行駛距離為半徑R畫圓，即為理想商圈范圍。公式為：R=V*T（V由選擇的交通工具類別決定）。

（2）搜索映射點和nodes（道路節(jié)點），搜索出所有的小區(qū)道路映射點和nodes。

（3）計算最優(yōu)路徑。遍歷道路上的nodes，計算機會點到各nodes的最優(yōu)路徑。

i.逐個判斷node到機會點的最短距離是否在N分鐘行駛距離范圍內(nèi)；Yes則保留，No則舍棄。再根據(jù)N分鐘行駛距離求出路徑上的極值nodes。

ii.考慮實際行駛過程道路參數(shù)、小區(qū)參數(shù)，對nodes再次篩選。并再次計算N分鐘行駛距離的極值nodes。

（4）將保留的點做最小覆蓋多邊形，得到N分鐘商圈范圍。

（5）對N分鐘商圈進行修正。對于位于商圈邊界附件的小區(qū)，只要小區(qū)和N分鐘商圈范圍相交，就將該小區(qū)包含于商圈之中。

4 結(jié)束語

本文基于最優(yōu)路徑算法，設(shè)計了在快餐業(yè)配送過程中最佳送餐路徑問題，并且通過該算法的研究，進一步利用最佳送餐路徑算法應(yīng)用于訂餐送餐服務(wù)，提升了快餐業(yè)的服務(wù)質(zhì)量和工作效率。由于送餐路徑問題是一個非常復(fù)雜的問題，甚至行業(yè)內(nèi)的不同市場定位的快餐企業(yè)所考慮的因素都不會完全相同，所以，本文只能結(jié)合送餐服務(wù)的通用特點，設(shè)計了與送餐相關(guān)的影響因子，使其與實際結(jié)合更加密切。

參考文獻

[1]魏海平，等.顧及交通時態(tài)屬性的最優(yōu)路徑算法與實現(xiàn)[J].測繪學(xué)院學(xué)報，2004，21（3）：69-72.

[2]陳玉敏，等.多級道路的最優(yōu)路徑算法研究[J].武漢大學(xué)學(xué)報.信息科學(xué)版，2006，25（1）：70-73.

[3]吳正明，等.基于實時交通最優(yōu)路徑算法的研究[J].機械與電子，2001，（10）：20-22.

[4]王豐元，等.基于交通限制的路網(wǎng)最優(yōu)路徑算法[J].交通運輸工程學(xué)報，2005，5（1）：92-95.

[5]廖秋敏，等.GIS支持下的零售商圈分析研究[J].科技情報開發(fā)與經(jīng)濟，2004，14（11）：169-170.