摘要
本文是關於送貨員需要以最快的速度及時送達貨物的問題，可看作是類貨郎擔問題。
第壹問中，我們采用最近點插入模型，得到了30個貨物的送貨方案及路線時間，並且應用局部全排列窮舉法將上面得到的路線進行優化，得到最終路線為：O->18->13->19->24->31->27->27->39->27->31->31->34->40->45->45->45->42
->49->42->43->43->38->36->38->35->32->32->32->23->23->16->14->17->21->26->O，總用時為（包括交貨時間）：228.18分。
第二問中，根據時間優先的原則，將所有貨物送達點進行分塊分組，即優先送達時間要求緊的貨物，並且利用窮舉法列舉出每壹塊中貨物送達點的任意排列順序，求出其中耗時最短的路線即為所需結果，最終路線為：O->18->13->19->24->31->27->27->39->27->31->31->34->40->45->45->45->42
->49->42->43->43->38->36->38->35->32->32->32->23->23->16->14->17->21->26->O，總用時為（包括交貨時間）：228.18分。
第三問中，由於貨物重量和體積的限制，送貨員需中途取貨。我們采用最遠點優先送貨和最近點優先送貨兩種方案進行路線的分劃，並根據最終求得結果的比較，得出前者方案更優，因此選用第壹種方案送貨。最終路線為：
第壹趟：0->18->13->11->12->15->25->29->22->20->22->30->28->33->28->30
->22->15->5->2->4->3->8->1->6->1->7->10->9->14->18->0,
第二趟：0->26->31->19->24->31->34->40->47->40->37->41->46->48->44->50
->45->36->27->39->27->31->26->0
第三趟：0->21->17->23->16->23->32->35->38->43->42->49->42->43->38
->36->21->0
第四趟：0->26->26->26->0
總時間為：394.3分。
關鍵字：快遞公司送貨 貨郎擔問題 最近鄰點插入 全排列窮舉法
1 問題重述
在物流行業中，送貨員需要以最快的速度及時將貨物送達，而且他們往往壹人送多個地方。
現有壹快遞公司，壹送貨員要按圖1中的路徑需將貨物送至城市內多處，要求設計送貨方案，使所用時間最少。假定送貨員只能沿圖中那些連通線路行走，而不能走其它任何路線。各件貨物的相關信息見表1，50個位置點的坐標見表2。
假定送貨員最大載重50公斤，所帶貨物最大體積1立方米。送貨員的平均速度為24公裏/小時。每件貨物交接花費3分鐘，並假定，同壹地點有多件貨物按照每件3分鐘交接計算。
現在送貨員要將100件貨物送到50個地點。請完成以下問題。
1. 若將1~30號貨物送到指定地點並返回。設計最快完成路線與方式。給出結果。要求標出送貨線路。
2. 假定該送貨員從早上8點上班開始送貨，要將1~30號貨物的送達時間不能超過指定時間，請設計最快完成路線與方式。要求標出送貨線路。
3. 若不需要考慮所有貨物送達時間限制(包括前30件貨物)，現在要將100件貨物全部送到指定地點並返回。設計最快完成路線與方式。要求標出送貨線路，給出送完所有快件的時間。由於受重量和體積限制，送貨員可中途返回取貨。不考慮中午休息時間。
2 問題分析
對於送貨員從快遞公司庫房O點出發將貨物送到城市內制定地點問題，可以轉換為圖論中的最短路徑求解問題，我們將城市內的各送貨地點看做是圖中的頂點，各地點之間送貨所需的時間看做是該邊上的權值，由題目表3所給的各地點之間的聯通性構建無向圖。
對於問題壹，要求送貨員以最快的方式將1~30貨物送達指定的地點並返回。因此，可以將問題簡化為貨郎擔問題進行求解。
對於問題二，要求送貨員從早上8點出發，將貨物在指定的時間內以最快的方式送達目的地，由題目已知可以根據時間將1~30號貨物所對應的地點分為4塊，即8：00至9:00、9:00至9:30、9:30至10:15、10:15至12：00四個時間段。再對每個時間段內的送貨地點進行窮舉，得到最佳路徑，評價各個時間段的結果。
對於問題三，在不考慮送貨時間限制的情況下，將體積與重量兩個因素考慮在內，允許送貨員可以往返取貨，要求送貨員以最快的方式將貨物送達指定地點並返回。由於所有物體的總重量是148公斤，總體積為2.98立方米，送貨員的最大載貨量為50公斤，最大載貨體積為1立方米，所以送貨員會往返三次取貨，因此可以將所有的送貨地點分為三塊。對於所有送貨地點的分塊，可以采用三種方案——尋找離始發點最遠的點，逐次加入次遠點，直至達到送貨員的最大載貨量；尋找離始發點最近的點，逐次加入次近點，直至達到送貨員的最大載貨量；人為的分塊，直至達到送貨員的最大載貨量；對此三種方法進行評價，得出分析結果。
3 模型假設
(1) 送貨員只能走題目中給定的聯通路線，不能走其他的任何路線；
(2) 假定送貨員最大載重50公斤，所帶貨物最大體積1立方米；
(3) 假定送貨員的平均速度為24公裏/小時；
(4) 假定每件貨物交接花費3分鐘，為簡化起見，同壹地點有多件貨物也簡單按照每件3分鐘交接計算；
(5) 送貨員在送貨期間無塞車現象，即業務員送快遞途中不受任何外界因素影響；
(6) 送貨員送貨期間不考慮中午休息時間；
(7) 假設送貨員到達送貨點後就將此站點上的所有貨物交付；
4 模型的建立與求解
4.1 各站點路徑求解模型
在計算機中通過編程可得到坐標系中各站點的點號以及1~30號貨物所對應的站點號，如圖1—1所示：
圖1—1 所有送貨站點及前30各送貨點的標號
由題目已知條件可將送貨問題看做是圖論求解最佳路徑問題，將送貨站點看做是圖中的頂點，送貨站點之間的路徑看做邊，將送貨站點之間的距離作為圖中邊的權值，構成圖 ，其中定點數n=50；
因此有 算法求解圖中任意兩站點直間的最短路徑，設圖中權矩陣為 ，其中 為 到 的距離。
當 ；
=
其他
算法基本步驟為：
(1) 輸入權矩陣 。
(2) 計算 ， ，其中
(3) 中元素 就是 到 的最短路長。
4.2 問題壹模型的建立於求解
壹、最近鄰點插入模型：
本題考慮應用貨郎擔問題，由於貨郎擔問題還沒有壹個精確的算法，加之前30個貨物的運送***涉及到22個站點數據量較大，故我們采用最鄰近點插入模型進行近似求解。其基本的思想為：以O點為起始點，納入到集合 中，依次計算剩余點到集合 的距離，取其中最小距離所對應的站點作為集合 中下壹個待插入點，依次計算此點插入到集合 各元素間時所對應的距離，將其中最小距離所對應的位置作為此點在集合 中的插入位置。依次類推，直到所有站點遍歷結束。
最鄰近插入法實現步驟為：（設 是帶權無向圖，***有n個結點，其中n=22）
(1) 以O點為初始點計作 ，建立有序集合（集合元素排列順序即為最佳路徑） ={ }，並由其余的n-1個點建立集合 ={ }，計算 集合中每壹個元素到集合 中各個元素的距離，取集合 中每壹個元素到集合 中每壹個元素的最小距離作為其對應與集合 的距離，比較集合 中各個元素到集合 的距離，取距離最小所對應的元素作為集合 的待納入元素，將其分別插入到集合 各個元素之間，計算其距離， 取最短距離所對應的插入點作為該元素在集合 中的最終位置，得到最終的有序集合 。
（2）假設集合 ={ }， ={ }，求出集合 中元素 分別到集合 中元素 之間的距離，依次即為 ，比較 的大小，取其中最小的值作為 到集合 的距離；再求集合 中元素 分別到集合 中元素 之間的距離，依次即為 ，比較 的大小，取其中最小的值作為 到集合 的距離；依次類推，求出集合 中各元素到集合 的距離。比較集合 的各個元素到集合 距離的大小，取其中距離最小的元素為待插入集合 的元素，為了便於理解這裏我們假設此元素為 ，然後計算 插入到集合 元素 ， ， 以及 後所得路徑的總距離，取其中距離最小的壹組作為 的插入點，得到集合 。
(3) 依次類推，直到所有的點遍歷壹遍，得到的集合 即為最佳路徑。
由程序可得其最佳路徑為：
O->21->17->14->16->23->32->35->38->36->38->43->42->49->42->45->40
->34->31->18->13->19->24->31->27->39->27->31->26->0
總的時間為：230.83分。
二、局部全排列窮舉法模型
前30個貨物的運送***涉及到22個站點數據量較大，直接采用全排列窮舉法難以實現，因此我問現將其分塊，並在每塊內部采用局部全排列窮舉法得到局部最佳路徑，在通過固定每壹塊路徑的起始點的方法是所有塊的路徑連接成壹個整體。（具體模型算法見下文問題二）
最佳路徑為：
O->18->13->19->24->31->27->27->39->27->31->31->34->40->45->45
->45->42->49->42->43->43->38->36->38->35->32->32->32->23->23->16->14->17->21->26->26->O
總的時間為：228.18分。
由此兩種模型的結果比較明顯可得分塊後利用窮舉法得到的結果優於前者，因此，前30個貨物的送貨路徑選擇局部全排列窮舉法：
O->18->13->19->24->31->27->27->39->27->31->31->34->40->45->45
->45->42->49->42->43->43->38->36->38->35->32->32->32->23->23->16->14->17->21->26->O
總時間為：228.18分。
路徑如圖1—2所示：
圖1—2 前30個貨物的最佳運輸路線圖
4.3 問題二模型的建立於求解
本題利用分塊思想，應用局部全排列窮舉法求解每壹塊的最佳路徑。由於考慮到送貨時間運輸限制，我們優先考慮送貨時間，即以送貨時間對所有貨物進行分塊，並在每壹塊內部采用局部全排列窮舉法求取路徑，並判斷其總的送貨時間是否滿足指定的時間。其基本步驟為：
(1) 第壹時間段為8:00——9:00之間送到的站點為：13、18、39、27、24、27，不計重復站點，總***有5個站點，利用窮舉法比較 次得到最佳路徑為：18->13->24->27->39，考慮交貨時間在內總時間為57.1分。
(2) 第二時間段為9:00——9:30之間送到的站點為：31、31、34、40、45、45、45，不計重復站點，總***有4個站點，利用窮舉法比較 次得到最佳路徑為：31->34->40->45, 考慮交貨時間在內總時間為46.05分。
(3) 第三時間段為9:30——10:15之間送到的站點為：42、49、43、43、38，不計重復站點，總***有4個站點，利用窮舉法比較 次得到最佳路徑為：42->49->43->43->38, 考慮交貨時間在內總時間為39.58分。
(4) 第四時間段為10:15——12:00之間送到的站點為：36、32、23、16、14、17、21、26，不計重復站點，總***有8個站點，利用窮舉法比較 次得到最佳路徑為：36->32->23->16->14->17->21->26, 考慮交貨時間在內總時間為81.97分。
因此，根據題目所給的時間段分塊所得結果如表1所示：
站點分塊表
第
壹
時
間
段
貨物號
送達地點
重量
體積
時間
最佳路徑
時間（含交
貨時間）/分
1
13
2.5
0.0316
9:00
18
57.1
2
18
0.5
0.0354
9:00
13
13
39
2.56
0.0595
9:00
24
19
27
2.45
0.0545
9:00
27
20
24
2.93
0.052
9:00
27
22
27
2.25
0.0018
9:00
39
第
二
時
間
段
3
31
1.18
0.0268
9:30
31
46.05
11
45
1.1
0.0287
9:30
31
14
45
2.28
0.0501
9:30
34
21
31
0.8
0.0108
9:30
40
24
34
2.8
0.0103
9:30
45
25
40
2.14
0.0155
9:30
45
26
45
0.68
0.0682
9:30
45
第
三
時
間
段
10
38
1.33
0.0319
10:15
42
39.58
12
43
0.95
0.0228
10:15
49
15
42
2.85
0.019
10:15
43
16
43
1.7
0.0782
10:15
43
27
49
1.35
0.0144
10:15
38
第
四
時
間
段
4
26
1.56
0.035
12:00
36
85.45
5
21
2.15
0.0377
12:00
32
6
14
1.72
0.01
12:00
32
7
17
1.38
0.0109
12:00
32
8
23
1.4
0.0426
12:00
23
9
32
0.7
0.0481
12:00
23
17
32
0.25
0.0512
12:00
16
18
36
1.79
0.0184
12:00
14
23
26
1.57
0.021
12:00
17
28
32
0.52
0.002
12:00
21
29
23
2.91
0.0587
12:00
26
30
16
1.2
0.0429
12:00
26
由表1可知其送貨路線為：
O->18->13->19->24->31->27->27->39->27->31->31->34->40->45->45
->45->42->49->42->43->43->38->36->38->35->32->32->32->23->23->16->14->17->21->26->26->O，總時間為：228.18分。
考慮時間限制時的最佳路線圖見如下圖所示：
圖1—3 考慮時間限制時前30個貨物的最佳運輸路線圖
4.4 問題三模型的建立於求解
在考慮送貨員所載貨物重量及體積限制，不考慮送貨時間限制的前提下，設計將貨物最快送到指定地點的往返路線。由於所有物體的總重量是148公斤，總體積為2.98立方米，送貨員的最大載貨量為50公斤，最大載貨體積為1立方米，所以送貨員會往返三次取貨，因此最少要將所有的送貨地點分為三塊。本題我們采用兩種分塊方案，分別為：
(1) 最遠送貨點優先法：
尋找離始發點O點最遠的點，以此點為中心尋找周圍離其最近的點，直至達到送貨員的最大載貨量和最大載貨體積，在剩余點鐘再以距離O的次遠點為中心尋找其周圍的點，直至達到送貨員的最大載貨量和最大載貨體積，直到所有貨物運送結束為止。
有題目數據計算可得，距離O點最遠點為2號點，因此以2號點為中心的壹組送貨點分塊數據為：2、3、4、5、8、15、15、1、6、7、7、11、11、12、12、13、13、10、10、18、18、20、20、22、25、25、25、29、30、28、9、33、33、14、14，***35個站點，送貨員運送的總重量為48.54公斤，總體積為0.9857立方米，不計重復站點，***有23個送貨點，將前12個站點作為壹部分，後11個站點作為壹部分，利用窮舉法得到其最佳路徑為：18->13->11->12->15->25->29->22->20->22->30->28->33->28->30->22->15->5->2->4->3->8->1->6->1->7->10->9->14,其總時間為167.48分。
除去此23個站點，由計算可知，距離O點最遠的點為48號點，以此點為中心的壹組送貨點數據為：48、44、46、46、46、41、41、50、47、40、40、37、37、34、34、19、19、24、24、45、45、45、45、31、31、31、27、27、27、39、39，***31個站點，送貨員運送的總重量為50公斤，總體積為0.9573立方米，不計重復站點，***有15個送貨點，將前11個站點作為壹部分，後4個站點作為壹部分，利用窮舉法得到其最佳路徑為：19->24->31->34->40->47->40->37->41->46->48->44->50->45->36
->27->39，其總時間為141.82分
出去前兩部的站點後，經計算的離O點最遠的站點時17號點，以此點為中心的壹組送貨點數據為：16、16、17、17、17、23、23、23、23、32、32、32、32、32、32、35、38、38、38、36、36、36、21、21、43、43、43、42、42、49、49，***31個站點，送貨員運送的總重量為45.07公斤，總體積為0.9751立方米，不計重復站點，***有11個送貨點，利用窮舉法得到其最佳路徑為：17->23->16->23->32->35->38->43->42->49->42->43->38->36->21，其總時間為78.04分。
最後以26、26、26為壹組送回點數據，***3個站點，送貨員運送的總重量為4.39公斤，總體積為0.0619立方米，不計重復只有1個站點，其總時間為6.96分。綜合此四塊的數據可知，總的運送時間為394.3分。
(2) 最近送貨點優先法：
尋找離始發點最近的點，逐次加入次近點，直至達到送貨員的最大載貨量和最大載貨體積，再在剩余點中尋找距離O點最近的點直至達到送貨員的最大載貨量和最大載貨體積，直到所有貨物運送結束為止。
有題目數據計算可得，距離O點最近點為26號點，因此以26號點為起始心的壹組送貨點分塊數據為：26、26、26、18、18、21、21、23、23、23、23、27、27、27、31、31、31、34、34、36、36、36、39、39、24、24、17、17、17、17、11，***31個站點，送貨員運送的總重量為45.77公斤，總體積為0.936立方米，不計重復只有11個站點，利用窮舉法得到其最佳路徑為：26->21->17->23->36->27->39->31->34->24->18,總時間為81.12分。
出去此11個站點外，由計算可得，剩余點中離O點最近的點為25號點，以此點為起始心的壹組送貨點分塊數據為：25、25、25、37、37、42、42、43、43、43、50、1、47、3、6、15、15、29、22、30、49、49、41、41、28、20、20、44、4、4、4、4、20，總***有33個點，送貨員運送的總重量為44.55公斤，總體積為0.8004立方米，不計重復只有20個站點，將前12個站點作為壹部分，後8個站點作為壹部分，利用窮舉法得到其最佳路徑為：25->29->22->30->33->28->20->15->4->3->1->6->47->37->41->44->
50->49->42->43,總時間為219.5分。
除去此31個點外，由計算可得，剩余的點中距離O點最近的點位38號點，以此點為起始點的壹組分塊數據為：38、38、38、9、11、11、12、12、13、13、14、14、16、16、19、19、32、32、32、32、32、32、35、40、40、45、45、45、45、45、8、10、10、7、7、15，總***有35個點，送貨員運送的總重量為48.73公斤，總體積為0.9839立方米，不計重復只有15個站點，將前10個站點作為壹部分，後5個站點作為壹部分，利用窮舉法得到其最佳路徑為：19->13->11->12->8->7->10->9->14->16->32->35->38->45->40,總時間為：125.35
剩余點中，由計算可得2號點距離O點最近，依此點作為起始點的壹組分塊數據為：2、5、48、46、46、46，***6個站點，送貨員運送的總重量為8.95公斤，總體積為0.2597立方米，不計重復只有4個站點，利用窮舉法得到其最佳路徑為：2->5->48->46,總時間為：125.55分。
綜合此四塊的數據可知其總時間為：551.52分。
綜上所述：有計算結果可知：應用方案壹所得總的送貨時間為：394.3分；應用方案二所得總的送貨時間為551.52分，方案壹優於方案二，因此，在考慮載重量及載重體積情況下，完成100件送貨任務的最優路徑為：
第壹趟：0->18->13->11->12->15->25->29->22->20->22->30->28->33->28->30
->22->15->5->2->4->3->8->1->6->1->7->10->9->14->18->0,
第二趟：0->26->31->19->24->31->34->40->47->40->37->41->46->48->44
->50->45->36->27->39->27->31->26->0
第三趟：0->21->17->23->16->23->32->35->38->43->42->49->42->43->38
->36->21->0
第四趟：0->26->26->26->0
總時間為：394.3分。
5 模型評價
5.1 模型壹評價
首先采用最鄰近點插入法得到其近似最佳路徑，然後通過分塊後利用窮舉法得到更佳路徑，並且局部全排列窮舉法具有更廣的應用性，應為其不受數據量的限制。
5.2 模型二評價
在第壹問的基礎上加入時間作為限制條件，我們可以根據題目所給定的運貨時間將前30件貨物的運達地點分為四塊，使得數據量減小，因此可以利用窮舉法將每壹時間段的運送路徑精確地表示出來，再根據每壹時間段首尾銜接的站點可以得到最終的最佳路徑。
5.3 模型三評價
根據題目已知的送貨員最大運載量及最大運載體積的限制條件，至少要將所有的貨物分為三組，往返三次送達最終地點。根據分組方案的不同得到不同的結果。本題我們分兩種方案，即最遠點優先法和最近點優先法進行計算，並通過比較得到結果，這樣可使結果更具說服力。但分類法也只選擇了兩種典型的分類方案，不夠全面，也許會有更好方案以期待討論。