送貨路線設(shè)計問題的分析

1、送貨路線設(shè)計問題分析摘要 本文是關(guān)于送貨員需要以最快的速度及時送達物資的問題，可看作是類貨擔(dān)問題。 第一問中，我們采納最近點插入模型，得到了30個物資的送貨方案及路線時刻，同時應(yīng)用局部全排列窮舉法將上面得到的路線進行優(yōu)化，得到最終路線為：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分。 第二問中，依照時刻優(yōu)先的原則，將所有物資送達點進行分塊分組，即優(yōu)先送達時刻要求緊的物資，同時利用窮舉

2、法列舉出每一塊中物資送達點的任意排列順序，求出其中耗時最短的路線即為所需結(jié)果，最終路線為：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分。第三問中，由于物資重量和體積的限制，送貨員需中途取貨。我們采納最遠點優(yōu)先送貨和最近點優(yōu)先送貨兩種方案進行路線的分劃，并依照最終求得結(jié)果的比較，得出前者方案更優(yōu)，因此選用第一種方案送貨。最終路線為：第一趟：0-18-13-11-12-15-25-29-

3、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分。關(guān)鍵字：快遞公司送貨 貨郎擔(dān)問題 最近鄰點插入 全排列窮舉法 1 問題重述在物流行業(yè)中，送貨員需要以最快的速度及時將物資送達，而且他們往往一人送多個地點?，F(xiàn)有一快遞公

4、司，一送貨員要按圖1中的路徑需將物資送至都市內(nèi)多處，要求設(shè)計送貨方案，使所用時刻最少。假定送貨員只能沿圖中那些連通線路行走，而不能走其它任何路線。各件物資的相關(guān)信息見表1，50個位置點的坐標見表2。假定送貨員最大載重50公斤，所帶物資最大體積1立方米。送貨員的平均速度為24公里/小時。每件物資交接花費3分鐘，并假定，同一地點有多件物資按照每件3分鐘交接計算。現(xiàn)在送貨員要將100件物資送到50個地點。請完成以下問題。1. 若將130號物資送到指定地點并返回。設(shè)計最快完成路線與方式。給出結(jié)果。要求標出送貨線路。2. 假定該送貨員從早上8點上班開始送貨，要將130號物資的送達時刻不能超過指定時刻，請

5、設(shè)計最快完成路線與方式。要求標出送貨線路。3. 若不需要考慮所有物資送達時刻限制(包括前30件物資)，現(xiàn)在要將100件物資全部送到指定地點并返回。設(shè)計最快完成路線與方式。要求標出送貨線路，給出送完所有快件的時刻。由于受重量和體積限制，送貨員可中途返回取貨。不考慮中午休息時刻。2 問題分析關(guān)于送貨員從快遞公司庫房O點動身將物資送到都市內(nèi)制定地點問題，能夠轉(zhuǎn)換為圖論中的最短路徑求解問題，我們將都市內(nèi)的各送貨地點看做是圖中的頂點，各地點之間送貨所需的時刻看做是該邊上的權(quán)值，由題目表3所給的各地點之間的聯(lián)通性構(gòu)建無向圖。關(guān)于問題一，要求送貨員以最快的方式將130物資送達指定的地點并返回。因此，能夠?qū)?/p>

6、題簡化為貨郎擔(dān)問題進行求解。關(guān)于問題二，要求送貨員從早上8點動身，將物資在指定的時刻內(nèi)以最快的方式送達目的地，由題目已知能夠依照時刻將130號物資所對應(yīng)的地點分為4塊，即8：00至9:00、9:00至9:30、9:30至10:15、10:15至12：00四個時刻段。再對每個時刻段內(nèi)的送貨地點進行窮舉，得到最佳路徑，評價各個時刻段的結(jié)果。關(guān)于問題三，在不考慮送貨時刻限制的情況下，將體積與重量兩個因素考慮在內(nèi)，同意送貨員能夠往返取貨，要求送貨員以最快的方式將物資送達指定地點并返回。由于所有物體的總重量是148公斤，總體積為2.98立方米，送貨員的最大載貨量為50公斤，最大載貨體積為1立方米，因此送

7、貨員會往返三次取貨，因此能夠?qū)⑺械乃拓浀攸c分為三塊。關(guān)于所有送貨地點的分塊，能夠采納三種方案查找離始發(fā)點最遠的點，逐次加入次遠點，直至達到送貨員的最大載貨量；查找離始發(fā)點最近的點，逐次加入次近點，直至達到送貨員的最大載貨量；人為的分塊，直至達到送貨員的最大載貨量；對此三種方法進行評價，得出分析結(jié)果。3 模型假設(shè)(1) 送貨員只能走題目中給定的聯(lián)通路線，不能走其他的任何路線；(2) 假定送貨員最大載重50公斤，所帶物資最大體積1立方米；(3) 假定送貨員的平均速度為24公里/小時；(4) 假定每件物資交接花費3分鐘，為簡化起見，同一地點有多件物資也簡單按照每件3分鐘交接計算； (5) 送貨員在

8、送貨期間無塞車現(xiàn)象，即業(yè)務(wù)員送快遞途中不受任何外界因素阻礙；(6) 送貨員送貨期間不考慮中午休息時刻；(7) 假設(shè)送貨員到達送貨點后就將此站點上的所有物資交付；4 模型的建立與求解4.1 各站點路徑求解模型在計算機中通過編程可得到坐標系中各站點的點號以及130號物資所對應(yīng)的站點號，如圖11所示：圖11 所有送貨站點及前30各送貨點的標號由題目已知條件可將送貨問題看做是圖論求解最佳路徑問題，將送貨站點看做是圖中的頂點，送貨站點之間的路徑看做邊，將送貨站點之間的距離作為圖中邊的權(quán)值，構(gòu)成圖 ，其中定點數(shù)n=50；因此有 算法求解圖中任意兩站點直間的最短路徑，設(shè)圖中權(quán)矩陣為 ，其中 為 到 的距離。

9、 當(dāng) ；= 其他算法差不多步驟為：(1) 輸入權(quán)矩陣 。(2) 計算 ， ，其中 (3) 中元素 確實是 到 的最短路長。4.2 問題一模型的建立于求解一、最近鄰點插入模型：本題考慮應(yīng)用貨郎擔(dān)問題，由于貨郎擔(dān)問題還沒有一個精確的算法，加之前30個物資的運送共涉及到22個站點數(shù)據(jù)量較大，故我們采納最鄰近點插入模型進行近似求解。其差不多的思想為：以O(shè)點為起始點，納入到集合 中，依次計算剩余點到集合 的距離，取其中最小距離所對應(yīng)的站點作為集合 中下一個待插入點，依次計算此點插入到集合 各元素間時所對應(yīng)的距離，將其中最小距離所對應(yīng)的位置作為此點在集合 中的插入位置。依次類推，直到所有站點遍歷結(jié)束。最鄰

10、近插入法實現(xiàn)步驟為：（設(shè) 是帶權(quán)無向圖，共有n個結(jié)點，其中n=22）(1) 以O(shè)點為初始點計作 ，建立有序集合（集合元素排列順序即為最佳路徑） = ，并由其余的n-1個點建立集合 = ，計算 集合中每一個元素到集合 中各個元素的距離，取集合 中每一個元素到集合 中每一個元素的最小距離作為其對應(yīng)與集合 的距離，比較集合 中各個元素到集合 的距離，取距離最小所對應(yīng)的元素作為集合 的待納入元素，將其分不插入到集合 各個元素之間，計算其距離， 取最短距離所對應(yīng)的插入點作為該元素在集合 中的最終位置，得到最終的有序集合 。（2）假設(shè)集合 = ， = ，求出集合 中元素 分不到集合 中元素 之間的距離，依

11、次即為 ，比較 的大小，取其中最小的值作為 到集合 的距離；再求集合 中元素 分不到集合 中元素 之間的距離，依次即為 ，比較 的大小，取其中最小的值作為 到集合 的距離；依次類推，求出集合 中各元素到集合 的距離。比較集合 的各個元素到集合 距離的大小，取其中距離最小的元素為待插入集合 的元素，為了便于理解那個地點我們假設(shè)此元素為 ，然后計算 插入到集合 元素 ， ， 以及 后所得路徑的總距離，取其中距離最小的一組作為 的插入點，得到集合 。 (3) 依次類推，直到所有的點遍歷一遍，得到的集合 即為最佳路徑。由程序可得其最佳路徑為：O-21-17-14-16-23-32-35-38-36-3

12、8-43-42-49-42-45-40-34-31-18-13-19-24-31-27-39-27-31-26-0總的時刻為：230.83分。二、局部全排列窮舉法模型前30個物資的運送共涉及到22個站點數(shù)據(jù)量較大，直接采納全排列窮舉法難以實現(xiàn)，因此我問現(xiàn)將其分塊，并在每塊內(nèi)部采納局部全排列窮舉法得到局部最佳路徑，在通過固定每一塊路徑的起始點的方法是所有塊的路徑連接成一個整體。（具體模型算法見下文問題二）最佳路徑為：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

13、-16-14-17-21-26-26-O總的時刻為：228.18分。由此兩種模型的結(jié)果比較明顯可得分塊后利用窮舉法得到的結(jié)果優(yōu)于前者，因此，前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分。路徑如圖12所示：圖12 前30個物資的最佳運輸路線圖4.3 問題二模型的建立于求解本題利用分塊思想，應(yīng)用局部全排列窮舉法求解每一塊的最佳路徑。由于考慮到送貨時刻運輸限制，我

14、們優(yōu)先考慮送貨時刻，即以送貨時刻對所有物資進行分塊，并在每一塊內(nèi)部采納局部全排列窮舉法求取路徑，并推斷其總的送貨時刻是否滿足指定的時刻。其差不多步驟為：(1) 第一時刻段為8:009:00之間送到的站點為：13、18、39、27、24、27，不計重復(fù)站點，總共有5個站點，利用窮舉法比較 次得到最佳路徑為：18-13-24-27-39，考慮交貨時刻在內(nèi)總時刻為57.1分。(2) 第二時刻段為9:009:30之間送到的站點為：31、31、34、40、45、45、45，不計重復(fù)站點，總共有4個站點，利用窮舉法比較 次得到最佳路徑為：31-34-40-45, 考慮交貨時刻在內(nèi)總時刻為46.05分。(3

15、) 第三時刻段為9:3010:15之間送到的站點為：42、49、43、43、38，不計重復(fù)站點，總共有4個站點，利用窮舉法比較 次得到最佳路徑為：42-49-43-43-38, 考慮交貨時刻在內(nèi)總時刻為39.58分。(4) 第四時刻段為10:1512:00之間送到的站點為：36、32、23、16、14、17、21、26，不計重復(fù)站點，總共有8個站點，利用窮舉法比較 次得到最佳路徑為：36-32-23-16-14-17-21-26, 考慮交貨時刻在內(nèi)總時刻為81.97分。因此，依照題目所給的時刻段分塊所得結(jié)果如表1所示：站點分塊表第一時間段物資號送達地點重量體積時刻最佳路徑時刻（含交貨時刻）/分

16、1132.50.03169:001857.12180.50.03549:001313392.560.05959:002419272.450.05459:002720242.930.0529:002722272.250.00189:0039第二時間段3311.180.02689:303146.0511451.10.02879:303114452.280.05019:303421310.80.01089:304024342.80.01039:304525402.140.01559:304526450.680.06829:3045第三時間段10381.330.031910:154239.581243

17、0.950.022810:154915422.850.01910:154316431.70.078210:154327491.350.014410:1538第四時間段4261.560.03512:003685.455212.150.037712:00326141.720.0112:00327171.380.010912:00328231.40.042612:00239320.70.048112:002317320.250.051212:001618361.790.018412:001423261.570.02112:001728320.520.00212:002129232.910.05871

18、2:002630161.20.042912:0026由表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分。考慮時刻限制時的最佳路線圖見如下圖所示：圖13 考慮時刻限制時前30個物資的最佳運輸路線圖4.4 問題三模型的建立于求解在考慮送貨員所載物資重量及體積限制，不考慮送貨時刻限制的前提下，設(shè)計將物資最快送到指定地點的往返路線。由于所有物體的總重量是148公斤，總體積為2.98立

19、方米，送貨員的最大載貨量為50公斤，最大載貨體積為1立方米，因此送貨員會往返三次取貨，因此最少要將所有的送貨地點分為三塊。本題我們采納兩種分塊方案，分不為：(1) 最遠送貨點優(yōu)先法：查找離始發(fā)點O點最遠的點，以此點為中心查找周圍離其最近的點，直至達到送貨員的最大載貨量和最大載貨體積，在剩余點鐘再以距離O的次遠點為中心查找其周圍的點，直至達到送貨員的最大載貨量和最大載貨體積，直到所有物資運送結(jié)束為止。 有題目數(shù)據(jù)計算可得，距離O點最遠點為2號點，因此以2號點為中心的一組送貨點分塊數(shù)據(jù)為：2、3、4、5、8、15、15、1、6、7、7、11、11、12、12、13、13、10、10、18、18、2

20、0、20、22、25、25、25、29、30、28、9、33、33、14、14，共35個站點，送貨員運送的總重量為48.54公斤，總體積為0.9857立方米，不計重復(fù)站點，共有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號點，以此點為中心的一組送貨點數(shù)據(jù)為：48、44、46、46、46、41、41、50、47、40、

21、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立方米，不計重復(fù)站點，共有15個送貨點，將前11個站點作為一部分，后4個站點作為一部分，利用窮舉法得到其最佳路徑為：19-24-31-34-40-47-40-37-41-46-48-44-50-45-36-27-39，其總時刻為141.82分 出去前兩部的站點后，經(jīng)計算的離O點最遠的站點時17號點，以此點為中心的一組送貨點數(shù)據(jù)為：16、16、17、17、17、23、23、23、23、32、32、32、32、

22、32、32、35、38、38、38、36、36、36、21、21、43、43、43、42、42、49、49，共31個站點，送貨員運送的總重量為45.07公斤，總體積為0.9751立方米，不計重復(fù)站點，共有11個送貨點，利用窮舉法得到其最佳路徑為：17-23-16-23-32-35-38-43-42-49-42-43-38-36-21，其總時刻為78.04分。 最后以26、26、26為一組送回點數(shù)據(jù)，共3個站點，送貨員運送的總重量為4.39公斤，總體積為0.0619立方米，不計重復(fù)只有1個站點，其總時刻為6.96分。綜合此四塊的數(shù)據(jù)可知，總的運送時刻為394.3分。 (2) 最近送貨點優(yōu)先法：查

23、找離始發(fā)點最近的點，逐次加入次近點，直至達到送貨員的最大載貨量和最大載貨體積，再在剩余點中查找距離O點最近的點直至達到送貨員的最大載貨量和最大載貨體積，直到所有物資運送結(jié)束為止。 有題目數(shù)據(jù)計算可得，距離O點最近點為26號點，因此以26號點為起始心的一組送貨點分塊數(shù)據(jù)為：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立方米，不計重復(fù)只有11個站點，利用窮舉法得到其最佳路徑為：26-21-1

24、7-23-36-27-39-31-34-24-18,總時刻為81.12分。 出去此11個站點外，由計算可得，剩余點中離O點最近的點為25號點，以此點為起始心的一組送貨點分塊數(shù)據(jù)為：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立方米，不計重復(fù)只有20個站點，將前12個站點作為一部分，后8個站點作為一部分，利用窮舉法得到其最佳路徑為：25-29-22-30-33-28-20-15-4-3-

25、1-6-47-37-41-44-50-49-42-43,總時刻為219.5分。 除去此31個點外，由計算可得，剩余的點中距離O點最近的點位38號點，以此點為起始點的一組分塊數(shù)據(jù)為：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立方米，不計重復(fù)只有15個站點，將前10個站點作為一部分，后5個站點作為一部分，利用窮舉法得到其最佳路徑為：19-13-11-12-8-7-10-9-14-16-32-35-38-45-40,總時刻為：125.35 剩余點中，由計算可得2號點距離O點最近，依此點作為起始點的一組分塊數(shù)據(jù)為：2、5、48、46、46、46，共6個站點，送貨員運送的總重量為8.95公斤，總體積為0.2597立方米，不計重復(fù)只有4個站點，利用窮舉法得到其最佳路徑為：2-5-48-46,總時刻為：125.5