圖論在快遞網(wǎng)點(diǎn)優(yōu)化設(shè)計(jì)中的應(yīng)用

陳艷仙

快遞作為一種新型的運(yùn)輸服務(wù)，中外有很多學(xué)者專(zhuān)家對(duì)快遞進(jìn)行了深入的研究，例如快遞路徑選擇的優(yōu)化、網(wǎng)點(diǎn)的優(yōu)化，并且相應(yīng)的給出了模型及算法，本文在前人的基礎(chǔ)上運(yùn)用圖論的知識(shí)對(duì)玉溪市個(gè)別圓通快遞選址進(jìn)行研究，網(wǎng)點(diǎn)的選址及收送包裹路徑的選擇可以規(guī)劃為收、發(fā)件的物流網(wǎng)絡(luò)優(yōu)化問(wèn)題，選址時(shí)以路徑最短所花時(shí)間最少為目標(biāo)。

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

本文運(yùn)用圖論知識(shí)對(duì)網(wǎng)點(diǎn)選址及收送包裹路徑進(jìn)行分析，運(yùn)用圖論知識(shí)已解決數(shù)學(xué)中眾多難以解決的問(wèn)題。有最先開(kāi)始的“七橋問(wèn)題”到后面的“中國(guó)郵路問(wèn)題”、“旅行售貨員問(wèn)題”都得到了很好的解決，從中我們可以看出圖論在解決實(shí)際問(wèn)題中存在巨大的價(jià)值，現(xiàn)階段我們?cè)谇叭搜芯康幕A(chǔ)上運(yùn)用圖論知識(shí)對(duì)小范圍的快遞網(wǎng)點(diǎn)進(jìn)行選址分析。

圖論知識(shí)背景

圖論創(chuàng)建于18世紀(jì)30年代，二百多年來(lái)經(jīng)過(guò)幾代人的不懈努力，使圖論發(fā)展成為重要的數(shù)學(xué)分支。圖論的不少研究成果具有很高的實(shí)用價(jià)值，它們?cè)诟鱾€(gè)科技領(lǐng)域（包括計(jì)算機(jī)科學(xué)理論和技術(shù)）都有廣泛的用途。在離散數(shù)學(xué)的領(lǐng)域中，圖論知識(shí)的運(yùn)用占有一定的主導(dǎo)地位，在解決實(shí)際問(wèn)題方面，圖論的運(yùn)用也具有直觀(guān)、清晰、簡(jiǎn)捷等特點(diǎn)，現(xiàn)實(shí)生活中的許多問(wèn)題可以轉(zhuǎn)化為等價(jià)的圖論問(wèn)題而得到解決。圖論知識(shí)具有廣泛的應(yīng)用價(jià)值，圖論可將各種復(fù)雜的工程系統(tǒng)和管理問(wèn)題用“圖”來(lái)描述，進(jìn)而設(shè)計(jì)算法求得最優(yōu)結(jié)果，給管理者提供最優(yōu)化的方案。圖論中研究的“圖”是由若干頂點(diǎn)（表示事物）和若干邊（表示事物之間的一定關(guān)系）。圖論中的“圖”的頂點(diǎn)位置、邊的長(zhǎng)短之間沒(méi)有太大關(guān)系，一般可以設(shè)定邊的不同權(quán)值來(lái)表示頂點(diǎn)之間的簡(jiǎn)單關(guān)系的強(qiáng)度。圖論知識(shí)作為離散數(shù)學(xué)重要的組成部分，已經(jīng)成為當(dāng)前算法設(shè)計(jì)中一項(xiàng)重要內(nèi)容，圖論和算法問(wèn)題之間有著密切聯(lián)系，事實(shí)上，許多算法問(wèn)題大多數(shù)都直接或間接地和圖有關(guān)。

模型的假設(shè)

僅在一定的備選取地點(diǎn)范圍內(nèi)考慮新的快遞網(wǎng)點(diǎn)的配置；不考慮各小區(qū)與網(wǎng)點(diǎn)的實(shí)際覆蓋面積，簡(jiǎn)化為點(diǎn)處理；每個(gè)小區(qū)的快遞包裹是快遞員送至小區(qū)門(mén)衛(wèi)處，同時(shí)由快遞員收件帶走；在現(xiàn)有小區(qū)與網(wǎng)點(diǎn)的基礎(chǔ)上拆分優(yōu)化網(wǎng)點(diǎn)位置；用戶(hù)的需求量按區(qū)域總計(jì)；假定路況一致，快遞員在途中按照規(guī)定的速度勻速行使。

問(wèn)題重述

問(wèn)題背景?，F(xiàn)下社會(huì)經(jīng)濟(jì)飛速發(fā)展，電子商務(wù)迅猛崛起，物流業(yè)面臨機(jī)遇的同時(shí)亦面臨巨大的挑戰(zhàn)，尤其是占物流比例居多的快遞行業(yè)，為了使快遞行業(yè)平穩(wěn)的發(fā)展，進(jìn)一步提高快遞企業(yè)的服務(wù)質(zhì)量和水平，為客戶(hù)提供更加舒適合理的服務(wù)平臺(tái)，提高快遞企業(yè)的收益，同時(shí)滿(mǎn)足客戶(hù)時(shí)效需要與費(fèi)用要求，快遞行業(yè)必須以降低成本、提高效率、提升覆蓋率來(lái)提高自身的競(jìng)爭(zhēng)力，而合理的選擇快遞網(wǎng)點(diǎn)、降低快遞網(wǎng)點(diǎn)所需成本、規(guī)劃快遞網(wǎng)點(diǎn)規(guī)模和數(shù)量進(jìn)而降低快遞企業(yè)運(yùn)營(yíng)成本及運(yùn)輸貨物費(fèi)用，提高快遞企業(yè)的總收益，并且在最短的時(shí)間內(nèi)滿(mǎn)足客戶(hù)的需求，為客戶(hù)提供最為優(yōu)質(zhì)的服務(wù)是快遞企業(yè)當(dāng)前的首要目標(biāo)。

問(wèn)題的提出。我們對(duì)玉溪市紅塔區(qū)的部分有代表性的區(qū)域進(jìn)行了走訪(fǎng)調(diào)查，對(duì)玉溪市紅塔區(qū)龍馬路56號(hào)北苑區(qū)總店、玉溪市紅塔區(qū)康井路28號(hào)圓通快遞這兩個(gè)網(wǎng)點(diǎn)獲取了比較詳細(xì)的相關(guān)數(shù)據(jù)。下面我們以第一個(gè)網(wǎng)點(diǎn)的優(yōu)化為例，講述分析、建模、求解的過(guò)程。男一個(gè)網(wǎng)點(diǎn)的優(yōu)化求解作為模型的應(yīng)用放在第6節(jié)。

玉溪市紅塔區(qū)龍馬路56號(hào)北苑區(qū)總店（現(xiàn)有網(wǎng)點(diǎn)）業(yè)務(wù)范圍內(nèi)的區(qū)域中共有11個(gè)地點(diǎn)（10個(gè)單位或小區(qū)，1個(gè)快遞網(wǎng)點(diǎn)），分別用A，B，C，…，I，J，O來(lái)標(biāo)記。任何兩個(gè)小區(qū)之間都是相通的，只是有小區(qū)是有道路直接相連，有的是通過(guò)其他小區(qū)聯(lián)系在一起，各個(gè)小區(qū)對(duì)應(yīng)詳細(xì)相關(guān)數(shù)據(jù)如下：

對(duì)于每個(gè)地區(qū)網(wǎng)點(diǎn)的建立與否，可以通過(guò)計(jì)算到網(wǎng)點(diǎn)的距離最短或是小區(qū)間的最短送貨路線(xiàn)來(lái)確定，然后充分利用小區(qū)的包裹數(shù)量以及小區(qū)間的路線(xiàn)數(shù)據(jù)，采用合適的方法搜索網(wǎng)點(diǎn)，求得最優(yōu)解。本文主要解決以下兩個(gè)問(wèn)題，選取最優(yōu)網(wǎng)點(diǎn)。

問(wèn)題一：利用優(yōu)化模型檢測(cè)當(dāng)前網(wǎng)點(diǎn)是否是所管轄的區(qū)域的最優(yōu)網(wǎng)點(diǎn)；

問(wèn)題二：從n個(gè)小區(qū)組成區(qū)域內(nèi)中，選出兩個(gè)最優(yōu)點(diǎn)設(shè)立網(wǎng)點(diǎn)，建立網(wǎng)點(diǎn)網(wǎng)絡(luò)，實(shí)現(xiàn)快遞員收送包裹的路線(xiàn)總距離最??；

模型的建立

本文采用優(yōu)化的Flovd-Warshall算法計(jì)算出小區(qū)間最短路線(xiàn)矩陣，再用0-1整數(shù)規(guī)劃的窮舉法獲得模型目標(biāo)函數(shù)的最優(yōu)解，選取最優(yōu)網(wǎng)點(diǎn)。

利用小區(qū)間路線(xiàn)數(shù)據(jù)。進(jìn)而構(gòu)造鄰接矩陣L：

若小區(qū)j和J間沒(méi)有直接相連的路線(xiàn)，則令（1，J）元素a_ij為正無(wú)窮大；否則a_ij（j=1，2，…，n，j=1，2，…，n）為j和J直接相連的路線(xiàn)長(zhǎng)度。

模型的求解

問(wèn)題一優(yōu)化檢測(cè)模型根據(jù)MATLAB程序及LINGO程序求解運(yùn)行結(jié)果分析確定玉溪市紅塔區(qū)龍馬路56號(hào)北苑區(qū)總店（現(xiàn)有網(wǎng)點(diǎn)）是其所管轄區(qū)域內(nèi)的最優(yōu)網(wǎng)點(diǎn)，包裹數(shù)量加權(quán)總路線(xiàn)長(zhǎng)度為143620米。

問(wèn)題二網(wǎng)點(diǎn)拆分模型在現(xiàn)有網(wǎng)點(diǎn)的管轄區(qū)域內(nèi)新建網(wǎng)點(diǎn)達(dá)到縮短路線(xiàn)距離，提高運(yùn)營(yíng)效率的目的，根據(jù)MATLAB程序及LINGO程序求解運(yùn)行結(jié)果分析確定當(dāng)前網(wǎng)點(diǎn)北苑區(qū)總店和公安局生活二區(qū)為網(wǎng)點(diǎn)拆分后的最優(yōu)網(wǎng)點(diǎn)，優(yōu)化后的包裹數(shù)量加權(quán)總路線(xiàn)距離為112520.0米。網(wǎng)點(diǎn)拆分后二者所管轄的區(qū)域如下：

模型的應(yīng)用——另一個(gè)網(wǎng)點(diǎn)的優(yōu)化

本文選取玉溪市紅塔區(qū)康井路28號(hào)圓通快遞針對(duì)問(wèn)題一、二的模型進(jìn)行檢驗(yàn)分析，調(diào)查數(shù)據(jù)類(lèi)型與玉溪市紅塔區(qū)龍馬路56號(hào)北苑區(qū)總店相一致。

根據(jù)我們調(diào)查收集整理的數(shù)據(jù)用MATLAB程序及LINGO程序求解運(yùn)行結(jié)果分析確定玉溪市紅塔區(qū)康井路28號(hào)快遞網(wǎng)點(diǎn)為所管轄區(qū)域的最優(yōu)網(wǎng)點(diǎn)，并知現(xiàn)有網(wǎng)點(diǎn)的包裹數(shù)量加權(quán)總路線(xiàn)長(zhǎng)度為45100米。

網(wǎng)點(diǎn)拆分模型檢驗(yàn)根據(jù)MATLAB程序及LINGO程序求解運(yùn)行結(jié)果分析確定康井路28號(hào)和鄉(xiāng)鎮(zhèn)小區(qū)為網(wǎng)點(diǎn)拆分后的最優(yōu)網(wǎng)點(diǎn)，優(yōu)化后的包裹數(shù)量加權(quán)總路線(xiàn)距離為22410.0米。網(wǎng)點(diǎn)拆分后二者所管轄的區(qū)域如下：

模型的評(píng)價(jià)與推廣

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

除了選擇合適的快遞網(wǎng)址得以提高經(jīng)濟(jì)效益及服務(wù)效益外，還可以根據(jù)當(dāng)?shù)鼐W(wǎng)址的實(shí)際情況定制相應(yīng)包裹收送計(jì)劃，進(jìn)行合理計(jì)劃收送，把包裹客戶(hù)按地區(qū)、包裹數(shù)量分為不同的層次，再按包裹客戶(hù)層次等分將包裹進(jìn)行分揀，根據(jù)合理快捷收送路線(xiàn)，進(jìn)行送貨服務(wù)，讓包裹到達(dá)客戶(hù)手中定時(shí)化、高效化。除此之外，網(wǎng)點(diǎn)與網(wǎng)點(diǎn)之間還應(yīng)進(jìn)行業(yè)務(wù)聯(lián)合，發(fā)展聯(lián)合收送包裹業(yè)務(wù)，可以達(dá)到降低快遞收送成本，緩和交通擁堵。實(shí)行多家快遞企業(yè)擁有共同倉(cāng)庫(kù)，以提高分揀，備貨的效益。

本文使用的兩個(gè)模型應(yīng)用范圍較為廣泛，可在處理及簡(jiǎn)化圖形數(shù)據(jù)方面將該模型作為參考。此模型不僅適用于快遞網(wǎng)點(diǎn)檢測(cè)及拆分問(wèn)題，對(duì)規(guī)劃問(wèn)題的求解起到一定的指導(dǎo)意義?？梢赃\(yùn)用到其他的一些服務(wù)業(yè)的選址中，在使用過(guò)程中具體的約束條件及所要達(dá)到的效果需要具體考慮。