基于最優路徑算法的快餐配送路徑優化問題研究

柯小波

摘 要：隨著快餐業的迅速發展，對快餐業中快餐配送問題的算法研究就愈發重要，快餐的配送問題，本質上就是最優路徑問題，現在分析一種最優路徑算法的基礎上，結合快餐配送的諸多影響因子，對算法進行了優化。

關鍵詞：最優路徑算法，快餐配送；研究

1 引言

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

目前傳統的最優路徑算法通常將路網模型理想化處理，實用性教差。較少考慮實際行駛過程中的道路屬性，如道路限速、紅綠燈、道路等級[2]、道路阻值、交通工具限制等。或者考慮不夠全面。

2 最優路徑算法優化研究

2.1 傳統最優路徑算法的優化

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

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

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

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

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

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

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

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

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

另外，為了提高系統的性能，對兩兩小區質心點間的路徑、路徑距離、通行時間，調用路網分析算法進行預先計算，結果存儲在表中。

3 實際應用分析

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

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

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

（2）搜索映射點和nodes（道路節點），搜索出所有的小區道路映射點和nodes。

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

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

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

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

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

4 結束語

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

參考文獻

[1]魏海平，等.顧及交通時態屬性的最優路徑算法與實現[J].測繪學院學報，2004，21（3）：69-72.

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

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

[4]王豐元，等.基于交通限制的路網最優路徑算法[J].交通運輸工程學報，2005，5（1）：92-95.

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