第1章 緒論

1.1 選題背景及研究意義

1.1.1 選題背景

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

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

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

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

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

1.1.2 研究意義

1.1.2.1 理論意義

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

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

1.1.2.2 現實意義

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