6/6基于中國郵遞員問題的物流配送線路優化基于中國郵遞員問題的物流配送線路優化

[

回到原出發點，這樣的線路稱為歐拉圖。

定義2：設G是一個無向連通圖，若存在一個回路，經過G中的每一條邊一次且僅一次，則稱這個同路為歐拉回路：

定義3：設G足一個無向連通圖，若在G中通過某頂點的弧的個數為偶數時，這個頂點被稱為偶點，否則被稱為奇點。

定理1：一個非空連通圖是歐拉圖當且僅當它沒有奇點。定理2：一個連通圖有歐拉跡當且僅當它最多有兩個奇點。

定理3：設C是一條經過賦權連通圖C的每條邊至少一次的回路，則C是G的最優回路，當且僅當C對應的歐拉圖G滿足：

(1)G的每條邊至多重復出現一次；

(2)G的每個圈上重復出現的邊的權之和不超過該圈總權的一半。基于以上定義和定理，應用圖論描述中國郵遞員問題如下：

在一個連通圖G=(V，E)中，E中的每一條邊對應一條街道，每條邊的權重l(e)=街道的長度。v中某一個頂點為郵局，其余為街道的交叉點。在連通圖c=(V，E)上找一個圈，該圈過每邊至少一次，且圈上所有邊的權和最小。

此問題分為兩種情況：

（1）若G中的頂點均為偶點，即G中存在歐拉回路，則該回路過每條邊一次且僅一次，此回路即為所求的投遞路線；

（2）若G中有奇點，不存在歐拉回路，所投遞的路線至少有一街道要重復走一次或多次。

在G中有奇點的情況中，選擇的最佳投遞路線就等同于選擇重復邊的權和最小的路線。下面我們來介紹初始郵遞路線的確定、改進，以及一個郵遞路線是否是最優路線的判定標準的方法圖上作業法。

（1）初始郵遞路線的確定方法。

任何一個圖中，若奇點的個數為偶數，就可以把它們兩兩配成對，而每對奇點之間必有一條鏈（圖是連通的），我們把這條鏈的所有邊作為重復邊追加到圖中去，這樣得到的新連通圖必無奇點，這就給出了初始投遞路線。

如在下圖中，v1是郵局所在地，并有四個奇點v2,v4,v6,v8,將它們兩兩配對，比如v2和v4為一對，v6和v8為一對。

v7

v8

v1

v7

v8

v1

2

4

（2）改進郵遞路線，使重復邊的總長不斷減少。

一般地，在郵遞路線上，如果在邊[vi,vj]旁邊有兩條以上的重復邊，從中去掉偶數條，那么可以得到一個總長度較少的郵遞路線。根據定理3的滿足條件，在最優郵遞路線上，圖中每一個圈的重復邊的總權

小于或者等于該圈總權的一半，得出下列歐拉圈就是最優郵遞路線。

3.網絡最小樹法求解中國郵遞員問題

中國郵遞員問題簡單圖上作業法雖然最后找出了最優路線，但尋找奇點的配對關系，難免帶有一定的盲目性，不如針對這一癥結所在，盡可能地將初始方案做得好一些，以減少后期調整所出現的麻煩，這就需要考慮和利用網絡最小樹的理念。

v6v3v4

v5

v22

5594

4

34

6

44

3v9v6v3

v4

v5

v25594

436

44

3v9

v6

v4

v5

v22

5

594434

6443v9

v7v6

v3

v4

v5

v8

v1v22

559

4

4

34

6

44

3

V9v3

v1

v8

v7

管谷梅先生在1960的時候給出過求最優集的相關判定定理，然而實際操作中我們卻有更貼近實際的解決方法，這即是判優準則。以上面提到的線路為例，

演示此方法，具體的步驟如下：(1)奇點出作出標記。

(2)求該網絡最小樹(使用避圈法或是破圈法，在操作中盡可能多保留與奇點相連的邊)。

(3)在最小樹的奇點處添加添加重復邊，以消滅奇點。(4)同到原來的問題，且按判優準則。

(5)檢驗和調整，直至最優。經過判優法檢驗，可知已經為最優解，該題圓滿解決!

v7v6v3v4v5

v8v1v22559443464

43v9v7v6v3

v4

v5

v8v1v22

55

9443

4

644

3v9v7

v6

v3v4v5v8

v1

v2

2

5

5

944

3

4

6

4

4

3v9

v7v6

v3v4v5v8v1v2255944

3

464

43V9

在此尋找最優解的過程中，始終遵循的兩個準則為：準則1：最優解中重邊的重數不多于2；

準則2：最優解中每個初等圈中，重邊總權數不大于該圈總權數的一半。通過實際解決最優路徑問題發現，借助最小樹的理念處理中國郵路問題時，能夠充分的考慮原有網絡的信息，這樣在添加重邊，消失奇點的過程中可以做到有的放矢。而避免了之前使用方法局部求解導致的局限性。

當然這種方法是一種初級方案，還有待于進一步的驗證。因為在實際計算中，逐一驗證全部有效圈的工作量實在太大，作為一種很接近于求解最優解的初始解的辦法，這不失為一種不錯的方法，值得我們去使用。

4.中國郵遞員問題規劃模型的建立

在用圖上作業法求解中國郵遞員問題時，需檢查圖中的每一條回路。當圖中回路較多時，檢查不便且容易出錯。對此，受求解最短路問題的EXCEL解法的啟發，本文建立基于EXCEL的“中國郵遞員問題”的整數規劃模型。

1

,01

,01

1

.min''''''''1

.1

,==+=+<=+=++=∑∑∑∑∑∑∈∈∈∈==x

xxxxxxxxxx

cxcpq

ijn

NqpqnMjijnNqpqnMjijqppqji

ij

pq

n

qppq

ij

njiij

t

sz}{}{n

qpnjipNiMn

pnin

qpnji?=?=???

?

???==?=?=?=?=2,1,2,1,2,12,12,1,2,1,點直接相連的與直接相連的點與

式中：

的距離

到頂點的距離到頂點圖中頂點數量

型決策變量

型決策變量配送總路程

qpjinzc

cxxpq

ij

pq

ij

1010

在此模型中，將線路分為實際弧cij和虛擬弧cpq是無向的，設定0-1型決策變量xij和xpq，目標函數∑∑==+

=n

jin

qppq

pq

ijijx

cxcz1,1

.min表示為所走的實際弧和虛

擬弧的最小路程。將線路分別設為實際邊和虛擬邊，邊是有向的。約束條件

1=+x

xji

ij

表示每一條實際邊走且只能走一次。而虛擬邊的約束條件是xxqp

pq+≤1，即每條虛擬邊最多走一次。設定流入某一頂點的線路為正，而流出此頂點的線路為負，則約束條件

∑∑∑∑∈∈∈∈+=+M

jN

qpqijM

jN

qpqijxxx

x'''''''

'

是用來保證每一個頂點

流人流出的線路總和為零，即保證每一個節點為偶點。

4、應用推廣

本文研究了物流配送路徑優化問題。基于EXCEL通過構建圖書配送的中國郵遞員問題優化模型，實現了物流配送路徑的遍歷性和路程的最小化。通過本文的研究，可以在物流配送過程中節省物流配送時間，降低配送成本，也可為其它遍歷路程最小化問題路徑優化提供借鑒。。

利用中國郵遞員問題的圖上作業法或最小樹法來分析得出投遞的最優路線。在時間、路