1、貨物配送問題【摘要】本文是針對解決某港口對某地區8個公司所需原材料A、B、C的運輸調度問題提出的方案。我們首先考慮在滿足各個公司的需求的情況下，所需要的運輸的最小運輸次數，然后根據卸載順序的約束以及載重費用盡量小的原則，提出了較為合理的優化模型，求出較為優化的調配方案。針對問題一，我們在兩個大的方面進行分析與優化。第一方面是對車次安排的優化分析，得出公司順時針送貨，公司逆時針送貨為最佳方案。第二方面我們根據車載重相對最大化思想使方案分為兩個步驟，第一步先是使每個車次滿載并運往同一個公司，第二步采用分批次運輸的方案，即在第一批次運輸中，我們使A材料有優先運輸權；在第二批次運輸中，我們使B材料有優

2、先運輸權；在第三批次中運輸剩下所需的貨物。最后得出耗時最少、費用最少的方案。耗時為40.5007、時，費用為4685.阮。針對問題二，加上兩個定理及其推論數學模型與問題一幾乎相同，只是空載路徑不同。我們采取與問題一相同的算法，得出耗時最少，費用最少的方案。耗時為26.063小時，費用為4374.4元。針對問題三的第一小問，我們知道貨車有4噸、6噸和8噸三種型號。我們經過簡單的論證，排除了4噸貨車的使用。題目沒有規定車子不能變向，所以認為車輛可以掉頭。然后我們仍舊采取公司順時針送貨，公司逆時針送貨的方案。最后在滿足公司需求量的條件下，采用不同噸位滿載運輸方案，此方案分為三個步驟：第一，使8噸車次

3、滿載并運往同一公司；第二，6噸位車次滿載并運往同一公司；第三，剩下的貨物若在16噸內，則用6噸貨車運輸，若在78噸內用8噸貨車運輸。最后得出耗時最少、費用最省的方案。耗時為19.6844小時，費用為4403.2一、問題重述某地區有8個公司（如圖一編號至），某天某貨運公司要派車將各公司所需的三種原材料A,B,C從某港口（編號）分別運往各個公司。路線是唯一的雙向道路（如圖1）。貨運公司現有一種載重6噸的運輸車，派車有固定成本20元/輛，從港口出車有固定成本為10元/車次（車輛每出動一次為一車次）。每輛車平均需要用15分鐘的時間裝車，到每個公司卸車時間平均為10分鐘，運輸車平均速度為60公里/小時（

4、不考慮塞車現象），每日工作不超過8小時。運輸車載重運費1.8元/噸公里，運輸車空載費用0.4元/公里。一個單位的原材料A,B,C分別毛重4噸、3噸、1噸，原材料不能拆分，為了安全，大小件同車時必須小件在上，大件在下。卸貨時必須先卸小件，而且不允許卸下來的材料再裝上車，另外必須要滿足各公司當天的需求量（見表1）。問題：1、貨運公司派出運輸車6輛，每輛車從港口出發（不定方向）后運輸途中不允許掉頭，應如何調度（每輛車的運載方案，運輸成本）使得運費最小。2、每輛車在運輸途中可隨時掉頭，若要使得成本最小，貨運公司怎么安排車輛數？應如何調度？3、（1）如果有載重量為4噸、6噸、8噸三種運輸車，載重運費都是

5、1.8元/噸公里，空載費用分別為0.2,0.4,0.7元/公里，其他費用一樣，又如何安排車輛數和調度方案？（2）當各個公司間都有或者部分有道路直接相通時，分析運輸調度的難度所在，給出你的解決問題的想法（可結合實際情況深入分析）。圖1唯一的運輸路線圖和里程數司材料、A41231025B15012423C52424351表1各公司所需要的貨物量二、模型假設1）港口的容量足夠大，多輛運輸車同時到達港口時不會發生阻塞現象；2）多輛運輸車可以在港口同時裝車，不必等待；3）雙向道路上沒有塞車現象；4）8個公司之間沒有優先級別，貨運公司只要滿足他們的需求量就可以；貨車完成他們日常的送貨任務之后，回到港口。5

6、）假設運輸車不會因天氣狀況，而影響其行駛速度，和裝載、卸載時間。6）運輸路不會影響運輸車行駛速度。7）運輸車正常出車。三、問題分析運輸過程的最大特點是三種原料重量不同，分為大小件，當大小件同車，卸貨時必須先卸小件，而且不允許卸下來的材料再裝上車，要區別對待運輸途中是否可以調頭的費用。在問題一中，運輸途中不能調頭，整個送貨路線是一個環形閉合回路，如果沿著某一方向同時給多家公司送貨時，運輸車必須為距離港口近的公司卸下小件，為距離港口遠的公司運送大件；而在問題二中，運輸途中可以調頭，可以首先為遠處公司運送小件，在返回途中為距離較近的公司卸下大件。從表面上看，這樣運輸能夠節省車次，降低出車費用。但我們

7、通過分析，在本題中，載重調頭運輸并不能降低費用。運費最小是貨運公司調度運輸車的目標，運費包括派車固定成本、從港口出車成本、載重費用和空載費用。建立模型時，要注意以下幾方面的問題：目標層：如果將調度車數、車次以及每車次的載重和卸貨點都設為變量，模型中變量過多，不易求解。由于各輛運輸車之間相互獨立，可以將目標轉化為兩個階段的求解過程，第一階段是規劃車次階段，求解車次總數和每車次的裝卸方案；第二階段是車輛調度階段，安排盡量少的車輛數，每車次盡量滿載，使總的運費最小。約束層：(1)運輸車可以從順時針或者逆時針方向送貨，要考慮不同方向時的載重用；(2)大小件的卸車順序要求不同原料搭配運輸時，沿途必須有序

8、卸貨；(3)每車次的送貨量不能超過運輸車的最大載重量；(4)滿足各公司當日需求。四、符號說明和名詞約定符號含義單位備注S1(n)從港口到各個公司的貨運最短里程集公里n=1、2、8;S2(n)卸載后返回港口的最短空載里程集公里n=1、2、8;Qi)(n)n公司對貨物i的實時需求量集單位/天n=1、2、8;i=A、BGW(n)第j批運至第n公司貨物的重量集噸n=1、2、8;j=1、2;Times(j)(n)第j批運至第n公司次數集次n=1、2、8;j=1、2Y(n)第j批運至第n公司的費用集元n=1、2、8;j=1、2;Y(d)第d問中組合運輸的費用集元d=1、2、3；Charge(d)第d問中所

9、有的運輸費用集元d=1、2、3;TTd)第d問中組合運輸的耗時集小時d=1、2、3;Time（d）第d問中所有的運輸耗時集小時d=1、2、3；五、建立模型一、問題一i.車次規劃模型的分析車次規劃階段只涉及到載重費用、空載費用和港口出車費用。運輸途中不能掉頭，所以每車次都是沿閉合回路繞圈行駛。1）運輸途中不能掉頭，所以為某些公司送貨時，運輸車從港口出發，按順時針方向沿閉合回路繞行，為其它公司送貨時，按逆時針方向沿閉合回路繞行。公司和港口之間存在順時針距離和逆時針距離，如下表：公司編號順時針距離815242937454955逆時針距離524536312315115由表可知，運輸過程中不可以掉頭，為

10、使得貨運費用最低，我們按照問題分析中給出的最佳運輸路徑進行貨物的分配運輸。即若港口按順時針和逆時針兩個不同方向出發，根據貨運里程短，點為順時針貨運方向最遠點，也是空載回港口的最近點，根據貨運里程短，點為逆時針貨運方向最遠點，也是空載回港口的最近點。結論：在符合載重相對最大化情況下，公司順時針送貨為最佳方案，公司逆時針送貨最佳方案。如下圖所示：2）卞M據3種原料的重量和運輸車的最大運載量可以看出，A和C可以搭配運輸，B和C可以搭配運輸，而A與B不能同車運輸。不論是以順時針方向送貨還是以逆時針方向送貨，當大小件搭配運輸時，必須首先卸下小件，在后續公司卸下大件。我們把這種特點總結如下：1、若在第j個

11、公司卸下的是大件A,說明本車次的貨物已經卸完，不能夠再為后續公司運送小件C（A與B不能同車運輸，更不可能有B）;2、若在第j個公司卸下的是B,說明本車次的貨物已經卸完，不能夠再為后續公司運送小件Coii .模型建立基于以上約束條件建立如下模型：第一步：根據車載重相對最大化的基本思想?？梢苑譃閮尚〔剑悍譃閮煞N滿載方案：第1種為每個車次裝載1單位A和2單位C;第2種是每個車次裝載2個單位B。并使每一車次在同一公司卸貨。滿載運載方案如下表1:表1車輛車次數公司貨物時間（小時）運費（元）各車工作時間（小時）111A,2C1.4167107.27.083521A,2C1.4167107.232A,2C1

12、.416718043A,2C1.4167273.653A,2C1.4167273.6264A,2C1.4167325.67.083575A,2C1.4167263.287A,2C1.4167138.497A,2C1.4167138.41022B1.416718031122B1.41671807.08351252B1.4167263.21362B1.41671801462B1.41671801572B1.4167138.441682B1.416776對于剩下各公司所需要貨物單位數量如下表:材料A20020005B11010001C10002311第二步：我們采用批次運輸方案：第一批次運輸，我們使

13、A材料有優先運輸權，在保證滿足各公司對A需求量條件下，1C與1A搭配滿足載重相對最大化方法運輸；第二批次運輸，我們使B材料有優先運輸權，在此次運輸我們滿足各公司尚缺B材料的量小于或等于2個單位；第三批次運輸剩下所需的貨物。具體運輸方式：首先優先考慮A貨物的處理方法，可知1公司還需1個車次的1A和一個車次的1A1C,4公司還需要2個車次的1A,8公司還需要4個車次的1A和1個車次的1A1C;接著處理B貨物，1公司和2公司共需要1個車次的2B,8公司和4公司共需要1個車次的2B;最后處理C貨物，5、6、7公司共需要1個車次的6C。由此可知共出車28次。如下表2:表2車輛車次數公司貨物時間（小時）運

14、費（元）各車工作時間（小時）41682B1416777.0835178A,C1.416767188A1.416758198A1.416758208A1.4167585218A1.4167586.1334221A,C1.416792.8231A1.416778.424122B1.5833142.26254A1.4167221.26.0333264A1.4167221.2277,6,56C1.75198.4288,42B1.58332062）根據1）和2）的結論及方法，不記派車成本和出車成本的28車次方案所需運費及時間如下表3:表3車輛車次數公司貨物時間（小時）運費（元）各車工作時間（小時）111

15、A,2C1.4167107.27.083521A,2C1.4167107.232A,2C1.416718043A,2C1.4167273.653A,2C1.4167273.6264A,2C1.4167325.67.083575A,2C1.4167263.287A,2C1.4167138.497A,2C1.4167138.41022B1.416718031122B1.41671807.08351252B1.4167263.21362B1.41671801462B1.41671801572B1.4167138.441682B1.4167767.0835178A,C1.416767188A1.416

16、758198A1.416758208A1.4167585218A1.4167585.8334221A,C1.416792.8231A1.416778.4241,22B1.5833142.26254A1.4167221.26.1667264A1.4167221.2277,6,56C1.75198.4288,42B1.5833206總446440.5007模型中變量對應的數值含義S1(n)n=1、2、8；81524292315115從港口到各個公司的貨運最短里程集S2(n)n=1、2、8；5245363137454955卸載后返回港口的最短空載里程集Q)(n)n=1、2、8；i=A、B、C;412

17、31025;15012423;52424351n公司對貨物i的實時需求量集W(n)n=1、2、8;j=1、2;2161214601221;0120061266第j批運至第n公司貨物的重量集Times(j)(n)n=1、2、8；j=1、2;41231025;02001211第j批運至第n公司次數集(d)ttd=15.0832第d問中組合運輸的耗時集)yd=1565.2第d問中組合運輸的費用集iii .目標分析運費最小是貨運公司調度運輸車的目標，運費包括派車固定成本、從港口出車成本、載重費用和空載費用。最后經過模型的計算得到最少費用為：4840.6元，最少耗時為：40.4999小時。二、問題二i.

18、車次規劃模型的分析兩個定理的證明定理一、車輛當且僅當運完最后一件貨物時才調頭途中允許調頭，運輸車可以先為較遠的公司送去小件原料，然后調頭，為比較近的公司送去大件。從表面上看，這樣運輸能夠節省車次，降低出車費用。但我們通過分析，在本題中，載重調頭運輸并不能降低費用。證明過程如下：在上圖中，記O點為港口，N、M為兩公司。M到港口的距離是S1,NM兩個公司之間的距離為S2假設將兩種貨物/口b（重量分別為x噸、y噸），分別運往N和M兩公司，現有兩種運輸方案：1 .若先運貨a、b到N,將a卸到N,調頭返回，將貨物b運往M,那么應、為C原料（x=1）,b為A或B（3EyE4）,記運費用為f12 .若先單獨

19、運送貨物彘小，返回港口后，再次出車，將貨物b運往M,即出車兩次，記運費用為f2。兩種方案需要的車輛相同時，為比較兩種運輸方式費用的大小，兩種運輸的種類質量均相同，記：f二f1一f2若f>0恒成立，則載重調頭送貨不節省費用，通過數據處理提取函數：因為4-y-3并且N、M兩公司在本題中的最小距離s2=4代入到f中，化簡得到令fmin=31.6-0.46：二0得到Si.75而港口到所有公司最短路的最大值為2蛤里，所以fminA0恒成立。說明前一種花費較高。方案二比方案一需要的車輛多時第二種方案是出車兩次，運輸時間較長，在8小時的工作時間內，可能會比調頭載重運輸時多安排車輛，派車費用增加。我們考

20、慮一種最差情況，因多運一次而增派一輛車，此時有得到Si_29因為港口到所有公司的最短路徑sM29所以fmin-0綜上，載重調頭運輸花費較高。證明了以運費用最小為目標時，車輛當且僅當運完最后一件貨物時才調頭。定理一的推論：運載里程與空載里程相同（表四中的第28車次例外），且每次出車均不繞圈工作。定理二、車輛載重行程是各公司到港口的最短路，且載重費用固定不變在定理一的基礎上，車輛當且僅當運完最后一件貨才調頭，且每次出車均不繞圈工作，那么每一單位的原料都可以由最短路徑運至需貨公司。我們變換視角，從宏觀的角度看去，對8個公司所需貨物的數量分別乘以公司和港口的最短距離和載重單價（1.8元/噸公里）就是將

21、貨物運至公司的載重費用，載重費用因子：貨物的數量、公司和港口的最短距離、載重單價都是定值，因此，載重費用是固定不變的。車次規劃階段只涉及到載重費用、空載費用和港口出車費用。運輸途中可以掉頭，即貨車可以送完貨沿原路返回港口。ii.模型建立根據問題一約束條件：在符合載重相對最大化情況下，公司順時針送貨為最佳方案，公司逆時針送貨最佳方案。此結論也可以適用貨車可以掉頭的情況。加上上面兩個定理，數學模型與問題一幾乎相同，只是空載路徑不同。故同樣分為兩步驟：第一步分為兩種滿載方案：第1種為每個車次裝載1單位A和2單位C;第2種是每個車次裝載2個單位B。并使每一車次在同一公司卸貨。第二步我們采用批次運輸方案

22、：第一批次運輸，我們使A材料有優先運輸權，在保證滿足各公司對A需求量條件下，C與A搭配滿足載重相對最大化方法運輸；第二批次運輸，我們使B材料有優先運輸權，在此次運輸我們滿足各公司尚缺B材料的量小于2個單位；第三批次運輸剩下的貨物。最終車次運載方案如下表4:表4車輛車次公司貨物時間（小時）運費各車工作時間（小時）111A,2C0.683489.67.283721A,2C0.683489.632A,2C0.916716843A,2C1.2167268.853A,2C1.2167268.864A,2C1.3834324.875A,2C1.1834257.6287A,2C0.7834123.27.78

23、3897A,2C0.7834123.21022B0.91671681122B0.91671681252B1.1834257.61362B0.91671681462B0.91671681572B0.7834123.21682B0.5834563178A,C0.5834474.2838188A0.583438198A0.583438208A0.583438218A0.583438221A,C0.683475.2231A0.683460.8424122B1.0833130.26.9501254A1.3834220.4264A1.3834220.4iii.目標分析運費最小是貨運公司調度運輸車的目標，運

24、費包括派車固定成本、從港口出車成本、載重費用和空載費用。由表4得知，第二問的總費用charga）=4127.2+20*4+10*28=4487.2元總時間Time=26.3014元三、問題三1）第一小問：結論：這次運貨不需要使用4噸貨車。只使用6噸、8噸貨車搭配運輸即可。i.模型建立我們經過上述論證，排除了4噸貨車的使用。題目沒有規定車子不能變向，所以認為車輛可以掉頭。我們仍舊采取公司順時針送貨，公司逆時針送貨的方案。根據上述條件我們建模如下：第一步，使8噸車次滿載并運往同一公司；第二步，使6噸位車次滿載并運往同一公司；運載方案如下表5:車輛車次公司貨物時間（小時）各車工作時間（/時）弟一輛8

25、噸車112A0.6834120.86.9504212A0.6834120.83r11B,5c0.6834120.842A,B,C0.9167226.5532A1.2167362.46r412A1.3834437.974A,B,C1.3834437.9第二輛8噸車85A,B,C1.1834347.35.41719r62B,2C0.9167226.51072A0.7834166.11172B,2C0.7834166.112r82A0.583475.51382A0.583475.5148A,B,C0.583475.5第一輛6噸車1522B0.91671687.31691622B0.916716817

26、5B,3C1.1834257.618612B0.91671681982B0.583456對于剩下各公司所需要貨物單位數量如下表:材料A00000000B00000000C01410130第三步，從上表可知只剩下2,3,4,6，公司需要C貨物10屯，必須要用至少兩個車次來運。我們已經論證排除了4噸貨車的使用，為了使費用降低，我們決定用2個6噸車次來運貨，具體運載方案如下表6:車輛車次公司貨物時間（小時）各車工作時間（小時）第一202,3,41C,4C,1C1.7167263.61.7167輛6噸車217.63C,1C1.083392.41.0833第四步，上述三個步驟，不記派車成本和出車成本的21車次方案所需運費及時間如下表7:車輛車次公司貨物時間（小時）各車工作時間（小時）弟一輛8噸車112A0.6834120.86.9504212A0.6834120.831B,5C0.6834120.842A,B,C0.9167226.5532A1.2167362.46二4二2A1.3834437.974A,B,C1.3834437.9第二輛8噸車85A,B,C1.