張東翰，趙銳

（商洛學(xué)院 數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛 726000）

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

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

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

2 快遞員送貨路線問(wèn)題分析

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

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

3 模型建立

3.1 模型假設(shè)

結(jié)合商州區(qū)快遞員送貨的特點(diǎn)，僅以商州區(qū)中心廣場(chǎng)這個(gè)區(qū)域?yàn)槔⒛Ｐ停⒛Ｐ颓坝幸韵录僭O(shè)：

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

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

3.2 實(shí)際的路線轉(zhuǎn)化成平面圖形

3.2.1 實(shí)際的道路信息轉(zhuǎn)化成虛擬的平面圖形

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

3.2.2 測(cè)量距離

利用谷歌地圖軟件和百度地圖將路線繪制并測(cè)量出來(lái)，再在增加路線長(zhǎng)度的基礎(chǔ)之上，就可以得到圖2 和圖3 所示的路線賦權(quán)圖。

圖2 含中心廣場(chǎng)的賦權(quán)路線圖

3.3 路線模型分析

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

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

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

圖3 簡(jiǎn)化后的賦權(quán)路線圖

4 模型求解

4.1 賦權(quán)路線圖轉(zhuǎn)化成歐拉圖

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

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

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

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

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

4.2 Fleury算法

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

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

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

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

圖4 人工初步配對(duì)后的賦權(quán)圖

圖5 賦權(quán)路線圖轉(zhuǎn)化成歐拉圖

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

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

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

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

5 結(jié)語(yǔ)

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