圖論在快遞網點優化設計中的應用

陳艷仙

快遞作為一種新型的運輸服務，中外有很多學者專家對快遞進行了深入的研究，例如快遞路徑選擇的優化、網點的優化，并且相應的給出了模型及算法，本文在前人的基礎上運用圖論的知識對玉溪市個別圓通快遞選址進行研究，網點的選址及收送包裹路徑的選擇可以規劃為收、發件的物流網絡優化問題，選址時以路徑最短所花時間最少為目標。

縱觀玉溪市近幾年的快遞企業發展，玉溪市每年的快遞累計完成業務量逐年增加，同比增長也越來越大，經濟增長比也是逐年增加，玉溪市快遞業持續保持平穩發展，快遞服務業普遍滿足快遞市場的基本需求，隨著快遞市場需求的快速增長，業務規模不斷擴大，快遞企業不斷增多，市場主體不斷優化，業務轉型持續改善，快遞行業整體實力進一步增強。整個快遞行業發展呈現快中趨穩的現象，快遞行業具有產業結構不斷更新優化，能力轉換不斷持續加快的特點，使得快遞服務業對經濟社會發展的基礎性作用進一步增強，快遞行業的經濟影響力逐漸擴大。快遞服務業通過不斷完善自身、規范經營模式、提高服務水平和質量等一些方式，對自身進行不斷地優化完善，在做好服務的基礎上努力保證自己快遞種類的優勢與市場份額，并積極尋求更大的市場，這就需要運用將所學的理論知識對快遞網址及路徑在各方面的條件下進行優化以保持本快遞的優勢在競爭的潮流中屹立不倒。

本文運用圖論知識對網點選址及收送包裹路徑進行分析，運用圖論知識已解決數學中眾多難以解決的問題。有最先開始的“七橋問題”到后面的“中國郵路問題”、“旅行售貨員問題”都得到了很好的解決，從中我們可以看出圖論在解決實際問題中存在巨大的價值，現階段我們在前人研究的基礎上運用圖論知識對小范圍的快遞網點進行選址分析。

圖論知識背景

圖論創建于18世紀30年代，二百多年來經過幾代人的不懈努力，使圖論發展成為重要的數學分支。圖論的不少研究成果具有很高的實用價值，它們在各個科技領域（包括計算機科學理論和技術）都有廣泛的用途。在離散數學的領域中，圖論知識的運用占有一定的主導地位，在解決實際問題方面，圖論的運用也具有直觀、清晰、簡捷等特點，現實生活中的許多問題可以轉化為等價的圖論問題而得到解決。圖論知識具有廣泛的應用價值，圖論可將各種復雜的工程系統和管理問題用“圖”來描述，進而設計算法求得最優結果，給管理者提供最優化的方案。圖論中研究的“圖”是由若干頂點（表示事物）和若干邊（表示事物之間的一定關系）。圖論中的“圖”的頂點位置、邊的長短之間沒有太大關系，一般可以設定邊的不同權值來表示頂點之間的簡單關系的強度。圖論知識作為離散數學重要的組成部分，已經成為當前算法設計中一項重要內容，圖論和算法問題之間有著密切聯系，事實上，許多算法問題大多數都直接或間接地和圖有關。

模型的假設

僅在一定的備選取地點范圍內考慮新的快遞網點的配置；不考慮各小區與網點的實際覆蓋面積，簡化為點處理；每個小區的快遞包裹是快遞員送至小區門衛處，同時由快遞員收件帶走；在現有小區與網點的基礎上拆分優化網點位置；用戶的需求量按區域總計；假定路況一致，快遞員在途中按照規定的速度勻速行使。

問題重述

問題背景。現下社會經濟飛速發展，電子商務迅猛崛起，物流業面臨機遇的同時亦面臨巨大的挑戰，尤其是占物流比例居多的快遞行業，為了使快遞行業平穩的發展，進一步提高快遞企業的服務質量和水平，為客戶提供更加舒適合理的服務平臺，提高快遞企業的收益，同時滿足客戶時效需要與費用要求，快遞行業必須以降低成本、提高效率、提升覆蓋率來提高自身的競爭力，而合理的選擇快遞網點、降低快遞網點所需成本、規劃快遞網點規模和數量進而降低快遞企業運營成本及運輸貨物費用，提高快遞企業的總收益，并且在最短的時間內滿足客戶的需求，為客戶提供最為優質的服務是快遞企業當前的首要目標。

問題的提出。我們對玉溪市紅塔區的部分有代表性的區域進行了走訪調查，對玉溪市紅塔區龍馬路56號北苑區總店、玉溪市紅塔區康井路28號圓通快遞這兩個網點獲取了比較詳細的相關數據。下面我們以第一個網點的優化為例，講述分析、建模、求解的過程。男一個網點的優化求解作為模型的應用放在第6節。

玉溪市紅塔區龍馬路56號北苑區總店（現有網點）業務范圍內的區域中共有11個地點（10個單位或小區，1個快遞網點），分別用A，B，C，…，I，J，O來標記。任何兩個小區之間都是相通的，只是有小區是有道路直接相連，有的是通過其他小區聯系在一起，各個小區對應詳細相關數據如下：

對于每個地區網點的建立與否，可以通過計算到網點的距離最短或是小區間的最短送貨路線來確定，然后充分利用小區的包裹數量以及小區間的路線數據，采用合適的方法搜索網點，求得最優解。本文主要解決以下兩個問題，選取最優網點。

問題一：利用優化模型檢測當前網點是否是所管轄的區域的最優網點；

問題二：從n個小區組成區域內中，選出兩個最優點設立網點，建立網點網絡，實現快遞員收送包裹的路線總距離最小；

模型的建立

本文采用優化的Flovd-Warshall算法計算出小區間最短路線矩陣，再用0-1整數規劃的窮舉法獲得模型目標函數的最優解，選取最優網點。

利用小區間路線數據。進而構造鄰接矩陣L：

若小區j和J間沒有直接相連的路線，則令（1，J）元素a_ij為正無窮大；否則a_ij（j=1，2，…，n，j=1，2，…，n）為j和J直接相連的路線長度。

模型的求解

問題一優化檢測模型根據MATLAB程序及LINGO程序求解運行結果分析確定玉溪市紅塔區龍馬路56號北苑區總店（現有網點）是其所管轄區域內的最優網點，包裹數量加權總路線長度為143620米。

問題二網點拆分模型在現有網點的管轄區域內新建網點達到縮短路線距離，提高運營效率的目的，根據MATLAB程序及LINGO程序求解運行結果分析確定當前網點北苑區總店和公安局生活二區為網點拆分后的最優網點，優化后的包裹數量加權總路線距離為112520.0米。網點拆分后二者所管轄的區域如下：

模型的應用——另一個網點的優化

本文選取玉溪市紅塔區康井路28號圓通快遞針對問題一、二的模型進行檢驗分析，調查數據類型與玉溪市紅塔區龍馬路56號北苑區總店相一致。

根據我們調查收集整理的數據用MATLAB程序及LINGO程序求解運行結果分析確定玉溪市紅塔區康井路28號快遞網點為所管轄區域的最優網點，并知現有網點的包裹數量加權總路線長度為45100米。

網點拆分模型檢驗根據MATLAB程序及LINGO程序求解運行結果分析確定康井路28號和鄉鎮小區為網點拆分后的最優網點，優化后的包裹數量加權總路線距離為22410.0米。網點拆分后二者所管轄的區域如下：

模型的評價與推廣

本文在基于所處的環境條件下考慮到的因素略有所不足，除本文考慮到的因素外也可以考慮一些其他的因素比如：各家快遞企業之間合作收送件目的、人口數量、居民自主取件、快遞網點附近是否有停車場、停車數量及時間等等。

除了選擇合適的快遞網址得以提高經濟效益及服務效益外，還可以根據當地網址的實際情況定制相應包裹收送計劃，進行合理計劃收送，把包裹客戶按地區、包裹數量分為不同的層次，再按包裹客戶層次等分將包裹進行分揀，根據合理快捷收送路線，進行送貨服務，讓包裹到達客戶手中定時化、高效化。除此之外，網點與網點之間還應進行業務聯合，發展聯合收送包裹業務，可以達到降低快遞收送成本，緩和交通擁堵。實行多家快遞企業擁有共同倉庫，以提高分揀，備貨的效益。

本文使用的兩個模型應用范圍較為廣泛，可在處理及簡化圖形數據方面將該模型作為參考。此模型不僅適用于快遞網點檢測及拆分問題，對規劃問題的求解起到一定的指導意義。可以運用到其他的一些服務業的選址中，在使用過程中具體的約束條件及所要達到的效果需要具體考慮。