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

柯小波

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）計(jì)算最優(yōu)路徑。遍歷道路上的nodes，計(jì)算機(jī)會(huì)點(diǎn)到各nodes的最優(yōu)路徑。

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)

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

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

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

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

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