第1章 緒論

1.1 選題背景及研究意義

1.1.1 選題背景

隨著商業(yè)模式的演變，物流成為企業(yè)的第三利潤源，在企業(yè)競爭中占據(jù)著越來越重要的地位。企業(yè)調(diào)研發(fā)現(xiàn)，卷煙生產(chǎn)原料運輸成本長期居高不下已成為煙草行業(yè)面臨的普遍問題。以中部地區(qū)某煙草公司為例，該公司下屬的8家卷煙廠分別位于省內(nèi)不同的城市，由于沒有原料中心倉庫，所以該公司采取分散倉儲的方式，即每家卷煙廠只存儲某些特定種類的生產(chǎn)原料。另外，該公司生產(chǎn)的卷煙有10多種規(guī)格且每種規(guī)格的卷煙需要幾十種生產(chǎn)原料，而每家卷煙廠生產(chǎn)的卷煙規(guī)格并不相同。因此，在這種分散式生產(chǎn)和分散式倉儲的模式下，生產(chǎn)原料在不同卷煙廠之間頻繁調(diào)撥就不可避免。在實際中，每家卷煙廠都會根據(jù)提前下達的生產(chǎn)計劃和生產(chǎn)配方，結(jié)合當(dāng)前原料庫存信息，計算出完成生產(chǎn)任務(wù)需要調(diào)撥的原料種類和數(shù)量；為了快速響應(yīng)生產(chǎn)計劃，每家卷煙廠都提前自行制訂具體的原料調(diào)撥方案以滿足自身的生產(chǎn)需求。目前，該公司采用送貨制的方式運輸原料，即當(dāng)卷煙廠1需求某種原料m時，由距離卷煙廠1最近且能供應(yīng)原料m的卷煙廠2派車把原料m運送到卷煙廠1，然后空車返回。如果卷煙廠2不能單獨滿足卷煙廠1的需求，則剩下的需求由最近且能供應(yīng)原料m 的卷煙廠3來滿足，這樣依次進行直到卷煙廠1的需求得到滿足為止。

在此模式下，一方面，原料調(diào)撥決策權(quán)分散于各個卷煙廠，每家卷煙廠都站在自己的角度對單批次需求做局部最優(yōu)的供需匹配決策，而沒有站在公司的角度考慮整體最優(yōu)的供需匹配，這是原料運輸成本較高的主要原因。另一方面，針對單次調(diào)撥，每家卷煙廠也只站在自己的角度考慮局部最優(yōu)路徑?jīng)Q策，而沒有站在公司的角度考慮整個運輸網(wǎng)絡(luò)的最優(yōu)路徑規(guī)劃，使運輸路徑安排不合理，這也是原料運輸成本較高的主要原因。此外，送貨制導(dǎo)致車輛空車返回率較高，運輸資源嚴重浪費，當(dāng)多個卷煙廠有多種原料需求時，易出現(xiàn)車輛緊缺現(xiàn)象。該公司決策權(quán)分散，沒有部門統(tǒng)一負責(zé)原料調(diào)撥任務(wù)，導(dǎo)致原料調(diào)撥效率較低且費用較高。為解決此問題，該公司希望成立一個物流管控部門（物流中心），通過制訂集中模式下的原料聯(lián)合調(diào)撥全局最優(yōu)方案（考慮全局最優(yōu)的供需匹配決策和車輛路徑?jīng)Q策），提高運輸資源利用率及原料調(diào)撥效率，進而降低原料運輸成本。

零售行業(yè)中也普遍存在類似的問題，如服裝連鎖店一旦有新產(chǎn)品上市，為了有效滿足客戶多元化需求，增加銷售機會，總公司會在各家連鎖店投放一定數(shù)量的某些產(chǎn)品。經(jīng)過一段時間的銷售后，總公司發(fā)現(xiàn)有些連鎖店的某種或某些類型的產(chǎn)品出現(xiàn)斷貨，而其他連鎖店的該種或該類型的產(chǎn)品卻仍有較高的庫存量。在目前實際運營中，當(dāng)客戶去某家商店購買某種產(chǎn)品時，恰好該種產(chǎn)品出現(xiàn)斷貨現(xiàn)象，此商店通常采用就近調(diào)貨的方式來盡快滿足客戶的需求。顯然，這種調(diào)貨模式?jīng)]有考慮其他商店的產(chǎn)品需求情況，所做的供需匹配決策及路徑?jīng)Q策同樣只是局部最優(yōu)。為快速響應(yīng)客戶需求，增加銷售機會，降低調(diào)貨成本，最好的選擇應(yīng)是在各商店出現(xiàn)斷貨之前，總公司從全局的角度對各商店的產(chǎn)品庫存進行重新布局。

也有文獻對類似問題進行了研究。首先，針對共享單車系統(tǒng)的自行車重新布局問題（Raviv et al.，2013；Chemla et al.，2013；Dell'Amico et al.，2014；Forma et al.，2015），系統(tǒng)中每個車站存放一定數(shù)量的自行車，客戶根據(jù)自己的需求可以在任何站點取走自行車，使用結(jié)束后可以歸還到任何站點。一段時間后，當(dāng)前系統(tǒng)中有些車站的自行車數(shù)量不能滿足客戶的需求，而有些車站的自行車數(shù)量大于客戶的需求。為使系統(tǒng)中自行車的利用率最大化，需要對系統(tǒng)中各個站點的自行車庫存重新布局。其次，針對國際原油運輸問題（Andersson et al.，2011；Hennig et al.，2012a，2012b；Agra et al.，2013，2014，2015；Siddiqui and Verma，2015），因石油是由多種不同規(guī)格的原油煉制而成的，所以每個煉油廠只生產(chǎn)一種或幾種規(guī)格的原油。在煉制過程中，有些煉油廠需要其他煉油廠提供所需規(guī)格的原油，從而需要在各個煉油廠之間轉(zhuǎn)運各種規(guī)格的原油來滿足每個煉油廠的需求。

本書針對這些行業(yè)面臨的現(xiàn)實問題進行提煉并加以研究，將為企業(yè)的實際運營提供重要的理論支撐和實踐指導(dǎo)。

1.1.2 研究意義

1.1.2.1 理論意義

本書對供需未匹配取送貨車輛路徑問題進行了全面且深入的探究，從客戶需求是否可任意拆分和滿足兩個角度出發(fā)，分別研究多次訪問條件下的多商品供需未匹配取送貨車輛路徑問題、單次訪問條件下的多商品供需未匹配取送貨車輛路徑問題，并針對以上問題分別構(gòu)建模型、分析特性和設(shè)計算法，以達到優(yōu)化的目的。

雖然當(dāng)前文獻中關(guān)于車輛路徑問題的研究較多，但大多數(shù)研究都是“供需匹配關(guān)系事先已知”的情況，而關(guān)于供需匹配關(guān)系事先未知的取送貨車輛路徑問題的研究較少；在已有的研究供需匹配關(guān)系未知的文獻中，大多是建立在客戶需求一次性滿足的條件下，關(guān)于供需匹配關(guān)系未知和需求可拆分的取送貨車輛路徑問題的研究則少之又少。盡管目前有少量文獻考慮了“供需匹配關(guān)系事先未知”的情況來研究取送貨車輛路徑問題，但主要集中在海上運輸系統(tǒng)。然而，在海上運輸系統(tǒng)中的研究一般考慮多周期，庫存約束、取送貨時間窗約束、供應(yīng)和需求信息均不確定，導(dǎo)致海上運輸系統(tǒng)研究的取送貨車輛路徑問題與本書研究的問題差異較大。具體差異如下：①在海上運輸系統(tǒng)中，在每個港口取貨或投貨時需考慮時間窗約束，而本書研究的問題不考慮取送貨時間窗約束。②在海上運輸系統(tǒng)中，在每個港口取貨或投貨時一般需考慮庫存約束，而本書研究的問題不考慮庫存約束。③在海上運輸系統(tǒng)中，網(wǎng)絡(luò)中每個客戶點關(guān)于每種產(chǎn)品的供應(yīng)總量和需求總量隨生產(chǎn)變化，并不確定；而在本書研究的問題中，運輸網(wǎng)絡(luò)中每個客戶點關(guān)于每種產(chǎn)品的供應(yīng)信息和需求信息事先確定。以上差別導(dǎo)致海上運輸系統(tǒng)的研究成果不能被直接應(yīng)用到本書研究的問題中。因此，本書試圖從客戶需求是否可任意拆分和滿足兩個角度進行探究，建立數(shù)學(xué)模型，設(shè)計相應(yīng)的求解算法，并進行數(shù)值測試。對供需未匹配的取送貨車輛路徑問題進行深入探究并對研究結(jié)果進行總結(jié)，預(yù)期研究成果在解決本書研究問題的同時，能對取送貨車輛路徑問題相關(guān)領(lǐng)域的現(xiàn)有理論進行有益擴展，從理論上為其他相關(guān)問題的研究提供借鑒。

1.1.2.2 現(xiàn)實意義

供需未匹配的取送貨車輛路徑問題來源于企業(yè)實際的物流需求。如中部地區(qū)某煙草公司有8家卷煙廠，分別位于省內(nèi)不同城市。這種分散式生產(chǎn)導(dǎo)致物流決策權(quán)在一定程度上分散。原料采購回來后存儲在各家卷煙廠，每家卷煙廠的原料供應(yīng)均由廠內(nèi)的物流部門負責(zé)。生產(chǎn)任務(wù)下達后，當(dāng)某家卷煙廠需求某種原料時，經(jīng)本廠原料部門負責(zé)人與其他卷煙廠的原料部門負責(zé)人溝通，由能夠供應(yīng)該種原料的卷煙廠派車把所需原料送到，然后空車返回。由于沒有從整個公司的角度考慮全局最優(yōu)的需求匹配決策和路徑?jīng)Q策，空車返回率高，運輸資源嚴重浪費，從而導(dǎo)致運輸成本較高。除制造行業(yè)外，零售行業(yè)也存在同樣的問題。如服飾、電器銷售一段時間后，有些商店某類產(chǎn)品出現(xiàn)斷貨，有些商店卻持有較高的該類商品庫存。為增加銷售機會，需要對各商店的產(chǎn)品庫存重新布局，即在各商店之間調(diào)貨。另外，在國際原油運輸系統(tǒng)（Hennig et al.，2012a，2012b）和共享單車系統(tǒng)（Raviv et al.，2013）中也存在類似的問題。針對企業(yè)面臨的實際問題構(gòu)建量化的數(shù)學(xué)模型，通過設(shè)計精確算法來求解中小規(guī)模的問題，設(shè)計高效的啟發(fā)式算法來求解大規(guī)模問題，有效降低物流成本、提高運輸資源利用率和原料調(diào)撥效率，從而提高企業(yè)的核心競爭力。