快遞員最優送貨路線研究

張東翰，趙銳

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

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

1 商州區主要街道分布

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

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

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

圖1 快遞員最優路線問題分析流程圖

3 模型建立

3.1 模型假設

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

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

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

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

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

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

3.2.2 測量距離

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

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

3.3 路線模型分析

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

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

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

圖3 簡化后的賦權路線圖

4 模型求解

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

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

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

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

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

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

4.2 Fleury算法

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

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

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

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

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

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

4.3 最優路線方案

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

將上面找到的歐拉環游還原到圖2 中，得到了中心廣場區域快遞員最優送貨路線的方案是：

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

5 結語

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