【文章內(nèi)容簡(jiǎn)介】 22500337504500056250注：返程價(jià)按單價(jià)的50%計(jì)算。結(jié)果發(fā)現(xiàn)，無論是以單程還是以往返計(jì)算，如果貨流量足以使運(yùn)送次數(shù)保持在大于等于三趟，自營(yíng)將比外包更經(jīng)濟(jì)。也可以用圖41來表示： A C運(yùn)費(fèi)Q運(yùn)量圖41 自營(yíng)外包車輛費(fèi)用曲線圖曲線1表示外雇車輛的運(yùn)送費(fèi)用隨運(yùn)輸量的變化情況；曲線2表示自有車輛的運(yùn)送費(fèi)用隨運(yùn)量的變化情況。當(dāng)運(yùn)量小于A時(shí)，外雇車輛費(fèi)用小于自有車輛費(fèi)用，所以應(yīng)選用外雇車輛；當(dāng)運(yùn)輸量大于A時(shí)外雇車輛費(fèi)用大于自有車輛費(fèi)用，所以應(yīng)選用自有車輛。但無論自有車輛還是外雇車輛，都必須事先掌握有那些車輛可以供調(diào)派并符合要求，即這些車輛的容量和額定載重是否滿足要求；其次，安排車輛之前，還必須分析訂單上貨物的信息，如：體積、重量、數(shù)量等對(duì)于裝卸的特別要求等，綜合考慮各方面因素的影響，做出最合適的車輛安排。運(yùn)輸路線選擇：主要是選擇起點(diǎn)到終點(diǎn)的最短路。最短路的度量單位可能是時(shí)間最短、距離最短或費(fèi)用最小等。路線選擇問題可分為以下幾類： 中間點(diǎn)相同，起訖點(diǎn)不同 中間點(diǎn)不同，但起訖點(diǎn)相同 多個(gè)起點(diǎn)，多個(gè)終點(diǎn)，沒有中間點(diǎn) 多個(gè)起點(diǎn)，多個(gè)終點(diǎn)，有中間點(diǎn)或轉(zhuǎn)運(yùn)點(diǎn) 起訖點(diǎn)不同這種情況通常不考慮其他運(yùn)輸因素，如路徑容量約束等。常用最短路算法，其步驟如下：第一步：確定網(wǎng)絡(luò)中已標(biāo)號(hào)及未標(biāo)號(hào)的點(diǎn)；第二步：對(duì)每個(gè)標(biāo)號(hào)的點(diǎn)，確定和它直接相連的未標(biāo)號(hào)的點(diǎn)進(jìn)行標(biāo)號(hào)；第三步：選擇和已標(biāo)號(hào)的點(diǎn)有最近距離的未標(biāo)號(hào)的點(diǎn)進(jìn)行標(biāo)號(hào)；第四步：若到達(dá)終點(diǎn)便停止，否則返回第二步，重新進(jìn)行。 起終點(diǎn)相同這類問題主要指考慮從設(shè)施點(diǎn)出發(fā)訪問一定數(shù)量顧客后又回到原來的出發(fā)點(diǎn)的線路確定問題。其目標(biāo)是確定回到出發(fā)點(diǎn)前服務(wù)顧客的次序，使總運(yùn)輸距離最小。通常的數(shù)學(xué)模型為： 式中：Cij——司機(jī)經(jīng)過對(duì)應(yīng)路段（i,j）所花的費(fèi)用，如時(shí)間、距離、費(fèi)用等；決策變量Xij——如果路段（i,j）在線路上，其值為1，否則為0。簡(jiǎn)單貪婪算法可以解決這類問題，其步驟如下：第一步：選擇距出發(fā)點(diǎn)最近的顧客位置：第二步：再?gòu)臎]有選擇的位置中選距離當(dāng)前已選擇的位置最近的顧客；第三步：如果所有位置都選了便停止，否則返回到第二步。多起點(diǎn)、多終點(diǎn)，沒有中間點(diǎn) 這個(gè)問題主要是將多個(gè)供應(yīng)點(diǎn)的供應(yīng)分配到多個(gè)顧客需求點(diǎn)，常用在產(chǎn)品從工廠到倉(cāng)庫(kù)的配送、從倉(cāng)庫(kù)向顧客供應(yīng)等。這類運(yùn)輸問題可以描述為：設(shè)某物資有m個(gè)產(chǎn)地A1，A2，…，Am；供應(yīng)n個(gè)銷地B1，B2，…，Bn；已知Ai的產(chǎn)量為ai（i=1,2,…,m,j=1,2,…,n）則運(yùn)輸問題的數(shù)學(xué)模型為： 多起點(diǎn)、多終點(diǎn)，有中間點(diǎn)這個(gè)問題是指最優(yōu)分配多個(gè)供應(yīng)點(diǎn)的供應(yīng)到多個(gè)需求點(diǎn)，也可以靈活地在各中間點(diǎn)處分配，有些起點(diǎn)或終點(diǎn)也可能是中間點(diǎn)。這類問題又稱為轉(zhuǎn)運(yùn)問題。解決此問題第一步要采用一些規(guī)則將它轉(zhuǎn)化為運(yùn)輸問題，那就可以用任何一種求解運(yùn)輸問題的算法來解決了。運(yùn)輸車輛增加，反應(yīng)時(shí)間短了，運(yùn)送頻率高了，服務(wù)水平也就增長(zhǎng)了。然而，這就有可能造成車輛的利用率降低。所以確定車輛的規(guī)模是取得運(yùn)輸效益的重要環(huán)節(jié)。下面用一些模型來確定運(yùn)輸車輛的規(guī)模。 齊次運(yùn)輸車輛模型 F——每天固定費(fèi)用（無論車輛是否使用都存在，包括折舊費(fèi)用、路稅、司機(jī)基本工資）；V——每天變動(dòng)成本（僅當(dāng)車輛使用時(shí)才存在，包括燃油、輪胎磨損等）； H——每天每輛車租金 Y——一年工作天數(shù)； P——額外租用其他車輛工作的天數(shù)。 所給模型為： 年租車總費(fèi)用=PH 年增加的車輛總費(fèi)用=FY+PVFY+PVPH或當(dāng)時(shí)，就可以再買一輛車。 齊次線性規(guī)劃的擴(kuò)展數(shù)學(xué)模型為：式中：xjk——第j天需要第k類車的數(shù)量； Hjk——第j天需要租用第k類車的數(shù)量； Djk——貨物的需求量（以相當(dāng)于第j天第k類車的數(shù)量計(jì)算）；Fk——每天所需的第k類車固定費(fèi)用；Vk——每天所需的第k類車變動(dòng)費(fèi)用；Hk——每天所需的第k類車的租金。上述模型的目標(biāo)函數(shù)是使變動(dòng)、固定費(fèi)用及額外租車費(fèi)用最小。第一個(gè)約束保證由合適類型的車輛進(jìn)行運(yùn)輸來滿足每天的需求量。第二個(gè)約束是決策變量的非負(fù)整數(shù)約束。 車輛分派模型式中：Xjk——如果第j類車分配給任務(wù)k，則其值為1，否則為0； Cjk——將第j類車分配給任務(wù)k的費(fèi)用（如果第j類車不能分給此任務(wù)，此費(fèi)用值將會(huì)特別大）。目標(biāo)函數(shù)是使分派車輛完成任務(wù)的總費(fèi)用最小，第一個(gè)約束保證每一輛車分派到一項(xiàng)任務(wù)；第二個(gè)約束保證每項(xiàng)任務(wù)都能有一輛車完成。此模型可用匈牙利法解。線路決策包括根據(jù)距離選擇起終點(diǎn)間各站次序，調(diào)度決策主要考慮運(yùn)輸時(shí)間，它在運(yùn)輸中是非常重要的。這些決策重點(diǎn)考慮在哪天什么時(shí)間、多少車輛從哪兒安排到哪兒。約束可能是車輛數(shù)量、根據(jù)車輛和設(shè)備類型選擇的可能線路、每個(gè)地點(diǎn)運(yùn)送或集貨的量、服務(wù)時(shí)間窗及基于安全考慮的員工休息和工作時(shí)間段等約束。進(jìn)行優(yōu)化調(diào)度的基本原則主要包括：將一個(gè)車輛分派到距離較近的?？奎c(diǎn)或城市，要考慮車輛運(yùn)輸能力（空間協(xié)調(diào)）；盡可能合并每個(gè)站點(diǎn)的集配貨工作。將本時(shí)間段內(nèi)需送的貨合并同一天配送（時(shí)間協(xié)調(diào)）；建立以距離倉(cāng)庫(kù)最遠(yuǎn)的站點(diǎn)為起點(diǎn)的線路；最大限度地利用車輛以使車輛利用率不足帶來的費(fèi)用最小；避免時(shí)間要求過高，盡量同用戶協(xié)商；運(yùn)用其他替代方案進(jìn)行遠(yuǎn)距離或低貨運(yùn)量地點(diǎn)的集配貨作業(yè)。車輛調(diào)度問題的解法：車輛調(diào)度問題的求解策略包括先分組后安排線路、先安排線路后分組、節(jié)約/插入法、改進(jìn)/交換法、數(shù)學(xué)規(guī)劃算法等。在先分組后安排線路方法中，先對(duì)需求點(diǎn)進(jìn)行分組聚類，每一組都包括一些滿足車輛能力及時(shí)間約束的距離較近的點(diǎn)集，然后再為每一組確定最佳線路。先安排線路再分組方法和上述操作程序正好相反，首先構(gòu)造一些包括所有需求點(diǎn)的線路，然后再把這些線路分成一些短而可行的線路。在節(jié)約/插入算法中對(duì)根據(jù)一定的準(zhǔn)則（最大節(jié)約準(zhǔn)則）兩點(diǎn)進(jìn)行比較，把不在線路上的點(diǎn)插入線路，已在線路中的點(diǎn)合并為一集合，直到整列所有點(diǎn)都被安排到線路中，在插入時(shí)要保證總運(yùn)行時(shí)間或距離滿足約束。同時(shí)，插入新點(diǎn)后的線路上載貨量不能超過車輛承載能力，每次所選插入的點(diǎn)都不能包括在已合并的點(diǎn)集中。另外還有時(shí)間的約束，當(dāng)運(yùn)送人拖延時(shí)間送達(dá)目的地則還要計(jì)算懲罰成本。下面用數(shù)學(xué)模型具體描述此種方法。①模型的建立車輛編號(hào)為k,任務(wù)編號(hào)為1,2,…,l ,考慮運(yùn)輸量約束、停車點(diǎn)車輛數(shù)目約束、集貨和卸貨時(shí)間約束等約束,可定義如下的基本模型 式中,Cij表示從點(diǎn)i到j(luò)的運(yùn)輸成本,它可以根據(jù)優(yōu)化的目標(biāo)具體體現(xiàn)為運(yùn)輸距離或運(yùn)輸費(fèi)用或運(yùn)輸時(shí)間。 Tij表示按要求準(zhǔn)時(shí)將貨物從客戶i運(yùn)到客戶j所用的時(shí)間。 Tijb沒按要求拖期將貨物從客戶i運(yùn)到客戶j所用的時(shí)間。ETi和LTi分別為任務(wù)i允許的最早開始時(shí)間和允許的最遲結(jié)束時(shí)間。gi為第i點(diǎn)的貨運(yùn)量。q為運(yùn)輸車輛的額定載重量。x ijk和yki為變量,定義為 ②模型的求解CW算法由Clarke和Wright提出，該算法簡(jiǎn)單易用，以改進(jìn)的CW節(jié)約啟發(fā)式算法為例來求解車輛調(diào)度問題。其步驟如下：①首先計(jì)算各個(gè)點(diǎn)i和點(diǎn)j之間線路的費(fèi)用節(jié)約值s(i,j)，形成集合M，并按照從大到小對(duì)s(i, j)進(jìn)行排序，其中，s(i,j)=ci0+c0jcij。②若M為空，則終止疊代，否則對(duì)M中的第一項(xiàng)s(i,j)考察是否滿足下列條件之一,如滿足則轉(zhuǎn)下步，否則轉(zhuǎn)⑥。(a)點(diǎn)i和j均不在已構(gòu)成的線路上；(b)點(diǎn)i和j在已構(gòu)成的線路上，但不與車場(chǎng)相連；(c)點(diǎn)i和j位于已構(gòu)成的不同線路上，均不與車場(chǎng)相連,且一個(gè)是起點(diǎn)，一個(gè)是終點(diǎn)。③考察點(diǎn)i和j連接后的線路上總貨運(yùn)量Q，若Q≤q，則轉(zhuǎn)下步，否則轉(zhuǎn)⑥。④計(jì)算連接點(diǎn)i和j所在的線路后，車輛到達(dá)j點(diǎn)的時(shí)間比原路線上車輛到達(dá)j點(diǎn)的時(shí)間的變化量為EFj=si+Ti+tijsj。(a)若EFj=0，轉(zhuǎn)⑤；(b)若EFj0，則計(jì)算Δj，當(dāng)|EFj|≤Δj，轉(zhuǎn)⑤，否則轉(zhuǎn)⑥；(c)若EFj0，則計(jì)算Δj+，當(dāng)|EFj|≤Δj+，轉(zhuǎn)⑤，否則轉(zhuǎn)⑥。式中,Δj為線路上j點(diǎn)后面的各任務(wù)處均不需要等待的到達(dá)j點(diǎn)時(shí)間的最大允許提前量。Δj+為線路上j點(diǎn)后面的各任務(wù)不違反時(shí)間約束的到達(dá)j點(diǎn)時(shí)間的最大允許推遲量。其中,Δjminr≥j{SrETr}Δj+minr≥j{LTrSr}⑤連接點(diǎn)i和點(diǎn)j,計(jì)算車輛到達(dá)各任務(wù)時(shí)的新時(shí)間。⑥令M=Ms(i,j),轉(zhuǎn)②。 運(yùn)輸成本與產(chǎn)品的種類、裝運(yùn)的規(guī)模以及運(yùn)輸距離直接相關(guān)。要減少運(yùn)輸成本，就需要實(shí)現(xiàn)整合運(yùn)輸。整合運(yùn)輸可根據(jù)時(shí)間、庫(kù)存、空間或設(shè)備進(jìn)行。這些方法都是通過減少運(yùn)輸次數(shù)使運(yùn)行費(fèi)用減少，但這樣有可能造成服務(wù)水平降低、庫(kù)存成本增加，不過通常能由設(shè)備、人員、維修成本的減少去抵消相關(guān)費(fèi)用的增加。 基于時(shí)間的整合當(dāng)在同一地點(diǎn)兩個(gè)顧客需要不同日期送達(dá)商品時(shí)，比如一個(gè)在星期一，一個(gè)在星期二，那么可能有三個(gè)選擇：①第一個(gè)顧客，星期一送達(dá)，第二個(gè)顧客，星期二送達(dá)。這樣導(dǎo)致要送達(dá)兩次，但能準(zhǔn)時(shí)送達(dá)；②都在星期一送達(dá)，這樣導(dǎo)致第二個(gè)顧客多余庫(kù)存但節(jié)省一次運(yùn)輸；③都在星期二送到，節(jié)省了一次運(yùn)輸，但增加了第一個(gè)顧客的周轉(zhuǎn)時(shí)間（假設(shè)顧客的總需求能用一輛車運(yùn)輸）。 貨物整合運(yùn)輸策略用于完成設(shè)備和空間整合的三種常用啟發(fā)式策略是：最近中轉(zhuǎn)站線路、最小距離線路、最小費(fèi)用線路。 最近中轉(zhuǎn)站線路：將貨物送到距起點(diǎn)或終點(diǎn)或距二者都很近的中轉(zhuǎn)站（除終點(diǎn)），這樣的結(jié)果是有些貨物需進(jìn)行返程運(yùn)輸。如果中轉(zhuǎn)站距起終點(diǎn)都比較近，可用短途運(yùn)輸。最近的中轉(zhuǎn)線路只是使地方短途運(yùn)輸費(fèi)用及距離都最小，但不能保證整個(gè)系統(tǒng)距離和費(fèi)用最小。最近距離線路：在這種情況下，貨物送到使總運(yùn)輸距離最小的中轉(zhuǎn)站。因此，從一起點(diǎn)出發(fā)的貨物可能根據(jù)其中點(diǎn)不同送到不同的中轉(zhuǎn)站。因此短途和長(zhǎng)途有差異，最近距離線路可能系統(tǒng)總費(fèi)用最小。最小費(fèi)用線路：在這種情況下，為了使總費(fèi)用最低，貨物通過中轉(zhuǎn)站運(yùn)輸。因此，如果貨物拼裝能使總費(fèi)用最低，允許有些貨物進(jìn)行返程運(yùn)輸。同時(shí)，從同一起點(diǎn)出發(fā)的貨物根據(jù)其目的地不同運(yùn)往不同中轉(zhuǎn)站。 復(fù)合運(yùn)輸選擇模型此模型最初是由Reddy(1995)給出的，此模型的特點(diǎn)是以費(fèi)用最小作為目標(biāo)函數(shù)，假設(shè)在任一給定兩城市間采用同一種運(yùn)輸方式，運(yùn)輸費(fèi)用和運(yùn)輸距離成線性關(guān)系。決策變量如下：①式①中目標(biāo)函數(shù)是使兩個(gè)線性費(fèi)用函數(shù)取值最小。右邊式子第一項(xiàng)是對(duì)一給定數(shù)目的貨物從起點(diǎn)到終點(diǎn)的總運(yùn)輸費(fèi)用。第二項(xiàng)是總轉(zhuǎn)運(yùn)費(fèi)用，此項(xiàng)只有在中間某地點(diǎn)將貨物從一種方式轉(zhuǎn)換為另一種方式時(shí)才存在。第一個(gè)約束保證在任兩市間只有一種方式運(yùn)輸貨物。第二個(gè)約束是指在某一城市只有一種轉(zhuǎn)運(yùn)類型。第三個(gè)約束保證其內(nèi)部具有一致性，即如果在城市i運(yùn)輸方式從k變?yōu)閘，那么從i1市到i時(shí)貨物就是通過k方式運(yùn)輸，而從i市到i+1時(shí)貨物將通過l方式運(yùn)輸。最后一個(gè)約束是決策變量的0—1約束。 求解算法對(duì)于m個(gè)運(yùn)輸方式n個(gè)城市來說，解的數(shù)目是mn1個(gè)，由于決策變量約束數(shù)目太多，因此可用動(dòng)態(tài)規(guī)劃的逆序解法求解這個(gè)模型。其具體算法如下：每個(gè)城市都作為動(dòng)態(tài)規(guī)劃的一個(gè)階段，從城市n1到城市n的總費(fèi)用包括在城市n1運(yùn)輸方式從k變?yōu)閘的轉(zhuǎn)運(yùn)費(fèi)用和從 n1市到n市采用l運(yùn)輸方式的運(yùn)輸費(fèi)用，用pn1表示 ②式中:q是貨運(yùn)量，其他符號(hào)同前面。給定進(jìn)入n1市的運(yùn)輸方式為k，則從n1市除去采用的運(yùn)輸方式的最佳方案為m*。m*由下式得出： ③從城市2到城市n2所對(duì)應(yīng)的任一城市i的最優(yōu)運(yùn)輸方式為r*，這樣計(jì)算： ④ ⑤假定：=0對(duì)于城市1到城市2，最好的運(yùn)方式計(jì)算公式為： ⑥上述動(dòng)態(tài)規(guī)劃算法只需計(jì)算m(n1)次， 是任兩城市對(duì)間運(yùn)輸方式的數(shù)目， 使整個(gè)運(yùn)輸中城市數(shù)目。根據(jù)以上遞推公式，在符合運(yùn)輸線路中解決最優(yōu)的運(yùn)輸結(jié)合方式的算法步驟如下：第一步：用公式 ② 和 ③ 選擇離開城市n1的最優(yōu)運(yùn)輸方式；第二步：用公式 ④ 和 ⑤ 選擇從城市2到城市n2所對(duì)應(yīng)的最優(yōu)運(yùn)輸方式：第三步：用公式 ⑥ 計(jì)算p1(s*) 最優(yōu)的運(yùn)輸方式則可以根據(jù)式 ⑥ 、⑤ 、④ 的結(jié)果反向推算得出。 運(yùn)輸效率的最大化，必然能使運(yùn)輸成本的最小化。基于此點(diǎn)，有必要了解如下