快遞員最優(yōu)送貨路線研究

張東翰，趙銳

（商洛學院 數(shù)學與計算機應用學院，陜西商洛 726000）

現(xiàn)今，各種購物網(wǎng)站應有盡有，人們在家就可以購買各種生活用品，這給廣大消費者帶來了便利，也為快遞公司的發(fā)展提供了機遇。然而，放眼于當今中國快遞行業(yè)的發(fā)展，送貨效率的高低已成為快遞公司生存與發(fā)展的決定因素之一，送貨路線的選擇是影響送貨效率的主要因素之一，快遞公司要想在巨大的競爭潮流中站穩(wěn)腳跟，獲得更多的效益和長遠的發(fā)展，必須在一定的硬件條件下，巧妙地借助信息技術和數(shù)學方法，為其快遞員制定一套具體可行的送貨路線方案。對于最優(yōu)路線的研究，目前已有許多專家學者做了大量的工作，包括模型的建立，計算方法的改進和問題的變形與推廣。大多數(shù)研究都是利用中國郵遞員問題的知識建立相關的模型，并對路線優(yōu)化給出了許多不同的算法，例如，貪心算法，匹配算法，動態(tài)規(guī)劃算法和構造法等[1-9]。本文以商洛市商州區(qū)為研究對象，根據(jù)中國郵遞員問題的相關理論[10-11]，對送貨員的送貨路線進行了研究，得到了商州區(qū)快遞員送貨的最優(yōu)路線，同時也為其他區(qū)域的最優(yōu)路線研究提供了理論參考。

1 商州區(qū)主要街道分布

通過對商州區(qū)人口密集分布的街道進行研究和分析，得知商州區(qū)繁華的街道有文衛(wèi)路，團結路，西街，東街，西背街，東背街，中心街，工農(nóng)路，西關，東關，金鳳路，假定送貨點分布在各個道路上的，可將快遞員送貨路線必須經(jīng)過送貨點的問題轉化成經(jīng)過送貨點的所在道路的問題即快遞員必須經(jīng)過他負責區(qū)域的所有路線，以最快的速度完成所有的送貨。對于這個問題的研究，僅以中心廣場區(qū)域為例進行路線優(yōu)化研究。

2 快遞員送貨路線問題分析

本研究利用谷歌地球軟件將快遞公司所管轄的區(qū)域各街道繪制出來，并結合百度地圖測距工具以及谷歌地球的測量功能將實際長度測量出來（如圖1 所示），再在考察路線的實際情況的基礎上，運用相關的求最短路的方法對路線進行優(yōu)化，最終得出快遞員送貨的最優(yōu)路線。

圖1 快遞員最優(yōu)路線問題分析流程圖

3 模型建立

3.1 模型假設

結合商州區(qū)快遞員送貨的特點，僅以商州區(qū)中心廣場這個區(qū)域為例建立模型，建立模型前有以下假設：

1）假設該區(qū)域內快遞員的送貨點（即接收人的接收點）在各條路線上是均勻分布的。

2）假設該區(qū)域快遞員的送貨量在配送車的車載量以內。即快遞員從起點出發(fā)，走完所負責區(qū)域的所有路線，完成所有的送貨量。

3.2 實際的路線轉化成平面圖形

3.2.1 實際的道路信息轉化成虛擬的平面圖形

忽略各個道路的寬度，形狀，將它抽象成直線，將各個道路的交叉點同樣抽象成一個點，使整條路拆分成不再有交叉口的平面圖。對于彎曲的街道，可以根據(jù)實際情況將它拉伸成一條直線或者轉化成一個點。比如，中心廣場這塊道路的信息處理，由于中心廣場是一個圓盤，圓盤連接北新街東段，北新街中段，中心街和和平路四個方向的道路，為了方便計算，將中心廣場抽象成一個點，將中心廣場與四條道路的交點延長交匯成一點（以兩旁的圓盤實際長度的平均值增加到該道路中）。

3.2.2 測量距離

利用谷歌地圖軟件和百度地圖將路線繪制并測量出來，再在增加路線長度的基礎之上，就可以得到圖2 和圖3 所示的路線賦權圖。

圖2 含中心廣場的賦權路線圖

3.3 路線模型分析

如果只考慮快遞員送貨的路線，解決此問題的方法是將問題轉化成中國郵遞員問題來求解。在圖3 中，快遞員無論在那個點出發(fā)，只要經(jīng)過所有的路線至少一次，并且所走的路線總路程最短。因此，快遞員的出發(fā)點，快遞公司可根據(jù)自身的具體情況可任意選一點。

經(jīng)過對問題的分析，可以將快遞員送貨路線模型的研究轉化為對解決帶有附加條件的中國郵遞員問題的研究。因此，本研究內容可以用圖論語言敘述為：在路線賦權圖G 中，尋找一條回路c，使c 包含的每條邊至少一次且回路c 的長度最短。

如果此非負賦權圖G 是歐拉圖，則只要找出它的歐拉環(huán)游，就得到了最優(yōu)路線。如果非負賦權圖G 不是歐拉圖，即圖G 中有奇度數(shù)結點，可以通過添加重復邊的方法，使圖G 擴充為一個歐拉圖G*，并且使得圖G 中各邊的權值和盡可能的小，可用Fluery 算法求出G*的歐拉環(huán)游，從而得出最優(yōu)路線。

圖3 簡化后的賦權路線圖

4 模型求解

4.1 賦權路線圖轉化成歐拉圖

在問題分析中，可知解決快遞員最優(yōu)送貨路線問題的思路可分為兩種情況：一種是圖G 中沒有奇度數(shù)結點，此時圖G 是歐拉圖。歐拉環(huán)游就是最小的送貨路線。另一種是圖G 中含有奇度數(shù)結點，如果圖G 有兩個奇度數(shù)結點時，找出這兩個點間的最短路并加入圖G 中，此時得到的圖為歐拉圖，圖中的歐拉環(huán)游就是最小送貨路線，如果圖G 中的奇度數(shù)結點大于兩個時，需要對這些奇度數(shù)結點進行配對，將這些奇度數(shù)結點（奇度數(shù)結點的個數(shù)為偶數(shù)）間的最短路加入圖G 中，得到的歐拉圖中的歐拉環(huán)游就是快遞員最小的送貨路線。

通過對簡化后的賦權路線圖（圖3）的分析，發(fā)現(xiàn)具有奇度數(shù)的結點有12 個，分別為B 點，T點，V 點，D 點，E 點，G 點，I 點，K 點，M 點，Y 點，N點，X 點。圖G中有大于兩個奇度數(shù)結點時，存在奇度數(shù)結點兩兩配對的方案共有顯然，用原始的計算兩兩點間距離的配對辦法工作量巨大，不科學。因此，采用在圖3 中加邊的方法對這12 個點進行配對。具體方法如下：

1）將這12 個點人工進行初步配對，配對的原則是尋找距離最近的兩點進行連接，比如離B點最近的點是T 點，依據(jù)此法將剩下的10 個點配對，配對的結果如圖4 所示。

2）初步配對好后，在含有配對兩點的最小歐拉圈中比較其權值是否小于其它幾條權值和的一半。如果小于，將這兩點的配對先確定下來。如果大于，將這兩點的配對去掉，把連接這兩點剩余的幾條邊相連接，再用這一步的方法進行判斷，直到完成最終的配對。此時得到的12 個點的連接就是遍歷這12 個點的最短路，最終配對的結果如圖5 所示。

由圖5 可知，送貨路線添加了8 條重復弧。根據(jù)Dijkstra 算法可以驗證，這8 條弧是經(jīng)過12個奇度數(shù)結點最短的路徑。

4.2 Fleury算法

步驟1：令圖G 中所有點的集合為V(G)，所有邊的集合為E(G)，在V(G)中選任意一點v0,w0=v0。

步驟2：設途徑已經(jīng)選定，則wt=v0v1v2…vt從E(G)-E(W)中選取一條邊 ei+1，使得 ei+1與 vi相關聯(lián)，且除非已經(jīng)沒有選擇的余地，否則不要選E(G)-E(W)的割邊。

步驟3：反復的執(zhí)行第二步，直到所有的邊都被選到為止。如此得到的wt=v0v1v2…vt就是圖G的歐拉環(huán)游。

需要注意：按照Fleury 算法尋找歐拉環(huán)游時，首次從起點出發(fā)，每次選定的下一個點盡量是沒有被選過的點，直到選完所有的點第一次回到起點。然后再從起點出發(fā)按照此方法，直到所有的邊都被選完，最終回到起點。

圖4 人工初步配對后的賦權圖

圖5 賦權路線圖轉化成歐拉圖

4.3 最優(yōu)路線方案

假設快遞員送貨的起點在I 點。因此，利用Fleury 算法步驟得到圖5 的歐拉環(huán)游為：W=IZKMYXNPQBTVDWD1EGD1ZIGD1EDBTQVWPXNMYZKI。

將上面找到的歐拉環(huán)游還原到圖2 中，得到了中心廣場區(qū)域快遞員最優(yōu)送貨路線的方案是：

從宏影路與北新街東段的交匯處（起點）—中心廣場東側—宏影路—和平路—金鳳路—金鳳路與北新街中段的交匯處—北新街中段—北新街中段與迎賓路的交匯處—迎賓路—府前路—府前路與人民路的交匯處—人民路—人民路與北新街中段的交匯處—北新街中段—北新街中段與文衛(wèi)路的交匯處—文衛(wèi)路—文衛(wèi)路與團結路的交匯處—團結路—團結路與工農(nóng)路的交匯點—工農(nóng)路—西關與西街的交匯處—工農(nóng)路—工農(nóng)路與西背街的交匯處—西背街—西背街與中心街的交匯處—中心街—西街與東街的交匯處—東街—東環(huán)路—東環(huán)路與東背街的交匯處—東背街——東背街與中心街的交匯處—中心街—中心廣場的西側—中心廣場的東側—宏影路與北新街東段的交匯處（起點）—北新街東段—東環(huán)路—東環(huán)路與東背街的交匯處—東背街—東背街與中心街的交匯處—中心街—中心街與西街的交匯處—西街—西關—西關與文衛(wèi)路的交匯處—文衛(wèi)路—團結路與文衛(wèi)路的交匯處—團結路（從文衛(wèi)路與團結路交匯點向東走第一個路口）—蘇尚巷與北新街中段的交匯處—蘇尚巷—團結路（從文衛(wèi)路與團結路交匯點向東走第二個路口）—團結路—工農(nóng)路與團結路的交匯處—工農(nóng)路與北新街中段的交匯處—北新街中段—北新街與迎賓路的交匯處—迎賓路—府前路—府前路與金鳳路的交匯處—金鳳路—北新街中段—中心廣場西側—戲鄉(xiāng)巷—戲鄉(xiāng)巷與和平路的交匯處—戲鄉(xiāng)巷—北新街東段—宏影路與北新街東段的交匯處。

5 結語

該模型以商洛市商州區(qū)為研究對象，從實際問題出發(fā)，容易理解與靈活應用，不僅可以為快遞員節(jié)省送貨時間，降低送貨成本，減輕快遞員每天的工作量，使快遞公司的運行更加高效，更能帶動商州區(qū)的經(jīng)濟發(fā)展，具有一定的實用性和較強的推廣性，而且也為現(xiàn)實中其它路線優(yōu)化提供了一定的理論基礎和參考依據(jù)。