1、快遞員配送路線優化模型摘要如今，隨著網上購物的流行， 快遞物流行業在面臨機遇的同時也需要不斷迎 接新的挑戰。 如何能夠提高物流公司的配送效率并降低配送過程中的成本， 已成 為急需我們解決的一個問題。 下面，本文將針對某公司的一名配送員在配送貨物 過程中遇到的三個問題進行討論及解答。對于問題一， 由于快遞員的平均速度及在各配送點停留的時間已知， 故可將 最短時間轉換為最短路程。在此首先通過 Floyd 求最短路的算法，利用 Matlab 程序將倉庫點和所有配送點間兩兩的最短距離求解出來， 將出發點與配送點結合 起來構造完備加權圖，由完備加權圖確定初始H圈，列出該初始H圈加點序的距 離矩陣，然后使

2、用二邊逐次修正法對矩陣進行翻轉， 可以求得近似最優解的距離 矩陣，從而確定近似的最佳哈密爾頓圈，即最佳配送方案。對于問題二， 依舊可以將時間問題轉化為距離問題。 利用問題一中所建立的 模型，加入一個新的時間限制條件，即可求解出滿足條件的最佳路線。對于問題三， 送貨員因為快件載重和體積的限制， 至少需要三次才能將快件 送達。所以需要對 100件快件分區，即將 50 個配送點分成三組。利用距離矩陣 尋找兩兩之間的最短距離是 50 個配送點中最大的三組最短距離的三個點，以此 三點為基點按照準則劃分配送點。關鍵字：Floyd 算法 距離矩陣 哈密爾頓圈 二邊逐次修正法 矩陣翻轉問題重述某公司現有一配送

3、員， ，從配送倉庫出發，要將 100 件快件送到其負責的 50 個配送點。 現在各配送點及倉庫坐標已知， 貨物信息、 配送員所承載重物的最大 體積和重量、配送員行駛的平均速度已知。問題一：配送員將前 30 號快件送到并返回，設計最佳的配送方案，使得路程最 短。問題二：該派送員從上午 8：00開始配送，要求前 30號快件在指定時間前送到， 設計最佳的配送方案。問題三：不考慮所有快件送達的時間限制 ，現將 100 件快件全部送到并返回。 設計最佳的配送方案。 配送員受快件重量和體積的限制， 需中途返回取快件， 不 考慮休息時間。符號說明Dn：n 個矩陣V ：各個頂點的集合E ：各邊的集合eij ：

4、每一條邊we : 邊的權G ：加權無向圖vi,vj ：定點C ：哈密爾頓圈f(Vi) ：最佳哈密爾頓圈模型的建立一、基本假設1、假設送貨員的始終以 24 千米/小時的速度送貨，中途沒有意外情況；2、假設送貨員按照路徑示意圖行走；3、假設倉庫點為第 51 點；4、假設送貨員回到倉庫點再次取貨時間不計。二、模型建立與求解 問題一：1、數據處理使用數據處理軟件，處理附表 2 求出給定配送點之間的相互距離。最終使用矩陣對處理數據進行數據統計整理。1319161828642207823LLLLLLLLL511821825121179751261392矩陣前兩列表示相互連接的配送點，第三列表示相鄰兩配送點

5、之間邊的距 離。使用上述數據矩陣可以構造路線示意圖的帶權鄰接矩陣， 再用 Floyd 算法求 出各配送點之間的距離。2、Floyd 算法基本思想 直接在示意圖的帶權鄰接矩陣中，通過插入定點的方法構造出 n 個矩陣Di,D2丄，Dn,最后得到的矩陣Dn為距離矩陣，同時求出插入點矩陣以便得到兩點之間的最短路程。i23LL49505ii07745i9i6LL20306i6989i00682774505829LL255702200ii69263i9i658290LL20705i7388i0467LLLLLLLL0LLLLLL49203062557020705LL03569ii72i50i6989220

6、0ii7388LL3569099285ii0068i6926i0467LLii72i99280令 G (V,E) 為一個加權無向圖，其中 V 表示各個頂點的 集合， V v0,v1,v2丄，vn ;其中E表示各邊的集合，E e ，而eij山“)。圖G中 每一條邊e都對應一個實數we ,則稱we為邊的權。如果任意兩邊相連，則G為 完備圖。設G (V,E)是連通無向圖，經過G的每個定點正好形成一個圈，則稱 G為 哈密爾頓圈，簡稱H圈。最佳哈密爾頓圈是在加權圖 G (V,E)中，權最小的哈 密爾頓圈。判定一個加權圖G (V,E)是否存在哈密爾頓圈是一個 NP問題，而它的完備 加權圖G' (V

7、,E')( E'中每條邊的權等于Vi,Vj之間的最短路徑的權)中一定存在 哈密爾頓圈。所以需要在完備加權圖G' (V,E')中尋求最佳哈密爾頓圈。該過程 需要采用二邊逐次修正法并且利用矩陣翻轉實現。3、二邊逐次修正法的選法過程、任取初始 H 圈：Co=Vi,V2,L ,Vi,L ,Vj ,L ,Vn, Vi、對所有的 i, j,1 i 1 j n，若w(Vj,Vj) w(Vi,Vji) w(V,Vii) w(Vj,Vj J， 則在Co中刪去邊w(Vi,Vj )和w(Vi i,Vj i)而加入邊w(Vi ,Vi i)和w(Vj,Vj 1 )，形成新的 H圈 C，即

8、 C Vi,V2丄，Vi,L ,Vj 丄，Vn,Vi(3)、對C重復步驟(2)，直到條件不滿足為止，最終得到的 C即為所求。4、矩陣翻轉 在一個矩陣中，對他的第 i 行(列)到第 j 行(列)翻轉是以 i 行(列)和j行（列）的中心位置為轉軸、旋轉180度，這樣：第i行（列）和第j行（列） 位置互換，第i+1行（列）和第j-1行（列）位置互換。圖一由附錄給定的快件信息可知，1 : 30號快件總重量為48.5kg、體積為0.88m3, 顯然送貨員可以一次性攜帶所有貨物到達配送點，經統計配送點共有21個，即V（13、14、16、17、18、21、23、24、26、27、31、32、34、36、38

9、、40、42、43、45、49)首先在程序里設置限制：30Wi50i 030Vi1i 0將出發點51點與21個送貨點結合起來構造完備加權圖，由完備加權圖確定 初始H圈，列出該初始H圈加點序的距離矩陣，然后使用二邊逐次修正法對矩陣 進行翻轉，可以求得近似最優解的距離矩陣，從而確定近似的最佳哈密爾頓圈。由于使用矩陣翻轉方法來實現二邊逐次修正法的結果與初始圈有關， 為得到 更優解，在使用軟件編程時，隨機搜索出若干個初始 H圈，例如2000。在所有 的H圈中篩選權值最小的一個，即就是最佳 H圈。最佳H圈的近似解為：2000f(Vi)min f (Vi)在Co中刪去邊W（Vi,Vj）和W（Vii,Vji

10、）而加入邊w（vi,vi 1）和W（Vj,Vj 1），形成新的H 圈C。最終由編程得到近似最佳配送路線以及總長度。Y j最佳配送路線：圖二5126211714162332353836384342494245403431273927312419131851解得路線總長為54709m耗時226.77min。問題二：因貨物可在一次性配送，故可以不用考慮送貨員的最大載重與體積問題。 但 是較于問題一在選擇路線上，需要考慮送貨時間問題，不得超過指定時間。所以 在問題一的程序中需要再增加時間限制。30Wi 50i 030 Vi 1i 0Ti t（i 0,1,2,L ,30）結合問題一，使用相同方法求解最佳

11、 H圈。圖三 最佳配送路線：51181319243134404542494243383532231614172136273927312651解得路線總長為54996m耗時227.50min冋題三：由附錄給定的快件信息知，1: 100號快件總重量為148kg、體積為2.8m3。 由于考慮送貨員的最大載重與體積， 送貨員必須分多次配送快件。送貨員顯然至 少需要連續三次配送，才能完成配送任務。因此問題三存在配送點分組、以及每組求最佳配送方案這兩個問題。 首先需 要制定一種比較合理的劃分準則，使三組總長加起來最短。需要選擇三個點作為 每一組的基點，要求這三個點兩兩之間的最短距離是50個配送點中最大的三

12、組最短距離。利用距離矩陣查找其他任意點與三個基點之間的距離，距離哪一個基點近，就被劃分在哪一組。通過計算三個基點為：9號、28號、43號配送點。通過距離矩陣將100件 快件的配送點分組如下：配送方案重量(kg)體積(m3 )-一-12345678910141617182123323549.90.9112二111213151920222526282930334144464848.380.985242731343637383940434547495049.720.9038求和1482.8表使用問題一與問題二中相同的方法：首先將出發點與其他組內點結合起來構 造完備加權圖，由完備加權圖確定初始H圈，列

13、出該初始H圈加點序的距離矩陣， 然后使用二邊逐次修正法對矩陣進行翻轉， 可以求得近似最優解的距離矩陣，從而確定近似的最佳哈密爾頓圈vi圖四最終由程序解得三組最佳配送路線為： 第一組：5118718342543161710914162332353223172151解得路線總長52743m耗時227.4min第二組：512631241925414448463328302229222022151211131851解得路線總長47736m耗時221.4min。第三組：51263127392736384342495045404740374034312651解得路線總長42421m耗時208.2min模型的優缺點點評對于問題一所建立的模型，通過Floyd算法和二邊逐