導語：如何才能寫好一篇數學建模啟發式算法，這就需要搜集整理更多的資料和文獻，歡迎閱讀由公務員之家整理的十篇范文，供你借鑒。

篇1

關鍵詞：物流工程；運籌學；庫存控制

作者簡介：謝逢潔（1974-），女，重慶人，西安郵電大學管理工程學院，講師。（陜西 西安 710061）崔文田（1966-），男，陜西米脂人，西安交通大學管理學院，教授。（陜西 西安 710049）

基金項目：本文系教育部高等學校物流類專業教學指導委員會教改課題（課題編號：JZW2011013）的研究成果。

中圖分類號：G642.0 文獻標識碼：A 文章編號：1007-0079（2013）04-0110-02

隨著電子商務近十年的迅速發展，我國物流企業如雨后春筍般成長起來。攤開一張中國物流地圖，密密麻麻的干線、支線一團亂麻似的交織在一起。然而，中國物流每年30%左右的增長速度仍然難以滿足每年100%速度增長的淘寶貨運需求。那么，有效地利用現有資源進行優化配置，成為物流企業滿足社會經濟發展需求的重要途徑，這無疑給物流專業的“運籌學”教學工作提出了前所未有的挑戰。根據《教育部高等學校物流類專業教學指導委員會關于物流工程本科專業培養方案的指導意見》，“運籌學”是各高校物流工程專業必需開設的學科基礎課程，建議課程學分為3分左右，其他學科基礎課具體課程及學分由各高校自定。這充分說明了“運籌學”課程在物流工程專業教學中的基礎性和重要性。那么，根據我國物流業發展中的實際問題，結合物流工程專業“運籌學”教學需求，探討教學內容和教學方法的改革具有重要意義，但同時這也是擺在每個物流工程專業“運籌學”教學工作者面前的重要問題。

一、我國物流業的主要問題及其原因分析

在電子商務環境下，涌現出大量種類多、批量小、批次多、目的地分散的隨機零散的物流需要，這與傳統的糧食、燃料、建材等大宗物資運輸需求有著明顯的差別。大量的零散物流需求為我國物流業發展帶來了契機，同時也暴露出其存在的問題。

首先，物流成本高是我國物流業一直以來存在的問題。隨著電子商務環境下零散物流需求的激增，成本問題愈發顯得嚴重。據國家發改委2011年12月1日披露的數據，2011年1月至10月，我國社會物流總費用6.4萬億元，同比增長18.7%。目前，中國的物流成本占GDP總量比重約為18%，而日本是11%，美國是8%，歐盟只有7%。究其原因，除了油價上漲以及物流運輸中的各種亂收費現象外，每年以30%左右的速度發展起來的物流企業資質參差不齊，配送中心的選址、庫存控制、車輛路徑規劃等有利于物流企業降低成本的優化途徑在一些新建物流企業中并沒有得到很好地應用。這是我國物流成本高的主觀因素，也是物流專業“運籌學”教學需要重點關注的問題。

此外，在電子商務環境下，客戶對產品可得性的心理預期增強，進而使得其對交貨時間的要求遠遠高于傳統物流貨運的要求。而我國大多數物流企業尚未形成一個完整有效的物流系統，配送中心和運輸系統缺乏協調，庫存控制和車輛路徑規劃存在矛盾，長途運輸和短途配送缺乏銜接等問題普遍存在。這無疑會導致物流企業貨運時間的拖延，使得客戶對交貨時間的需求時常難以得到滿足。因此，物流系統的協調優化也是“運籌學”教學需要重點關注的問題。

二、物流工程專業“運籌學”教學的主要內容

“運籌學”教材種類繁多，本文以清華大學出版社出版的《運籌學》章節劃分為例進行相關內容的闡述。目前，我國各高校管理類本科層次的運籌學教學內容通常由線性規劃與目標規劃、整數規劃、動態規劃、圖與網絡、排隊論等幾部分構成，略有差異。非線性規劃、存儲論、對策論、決策論、啟發式方法等則通常作為研究生階段的教學內容。物流工程專業具有管理學科的一般屬性，同時還具有本專業的一些特性。為了更好地滿足我國快速發展的物流業對專業人才的需求，物流工程專業“運籌學”教學應在保持管理類運籌學教學內容廣度的基礎上，突出物流工程專業“運籌學”教學需要解決的一些重要問題，包括配送中心選址、庫存控制、車輛路徑規劃以及物流配送系統協調優化等問題。

1.配送中心選址問題相關教學內容

配送中心選址問題是給定某一地區所有需求點的集合，要求從中選出一定數目的需求點建立配送中心，實現對所有需求點的配送，并使得總配送路徑或配送費用最小。整數規劃是目前應用最廣泛也是最主要的定量選址技術，其求解方法包括分支定界法、割平面法和隱枚舉法，其優點是能獲得精確的最優解。但是對一些模型太復雜的情況，如對整個物流網絡進行規劃時的大型復雜選址問題，由于變量和約束條件眾多、形式復雜，往往只能用啟發式算法獲得最優解。此外，多目標決策方法可以和啟發式算法相結合進行配送中心的合理選址。

2.庫存控制問題相關教學內容

庫存控制問題是在保證生產或銷售對物資需要的前提下，盡可能地減少資金占用，降低物資的庫存成本。目前，庫存控制研究已取得了豐碩的成果，形成了較為完整的庫存控制理論——存儲論，主要包括定常需求的庫存控制、時變需求的庫存控制、隨機需求的庫存控制、依賴于庫存水平需求的庫存控制以及多種物品的庫存控制等。庫存控制模型的求解主要利用高等數學中的微積分原理給出最優解的性質，并結合啟發式算法給出最優值。

3.車輛路徑規劃問題相關教學內容

車輛路徑規劃問題是針對一系列發貨、收貨點，設計適當的行車路線，使車輛有序地通過它們，在滿足規定的約束條件（如貨物需求量、交發貨時間、車輛容量、時間限制等）下，實現一定的目標（如路程最短、費用最低、時間盡量短、車輛盡量少等）。根據研究重點的不同，車輛路徑規劃問題的模型構造及算法有很大差別。但整數規劃、動態規劃和圖論是車輛路徑規劃問題最常用的建模方法，啟發式算法在車輛調度問題的求解中得到了廣泛應用。

4.物流系統協調優化相關教學內容

配送中心選址、庫存控制、車輛路徑規劃問題之間有著千絲萬縷的關系，其中一個問題的決策往往影響到其他問題的決策，如果某一問題決策失敗就無法獲得整個物流系統的最優。因此，物流系統的協調優化越來越受到重視，配送中心選址與運輸路線安排問題的集成建模、庫存控制與車輛路徑的集成建模、以及配送中心選址與庫存控制的集成建模已經得到了廣泛研究，主要涉及的運籌學方法有整數規劃、非線性規劃、動態規劃和啟發式算法等。

由以上分析可知，物流系統優化涉及的“運籌學”教學內容主要包括整數規劃、非線性規劃、動態規劃、圖論、存儲論、多目標決策、啟發式算法等，這分別對應于清華大學出版社《運籌學》教材中的第5章、第6～7章、第8～9章、第10章、第13章、第16章、第17章。其中，以整數規劃和啟發式算法的應用最為廣泛。以此為依據，筆者建議對物流工程專業的“運籌學”教學內容作適當調整，打破以教材章節為依據劃分本科和研究生教學內容的模式，在本科階段教學中增加非線性規劃、存儲論、決策論、啟發式算法的內容，在研究生階段教學中進一步深化整數規劃、動態規劃、圖論的內容，保證本科和研究生階段課程的可延續性，并在教學深度上形成一定的梯度。本科階段側重于物流系統基本問題的建模和基本求解方法的掌握，研究生階段則側重于綜合問題的建模和多種求解方法的結合應用以及優化理論的創新。

三、物流工程專業“運籌學”教學的實施手段

“運籌學”是一門以數學方法為基礎尋求實際問題最優方案的應用科學，特別強調對實際問題的解決。應用運籌學解決現實生產、生活中的實際問題，需要針對實際問題的優化要求及面臨的客觀條件作必要的假設，抽象為數學模型，然后利用恰當的數學方法加以解決。根據《教育部高等學校物流類專業教學指導委員會關于物流工程本科專業培養方案的指導意見》，物流工程專業是一門實踐性很強的專業，要求該專業的教學注重理論教學與實踐教學相結合，課堂教學與課外活動和諧統一。因此，對于物流工程專業的“運籌學”教學，強調對物流系統中實際問題的解決則顯得尤為重要。然而，由于“運籌學”本身所具有的明顯的數學學科特征，加上“運籌學”教材的通用性特點，教師在教學實踐中很容易產生偏重數理演算、忽略實踐應用的傾向，在基本原理和手工演算的講授上花費大量的課時，而對于如何從物流系統的實際問題出發，抽象出合理的數學模型以及如何應用先進的計算軟件實現模型的求解則重視不夠，甚至忽略。鑒于此，筆者建議對物流工程專業“運籌學”教學的實施手段做以下改革嘗試。

1.講述教學法和問題解決教學法相結合的課堂教學方式

由于“運籌學”既要求對基本理論和優化方法的理解，又強調應用理論方法解決實際問題的能力。因此，筆者建議采用講述教學法和問題解決教學法相結合的課堂教學方式。

講述教學法是指教師運用敘述的方式傳遞教材知識的教學方法，也是最為常用的一種教學方法。“運籌學”的基本理論和優化方法以數學為基礎，對于物流工程專業的學生而言相對抽象和晦澀。如果在課堂講述時利用高深的數學理論來推導一個定理，或者花費大量的時間手工求解一個問題，則違背了物流工程專業“運籌學”教學的應用目的，學生不僅難以接受講述的內容，而且其學習積極性會受到打擊。因此，筆者建議教師在課堂講述中弱化“運籌學”中定理的推導以及手工演算過程，通過板書教學與多媒體教學相結合的講述方式，根據課程內容的需要穿插一些動畫、聲音視頻，充分調動學生的學習興趣，使學生快速理解“運籌學”的基本理論和優化方法。在此基礎上，結合問題解決教學法培養學生應用理論方法解決實際問題的能力。問題解決教學法是啟發式教學方法的一種，是以學習者為中心的教學方法。教師可在教學中有目的地引導學生選擇典型的物流系統優化案例，可以從簡單的配送中心選址、庫存控制以及車輛路徑規劃問題入手，協助學生對實際問題進行合理假設、抽象和建模，使學生逐步掌握運用“運籌學”解決物流系統優化問題的思維方式和方法。

2.課堂教學、計算實驗和課外活動緊密配合

由于課堂教學中弱化了定理的推導和手工演算的過程，加上啟發式算法在物流系統優化問題中的廣泛應用，物流工程專業的“運籌學”教學應開設專門的實驗課程，將課堂教學內容和上機實驗緊密結合起來，幫助學生掌握WINQSB、LINDO、LINGO、MATHEMATICA、MATLAB 等優化軟件，利用計算機代替手工演算實現模型的求解。同時，注重培養學生不拘泥于課本上的算法與思維，努力嘗試新方法，開拓新思路，提高自己的創造性思維能力，逐步引導學生將學習的重點放在對實際問題的分析建模和求解思路的設計上來。此外，可以鼓勵學生積極參加全國大學生物流大賽，實現“運籌學”教學與物流優化實踐的結合，提高學生應用運籌學解決物流企業實際問題的能力。

3.改革考核體系，突出教學重點

成績考核是整個教學周期的最后環節，是評估教學質量和學習水平的關鍵。為了與物流工程專業“運籌學”教學內容和教學方式的調整保持一致，其成績考核方式也應做相應的調整。首先，突出物流工程專業的“運籌學”教學目的，考核內容應圍繞物流系統優化問題展開，比如配送中心選址、庫存控制、車輛路徑規劃等都是重點考核內容，相應地弱化對其他專業的相關問題考核。其次，改變目前“運籌學”課程考核采取的形式單一的筆試方式，將平時課堂教學中的問題討論和實驗課程中的上機練習作為課程考核的一部分。比如，可以在課堂教學中定期地進行物流系統案例優化小測驗，讓學生在規定的時間內完成問題分析和模型構建，將評價結果記入課程考核，還可以在實驗課程中設置一定的考核環節，檢查學生利用計算機求解運籌學模型的能力，將評價結果記入課程考核。最后，在試卷考核中要注重檢驗學生掌握運籌學思維方式和方法的程度，即檢驗學生針對一個具體的物流系統優化問題展開分析，進行適當的假設和理論抽象，建立合理的數學模型的能力，避免學生把大量的時間花費到簡單記憶和繁雜計算中。

四、結語

本文從電子商務環境下我國物流業存在的實際問題出發，確定物流工程專業“運籌學”教學需要重點關注的問題包括配送中心選址、庫存控制、車輛路徑規劃以及物流系統協調優化。在此基礎上，通過對這些重要問題的分析給出了物流工程專業“運籌學”教學的重點內容和章節，并對教學實施手段提出了改革建議。這些有針對性改革措施不僅有利于物流工程學生掌握運籌學的思維方式和方法，而且有利于培養學生應用運籌學解決物流系統優化問題的能力。

參考文獻：

[1]楊艷，王克近.配送中心選址方法研究綜述[J].物流技術，2011，

（23）：148-152.

[2]周永務.物流系統的庫存控制模型與方法研究[D].合肥：合肥工業大學，2002.

[3]劉云忠，宣慧玉.車輛路徑問題的模型及算法研究綜述[J].管理工程學報，2005，19（1）：124-130.

[4]林巖，胡祥培，王旭茵.物流系統優化中的定位——運輸路線安排問題（LRP）研究評述[J].管理工程學報，2004，18（4）：45-49.

[5]李文鋒，畢婭.物流系統優化與仿真[M].北京：中國標準出版社，

2010.

[6]王旭.管理運籌學的課程定位研究[J].高等教育研究，2008，

25（3）：75-76.

篇2

【關鍵詞】配電網規劃；優化方法；分析

配電網規劃的數學規劃方法包括確定性方法和不確定性方法。其中，確定性方法又包括線性規劃法、非線性規劃法、動態規劃法、網流規劃法，而不確定方法有模糊規劃法、場景分析法、風險度估計法等。配電網規劃的啟發式方法包括傳統啟發式方法、啟發式專家系統和現代啟發式方法。

1.配電網數學規劃優化方法

（1）線性規劃法。在眾多的數學規劃方法中，線性規劃法是研究最早，也是最為成熟的一種數學優化方法，它在配電網規劃中的應用幾乎涵蓋了配電網規劃早、中期的所有研究。線性規劃法又分為運輸模型、線性規劃、整數規劃、混合整數規劃等。運輸模型是最為簡單的一種線性規劃法。由于模型簡單，其求解算法也最為有力。然而，運輸模型的一個嚴重缺陷是運輸費用必須嚴格表達為線性化費用，而用嚴格線性化費用模型來代替實際的非線性化費用模型是不準確的。運輸模型另一個嚴重缺陷是它不滿足電網運行的許多約束條件。不帶整數變量的線性規劃是傳統的、狹義的線性規劃法。它的模型雖然較運輸模型復雜，但其求解算法也比較成熟。

無論是采用線性規劃的運輸模型還是不帶整數受量的純線性規劃模型，都無法考慮到配電網規劃的離散性，而整數規劃則彌補了這方面的缺陷。在求解整數規劃問題時，由于整數規劃的離散特征，解的數目是有限的，并且隨整數約束變量數目的增加而呈組合性的增加，因此，通過顯式的方法枚舉所有解的方案通常是不現實的。整數規劃的常用方法是分文定界法，它是一種把隱式枚舉和顯式枚舉有效結合起來的整數規劃方法，它的有效性依賴于它的枚舉邏輯的有效性。

（2）不確定性規劃。目前，在配電網規劃中考慮不確定性主要有三種方法。第一種方法是采用模糊數學理論。對配電網規劃問題建立了相應的模糊線性規劃模型，并相應發展了直流模糊潮流和交流模糊潮流。建立了以模糊供電總成本最小為優化目標，通過計算電網故障狀態下的模糊電量不足期望值計算模糊缺電成本，最后利用遺傳算法產生動態優化解。采用盲數模型在合理的考慮多種不確定信息基礎上進行了電網規劃，達到了理想效果。第二種方法是場景分析法。場景分析法并不直接對配電網規劃中的不確定性因素進行建模，而是將未來規劃年的環境預想為多種可能的確定性場景，然后在不同的場景下進行確定性的常規配電網規劃，考慮對各種場景都具有較高適應性的配電網規劃方案為最優的柔性方案；第三種方法是風險評估法。這種方法是通過對可能出現的不確定性情形進行評估和考慮，確定各個方案的風險率，然后進行確定性的電網規劃，從而得到最優的柔性擴展方案。

2.配電網啟發式規劃優化方法

以上分析了數學規劃方法在配電網規劃中的應用，可以發現，非線性規劃方法的局限性使得建立在非線性費用函數和非線性約束條件上的配電網規劃模型往往得不到有效的解，而混合整數線性規劃模型既彌補了運輸模型和不帶整數變量的純線性規劃模型過于簡化的特點，又避免了非線性規劃的“非魯棒性”，因而成為求解配電網規劃問題較理想的數學規劃方法。但是，即使是這種最為理想的數學規劃方法，當進行實際的配電網規劃時，由于變量的數目和約束條件很多，也會變得非常因難，更不用說再在配電網規劃中加入其他方面的考慮，如不確定性因素等。針對以上數學規劃方法的不足，啟發式算法的特點就更為突出，它綜合考慮了規劃效率和規劃效果兩個指標。在實踐過程中，許多啟發式方法，特別是現代啟發式方法常常能給出令人滿意的、高質量的解。啟發式方法的優點是直觀、靈活、計算速度快，便于規劃人員在規劃過程中參與具體的決策，通過規劃人員過去的經驗和常用的配電網規劃啟發式規則，并借助于數學規劃方法，得出符合工程實際的規劃方案。

（1）傳統的啟發式方法。傳統的啟發式方法通常基于系統某一性能指標對可行性路徑上線路參數的靈敏度，根據一定的原則，逐步選代直到得到滿足要求的方案為止。這種方法在配電網規劃中的應用主要是結合“支路交換”技術進行的。所謂支路交換是指：對輻射狀配電網，通過添加—條支路來形成一個環，然后斷開另一條支路以恢復其輻射狀網絡結構。重復該過程，直到任意支路交換均不能使目標函數減小為止。

（2）專家式啟發方法。啟發式專家系統可以看作是傳統啟發式方法的發展，它與傳統啟發式方法的區別是在規劃過程中引入了規劃專家的經驗，并便于規劃人員參與到具體的規劃決策中去。值得指出的是，專家系統不是用來代替規劃人員的，而是利用存放在知識庫中的知識和數據庫中的基礎數據，并通過推理機的推理，給規劃人員提供相對較優的規劃方案，而最終的規劃方案的選擇是由規劃人員作出的。

（3）現代啟發式方法。現代啟發式方法是一種通用的優化算法。它的另外一個重要特點是所有這些方法均能實現并行計算。由于現代啟發式方法在求解組合最優問題時表現出的卓越性能，在過去的20年中，它受到前所未有的關注。然而，現代啟發式方法也有其不足之處，它在處理具體問題的約束條件時，雖然采用懲罰函數的方法把約束條件加到目標函數中去，但是在如何選擇合適的懲罰函數方面，它往往缺少有效的手段。另外一個不容忽視的缺點是，當配電網節點比較多時，不可避免的會出現“維數災”問題。

3.結論

綜上所述，在配電網架優化規劃的各種方法中，總的來講可以分為數學規劃和啟發式算法兩大類。但是，即使對于最理想的數學規劃方法，由于配電網規劃中變量的數目和約束條件很多，使用該類方法變得非常因難，更不用說再在配電網規劃中加入其他方面的考慮，如不確定性因素等。而啟發式算法又分為傳統啟發式方法、專家式啟發方法和現代啟發式方法的算法。傳統的啟發式方法具有較高的計算效率，但是容易陷入局部最優解；專家式啟發方法目前還不成熟，有待進一步研究。 一方面，從表面上看，對于規劃問題計算效率似乎并不重要，但是配電網規劃中負荷點眾多，若使用輸電網規劃方法或遺傳算法等方法，不可避免地會遇到“維數災”問題。更重要的是，實際上任何一種優化規劃方法都是在規劃工程師根據經驗確定了設計思路和限制因素的情況下開展的，規劃工程師需要根據所得結果不斷調整設計思路和限制條件。因此電網規劃實際上是一種人機交互式的設計過程，人的藝術性和經驗性在其中起到了很大的作用，優化規劃方法僅僅是針對設計師各種思路的輔助工具。因此要求優化規劃算法具有較高的計算效率，以便能夠對設計師眾多的設計思路和調整方案產生較快的響應。另一方面，實踐經驗表明：對于配電網架規劃問題，盡管存在大量局部最優解，但是大部分局部最優解與全局最優解的指標相差不大，作為工程近似最優解完全可行。

參考文獻

篇3

【關鍵詞】物流配送；雙向物流；物流路徑優化；蟻群算法；減法聚類

Two-way Logistics Path Optimization Problems Based on Clustering Analysis Research

LIU Yan-qiu YANG Yong

（Shenyang University of Technology， Shenyang Liaoning 110000， China）

【Abstract】According to the characteristics of two-way logistics， this paper focus on analysis and research the vehicles distribution. In order to better coordinate the vehicle path selection and the relationship between transport costs， and better conditions for considering comprehensive factors and the choice between nodes， study of two-way logistics path problem method， established the mathematical model of optimal path minimization. Finally based on path optimization method and the research situation， adopted the cluster analysis and the ant colony algorithm， and it has been verified by the simulation， the results reasonable and effective.

【Key words】Logistics distribution； Two-way logistics； Logistics path optimization； Ant colony algorithm； Subtraction clustering

0 引言

物流配送在物流管理中占有重要地位，它是指按照客戶的訂貨需求，在配送中心進行分貨、配貨，并調度車輛及時為客戶配送貨物[1]。車輛路徑問題（vehicle routing problem，VRP）是車輛配送研究中最核心的問題，一直是組合優化領域的熱點和前沿問題[2]，而雙向物流路徑優化問題（vehicle routing problem with simultaneous delivery and pickup，VRPSDP）是VRP問題中的一個典型，它是指同時帶送貨取貨的物流車輛路徑優化問題，既考慮了客戶需要的貨物從配送中心送到各個客戶，又需要把客戶需要回送的貨物運回到配送中心，要求取貨送貨同時進行，因此比單向物流問題還要復雜，也是一種NP-hard難題，所以求解復雜度較高，計算量較大。本文在前人研究的基礎上通過聚類分析方法和蟻群算法對雙向物流路徑優化問題進行了求解。

1 雙向物流配送的數學模型

1.1 問題描述

雙向物流路徑優化問題可以這樣描述：

已知有C個客戶點，給定每個客戶的坐標點和需求量，貨車從配送中心出發，將貨物送到各個客戶，并同時把客戶供應的貨物帶回到配送中心。車輛應在條件允許下進行服務，當完成任務或者不存在能滿足約束條件的情況下，返回配送中心，直到所有的客戶的送取貨任務完成，整個流程結束。物流路徑優化要求在滿足約束的條件下，合理安排貨車的配送路線，使得運輸成本最小。由于運輸成本很大程度上是由貨車的路徑長度決定的，因此本文求解VRPSDP問題的目標函數的最優解就是要求路徑最短。

1.2 數學模型的建立

1.2.1 參數說明

1.2.2 數學模型

根據上面對VRPSDP問題的描述和已設定的數學參數，加之針對該問題所需要考慮的約束條件，對此問題進行了建模，將服務完所有客戶點后所有車輛的行駛總路程定義為目標函

2 VRPSDP模型的求解

本文中求解模型的方法，首先是通過FCM聚類，把需要提供服務的城市進行分類，然后再用蟻群算法在滿足約束的情況下對每個分類進行求解最優路徑，具體做法如圖1所示。

圖1 求解流程圖

3 實例仿真

為了檢驗上述雙向物流路徑優化方法的有效性，本文采用實例數據對其進行性能分析。設車輛從配送中心出發，為各個客戶提供服務，配送中心坐標位置是（0km，0km），車輛在滿足約束的情況下向 30 個客戶配送貨物。

首先經matlab仿真得到的30個城市的聚類圖如圖2所示。

圖2 經FCM聚類的城市坐標圖

然后經過蟻群算法對每個聚類進行路徑優化，得到的車輛配送路徑圖如圖3所示。

圖3 車輛配送路線圖

4 結論

本文針對雙向物流的特點，首先給出了問題的相關描述，然后通過抽象建模，給出了帶路程和負載量約束的雙向物流路徑優化模型。根據給出的VRPSDP問題模型，用基于FCM聚類和蟻群算法的混合算法對模型進行求解。最后通過仿真實驗，證明了本文混合算法求解雙向物流路徑優化問題的的正確性和有效性。

【參考文獻】

[1]楊燕霞，伍岳慶，姚宇，等.帶時間窗車輛調度問題的啟發式算法研究與應用[J].計算機應用，2013，33（S1）：59-61.

篇4

關鍵詞：車輛路徑問題；遺傳算法；ExtendSim；仿真；優化

中圖分類號：U116.2 文獻標識碼：A

Abstract： This article has introduced the classical vehicle routing problem（VRP）in the field of logistics and the algorithm which can solve the problem firstly， then discusses that how to apply genetic algorithm to solving VRP， and describes how ExtendSim simulation software construct a model and make a optimize for an certain VRP in detail， with this method， finally concludes the optimal solution， and proves that the simulation optimization method is an effective way to solve the VRP.

Key words： vehicle routing problem； genetic algorithm； ExtendSim； simulation； optimization

我國國家標準《物流術語》（GB/T 18354-2006）中，給物流下的定義是：“物流是指物品從供應地向接收地的實物流動過程。根據實際需要，將運輸、存儲、裝卸、搬運、包裝、流通加工、配送、信息管理等基本功能實施有機結合。”物流有多方面的功能，而運輸和儲存保管則是其主要功能。在整個物流活動過程中，運輸是其中各項子活動的核心活動，它是第三利潤源的主要的源泉[1]。

日本在20世紀70年代就對物流有深刻的認識了，日本早稻田大學的西澤修教授在其著作中把物流稱作不為人知的利潤源泉，他認為，物流能為企業創造價值，是企業的利潤源泉。石油危機后這一觀點得到證實，物流也因而在企業管理中得到更加重視。目前我國生產型企業的物流成本占到總成本的20%～30%，而發達國家的則為10%左右[2]。因此，為了降低企業經營成本，獲得更多的利潤，必須盡量降低物流成本的比重，這對于國民經濟的更好發展具有十分重要的作用。

在商品經濟社會中，人們的生活質量與商品消費息息相關，而商品的價格直接影響人們的生活水平，如果商品價格不合理，超出人們普遍的可接受范圍，那么人們的生活幸福度將會大大降低。而商品價格的構成部分除了有生產成本，還有更重要的一部分是物流成本，并且物流成本中的運輸費又占了較大的比重。商品運輸需要耗費大量的能源動力，消耗越多，花費成本越高，如果運輸組織的不合理，就會加大運輸成本，因而抬高物流成本，商品價格也因而升高，結果是不僅降低企業的利潤，也間接提高人們的生活成本。

所以，運輸問題是物流領域中值得研究的關鍵問題。其中車輛路徑問題（Vehicle Routing Problems，VRP）是運輸問題中的一個熱點問題。該問題是指：在物資流通過程中，每個需求點的位置和需求量已知，供方如何調度車輛和安排行車路徑向需方供應物資，使得在滿足需方需要的同時也達到某些關鍵目標（如車輛數盡量少、花費時間盡量少、費用最少、路程最短等）。

學者們很早就開始對車輛路徑問題進行了研究，積累了豐富的研究成果。在20世紀50年代末，車輛路徑問題首先被G.Dantzig和J.Ramser[3]提出，兩位學者根據如何運送汽油到加油站這個現實中的問題，利用數學方法對其建立模型，并得出求解算法。在1964年，Clark和Wright這兩位學者研究了G.Dantzig和J.Ramser的方法后，認為后者的方法有改進的空間，并最后提出了Clark-Wright節約算法（即C-W算法）。從此VRP成為運籌學領域的研究熱點。五年后，Christofides與Eilon又想出新的方法，他們應用2-opt和3-opt處理VRP，取得較好的效果。到1981年，Fisher、Jaikumar和Gullen、Ratliff、Jarvis提出不同的研究方法。前者主要利用數學規劃，來對VRP進行最優化處理，后者則是運用人機互動的啟發式方法處理VRP。到90年代，學者們開始利用人工智能構造大量的啟發式算法來解決VRP，如禁忌搜索發、模擬退火法、遺傳算法等。首先采用遺傳算法（Genetic Algorithm，GA）的學者是Holland[4]，他利用遺傳算法中的編碼方法處理了VRP。在這幾種人工智能方法中，遺傳算法能較好地逼近最優解的同時具有較高的運算速度和效率，具有很好的發展前途。

1 VRP數學模型及遺傳算法

1.1 VRP的基本數學模型

VRP的一般描述[5]：

（1）車輛的載重量大于等于配送路徑上總的需求量；

（2）任一配送路徑的長度小于等于車輛在一次配送任務中的最大行駛距離；

（3）每個需求點的需求都只能被同一輛送貨車滿足；

（4）設定每輛車都是從中心出發開展配送任務，任務完成后再重新回到中心。

將一個配送中心編號設為0，該配送中心擁有車k輛，車輛數m，車的額定載重量為q，該中心面向L個客戶，第i個客戶需求量為g■，且g■≤q（i=1，2，…，L），VRP的基本模型如下：

minz=■■■c■x■ （1）

■g■y■≤q ？坌k （2）

■y■=1 i=1，…，L （3）

■x■=y■ j=0，1，…，L； ？坌k （4）

■x■=y■ i=0，1，…，L； ？坌k （5）

x■=0 or 1 ？坌i，？坌j，？坌k （6）

以上式（1）中，c■表示由點i到點j的運輸成本，該函數為最小運輸成本目標函數；（2）為車容量的約束；（3）表示每個客戶僅有一輛車服務；（4）、（5）表示到達和離開某一客戶僅有一輛車。x■和y■為變量，定義為：

x■=■

y■=■

1.2 遺傳算法

本文中的仿真軟件ExtendSim擁有一個自帶遺傳算法的優化模塊。遺傳算法在處理車輛優化調度問題時，有以下幾個步驟：

（1）確定染色體的編碼和初始群體

對可行路線編碼，如長度為1+m的染色體編為：

0，i■，i■，…，i■，0，i■，…，i■，0，…0，i■，…，i■

i代表著每一項運輸任務，此染色體可理解為車輛從配送中心0出發，完成i■，i■，…，i■后返回配送中心0，形成子路徑1；然后又從0出發，完成i■，…，i■后返回0，形成路徑2，如此反復直至完成所有的任務。這個過程中，行走路徑不斷改變，使得函數目標也改變，這樣的遺傳迭代就能讓函數目標最小，也即趨向于最佳路徑。

（2）確定目標函數

根據所研究的具體問題，數學模型的目標函數可以表示相應問題（如運費最少問題、車輛數最少問題、路徑最短問題、運輸時間最少問題等）的最優解方程。

（3）約束的處理

遺傳算法中各個染色體對應的解在群體中是占有一定比重的，在遺傳算法迭代運算進程中，如果某個染色體的解不符合約束條件，則會受到遺傳算法的懲罰機制的懲罰，使得其在群體中所占比重越來越小，而相反，可行解則越來越大，通過這樣的一個機制最終可以得出最優解。

（4）遺傳算子

遺傳算子一般包括復制、交叉、變異。復制的目的是保留優良個體，提高全局收斂性和效率；交叉的作用是組合新個體，降低對有效模式的破壞概論；變異的目的，是為了減少基因的缺失和不成熟收斂對結果的影響。

（5）確定最終方案

經過上述遺傳過程后，最終產生性能最優的染色體串。

2 仿真優化方法在VRP上的運用

對VRP的研究，大多停留在理論層面上，這些研究是通過分析問題，運用運籌學知識，用各種數學符號將問題抽象為一系列公式，形成能解決VRP的數學算法。這一類方法稱為解析法，是通過建立某種符合邏輯推理的數學模型來解決VRP，具有精確求解的優點，但不足的是，它完全以數學公式的形式存在，所以它不易于理解，不具備良好的人機交互及可視化，也就無法讓人直觀地感受到所描繪系統是如何運行變化的。相反，仿真方法卻可以直觀方便地處理問題。

仿真方法是利用以計算機和軟件為工具的仿真技術對實際或者設想的系統進行建模并運行，結合某種算法對系統分析，從而得出結果。它結合優化算法來計算模型，則可以求解出最優解。

李先永[6]根據VRP模型，利用EM-Plant仿真軟件構建了相應的仿真模型，同時結合啟發式求解方法計算和優化，從而驗證了該仿真方法的可靠性。劉芳華、楊娟都采用了仿真平臺MATLAB結合遺傳算法對具體的VRP進行參數輸入并運算，得到很好的效果。白雪利用ProModel對某汽車租憑公司的運營方案進行建模優化并評比備選方案，得出最優排程方案。孫姝婷利用 VISSIM 微觀仿真軟件對城市配送線路進行優化搜索，對多條配送路線進行評價分析，為配送車輛選出最優配送線路。陳靜靜[7]針對定位—路徑—庫存問題（Location—Routing—Inventory Problem，LRIP）這一物流領域中新的研究熱點問題，采用ExtendSim仿真軟件構造了該問題的模型，并用軟件的遺傳算法對其優化計算，求解出LRIP的最優方案。

3 ExtendSim對VRP建模優化

3.1 運輸問題

運輸問題，解決的是如何組織一個合理的運輸方案，使得物資在供求地運送到需求地所需要的總運費最小。其數學模型如下[8]：

設有m個產地，記為A■，A■，…，A■，生產某種物品，可供應產量分別為a■，a■，…，a■；有n個需求地，記為B■，B■，…，B■，其需求量分別為b■，b■，…，b■；供需平衡，即■a■=■b■。從第i個產地到j個需求地的單位物品的運費為c■，在滿足各地需要的前提下，求使得運費最小的調運方案。

設x■i=1，2，…，n為第i個產地到第j個需求地的運量，則該運輸問題的數學模型可寫為：

minz=■■c■x■ （7）

■x■=a■ i=1，2，…，m （8）

■x■=b■ j=1，2，…，n （9）

x■≥0 i=1，2，…，m j=1，2，…，n （10）

3.2 對具體問題建模

設有A■，A■兩個工廠面向B■，B■，B■三個客戶服務，工廠可供應產品數量分別為10，8個單位，客戶需求量分別為5，6，7個單位，A■到B■，B■，B■的每單位產品運費分別為3，2，6個單位，A■到B■，B■，B■的每單位產品運費分別為5，3，8個單位。根據以上信息，如何安排一個運輸計劃，使總運費最少。

對此問題，本文采用ExtendSim仿真軟件，實現了模型的整體構建。其整體結構如圖1所示。

3.3 模塊說明

ExtendSim中的每一個模塊都有其特定的功能，這種功能可以是多個的，另外模塊內部還有能輸入和輸出參數的結構。

首先，上述運輸問題是一個離散事件，需要放置Executive仿真時鐘模塊，讓軟件自動推進事件的發展。兩個Create模塊表示兩個工廠生產產品，Queue模塊表示存放產品的倉庫，Select item out模塊表示選擇不同的送貨路徑，Gate是個路徑開關，與Information、Math、Decition共同作用，具有能根據客戶是否得到滿足而控制路徑開通與否的功能。Get模塊可設置此路徑上每單位產品運費，而Activity模塊則是計算運送給某個B客戶的總成本，整個產品送貨流程以Exit模塊結束。

3.4 優化

以上模型只能直觀地演示系統的運行，還不能對該系統進行計算最優方案，所以要求解最佳方案，必須使用優化模塊Optimizer。

該模塊內置遺傳算法，在本問題中，有六個決策變量，該模塊對這六個量分別隨機編碼成二進制的基因b■i=1，2，…，n，并使它們連接組成每一個都擁有六個基因的染色體個體，然后模塊自行隨機產生初始種群數，再根據目標函數來確定能評價染色體優劣的適應度函數，在本題中以值越小越優，并接著按照一定概率選擇較優個體淘汰較劣個體進而產生一個種群，然后按一定概率對這種群里的個體進行交叉、變異運算，最終產生新一代的種群，這一代個體的適應度的數值和平均值都比上一代的有了明顯的改進，也就是說向最優值靠攏，接著再繼續對這新一代種群不斷循環運算，經過運算多代直至不能搜尋到更優的解后，就停止運行并顯示最優解了。

在Optimizer的Objectives中，對分別輸入運量的最小值0和最大值（客戶B的需求量），以及表示總費用最少的目標函數：Mincost=yunfei1+yunfei2+yunfei3。

在Optimizer的Constraints中，輸入決策變量的約束條件：

if（yunliang1+yunliang4 ！=5） reject=true；

if（yunliang2+yunliang5 ！=6） reject=true；

if（yunliang3+yunliang6 ！=7） reject=true；

if（yunliang1+yunliang2+yunliang3 ！=10） reject=true；

if（yunliang4+yunliang5+yunliang6 ！=8） reject=true；

最后，點擊New Run，系統自動運行，最終求解出最優結果，結果顯示，軟件運行了24秒，最小總成本值為82，最優解方案為best行：A■向B■，B■，B■分別運送1、3、6單位的產品；A■向B■，B■，B■分別運送4、3、1單位的產品。

4 結 論

本文論述了當前物流領域熱點問題車輛路徑問題及前人對其研究出來的解決方法，這些方法當中以某種算法來建立數學模型的理論研究居多，仿真建模層面上的研究比較少，因此重點探討了仿真優化方法在VRP上的應用，并基于ExtendSim仿真優化軟件對某一VRP問題進行了建模和優化，得出可靠結果，突顯出了仿真軟件界面友好、可視化強、操作簡單易懂、運算速度快的特點，是解決物流領域中VRP的一種有效的途徑。

參考文獻：

[1] 鄧紅星，韓銳，武慧榮. 物流技術[M]. 哈爾濱：東北林業大學出版社，2010.

[2] 紀紅任，游戰清，劉克勝，等. 物流經濟學[M]. 北京：機械工業出版社，2007.

[3] C.G.Dantzig， J.Ramser. The truck dispatching problem[J]. Management Science， 1959（6）：80-91.

[4] J Holland. Adaptation in Natural and Artificial System[D]. The University of Michigan Press， Ann Arbor， MI， 1975.

[5] 彭揚，伍蓓. 物流系統優化與仿真[M]. 北京：中國物資出版社，2007.

[6] 李永先. 車輛路徑問題的仿真模型及優化方法研究[D]. 大連：大連理工大學（博士學位論文），2008.

篇5

Abstract： Critical chain method adhering of the TOC process, both in the planning of projects between the process logic operations and identify key chain of the resource constraints relationships, through the buffer to deal with uncertainty. However, most of the existing key chain theories are researched based on certain networks. Petri nets with similar description and flow charts and other visual identification of the flow though the simulation system of dynamic event. This article describes how to identify the critical chain of the projects based on the Petri nets, in order to respond to complex and changing reality better, it has important theoretical significance to perfect critical chain theory.

關鍵詞： Petri網；關鍵鏈；變遷

Key words： Petri net；Critical Chain；transition

中圖分類號：TP393文獻標識碼：A文章編號：1006-4311（2011）01-0186-02

0引言

關鍵鏈管理[1]正是把項目看作一個系統，來實施對項目的管理。關鍵鏈依托于約束理論，從瓶頸、系統思考方式入手，將DBR的核心思想應用到項目管理中，把著眼點從工序提升到整個系統，考慮整體系統的有效性，關鍵鏈理論對傳統網絡計劃技術諸多方面予以較大改進，綜合考慮資源約束以及人的行為，突破了傳統計劃的模式，提出的面向項目的進度計劃方法[2]。在關鍵鏈的判斷方面，J-B Yang[3]通過一個例子對關鍵鏈和關鍵路經進行了比較，并指出如果所有的項目參與者都能改變他們以往在關鍵路經上的行為因素，那么關鍵鏈的方法對于大多數的建筑項目都非常有用的。同時他也提出現有的一些關鍵鏈的確定方法存在著很多的不足。 田文迪運用動態規劃的思想設計一個啟發式算法來識別關鍵鏈和非關鍵鏈，并將此法與標準問題庫中其他方法所得解進行比較，證明了方法的優越性，但由于方法的設計過程復雜，不具有通用性。 萬偉、蔡晨等[2]也關鍵鏈管理進行了系統的論述，但也不夠完善。近年來，Petri網理論的發展十分迅猛， Petri網既是圖形工具又是數學工具，具有圖形直觀、能描述沖突和并發，且能以狀態分布表示等優點，Petri網因其強大的并發處理功能日顯優越，因此將關鍵鏈的先進思想與Petri網的有機結合將有力的推動關鍵鏈理論的完善[4]。

1Petri網

Petri網(PN)是1962年德國的C.A.Petri博士在研究自動機通信時，提出了一套形式化的建模方法，以他的名字命名，在當時引起了學術界的廣泛關注。其是一種系統建模與分析工具，以并發論、網邏輯和網拓撲為主要內容，它同時具有充分的模擬能力和豐富的分析方法[4]。經過幾十年的發展，Petri網理論已經被廣泛應用于許多領域， 本文采用Petri網對項目管理建模與分析優化調度方案。

1.1 Petri網的定義在生產調度中Petri網模型是一個五元組∑=（P，T，F，W，M），P={P1，P2，…，Pm}為庫所集；T={t1，t2，…，tm}稱為變遷集；F表示連接庫所和變遷的有向弧集合；W為關聯庫所和變遷的實數對[a（S）i，β（S）i]（a（S）i1時，將W（f）標注在流關系上。當一個庫所的容量有限時，通常將K（p）標注在庫所旁邊。K（p）=∞時，通常省略K（p）的標注，標識是托肯在庫所中的一種分布[4]。

1.2 Petri網與項目管理項目管理從本質上來說就是一個離散事件動態系統，其特點在于事件發生在離散的時間點上，具有并發、異步和突發性。而Petri網恰好是為離散事件系統建模的最好工具之一。所以，用Petri網理論來研究項目管理，能起到比較好的效果。Petri網理論能夠正確、合理地表示出項目管理的整個過程。這對于發現問題、解決問題會有極大的幫助,通過Petri網與傳統的、成熟的項目管理模型之間的映射，我們可以直觀地了解項目的情況，從而實時地調整項目計劃和動態控制項目的執行。在隨機事件驅動計劃下，多項目管理網絡計劃的在時間τ的HLPN:（Ω，R，M0）滿足以下需求：

（1）Ω是一組項目集合：

在τ時間，每個項目ω∈Ω是一個集合（P，T，δ，∑，D+，D-，μ0）

P是庫所的集合；T變遷的集合：T=T1∪TD，T1是立即變遷，TD是一系列時間延遲變遷；δD（t）R是TD的時間延遲函數，R是正實數；∑是染色集合；∑（pi）是庫所pi的聯系，是∑（tj）變遷tj的聯系；D是輸入函數；D是輸出函數；μ0是項目ω的初始標識；

（2）R={r，r，r，…，r}是一組資源集合；R=R∪R=R∪R

R代表的是被多項目共享的資源；R代表的是只分配給一個項目使用的資源；R代表的是可循環使用的資源；R代表消耗性資源；R∪R=

（3）M0是Ω的一個初始標識，μ0∈M0

在模型中庫所中有一個托肯意味著，活動即將發生或資源可以使用。由于模型的整個網絡計算工作比較復雜，我們用計算機對可達性及矩陣的運行進行分析。

2基于Petri網項目管理中關鍵鏈判斷方法

Step.1構建多項目管理下的隨機PETRI網模型根據定義及Petri網的規則建立項目管理的Petri網模型用高級PN的展開模型來定義資源約束的活動，資源類型，及沖突的原因。Step.2尋找鎖死點鎖死是當并行的活動競爭相同的資源，通常是資源配置不合理造成，基于PN的鎖死算法可以找到潛在的鎖死，從而重新設計或修正資源安排，來防止與回避鎖死。相反，無鎖死，說明條件可行，資源滿足項目活動。

鎖死尋找:

輸入：AHLPN代表在τ時多項目管理的網絡計劃

輸出：無鎖死方案

01 Definition；

μ0=初始標識，μm=結束標識，μk=活動標識

D=輸入函數D=輸出函數

D=D-D，關聯矩陣，α=實施向量

02 Findμ0 and μm

03 perform: calculate D，D and D

04 Set k=0

05 Let μk+1=μk+α•D， solve for α

06 If a is a feasible solution

07 If k=m

08 Indicate deadlock-free state

09 Else

10 Set k=k+1

11 Go to 05

12 End if

13 Eels

14Indicate deadlock

15 End if

16 End

Step.3產生可行性計劃安排及輸出關鍵鏈

根據step.2的無鎖死路徑及，可以運用計劃概括計算產生可行性計劃安排并估計其工期，所有作業根據資源約束，資源的有效利用，一種資源每次只能用作一項任務。通過PN模型得到多個可行性計劃（根據不同的PN的不同變遷順序），通常會工期最短的作為最優的，即得到相應的關鍵鏈。

程序：總體計劃

輸入：無鎖死方案

輸出：可行性計劃及工期

01 Definition:

μ0=初始標識，μm=結束標識，μk=活動標識

MS=makespan，MSL=the lower bound of makespan

02 Find μ0 and μm

03 Initialize MSL of MS

04 Set k=1

05 Find the enabled transition(s) of μk

06 Perform: select one enabled transition to fire(put others in waiting lit)

07 Perform: record the firing transition

08 Perform: calculate MS from μ0 to μk

09 If MSL

10If Waiting-list of transition is empty

11 If k= m

12MSL=feasible solution

13 Else

14 Set k= k+1

15 Go to 06

16End if

17 Else

18 Go to 06

19 End if

20 Else

21 MSL=MS

22Go to 10

23 End if

24 End

3算例分析

本算例由兩個項目同時開始，需要3種可恢復資源R1、R2、 R3資源的可使用量分別是3、2、2。項目活動及資源分配如表1。項目的Petri 網模型如圖1，通過鎖死判斷及項目計劃計算，項目計劃的最短工期為22天，可得到項目的甘特圖如圖2。

可得出關鍵鏈為:1.1-1.2-2.2-2.7-2.8-2.10-1.8

4結論

本文是結合時間Petri網對多項目管理的關鍵鏈進行研究，其作為數學工具，在判斷關鍵鏈有嚴密的數學基礎，作為圖形工具，能清晰的描述項目管理計劃。本文是在確定型網絡中對關鍵鏈分析，為其關鍵鏈在不確定型網絡研究提供了研究方向。

參考文獻：

[1]龔俏巧，韓文民.關鍵鏈技術在RCPSP問題中的應用研究[J].中國管理信息化，2009：（15）：105-107.

[2]蔡晨，萬偉．基于PERT/CPM的關鍵鏈管理[J].中國管理科學，2003，12（11）：35-39．

篇6

第一節 物流發展的現狀

物流最早是在二戰中，圍繞戰爭物資供應，美國軍隊建立的“后勤”（logistics）理論發展過來的。當時的“后勤”是指將戰時物資生產、采購、運輸、配給等活動作為一個整體進行統一布置，以求戰略物資補給的費用更低、速度更快、服務更好。后來，將“后勤”體系移植到現代經濟生活中，才逐步演變為今天的物流。

物流科學于80年代傳入我國，由于經濟體制的問題，物流研究直到改革開放進行了十幾年的90年代末期才開展起來。總的說來，由于我國的市場經濟剛剛起步，一方面存在限制物流發展的因素，另一方面又存在許多可以挖掘的物流潛力。同發達國家相比，我國物流研究的市場基礎還存在很多的差距。

根據中國物流與采購聯合會此前的數據顯示，在2008年之前，我國物流業規模快速增長，全國社會物流總額達89.9萬億元，比2000年增長4.2倍，年均增長23%；物流業實現增加值2.0萬億元，比2000年增長1.9倍，年均增長14%。2008年，物流業增加值占全部服務業增加值的比重為16.5%，占GDP的比重為6.6%。而到了2009年，受國際金融危機的影響，我國社會物流總額同比增速由一季度下降3.3%，上半年下降0.8%，轉為前三季度增長 2%，反映出物流需求在逐步擴大；前三季度物流業增加值同比增長4%，增幅比上半年提高1.9個百分點，呈加快增長態勢。從企業來看，2009年業務收入基本上經歷了一季度止跌，二季度企穩，三季度回升，全年比前一年略有增長的積極變化。整個行業運行呈現加快回升的積極變化。在2009年，國務院及時出臺了《物流業調整和振興規劃》，實現傳統物流業向現代物流業的轉變，不僅是物流業自身結構調整和產業升級的需要，也是整個國民經濟發展的必然要求。

物流行業的發達程度與發展水平，直接關系到制造業的效率和利潤。中國是世界有名的“工廠”，以前物流外包的比例還比較低，制造企業自營物流仍是主流，第三方物流占物流服務份額很低，據調查僅為17%左右，且第三方物流發展不成熟，目前其需求仍呈增長趨勢。我國近幾年的物流發展比較迅速，有很多的物流企業，但是現代化的物流企業還不多，基礎建設落后、信息化程度低、服務范圍小、內容單薄、總體服務質量和水平不好，無法跟上制造業的發展腳步，提供有利的支持。制造企業不放心物流企業的供應服務能力，認識程度低，擔心物流外包會喪失主動權，而過于依賴物流企業，導致控制權減弱。雙方之間的溝通并不流暢，物流企業也不了解制造企業的真實需求，導致供應能力不足和有效需求不足并存的矛盾。但隨著近幾年，物流行業的迅速發展，制造行業的物流外包速度加快，產業融合與聯動趨勢更加明顯，比如2006年銷售物流外包以5％～10％的速度增長，運輸與倉儲外包以10％～15％的速度增長，運輸業務委托第三方已占企業運輸業務的67．1％。

第二節 選題的意義與背景

在物流管理出現之前，制造業企業還沒有一個獨立的配送管理部門，只是被作為制造活動的一部分，沒有職業物流人員和關于這方面的學術研究。直到20世紀60年代物流管理和物資配送出現后，情況才有了變化。20世紀80年代有了一個新的理論----集成物流，把企業的輸入、輸出物流管理以及一部分制造功能集成在一起。在90年代，供應鏈管理這種新的模式出現了，隨即就有了集成供應鏈的概念，企業把焦點從里面轉到外面，通過和其他供應鏈的成員進行物流的合作協調尋找商業機會。而制造業配送包括制造企業的物料和成品在供應商、制造商和客戶之間，以及企業內部各生產車間甚至生產工位之間的有序平穩流動，以及它們之間的信息流動。配送管理對于有效提高制造業的柔性和對市場的響應速度具有決定性的作用，因此非常有必要開展對制造業配送管理的研究。

     

第二章 配送管理  

第一節 配送的概念和作用

一、配送的概念

日本1991年版《物流手冊》的表述：生產廠到配送中心之間的物品空間移動叫“運輸”，從配送中心到顧客之間的物品空間移動叫“配送”。 美國《物流管理供應鏈過程的一體化》表述：實物配送這一領域涉及特制成品交給顧客的運輸。實物配送過程，可以使顧客服務的時間和空間的需求成為營銷的一個整體組成部分。我國出版的《現代物流學》的表述：配送是以現代送貨形式實現資源最終配置的經濟活動；按用戶訂貨要求，在配送中心或其他物流結點進行貨物配備并以最合理方式送交用戶。而對于制造業來說，配送是圍繞制造業企業所進行的原材料、零部件的供應配送，各生產工序上的生產配送以及企業為銷售產品而進行的對客戶的銷售配送。

制造業配送結構模型如圖2-1所示。

 

                                        圖1-1 制造業配送結構模型

二、制造業配送的作用

（一）通過集中庫存使企業實現低庫存或零庫存

制造業企業為了實現高水平的配送，而依靠配送中心的準時配送，一方面可以降低庫存量甚至是“零”庫存，從而解放大量的的 儲備資金，另一方面采用配送中心集中庫存可以利用規模經濟的優勢使單位存貨成本下降。

（二）簡化事務，方便客戶

客戶只需要向一個配送中心訂貨，就能訂到所有想要的貨物，降低交易成本，提高效率。而對于生產單位來說，只需要把貨物集中配送到一個地方，減少接貨成本，可以全身心投入到自己擅長的業務中。

（三）提高供應保證程度

         制造企業自己保持庫存，維持生產，供應保證程度很難提高，受到庫存費用的控制。采取配送，配送中心可以比任何單位企業的儲備量更大。而對于每個企業而言，中斷供應、影響生產的風險相應縮小，使客戶免去缺貨之憂。

（四）降低缺損，防止內盜

假如各個生產車間自己保持庫存，由于沒有專業的倉庫保管人員，同時設施也不可能十分完善，容易造成貨物的缺損。同時由于庫存分散，造成管理混亂，容易發生內盜事件，造成大量損失。配送中心經驗豐富的專業倉庫保管員和完善的倉庫保管設施，可以最大程度地保證貨物得到妥善保管，降低缺損率。

 

第二節 配送作業流程

一、進貨

在配送的基本作業流程中，進貨作業包括把貨品等物質從實體上領取，從貨車上將貨物卸下、開箱、檢查其數量。當客戶下訂單以后，工廠因為成品的可存率不足，并會向供應商訂購原材料、零配件等。這個時候，要按照保證貨物先進先出，緩不圍急，根據貨物的尺寸、數量 、特性、保管要求選擇貨位，出入庫頻率高使用方便作業的貨位，小票集中、大不圍小，方便操作，作業分布均勻等原則安排貨位。

二、訂單處理

從接受客戶訂單開始著手準備揀貨之間的作業階段，稱為訂單處理。通常包括訂單資料確認、存貨查詢、單據處理等內容。其中有以下幾個內容確認：貨物數量及日期的確認、客戶信用的確認、訂單形態的確認、訂單價格的確認、加工包裝的確認、設定訂單號碼、建立客戶檔案、存貨查詢和存貨分配、計算揀取的標準時間、按訂單排定出貨時序及揀貨順序、訂單資料處理輸出等。

三、揀貨作業

揀貨作業是配送作業的中心環節。所謂揀貨，是依據顧客的訂貨要求或配送中心的作業計劃，近盡可能迅速、準確地將商品從其儲位或其他區域揀取出來的作業過程。揀貨作業在配送作業環節中不僅工作量大，工藝復雜，而且要求作業時間短。揀貨方式包括按訂單揀取、批量揀取、復合揀取。

四、補貨作業

是將貨物從倉庫保管區域搬運到揀貨區的工作。

五、配貨作業

指把揀貨分類完成的貨品經過配貨檢查過程后，裝入容器和做好標示，在運到配貨準備區，待裝車后發送。

六、送貨作業

送貨作業是利用配送車輛把用戶訂購的物品從制造廠、生產基地、批發商、經銷商或配送中心，送到用戶手中的過程。送貨通常是一種短距離、小批量、高頻率的運輸形式。它以服務為目標，以盡可能滿足客戶需求為宗旨。本文著重探討就是制造業送貨過程中，車輛的安排、送貨路線的選擇、送貨的順序。

制造業的配送流程如圖2-2所示。

                                                  圖2-2 制造業的配送流程

第三節  配送模式的選擇

配送模式是企業對配送所采取的基本戰略和方法，根據國內外的發展經驗及我國配送理論與實踐，目前，主要形成了以下幾種配送模式：

一、自營配送模式

自營配送模式是企業物流配送的各個環節由企業自身籌建并組織管理，實現對企業內部及外部貨物配送的模式。這種模式有利于企業供應、生產、和銷售的一體化作業，系統化程度相對較高，既可滿足企業內部原材料、半成品、及成品的配送需要，又可滿足企業對外進行市場拓展的需要。其不足之處表現在，企業為建立配送體系的投資規模將會大大增加，在企業配送規模較小時，配送的成本和費用也相對較高。

二、共同配送模式

共同配送是物流配送企業之間為了提高配送效率以及實現配送合理化所建立的一種功能互補的配送聯合體。共同配送的優勢在于有利于實現配送資源的有效配置，彌補配送企業功能的不足，促使企業配送能力的提高和配送規模的擴大，更好地滿足客戶需求，提高配送效率，降低配送成本。

共同配送的核心在于充實和強化配送的功能。提高配送效率，實現配送的合理化合系統化。因此，作為開展共同配送的聯合體成員，首先要有共同的目標、理念和利益，這樣才能使聯合體有凝聚力和競爭力，才能有利于共同目標和利益的實現。開展共同配送、組建聯合體要堅持以下幾個原則：

1、功能補充

2、平等自愿

3、互惠互利

4、協調一致。

共同配送的實施步驟為：

1、選擇聯合對象

2、組建談判小組，做好談判準備

3、簽訂合同意向書及合同，并進行公證

4、組建領導班子，擬定管理模式

5、正式運作

共同配送的類型，大體可歸納為：緊密型、半緊密型和松散型；資源性和管理型；功能型；集貨型、送貨型和集送型等。

三、互用配送模式

互用配送模式是幾個企業為了各自利益，以契約的方式達成某種協議，互用對方配送系統而進行的配送模式。其優點在于企業不需要投入較大的資金和人力，就可以擴大自身的配送規模和范圍，但需要企業有較高的管理水平以及相關企業的組織協調能力。

與共同配送相比，它的特點主要有：

1、共同配送模式旨在建立配送聯合體，以強化配送功能為核心，為社會服務；而互用配送模式旨在提高自己的配送功能，以企業自身服務為核心。

2、共同配送模式旨在強調聯合體的共同作用，而互用配送模式旨在強調企業自身的作用。

3、共同配送模式的穩定性較強，而互用配送模式的穩定性較差。

4、共同配送模式的合作對象需要經營配送業務的企業，而互用配送模式的合作對象即可以是經營配送業務的企業，也可以是非經營配送業務的企業。

四、第三方配送模式

第三方就是為交易雙方提供部分或全部配送服務的一方。第三方配送模式就是指交易雙方把自己需要完成的配送業務委托為第三方來完成的一種配送運作模式。隨著物流產業的不斷發展，以及第三方配送體系的不斷完善，第三方配送模式應成為工商企業和電子商務網站進行貨物配送的首要模式和方向。

隨著物流管理的理念在中國企業內逐步被認知，第三方物流作為有著較新物流理念的產業正在逐步形成。中國原有的運輸企業、倉儲企業、電子商務企業經過改造和合并，形成了新興的第三方物流企業。第三方物流企業在對企業的服務中逐漸形成了一種戰略關系，隨著JIT管理方式在中國的普及，不論制造業還是商業企業，普遍應用JIT管理的理念，采用拉動方式，減少庫存，降低庫存儲備，適應市場變化。JIT管理方式的應用，使服務于制造企業和商業企業的第三方物流企業，采取小批量、多頻次的JIT運輸。第三方運輸與傳統運輸的比較如表2-1。

表2-1 傳統運輸與第三方運輸的比較

傳統運輸的特點 組合配送的特點

供應商對運輸獨立管理 第三方物流企業管理

分散操作，缺乏合作及可見性 整合操作完全的可見性和管理

分散復雜的流動 簡單集中的流動

低貨物空間利用率 優化車輛利用率

庫存水平不均 有效的庫存控制

無IT解決方案平臺 有一體化的IT平臺支持

第三方運輸是一種適應市場發展的新型的運輸配送模式，但其發展和推廣又有相當的條件和前提。

1、 市場需求程度。消費者的需求變化是導致市場需求變化的主要因素，對消費品本身可變性和帶動性需要進行分析。

2、 供應鏈體系的建立。供應鏈體系的建立是組合配送模型實施的前提，作為第三方物流企業，掌握了相當的主導企業和配套企業的機密信息，沒有戰略性的合作伙伴關系，第三方物流企業無法深入到供應鏈管理體系當中。作為第三方物流企業，在沒有建立戰略關系時，為供應鏈服務無形中會增加相當的交易成本和溝通成本，導致整個供應鏈成本上升和供應鏈體系的不穩定，無法發揮整合物流的優勢。

3、 信息技術和物流標準的推廣。依托Internet和企業內部局域網有效實施信 息共享是建立組合配送的基礎。供應鏈企業通過電子數據交換系統（EDI）、電子郵件系統等通過Internet在企業之間進行快速的信心交換，完成訂單下達和處理工作，減少了前置時間。第三方物流企業建立自己的物流管理系統與供應鏈主導企業和配套企業的信息系統進行有效連接，完成提貨通知、發運狀態、線路設定、發運結算等信息的交換，對配送指令進行快速反應。通過集裝化運輸、GPS跟蹤控制、條形碼技術等的應用，有效控制運輸，降低貨物的操作時間，適應快速的供應體系。

總之，第三方配送作為一種配送模式，符合企業發展和供應鏈發展的要求，對今后物流體系發展有著一定的引導作用。而本論文所要研討的配送方式正是符合第三方配送模式。

第四節 貨物運輸與配送管理

一、貨物運輸的影響因素與原則

貨物運輸是物流的核心業務，也是配送管理中不可缺少的一環。充分利用現有運輸管道，提高運輸、改進經營組織、管理體制等對改善配送管理有著重要的作用。

貨物運輸子系統的基本目標是安全、迅速、準確的成本。配送運行過程必須利用運輸網絡，即利用有運輸路線和結點組成的資源體系。在一定綜合運輸格局的情況下，不同運輸方式的服務質量、技術性能、方便程度、管理水平是影響不同層次物流系統選擇運輸方式的重要因素。在構思貨物運輸系統時，應根據系統實際擔負的貨運量的大小、作業內容與范圍、以及與其他各個子系統的協調關系，進行規劃、構筑工作，一般必須考慮一下幾個方面的因素：

1、 貨物的特點、性質、數量以及運輸方式的選擇。

2、 運輸路線的確定。

3、 設備設施、工具的配備和利用情況。

4、 運輸質量的保障。

5、 運輸戰場的利用。

6、 運輸費用的節約。

7、 運輸計劃的制定、貨物運輸與集散過程的控制。

8、 運輸網絡的形成與運行機制。

9、 不同的運輸方式之間的協作。

10、運輸與物流其他作業環節活動的綜合集成與管理等。

就組織運輸工作，應貫徹執行“及時、準確、經濟、安全”的原則，即

1、 及時。就是按著產、供、運、銷情況，及時把貨物從產地運到銷地，盡量縮短貨物在途時間，及時供應工農業生產和人民生活的需要。

2、 準確。就是在貨物運輸過程中，切實防止各種差錯事故，做到不錯不亂，準確無誤的完成運輸任務。

3、 經濟。就是采取經濟、最合理地運輸方案，能有效地利用各種運輸工具和運輸設施，節約人力、物力和運力，提高運輸經濟效益，降低貨物運輸費用。

4、 安全。就是貨物在運輸過程中，不發生霉爛、殘損、丟失、燃燒、爆炸等事故，保證貨物安全地達到目的地。

在配上過程中，要組織合理的運輸，所謂合理運輸就是按照商品流通規律、交通運輸條件、物品合理流向、市場供需情況、走最少的里程、經最少的環節、用最少的運力、花最少的費用、以最快的時間、把貨物從生產地運輸到消費地。也就是用最少的勞動消耗，運輸更多的貨物，取得最佳的經濟效益。因此，在運輸生產活動中，需要一定的勞動消耗，衡量運輸的合理與否，是從技術經濟角度，看消耗在運輸上的社會勞動量，來評價運輸的經濟效益。

二、運輸的五要素

組織合理運輸工作，涉及面廣，比較復雜，影響它的因素很多。要實現運輸合理化，起決定作用的有以下五個主要因素，物流業稱為合理運輸“五要素”。

（一）運輸距離

運輸既然是商品在空間的移動，那么這個移動的距離，即運輸里程的遠近，是決定其合理與否因素中一個最基本的因素。因此，物流部門在組織貨物運輸時，首先要考慮到運輸距離，應盡可能實習近產近銷，就近運輸，近可能避免舍近求遠。

（二）運輸環節

    在物流過程環節中，運輸是一個主要的環節，也是決定合理運輸的一個重要因素。因為，圍繞著運輸業務活動，還有進行裝卸、搬運、包裝等工作，多一道環節，須多花費、多勞動。所以，物流部門在調運物資時，對有條件直達、直撥運輸。使物資不進入中轉倉庫，越過一切不必要的中間環節，有產地直運到銷地，越過一切不必要的中間環節，減少二次運輸。

（三）運輸工具

在交通運輸日益發展，各種運輸工具并存的情況下，必須選擇運輸工具和運輸路線，合理運用。根據不同貨物的特點，分別利用鐵路、水運和汽車運輸，選擇最佳的運輸路線。

（四）運輸時間

對物流業來說，為了更好的為顧客服務，及時滿足顧客的需要，時間是一個決定性的因素。尤其在市場變化很大的情況下，時間問題更為突出。所以在物流過程中，必須特別強調運輸時間，要搶時間、爭速度，想方設法加快貨物運輸，盡量壓縮待運期，使大批貨物不要長期徘徊、停留在運輸過程中。

（五）運輸費用

運輸費用占物流費用比重大，它是衡量運輸經濟效益的一項重要指標，也是組織合理輸的主要目的之一。運輸費用的高低，不僅關系到物流企業或運輸部門的經濟核算，而且也影響商品銷售成本。為此，在組織合理運輸工作中，積極節約運輸費用，是物流企業的一項重要任務。

上述五個因素，既是互相聯系，又是互相影響的，有的甚至是互相矛盾的。這就要求進行綜合比較分析，要求最佳運輸方案。在一般情況下，運輸時間快、運輸費用省、是考慮合理運輸的兩個主要因素，它集中體現了物流過程中的運輸經濟效益。

第五節 配送的信息技術

一、條碼技術

條碼技術是在計算機的應用實踐中產生和發展起來的一種自動識別技術。為我們提供了一種對物流中的貨物進行標識和描述的方法。條碼是實現POS系統、EDI、電子商務、供應鏈管理的技術基礎，是物流管理現代化、提高企業管理水平和競爭能力的重要技術手段。

二、EDI技術

EDI (Electronic Data Interchange)是指通過電子方式，采用標準化 的格式，利用計算機網絡進行結構化數據的傳輸和交換。構成EDI系統的三個要素是EDI軟硬件、通信網絡以及數據標準化。

工作方式大體如下：用戶在計算機上進行原始數據的編輯處理，通過EDI轉換軟件(Mapper)將原始數據格式轉換為平面文件(Flat File)，平面文件是用戶原始資料格式與EDI標準格式之間的對照性文件。通過翻譯軟件{Translator)將平面文件變成EDI標準格式文件。然后在文件外層加上通信信封(Envelope)，通過通信軟件(EDI系統交換中心郵箱(Mailbox))發送到增值服務網絡(VAN)或直接傳送給對方用戶，對方用戶則進行相反的處理過程，最后成為用戶應用系統能夠接收的文件格 式。

三、射頻技術

射頻識別技術（RFID）是一種非接觸式的自動識別技術，它通過射頻信號自動識別目標對象來獲取相關數據。識別工作無須人工干預，可工作于各種惡劣環境。短距離射頻產品不怕油漬、灰塵污染等惡劣的環境，可以替代條碼，例如用在工廠的流水線上跟蹤物體。長距射頻產品多用于交通上，識別距離可達幾十米，如自動收費或識別車輛身份等。

四、GIS技術

GIS（Geographical Information System，地理信息系統）是多種學科交叉的產物，它以地理空間數據為基礎，采用地理模型分析方法，適時地提供多種空間的和動態的地理信息，是一種為地理研究和地理決策服務的計算機技術系統。其基本功能是將表格型數據（無論它來自數據庫、電子表格文件或直接在程序中輸入）轉換為地理圖形顯示，然后對顯示結果瀏覽、操作和分析。其顯示范圍可以從洲際地圖到非常詳細的街區地圖，顯示對象包括人口、銷售情況、運輸線路和其它內容。

五、GPS技術

全球定位系統（Global Positioning System－GPS）具有在海、陸、空進行全方位實時三維導航與定位能力。GPS在物流領域可以應用于汽車自定位、跟蹤調度，用于鐵路運輸管理，用于軍事物流。

第三章  配送路線優化的理論模型

  第一節   啟發式算法理論

一、啟發式算法的概念

啟發式源自英文單詞heuristics,啟發式方法意為通過對過去經驗的歸納推理以及實驗分析來解決問題的方法，即借助于某種直觀推斷或試探的方法。啟發式方法要求分析人員必須運用自己的感知和洞察力，從與研究問題相關而較基本的模型及算法中尋找其間的聯系，從中得到啟發，去發現適于解決該問題的思路和途徑。

用啟發式方法解決問題時強調“滿意”，常常是得到滿意解，決策者就認為可以了，而不去追求最優性和探求最優解。之所以這樣，其原因是：1、很多問題不存在嚴格最優解，這時，對目標的滿意性常比最優性更能準確地描述人們的選擇行為。2、對有些問題，得到它的最優解所花的代價太大。3、從實際決策的需要出發，有時要求解具有過高的精度沒有意義。

用啟發式方法求解問題是通過迭代過程實現的，因而需擬定出一套解得探索規則。為能得到滿意解，在整個迭代過程中要不斷吸收新的信息，必要時改變原來擬定的不合適的策略，建立新的搜索規則，注意從失敗中吸取教訓，并逐步縮小搜索范圍。啟發式方法具體求解過程如圖3-1所示。

 

                          圖3-1 啟發式方法的求解過程

二、啟發式算法的求解策略

用啟發式方法求解問題時，需采用一定的策略，下面列出幾個常用的策略，可根據問題的性質和要求選用。

（一）逐步構造解策略

逐步構造解策略是指每次增加解的一個元素（如節點、弧等），直到得到一完整的可接受解。

（二）改進解策略

從一初始解（初始解不一定可行）開始，通過一系列替換分解和合并過程來逐漸修正解，以提高解的可接受性。

（三）數學規劃策略

運用數學模型和優化算法，并通過對解的判別和修正以提高對問題的適用性，常會提出高效的啟發式算法。

（四）分解策略

把一個復雜的問題分解成一系列易于處理的子問題來求解，一個子問題的輸出常是下一個子問題的輸入。

（五）分割策略

把一個復雜的問題分割成一些平行的小的子問題，然后求解每個子問題，最后在相容原則下進行綜合，把子問題的解合并成原問題的一個解。

（六）可行解空間的限制策略

在某些情況下，把可行解集限制在一個可應用已存在高效算法的解集上，然后再求解問題。

（七）松弛策略

有時擴展問題的可行域以得到一個易于處理問題，然后求解松弛問題，就能直接得到或者很容易得到原問題的一個可行解，然后再對得到的解進行修正。

（八）搜索學習策略

包括在解的空間的定向搜索以及在搜索過程中發現和收集新的信息，并根據對新信息的分析，重新確認或改變搜索方向，修正搜索參數，消去不必要的搜索范圍，以有效提高搜索效率，盡快獲得問題的解。

第二節 遺傳算法理論

一、遺傳算法的由來

遺傳算法是60年代由美國 J. Holland 教授和他的學生建立發展的，其思想源于生物遺傳適者生存的自然規律，是一種新興的自適應隨即搜索方法，它對優化對象既不要求連續，也不要求可微，并具有極強的魯棒性和內在的并行計算機制，特別適合于非凸空間中復雜的多極值優化和組合優化問題，在機器學習、自動控制、機器人技術、電氣自動化以及計算機和通信等領域已取得了非凡的成就。近些年來，人們在用遺傳算法解決現實中的各種組合優化問題上進行了探索。

遺傳算法的工作機理是從達爾文進化論中得到靈感和啟迪，借鑒自然選擇和自然進化的原理，模擬生物在自然界的進化過程中所形成的一種優化求解方法。盡管這種自適應尋優技術可用來處理復雜的線性、非線性問題，但它的工作機理十分簡單。

二、遺傳算法的步驟

（一）構造滿足約束條件的染色體。

由于遺傳算法不能直接遺傳算法是60年代由美國 J. Holland 教授和他的學生建立發展的，其思想源于生物遺傳適者生存的自然規律，是一種新興的自適應隨即搜索方法，它對優化對象既不要求連續，也不要求可微，并具有極強的魯棒性和內在的并行計算機制，特別適合于非凸空間中復雜的多極值優化和組合優化問題，在機器學習、自動控制、機器人技術、電氣自動化以及計算機和通信等領域已取得了非凡的成就。近些年來，人們在用遺傳算法解決現實中的各種組合優化問題上進行了探索。

遺傳算法的工作機理是從達爾文進化論中得到靈感和啟迪，借鑒自然選擇和自然進化的原理，模擬生物在自然界的進化過程中所形成的一種優化求解方法。盡管這種自適應尋優技術可用來處理復雜的線性、非線性問題，但它的工作機理十分簡單。

處理解空間中的解，所以必須通過編碼將解表示成適當的染色體。實際問題的染色體有多種編碼方式，染色體編碼方式的選取應盡可能地符合問題約束，否則將影響計算效率。

（二）隨即產生初始群體。

初始群體是搜索開始時的一組染色體，其數量應適當選擇。

（三）計算每個染色體的適應度。

適應度是反映染色體優秀與否的唯一標識，遺傳算法就是要尋得適應度最大的染色體。

（四）使用復制、交叉和變異算子產生子群體。

這三個算子是遺傳算法的基本算子，其中復制體現了競爭與淘汰的自然規律，交叉體現了有性繁殖的思想，變異體現 了進化過程中的基因突變。

（五）重復步驟3、4直到滿足制止條件為止。

三、遺傳算法的優勢

（一）遺傳算法對問題參數的代碼集起作用，而不是對參數本身起作用。遺傳算法處理的對象是染色體，因而要求把所要優化問題的基本參數轉化成定長的有限符號的染色體。

（二）遺傳算法是從初始群體開始搜索的，而不是從單點開始搜索的，許多傳統優化方法都是從搜索空間的單點出發，通過某些轉換規則確定下一點。這種點到點的搜索方法在多峰值優化問題中，首先找到的可能不是最優峰值；而遺傳算法是以點集開始的尋優過程，初始群體是隨機地在搜集空間中選取的，這樣在搜索過程中達到最優峰值的概率遠大于點到點方法的概率。

（三）遺傳算法在搜索過程中只使用適應度函數信息，而不用倒數及其他輔助信息。對于不同類型的優化問題，傳統方法需要不同形式的輔助信息，沒有一種優化方法能適應各類問題的要求。遺傳算法在優化過程中，放棄使用這些輔助信息，具有廣泛適應性。

（四）遺傳算法使用頻率轉換規則而不用確定性規則。遺傳算法使用概率轉換規則來調整期搜索方向，各代群體間沒有統一的聯系規律。但使用概率轉換規則并不意味著這種方法屬于隨機算法范疇，它只是使用隨機轉換作為工具來調整搜索過程中趨向于目標函數不斷改進的區域。

于傳統方法相比，遺傳算法的優越性主要表現在：首先，在遺傳算子的作用下，遺傳算法具有很強的搜索能力，能以很大概率找到問題的全局最優解；其次，由于它固有的并行性，能有效地處理大規模的優化問題。

第三節  配送路線的優化模型

一、模型簡介

TSP一般描述為：旅行商從駐地出發，經所要去的城市至少一次后返回原地，應如何安排其旅行線路，才能使總的旅行距離（時間、費用）最少。對于現實問題，由于限制條件的增加，TSP可衍生出許許多多相關的問題。

一般TSP指一個旅行商訪問所有的城市。這里設城市O為旅行商出發城市，需要訪問的L各城市編號為1，••••，L，為了便于說明問題，把旅行商問題構造成網絡圖，以G=｛V,A,C｝表示，其中

V=｛0,1，L｝------點集，表示旅行商需要經過的地點。

A=｛（i,j）|i,j=1,1,••••，L, i≠j｝-----弧集，表示旅行商可能走過的線路段集合。

C=｛ |（i，j）≤A｝-----費用矩陣， 表示旅行商經過對應弧段（i，j）所花費，如時間、距離、花費等。

求解TSP即要求在加權圖G找到總費用做小的哈密爾頓回路，這里點O稱為源點。定義變量如下：

 =1 若弧（i,j）在線路上  或者   =0  若弧（i,j）不在線路上

則得到一下模型

 

 =1,j=0,1,••••l

 =1,i=0,1,••••l

X=( ) ≤S

 =0或1

二、求解方法

（一）節約法算法

節約算法又稱C—W算法，是有Clarke和Wright于1964年首次提出的。

它的基本思想是首先把各點單獨與源點O相連，構成1條僅含一個點的線路。總費用那個為

                    

然后計算將點i和j連接在一起線路上費用的“節約值”：

         

         

    

S(i,j)越大，說明把i和j連接在一起時總路程減少越多。構建線路時，根據S(i,j)從大到小的順序進行，實現時可在表上操作，具體步驟如下:

Step1：計算節約紙S(i,j)，并排列成表格形式。

Step2：在表格中選擇最大元素S(i,j):

Step3：考察對應的點i和點j，檢查是否滿足下列條件：

1、若點i和j均不在已構成的線路上，則可連接點i和j，得到線路段o→i→j→o，轉步驟step4；

2、若點i和j在已構成的線路上，連接后，但不是線路的內點（即不與源點O直接相連），則可以連接，連接后得到線路段o•••→i→j→o或o→i→j→•••o，轉步驟step4；

3、若點i和j在已構成的同一條線路上，則不能再進行連接，轉步驟step4。

Step4：劃去第i行和第j列，則i點不能再到其他點，而j點也不能有其他點達到；

Step5：若所有元素均被劃去，則已得到完整線路，算法終止；否則，在未被劃去的元素中選擇最大元素，轉步驟step3。

（二）最鄰近法

Step1：取源點O開始作為線路的起點；

Step2：尋找與上一次加進線路中的點距離最近的點，把此點加到線路中去；

Step3：重復step2，直到所有的點都已考慮，這就得到了一條線路。

（三）幾何啟發式算法

step1：構建點集的凸組合，此組合給出一初始線路。

Step2：選擇不屬于初始線路上的點k*及線路上的弧（ ， ），使由弧（ ， ）與弧（ ， ）構成的角度最大。

Step3：把點k*插入到點 與 之間。

Step4：重復step2---step3，直到得到—哈密爾頓回路。

（四）最小生成樹算法

Step1：求圖G的一顆最小生成樹T；

Step2：在T的所有奇數度頂點上，求最小費用匹配，從匹配解中增加分枝給已在T中的分枝，得到—歐拉回路；

Step3：檢查所有被不足訪問過一次的頂點，將歐拉回路轉化成哈密爾頓回路。

（五）最近插入算法

Step1：取源點O作為起點。

Step2：找到點L，使 最小，構成局部線路O—L—O；

Step3：對于已形成的局部線路，在不屬于此線路的點中，尋找離線路上的點最近的點K。

Step4：在線路上尋找弧(i,j)，使滿足 極小，把K插入點i與j之間。

Step5：返回step3，直到得到—哈米爾頓回路。

（六）最節約插入算法

Step1、step2與最近插入算法相同。

Step3：在局部線路中尋找（i,j）及不屬于此線路上的點K，滿足 極小，然后把K插入i與j之間；

Step4：重復，直到得到—哈密爾頓回路。

（七）凸集插入算法

Step1：構造點集的凸組合，此組合給出—初試線路。

Step2：對不在線路上的點K,確定在線路的哪兩個點i與j間插入點k。即對每個點k，找到 極小的（i,j）；

Step3：對在step2中找到的所有（i，k，j），確定（ ），使 極小；

Step4：把點k*插入到線路上的點 與 之間；

Step5：重復step2—step4，直到得到—哈密爾頓回路。

第四章 貝因美公司的配送流程優化

第一節 貝因美公司的簡介

貝因美始創于1992年，總部設在中國杭州，并在上海、北京、沈陽、武漢、成都、敦化、鄭州設有分公司。全國設立25個分公司，有K/A、批銷、嬰童店、百貨、網絡五大渠道，50000多個零售網點。品牌價值超過50億元人民幣。2008年的全年銷售總額 有50多億元，2009年的全年銷售總額達到了100億元。

貝因美以“關愛生命，熱愛生活”為宗旨，全方位服務于中國嬰童事業，致力于嬰幼兒食品及嬰童產業的研究與國際性合作。主營事業以嬰幼兒食品、嬰幼兒用品、育嬰咨詢服務、生命科學和母嬰保健、育嬰工程、愛嬰工程六大塊架構而成。其中嬰幼兒食品為主導項目，全面涵蓋代乳品、斷奶期食品和輔助食品三大類，是華東地區最大的斷奶期食品生產基地和中國三大嬰幼兒基本營養食品專業生產企業之一，產品覆蓋全國。產品包括貝因美商標各階段嬰幼兒米粉，奶粉，豆粉，營養奶糕，營養荷花糕，嬰幼兒磨牙餅，葡萄糖，蜂蜜，母嬰護理用品，童車，童床，童裝，玩具等。

貝因美奶粉的三大優勢 優質奶源、先進工藝、科學配方是打造奶粉品質的三大關鍵因素，貝因美三者兼備，建立、實施和不斷完善生產管理體系，應用全球領先的生產工藝與專業設備，為中國寶寶提供代表國際先進水平的產品。 優質奶源——北緯45度以上是國際公認的“黃金奶帶”。貝因美在地處北緯45度以上、有“中國奶牛之鄉”美譽的黑龍江省安達市設有貝因美奶源基地，并從同樣地處北緯45度以上、有“歐洲農村”之稱的愛爾蘭進口優質原料乳。

優質奶源，是安全的品質基礎；

全面科學管理，是安全的制度保障。

先進工藝——在生產工藝與設備方面，貝因美投資13億元，聯手全球乳業工藝巨頭荷蘭斯托克公司，配置專門為嬰幼兒奶粉生產設計的謝弗爾斯三效牛奶濃縮器等國際一流專業生產設備，并在安達工廠建成了國內首條高端嬰幼兒配方奶粉專用生產線；杭州工廠也分別從荷蘭高達公司和日本引進了國際先進的滾筒干燥營養米粉生產設備 ，形成了具有年產嬰幼兒營養米粉2萬噸的生產能力，是華東地區最大的斷奶期食品專業工廠之一，從硬件上保障了為中國寶寶提供專業的國際先進的產品。

科學配方——專為中國寶寶研制是貝因美的研發理念。不同國家的民族特性、地域環境和膳食結構導致了各國嬰童食品配方的不同需求。

貝因美17年來，一直致力于研發符合中國嬰童特質的產品，不斷完善研發組織和制度、引進尖端研發人才和設備；與國內外研發機構展開深度合作，比如創建貝因美母乳研究中心，致力于精準還原中國母乳復雜的營養結構,研發實現從高級配方到仿生配方的目標，針對中國寶寶的身體特點能夠提供更為專業的配方和養育方案，以確保科學性與安全性。 這些就是貝因美為什么能夠一直沒有出任何問題的原因，因為貝因美始終以質量位企業發展的原則，16年來一直嚴把質量關，始終做到對寶寶負責，讓媽媽放心！

 本文要研究的是貝因美坐落在杭州余杭區的安溪工廠，是全國最大的GMP標準嬰兒營養米粉工廠，安溪工廠年產6萬噸配方乳粉，總投資近3億引進全套進口全球領先工藝設備，目前在生產嬰幼兒配方奶粉生產線中首屈一指，采用全自動化流程高架立體庫，建設現代化物流中心，打造了國家級檢測中心，已全面質量監控的軟硬件建設為中國寶寶提供專業的國際先進產品。

            

圖4-1 貝因美工廠的生產車間

          

圖4-2 貝因美嬰幼兒用品

 

圖4-3 貝因美公司的組織結構

第二節 貝因美的配送流程分析

首先，貝因美的安溪工廠每天會生產出全國各個分公司所需要的產品，包括貝因美什錦營養米粉、營養磨牙餅、磨牙棒、健兒葡萄糖、兒童成長配方奶粉、乳清蛋白營養米粉、豬肝番茄營養米線、寶貝寶寶成長奶粉、營養小饅頭、淮山營養米粉、深海旗魚營養魚酥等。因為貝因美安裝ERP系統，每個分公司可以根據自己的需求情況給工廠下訂單，工廠根據訂單進行生產。接下來的流程是對生產出來的產品進行分類保管，同時要檢查產品的品種和數量是否正確，檢查包裝是否有破損的情況，一切就緒之后，工作人員通過叉車把貨物搬到倉庫的指定位置。

當第二天要發貨的時候，工作人員開始根據訂單把商品分揀出來，放到發貨場所指定的位置。配貨作業采用的是機械化的設備，采用的是摘果方式，即搬運車往返保管場所，按照分公司的要求從某個貨位上取下某種商品，巡回完畢后就完成了一個分公司的配貨，接著在對下一個分公司配貨。

發貨是配送中心工作流程的最后一道環節，貝因美在浙江、上海、南京、蘇州、武漢、貴陽、成都、北京、天津等全國各地都有自己的分公司，每天的發貨量平均有300多噸，每天光運費就要10萬左右，所以如何通過優化配送路線控制物流的成本是本文要研究的重點，因為貝因美的網點遍布全國各個城市，所以要進行全部的路線的優化有一定的困難，本文選擇的研究范圍是浙江省內的各個城市，有衢州、浦江、蘭溪、桐鄉、義烏、金華、湖州、諸暨、東陽、嘉善10個城市。這些城市一個星期內的需求情況相關數據如表4-1。杭州余杭到各個城市的距離的相關數據如表4-2。

表4-1 各個城市的一個星期之內的需求數據

省份 單位名稱 食品件數 食品體積 促銷品體積 總體積 總重量 發貨地

浙江 東陽一諾（杭州分公司） 256 6.3 0.9  7.2  1.8  杭州分公司發

浙江 湖州黎明（杭州分公司） 1274 31.9 2.9  34.8  6.9  杭州分公司發

浙江 嘉善新昕（杭州分公司） 950 22.5 3.2  25.7  5.7  杭州分公司開

浙江 金華鑫金珠（杭州分公司） 805 19.3 1.7  21.0  4.8  杭州分公司發

浙江 蘭溪永旺（杭州分公司） 416 9.9 2.4  12.3  2.9  杭州分公司開

浙江 浦江金貝（杭州分公司） 479 11.8 1.0  12.8  3.2  杭州分公司發

浙江 衢州龍游（杭州分公司） 1269 29.8 36.0  33.4  8.3  杭州分公司開

浙江 桐鄉梧桐店（杭州分公司） 267 6.7 5.4  13.7  5.3  杭州分公司開

浙江 義烏鈺爾（杭州分公司） 526 11.9 4.0  15.9  4.7  杭州分公司發

浙江 諸暨一百（杭州分公司） 590 14.4 5.4  19.8  4.3  杭州分公司發

                 

表4-2   各個城市之間的距離

杭州 杭州

東陽 172.0 東陽

湖州 93.6 243.0 湖州

嘉善 88.9 237.0 106.0 嘉善

金華 193.0 74.9 264.0 260.0 金華

蘭溪 209.0 90.6 280.0 276.0 27.8 蘭溪

浦江 146.0 46.2 217.0 213.0 76.4 57.0 浦江

衢州 270.0 159.0 310.0 345.0 101.0 92.1 161.0 衢州

桐鄉 45.9 194.0 65.7 59.0 216.0 231.0 168.0 303.0 桐鄉

義烏 149.0 20.7 220.0 217.0 56.8 71.8 32.5 135.0 172.0 義烏

諸暨 99.6 82.3 171.0 167.0 108.0 123.0 60.2 187.0 122.0 64.0 諸暨

                           

 

                                     圖4-1 目前的配送模式

目前的配送模式來回所需的總路程有2934公里。

第三節 配送路線的分析與優化

這里所用的配送車輛都是12頓的柴油貨車。

一、 方案一

不考慮車輛裝載，只考慮路線設計，使配送路線最短。先從杭州出發找距離杭州最近的城市，再由該城市作為中心點，找出距離該城市最近的另一個城市，這樣依次類推，回到杭州的話就是一個回路了。要是還有城市沒連的話再按照這個方法依次連起來，直到各個城市都與杭州連起來成為一個回合了，這樣才算完成本次的配送。

可以得出的最終的配送路線如圖4-2所示：

 

                                       圖4-2  改進后的配送路線

經過計算優化得到的路線有：

杭州－桐鄉－諸暨－杭州   總距離為267.5公里  總需求量為9.6噸 需要1輛車子

杭州－嘉善－浦江－義烏－杭州   總距離為483.4公里  總需求量為13.6噸  需要2輛車子

杭州－湖州－金華－蘭溪－衢州－杭州   總距離為747.5公里   總需求量為22.9噸  需要2輛車子

杭州－東陽   總距離為172公里  總需求量為1.8噸  需要1輛車子

二、方案二

考慮車輛最優裝載的路線優化

配送中心與用戶最短的距離的相關數據如表4-2。

表4-2  各個城市之間的距離

貨運量 杭州

1.8 172.0 東陽

6.9 93.6 243.0 湖州

5.7 88.9 237.0 106.0 嘉善

4.8 193.0 74.9 264.0 260.0 金華

2.9 209.0 90.6 280.0 276.0 27.8 蘭溪

3.2 146.0 46.2 217.0 213.0 76.4 57.0 浦江

8.3 270.0 159.0 310.0 345.0 101.0 92.1 161.0 衢州

5.3 45.9 194.0 65.7 59.0 216.0 231.0 168.0 303.0 桐鄉

4.7 149.0 20.7 220.0 217.0 56.8 71.8 32.5 135.0 172.0 義烏

4.3 99.6 82.3 171.0 167.0 108.0 123.0 60.2 187.0 122.0 64.0 諸暨

 

表4-3 所得的節約路程如表

貨運量 杭州

1.8  東陽

6.9  22.6 湖州

5.7  23.9 76.5 嘉善

4.8  290.1 22.6 21.6 金華

2.9  290.4 22.6 21.9 374.2 蘭溪

3.2  271.8 22.6 21.9 262.6 298.0 浦江

8.3  283.0 53.6 13.9 362.0 386.9 255.0 衢州

5.3  23.9 127.4 75.8 22.9 23.9 23.9 12.9 桐鄉

4.7  300.3 22.6 20.9 285.2 286.2 262.5 284.0 22.9 義烏

4.3  189.3 22.2 21.5 184.6 185.6 185.4 182.6 23.5 184.6 諸暨

表4-4 節約路程排序（從大到小）

從（i-j) 蘭溪-衢州 金華-蘭溪 金華-衢州 東陽-義烏 蘭溪-浦江 東陽-蘭溪

路程（i-j) 386.9 374.2 362.0 300.3 298.0 290.4

從（i-j) 東陽-金華 蘭溪-義烏 金華-義烏 衢州-義烏 東陽-衢州 東陽-浦江

路程（i-j) 290.1 286.2 285.2 284.0 283.0 271.8

從（i-j) 金華-浦江 浦江-義烏 浦江-衢州 東陽-諸暨 蘭溪-諸暨 浦江-諸暨

路程（i-j) 262.6 262.5 255.0 189.3 185.6 185.4

從（i-j) 金華-諸暨 義烏-諸暨 衢州-諸暨 湖州-桐鄉 湖州-嘉善 嘉善-桐鄉

路程（i-j) 184.6 184.6 182.6 127.4 76.5 75.8

從（i-j) 湖州-衢州 東陽-嘉善 東陽-桐鄉 蘭溪-桐鄉 浦江-桐鄉 桐鄉-諸暨

路程（i-j) 53.6 23.9 23.9 23.9 23.9 23.5

從（i-j) 桐鄉-義烏 金華-桐鄉 湖州-金華 湖州-蘭溪 湖州-浦江 湖州-義烏

路程（i-j) 22.9 22.9 22.6 22.6 22.6 22.6

從（i-j) 東陽-湖州 湖州-諸暨 嘉善-蘭溪 嘉善-浦江 嘉善-金華 嘉善-諸暨

路程（i-j) 22.6 22.2 21.9 21.9 21.6 21.5

從（i-j) 嘉善-義烏 嘉善-衢州 衢州-桐鄉   

路程（i-j) 20.9 13.9 12.9   

 

表4-5  用戶連接過程

（i-j)

蘭溪-衢州 金華-蘭溪 金華-衢州 東陽-義烏

 11.2 >12 >12 6.5

連接與否 蘭溪-衢州 不連 不連 東陽-義烏

（i-j)

蘭溪-浦江 東陽-蘭溪 東陽-金華 蘭溪-義烏

 >12 >12 11.3 >12

連接與否 不連 不連 義烏-東陽-金華 不連

（i-j)

金華-義烏 衢州-義烏 東陽-衢州 東陽-浦江

 11.3 >12 >12 >12

連接與否 義烏-東陽-金華 不連 不連 不連

（i-j)

金華-浦江 浦江-義烏 浦江-衢州 東陽-諸暨

 >12 >12 >12 >12

連接與否 不連 不連 不連 不連

（i-j)

蘭溪-諸暨 浦江-諸暨 金華-諸暨 義烏-諸暨

 >12 7.5 >12 >12

連接與否 不連 浦江-諸暨 不連 不連

（i-j)

衢州-諸暨 湖州-桐鄉 湖州-嘉善 嘉善-桐鄉

 >12 >12 >12 11.0

連接與否 不連 不連 不連 嘉善-桐鄉

（i-j)

湖州-衢州 東陽-嘉善 東陽-桐鄉 蘭溪-桐鄉

 >12 >12 >12 >12

連接與否 不連 不連 不連 不連

（i-j)

浦江-桐鄉 桐鄉-諸暨 桐鄉-義烏 金華-桐鄉

 >12 >12 >12 >12

連接與否 不連 不連 不連 不連

（i-j)

湖州-金華 湖州-蘭溪 湖州-浦江 湖州-義烏

 >12 >12 >12 >12

連接與否 不連 不連 不連 不連

（i-j)

東陽-湖州 湖州-諸暨 嘉善-蘭溪 嘉善-浦江

 >12 >12 >12 >12

連接與否 不連 不連 不連 不連

（i-j)

嘉善-金華 嘉善-諸暨 嘉善-義烏 嘉善-衢州

 >12 >12 >12 >12

連接與否 不連 不連 不連 不連

經過節約法計算后得出的方案二的配送路線如圖4-3所示。

 

                                            圖4-3 方案二的配送路線

杭州－蘭溪－衢州－杭州  總距離為571.1公里   總需求量為11.2噸  需要1輛車子

杭州－義烏－東陽－金華－杭州  總距離為437.6公里  總需求量為11.3噸 需要1輛車子

杭州－浦江－諸暨－杭州  總距離為305.8公里  總需求量為7.5噸  需要1輛車子

杭州－嘉善－桐鄉－杭州  總距離為193.8公里  總需求量為11.0噸 需要1輛車子

杭州－湖州－湖州   總距離為187.2公里  總需求量為6.9噸 需要1輛車子

三、 選擇最優解

表4-6 各個方案之間的比較

 所需車輛 共行駛距離 共行駛小時數 運輸費用

線路優化前 10  2934.0  48.9 5253

線路優化方案一 6 1670.4  27.9  3542

線路優化方案二 5  1695.5  28.3 2800

 

圖4-4  三個方案的車輛和行駛小時的比較圖

 

                                          圖4-5 三個方案的行駛距離和運輸費用的比較圖

從圖表4-6中可以看出來，方案二的運輸費用是最少的，所以方案二為最優方案。

第五章 總結和展望

        通過對制造業配送的研究，讓我更深入地了解了配送的各個流程，進貨、訂單處理、揀貨作業、補貨作業、配貨作業、送貨作業，并且通過對貝因美公司的配送流程的研究，理論結合實踐，對整個流程的操作體系有了新的理解。

        大型的制造業公司，往往在全國各地都有自己的分銷公司，本文因為篇幅限制的原因，只對貝因美公司在浙江省內的各個網點進行了跟蹤調查，并且搜集了很多的數據，最后對其配送路線進行了優化，得出了新的配送方案。

        但是這個模型是一個非常理想的情況，現實中會遇到很多的情況，比如說天氣情況、路上的交通情況、甚至要考慮員工的流失情況，非常多的不可預測因素會影響這個模型最后的結果，所以我在這邊只能謙虛地說配送路線的優化的精確度還有很大的空間可以提高。

        未來，物流業和制造業的聯動發展是一定是以后發展的趨勢，并且發展潛力巨大。在物流需求擴大，成本上升的壓力之下，越來越多的制造企業開始從戰略高度重視物流功能整合，實施流程再造，分離外包物流業務，以更加專注于核心競爭力的打造。制 造業為物流業的發展提供設施和技術基礎，物流業為制造業提供生產，現代物流業發展的滯后，必將在一定程度上影響制造業的發展，影響制造業產業結構的升級。

參考文獻：

[1]汝宜紅，宋伯慧.配送管理[M].北京：機械工業出版社，2004.10

[2]李軍，郭耀煌.物流配送車輛優化調度和理論與方法[M].北京：中國物資出版社，2001.11

[3]胡運權.運籌學教程[M].北京：清華大學出版社，2007.4

[4]郎茂祥.配送車輛優化調度模型與算法[M].北京：電子工業出版社，2009.3

[5]張潛.物流配送路徑優化調度建模與實務[M].北京：中國物資出版社，2006.9

[6]白世貞，言木.現代配送管理[M].北京：中國物資出版社，2005.1

[7]徐天亮.運輸與配送[M].北京：中國物資出版社，2002.9

[8]丁立言，張耀平.配送物流新趨勢[M].北京：清華出版社，2003.6

[9]薛荔.我國商業物流現狀與發展對策[A].武漢：西南農業大學學報，2009.10

[10]龐文英.淺談我國制造業與物流業的聯動發展[A].上海：物流工程與管理，2009

[11]李云，王平，陳勇，馬根峰，焦方源，蘇水根.郵政物流配送的數學模型研究[A].重慶：實用物流技術，2002

[12]劉寧杰，陳宇.基于ERP平臺的物流配送路徑優化[A].廣西財經學院工商管理系，2009

[13]楊錦冬，徐麗群.城市物流中心車輛配送配載調度指派模型研究[J].同濟大學學報(自然科學版)，2004，11（32）:1452-1456.

[14] 霍震佳，張磊.求解配送收集旅行商問題的啟發式算法[J].同濟大學學報， 2006，34（1）： 134-138

[15]蔣忠中，注定偉.物流配送車輛路徑優化的模糊規劃模型與算法[J].系統仿真學報， 2006，18（11）：3301-3304， 3312

[16]姜昌華，戴樹貴，胡幼華.求解車輛路徑問題的混合遺傳算法[J].計算機集成制造系統， 2007， 13（10）：2047- 2052

[17]唐連生，程文明，張則強.基于改進蟻群算法的車輛路徑仿真研究[J].計算機仿真， 2007， 24（4）：262-264

[18]劉興，賀國光.車輛路徑問題的禁忌搜索算法研究[J].計算機工程與應用，2007，43（24）：179-181，199

.上海：上海海事大學，2007.

[20] 何明珂.現代物流與配送中心.[M].中國商業出版社，1997.

[21] 吳清一著. 現代物流概論［M］.北京：中國物資出版社，2005.

[22] 周程著. 物流配送路徑優化策略研究 [J].武漢理工大學學報，2005.

[23] MARKUS HESSE.Global Chain, Local Pain Regional Implications of Global Distribution Networks in the German North Range.  Growth and Change,2006,Vol. 37 No. 4 , 570–596.

[24] Alan Rushton, John Oxley, Phil Croucher. The handbook of logistics and distribution management [M]. Kogan Page Publishers，2000.

[25] Ronald H Ballou. Business Logistics Management.[M]. Fourth Edition.

Prentice-Hall,Inc.,1999.

       致 　謝

篇7

關鍵詞：隨機模擬法 航班計劃 航班元素 統計特征

中圖分類號：TP31 文獻標識碼：A 文章編號：1674-098X（2014）01（b）-0089-04

Abstract：The paper aimed at the requirements for simulation flight plan in the airspace capacity evaluation work，sets up a mathematics model according to the flow and pivotal property statistical characteristics of flight plan，the stochastic simulation method is used to solve the problem.For simulatingmany times，the simulation results is analyzed，the results shows that：the advantages of stochastic simulation method that solve complex and uncertainty problem can effectively solve the problem of generating simulation flight plan，the various flow statistical characteristics can meet the requirements，the method has strong stability and practicability.

Key Words：stochastic simulation flight plan flight elements statistical characteristics

我國經濟的快速發展，對民航運輸提出了新的要求，全國各主要機場通過改擴建或者增加航班架次等方式來提高運力運量，這就需要對運量提升進行容量評估。在進行容量評估工作時，往往需要多種不同容量的航班計劃作為評估模型的輸入數據。仿真航班計劃的生成對空域容量評估工作具有重大意義。

國際上，Terrab、Odoni和Richetta等人研究了基礎網絡中單個機場的航班集合起降時間分配問題[1]。2003年，Thomas、Frederick等人研究了基于TAAM的仿真航班計劃，利用仿真的方法安排跑道航班計劃[2]。在國內，1996年，王峰、馬壽峰和賀國光研究了航班計劃制定及優化因素，運用非線性規劃方法對航班計劃進行優化[3]。2001年，朱晶波等人建立了多元受限航班計劃優化模型，提出了求解的改進啟發式算法，并設計了相應的航班時刻優化系統[4]。2008年，鐘育鳴、韓松臣等人以機場實際航班運行數據庫為基礎，討論了仿真飛機流的數據構成，提出了飛機流的仿真思路、模塊結構設計和仿真流程，構建了飛機流的生成模型[5]。2011年，黃魁建立了終端區容量評估模型，并對終端區容量評估中的飛機流產生算法進行了優化研究[6]。

生成仿真航班計劃既要滿足相應的流量分布要求，又要保證航班流的隨機性，同時航空公司對機場機位的使用權以及管制因素，也對容量評估工作以及航班計劃生成有重要影響。本文在跑道航班時刻研究的基礎上，考慮了航空公司機位的使用問題以及管制因素，結合航班時刻分配的規則，對航班流量特征進行分析并建立數學模型，然后采用隨機模擬法將目標航班計劃流量特征參數作為已知參數，并針對航班流的隨機性，對模型進行求解并生成仿真航班計劃。

1 航班流量分析及建模

在已知仿真航班計劃流量分布的條件下，首先根據進離港高峰的數學特征對進離港航班時刻進行分配，然后綜合考慮以該機場為基地的航空公司的流量特征，進行進離港航班時刻的再分配，最后根據管制部門要求，對各時段各公司各機型的航班的具體航班時刻進行最終分配。

1.1 仿真航班計劃流量分布

仿真航班計劃流量分布是由數據提供單位根據機場所在地理位置、人群出行特征、經濟社會環境等因素，對未來航班流量預測的結果。作為仿真航班計劃生成的已知條件，仿真航班計劃流量分布還包含離港高峰、全天高峰和全天航班總流量三個關鍵條件。以圖1為例，已知的離港高峰時段出現在7點至10點之間，進港高峰出現在18點以后，全天高峰流量出現在10點至18點之間，全天高峰流量值為32架次，全天流量為466架次。

1.2 進離港航班時刻初次分配

2 隨機模擬法的應用

隨機模擬法也被稱為蒙特卡洛法或者統計試驗法，隨機模擬法求解問題的思想為：首先，建立一個概率模型或者隨機過程，使它的參數等于問題的解；然后通過對模型或者過程的觀察或抽樣試驗來計算所求參數的統計特征，最后給出所求解的近似值。而解的精確程度可用估計值的標準誤差來表示。

仿真航班計劃數據量大，除了要保證各種機型、公司以及各個方向的航班的到達和離港具有隨機性，還要保證航班計劃的各項統計特征能夠滿足對應的預測參數，只有滿足這些條件，生成的仿真航班計劃才有意義。由此可知，仿真航班計劃的生成問題，就變成了如何產生滿足相應參數要求的航班計劃的問題和如何保證航班計劃隨機性的問題。

仿真航班計劃的各項特征，決定了傳統的確定性模型難以解決航班計劃生成中的不確定性難題。在這種情況下，可以考慮隨機模擬法。隨機模擬法可以針對仿真航班計劃中的各項屬性的隨機性問題建立一個簡單且便于實現的概率統計模型，使所求的量或解恰好是各項航班屬性概率分布或者數字特征。

2.1 隨機模擬法實現航班時刻初次分配

在已知航班流量分布的情況下，結合隨機模擬法，可以生成全天各小時的航班進離港流量，并完成航班時刻的初次分配。

使用隨機模擬法，將航班計劃中的進離港流量參數的目標值作為已知條件，設，，，。為進離港流量相對均衡時段離港航班流量占該時段航班流量的比例，為進港高峰時段離港航班的流量比例，為進離港相對均衡時各時段的航班流量集合。在進港高峰時間為，在該時段內生成取值范圍為的均勻分布隨機數，離港高峰時間為，在該時段內生成取值范圍為的均勻分布隨機數，在進離港流量相對均衡的時段內，生成取值范圍為的均勻分布隨機數。令，

，由此可得全天各個時段的離港航班流量，的表達式為：。那么全天各時段的進港航班流量也可求得。

2.2 隨機模擬法實現航班時刻再分配

對航空公司進行分類，在該機場有基地的航空公司稱為基地航空公司，其他的航空公司稱為無基地航空公司。在離港高峰時段，基地航空公司離港航班流量比例和無基地航空公司離港航班流量的比例可由終端區或者機場規劃設計部門給出預測值。假設第個小時的航班流量占全天航班流量比例為，航空公司的預測份額為，各航空公司航班流量占該時段航班總流量的比例為，那么由可以求得各個時段各航空公司航班流量的比例。

生成均勻分布的隨機數列，根據求得的值將生成的隨機數列劃分為區間，當隨機數值落在對應的區間時，設定該航班所屬的航空公司為對應的航空公司，由此可以完成航空公司航班時刻的再分配。

2.3 航班時刻的最終分配

以8點至9點的航班為例，該時段，該小時航班流量占全天航班流量的比例為5.4%，那么可以求得該時段各個航空公司的離港流量占全天流量的比例，同理可以求得其它時段的比例值。表2為添加了航空公司信息的8點到9點的部分航班計劃表，進離港標志中，A代表航班進港，D代表航班離港。各航空公司8點到9點的航班流量為。

第三步，同樣以8點至9點的航班時刻為例，令，。生成隨機數對航班排序，以五分鐘為單位對航班時刻進行規范化處理，得到如表3所示的部分航班計劃表。由于8點至9點之間航班量為28架次，以五分鐘為單位規范航班時刻時，每五分鐘的航班流量為。

3.2 結果分析

經過以上三個步驟，可以生成目標航班計劃。使用matlab程序進行100次航班計劃生成仿真，對航班計劃中的關鍵流量數據進行統計，統計結果見表3。由以上結果可知，該文采用的航班計劃生成方法具有較好的穩定性和實用性。

航班計劃是由管制部門、機場部門以及航空公司多方參與制作的，限于篇幅，本文未考慮航班來向去向、航班機型等因素。同時，隨機模擬法中對隨機數的使用，使本文中的方法更適用于大流量機場的仿真航班計劃的生成。對于更復雜仿真條件下航班計劃的分析與生成，還有待進一步的深入研究。

參考文獻

[1] O.Richetta，A.R.Odoni.Solving optimally the static ground-holding policy problem in air traffic control[J].Transportation Science，1983，27，August 1993：p228-238.

[2] Thomas Curtis Holden，FrederickWieland.Runway schedule deter-mination by simulation optimization[Z].Proceedings of the 2003 Winter Simulation Conference.McLean，MITRE corporation，2003：1670-1676.

[3] 王峰，馬壽峰，賀國光.航班時刻表優化模型的研究[J].系統工程學報，1996，11（1）：50-56.

[4] 胡明華，朱晶波，田勇.多元受限的航班時刻優化模型與方法研究[J].南京航空航天大學學報，2003，35（3）：326-332.

篇8

關鍵詞：運籌學；應急物流；選址―定位

中圖分類號：F250 文獻標識碼：A

Abstract： Because the efficient of emergency logistics can reduce the harms caused by emergency， it has caused wide public concerns among theorists. This paper provides an overview of Chinese emergency logistics study from many aspects： basic theory， the construction of system and the related models on the base reviewing the liberations in recent years， also it indicated that the modeling sense in operation research plays a decisive role in the research of emergency logistics.

Key words： operation research； emergency logistics； location-routing

近年來，我國各地突發事件頻發，其中自然災害的發生的占比非常高，如2010年8月甘肅舟曲發生特大山洪泥石流、2014年7月云南發生洪澇泥石流災害、2013年3月墨竹工卡縣發生山體滑坡災害、2013年7月甘肅岷縣漳縣發生6.6級地震災害、2014年新疆于田發生7.3級地震災害、2015年9月江西福建等地發生洪澇風雹災害、2015年8月陜西山陽發生滑坡災害等。這些自然災害的發生嚴重威脅人類的生命和財產安全，以及社會的經濟發展甚至會影響和諧社會的構建，在突發事件發生后，如何盡快地將賑災物資送至災區以減少災害損失是應急物流問題研究的主要內容，即應急物流LRP問題的研究。應急救援部門必須以最小的成本、最快的時間、合理地選擇物資存儲點將存儲物資科學地安排車輛對受災點進行物資的配送服務以減少傷亡，提高受災地區民眾的抗災信心。

當前國內外學者對一般LRP問題的研究比較具體深入，比如Min等[1]（1998）、Nagy等[2]（2007）、陳久梅等[3]（2014）都做過一般LRP問題的優化研究，當前應急物流的優化問題已經引起了眾多學者的關注，但是對于應急物流的LRP研究（定位―路徑）還相對較少。現有文獻主要有兩種研究范式：一種是單獨研究其中一個問題，即單獨研究應急物流中心選址問題或單獨研究應急資源調度問題；另外一種是將這兩個問題集成起來進行研究。然而應急物流中物流中心點的選擇和運輸路徑安排是直接影響應急物流系統效率的兩個關鍵問題，兩者之間相互依賴和影響，有必要結合應急物流的突發性、不確定性、緊急性等特點，從整體系統優化的角度，將這兩方面結合起來進行研究，故近年來，大部分對于應急物流問題的研究均是對選址―配送這兩個問題集成起來進行研究。根據現有的研究，應急物流LRP問題基本可以按照信息是否確定分為以下兩類：確定信息下的應急救援問題研究和不確定信息下的應急救援問題研究。

1 確定信息下的應急物流LRP研究

確定性的應急物流LRP問題，通常考慮的問題中信息基本都是確定的，即不存在任何風險因素，并且受災點的需求是確定的。針對確定性的應急物流LRP問題的研究，張玲[4]（2008）考慮到由于災區范圍比較廣泛進而災區存在不同的級別，針對該實際情況，通過對災區進行分組，并運用場景分析的發放，考慮其資源的布局和選址問題，引入多類0-1變量來表述該優化問題，構建了基于多級別的資源布局多目標規劃模型。黃向榮等[5]（2009）在考慮食品物流的相關特點和突發事件的突發性、緊急性以及弱經濟性等特性的基礎上，構建了食品的應急物資分發中心選址決策的評價體系，并且結合蟻群算法（ACA）和徑向基神經網絡（RBFNN）構建了應急物流物資分發點選址決策模型。曾敏剛等[6]（2009）針對應急服務應急物資分發點定位以及物資配送路徑這兩個子問題，引入多個0-1決策變量去表述該優化問題，建立了以最小化總成本為目標的選址―定位模型。葛春景等[7]（2011）研究了應急設施選址中的多重覆蓋問題，并以在滿足需求點的多次覆蓋需求和多需求點同時需求的條件下覆蓋的人口期望最大為目標，建立了確定性的應急物流優化模型，通過改進的遺傳算法對該模型進行求解。鄭斌、馬祖軍等[8]（2013）針對兩級應急物流系統中的中轉站選址和上下級進行聯運調度的集成優化問題，建立雙層規劃模型，并根據該模型的特點設計了一種混合遺傳算法。

通過以上文獻梳理可知，在運用運籌學建立應急物流LRP模型過程中，通常引入0-1決策變量去解決應急物資分發點選址問題和車輛物資配送問題，引入三類決策變量，第一類0-1決策變量是表示應急物資分發點是否開設，通常1表示該應急物資分發點開設，0則表示不開設，當該決策變量為1時，才分配運輸車輛從該應急物資分發點出發進行物資配送服務，并且從同一個應急點出發車輛的物資運輸量需小于應急點的物資存儲量；第二類0-1決策變量是用來表示某運輸車輛服務哪個受災點的問題，1表示運輸車輛服務該受災點，0則表示運輸車輛不服務該受災點；第三類決策變量則表示某運輸車輛是否從該應急物資分發點出發，1表示這運輸車輛從該應急物資分發點出發，0則表示這個運輸車輛不從該應急物資分發點出發。這三類0-1變量的引入合理地表述了應急物流系統的優化問題，目標函數通常為應急物流系統總成本最小以及運輸車輛到達所有受災點的總時間最小，建立的模型均為0-1線性規劃模型。運籌學中0-1規劃主要用于求解互斥的計劃問題、約束條件互斥問題、固定費用問題和分派問題等方面，而應急物流的優化問題從運籌學的角度就是一種分派問題，因此運籌學能夠在應急物流優化問題中大放光彩。目前，0-1應急物流規劃問題通常有三種解法，即窮舉法、變換法和隱枚舉法。解0-1型整數規劃最容易想到的方法，和一般整數線性規劃的情形一樣，就是窮舉法，即檢查變量取值為0或1的每一種決策組合，比較目標函數值的大小，從而選出目標值最小的那一組決策組合就是應急物流優化問題的最優解。然而由于應急物流優化問題中涉及的變量較多，所有決策組合就非常多，可能解集將成指數劇增加，此時用這種方法效率就比較低下，因此通常運用隱枚舉法進行求解，“隱”的含義是指在檢驗可能解的可行性和非劣性過程中，根據目標函數的特性增加一個以前一非劣解目標值的附加約束的過濾條件，以此達到減少問題求解過程的運算次數的目的。方法的核心思想均為檢查變量取值為0或1的策略組合，通過目標函數值比較從而得出最優解。

2 不確定信息下的應急物流LRP研究

針對不確定性的應急物流LRP研究，通常考慮的問題中信息基本都是不確定的，并且在救災期間存在一定的風險，比如應急設施點失靈風險、路徑中斷風險、路徑復雜度等，同時往往受災點的需求是不確定的。

何珊珊等[9]（2013）針對在突發事件發生的緊急救援期，受災點的需求很難確定，基于此建立了受災點配送總時間最短和系統總成本最小的選址―路徑問題的數學模型，并通過算例驗證了多目標魯棒優化模型能夠體現受災點對各類物資需求不確定條件下選址―配送方案的最優性與魯棒性的均衡。孫華麗等[10]（2013）針對需求隨機變化的應急物流定位―路徑問題，將救援過程劃分為兩個階段，將受災點的物資需求表示為一個區間數，以物資送達時間最短和系統總成本最小為目標，構建了多物資、多運輸車輛、多目標的定位―路徑模型。張玲等[11]（2014）也將救災過程分為了兩個階段，考慮到突發災害初期災情相關參數概率分布信息很難精確獲得，建立了基于情景的最小最大后悔值準則的魯棒優化模型，求解模型時，利用有限情景集表示第二階段的不確定數據，并將模型化為與其等價的混合整數模型，利用情景松弛的迭代算法進行求解。商麗媛等[12]（2013）考慮不同情景下應急物流需求的不確定性，將不確定需求用區間灰數表示，構建了多情景下不確定需求的應急物流配送中心選址模型，并設計了免疫量子粒子群算法進行求解。針對由于自然災害帶來的路網風險的應急物流LRP問題，閻俊愛、郭藝源[13]（2016）考慮到路網情況實時變化的復雜性下，構建了應急物流LRP動態模型，以車輛配送時間最小為目標，并通過設計的遺傳算法實現了基于動態路網實時調整的問題求解。陳鋼鐵、黎青松等[14]（2016）考慮到路網存在災后受損的風險，故引入多種運輸方式，基于此構建了震后多式聯運的應急物資配送路徑優化模型，并設計了啟發式算法對該應急物流模型進行了求解。

以上不確定信息下的應急物流LRP優化問題研究中，均運用了運籌學不確定規劃的思想建立了應急物流LRP模型，在應急物資分發點選址問題以及路徑配送與否方面，同樣引入三類0-1決策變量來表示應急物資分發點建立與否，車輛是否從某個應急物資分發點出發以及車輛是否服務某個受災點。除此以外，引入兩類整數決策變量，一類為運輸車輛配送至某個受災點的物資量，一類為某個受災點的物資未滿足量，在約束中，這兩個量的和大于該受災點的物資需求量，同時針對未滿足量盡量最小化的目標，將在目標函數中賦予未滿足量一個很大的懲罰數。在模型求解中，運用了隨機規劃的思想去處理一些風險因素，在處理受災點物資需求的不確定方面，則運用三角模糊數的理論或魯棒優化的思想去處理不確定性，在模型求解過程中，最終均通過一定的方法把不確定模型轉化為確定的混合整數模型去進行求解。

運籌學的核心思想即為從現實生活場合抽出本質的要素來構造數學模型，探索求解的結構，從可行方案中尋求系統的最優解作為決策者最好的選擇。通過以上文獻的梳理，可以看出運籌學在應急物流系統定位―路徑優化問題中已經成為核心工具之一，而應急物流系統定位―路徑優化問題作為當前的熱點問題之一，它的研究仍然處于初步階段，許多領域還缺乏系統性和深入性的研究，需要進一步加強研究。

參考文獻：

[1] Min H， Jayaraman V， Srivastava R. Combined location-routing problems： a synthesis and future research directions[J]. European Journal of Operational Research， 1998，

108（1）：1-15.

[2] Nagy G， Salhi S. Location-routing： issues， models and methods[J]. European Journal of Operational Research， 2007，177（2）：649-672.

[3] 陳久梅，邱晗光. 兩級定位―路徑問題模型及變鄰域粒子群算法[J]. 運籌與管理，2014（6）：38-44.

[4] 張玲，黃鈞，朱建明. 應對大規模突發事件的資源布局模型與算法[J]. 系統工程，2008，26（9）：26-31.

[5] 黃向榮，謝如鶴. 基于蟻群算法與RBF神經網絡模型的突發應急配送決策[J]. 決策參考，2009（15）：56-58.

[6] 曾敏剛，崔增收，余高輝. 基于應急物流的減災系統LRP研究[J]. 中國管理科學，2010，18（2）：75-80.

[7] 葛春景，王霞，關賢軍. 重大突發事件應急設施多重覆蓋選址模型及算法[J]. 運籌與管理，2011，20（5）：50-56.

[8] 鄭斌，馬祖軍，李雙琳. 基于雙層規劃的應急物流系統選址―聯運問題[J]. 系統科學與數學，2013，33（9）：1046

-1060.

[9] 何珊珊，朱文海，任晴晴. 不確定需求下應急物流系統多目標魯棒優化模型[J]. 遼寧工程技術大學學報，2013，32（7）：998-1003.

[10] 孫華麗，周戰杰，薛耀鋒. 考慮路徑風險的不確定需求應急物流定位―路徑問題[J]. 上海交通大學學報，2013（6）：962-966.

[11] 張玲，陳濤，黃鈞. 基于最小最大后悔值的應急救災網絡構建魯棒優化模型與算法[J]. 中國管理科學，2014（7）：131-139.

[12] 商麗媛，譚清美. 不確定應急物流中心選址模型及算法研究[J]. 計算機應用研究，2013，30（12）：3603-3605.

篇9

關鍵詞：配送中心；選址問題；成本；服務半徑

中圖分類號：F252.14 文獻標識碼：A

0 引 言

物流配送中心是專門從事物資配送業務的物流基地，是通過轉運、分類、保管、流通、加工和信息處理等作業，根據用戶的訂貨要求備齊商品，并能夠迅速準確和廉價地進行配送的基本設施。物流配送中心連接著供應商、制造商和分銷商及客戶，決定著供應鏈的流通成本和運作效率。在整個物流配送中心建設規劃中，一個非常重要的問題就是配送中心的選址。正確的選址策略不僅可以減少企業的各項成本，還能為客戶提供更優質的服務。

一般來講，配送中心是一個成本中心而非利潤中心，如果使用絕對成本作為考核指標，管理人員將會更傾向于壓縮支出，這樣不利于高質量地完成物流服務。因此，使用相對指標更加合理，例如企業配送中心的服務半徑。如果配送中心的服務半徑過大，那么它的輻射范圍也越大，覆蓋的客戶就越多，其服務能力將供不應求，這樣會影響配送服務的質量及水平；另一方面，如果配送中心的服務半徑過小，那么它的輻射范圍也就越小，服務能力將會過剩，嚴重影響配送中心的使用效率。21世紀以來，物流企業的側重點已經由單純地追求收益和利潤向更好更高效地為客戶服務轉變。例如，以前百勝的配送中心設定300公里的最遠服務半徑。在2012年年末盼盼食品等17家食品企業為了合理地布局增加企業競爭力而大大縮短企業在全國各配送中心的配送半徑。由此可見，服務半徑對于企業來說是一個決定企業布局的重要影響因素。

而配送中心最終是要為特定的目標客戶服務的。因此，配送中心一定要能夠輻射到其特定的目標客戶。那么配送中心的位置就必然要受到服務半徑的制約。配送中心選址問題就是確定配送中心的數目、位置以及每個配送中心所服務的客戶群體。配送中心選址問題所追求的目標可歸納為三類：一是成本，即追求總費用最低；二是距離，即如何選擇確定配送中心的位置使得整個物流網絡總路徑最短；三是時間，即要求在最短的時間內將物資運送到需求點。這三個方面互為側重點，國內外很多學者分別從三個方面加以研究，取得了重要的研究成果。

選址問題近年來受到了越來越廣泛的關注，并且形成了幾種基本的模型，如連續選址模型、網絡選址模型和離散選址模型。連續選址也稱為平面選址，允許在可行的連續空間任何位置選址。它有兩個基本的屬性，一個是解空間是連續的，另一個是要用適當的量度測量其距離。相關研究，如Brimberg等（2000）[1]、Kafer and Nickel（2001）[2]、Klamroth（2001）[3]等。對于網絡選址，距離被視為地圖中的最短路徑，允許在指定網絡的頂點和邊上選址。網絡選址的研究，如Boffey等（2003）[4]、Beasley（1993）[5]等。如果給定一個預配送中心集合，選址問題可歸為離散選址。有興趣的讀者可以查閱Goldengorin等（2003）[6]、Harkness and ReVelle（2003）[7]、Grunert（2002）[8]、Chardaire（1999）[9]、Gourdin（2000）[10]等。

針對選址問題模型的求解方法主要有定性和定量兩種。定性方法包括專家打分法和德爾菲法等；定量方法包括重心法、P中值法、數學規劃法、多準則決策方法、各種啟發式算法、仿真法以及這幾種方法的結合等。

本文遵循經濟性與服務性的原則，與傳統離散選址模型不同之處是，在考慮成本，即運輸成本、固定建設成本、存儲成本基礎上，引入了服務半徑的約束，建立了多物流配送中心選址問題的數學模型。最后，通過一數學例子對模型進行了數值計算。然后用分區域法對同一例子進行了求解。并將結果進行了對比分析。結果表明帶服務半徑約束的選址模型比企業普遍使用的區域劃分選址方法成本更低，服務更高效。本文的研究將對實際問題具有一定的借鑒作用。

1 建立模型

1.1 問題描述

物流配送中心選址問題可描述為：某地區有需求點若干個，已知每個需求點的需求量，現欲在有限個備選地址中選擇某幾個地址建立配送中心，并為每個需求點運送物資，用來滿足每個需求點的需求，配送中心到其服務的需求點的配送半徑不能超過限值。目標是使總費用最少。結構圖如圖1所示：

1.2 假設條件

為了簡化配送中選址問題，我們不妨做如下的幾個假設：

（1）在給定的若干個備選地址中選擇某幾個地點建立配送中心；

（2）每個需求點可由多個配送中心提供物資；

（3）配送中心容量足夠大，能夠滿足所有需求點的需求；

（4）各需求點的需求量一定且為已知；

（5）各配送中心沒有多余的物資冗余；

（6）配送中心與各用戶間的單位運費已知；

（7）運輸費用與運輸量成正比。

為了建立模型，我們引入以下的幾個變量：

2 案例分析

山東某物流公司的客戶分布在本省的17個城市，為了滿足客戶需求并且降低成本，該公司決定在這些城市中建立3個配送中心，配送中心備選地分別是城市1、2、3、8、11、15、17，單位運輸成本為1.8（元/噸公里），要求配送中心的服務半徑是270公里。公司面臨的首要問題就是配送中心的位置和配送方案。圖2為山東省地圖，表1至表4分別列出了各需求點及其編號、各需求點的年需求量、各需求點的物資單位存儲費用和固定建設成本，以及各需求點與備選點間的公路距離等。

2.1 精確求解

用LINGO軟件求解，得到目標值為1 311 818元，配送中心選擇的地點為2、11、17（如圖3所示），配送方案如圖4所示。

2.2 分區域解法

精確解法將所有的地點放在一起進行整體選址、配送。而現如今，很多企業是將配送中心按要求進行分區域配送，比如現在很多企業習慣將中國分為華南、華中、華北、東北、西北、西南6個大區，然后分別在每個大區設定區域機構，然后向下屬單位或者客戶進行區域內配送。

本案例中由于需求點較多而且分布比較廣，因此首先對所有的需求點進行區域劃分，形成若干個配送區域。影響選址決策的因素有很多，本文選擇主要的幾個宏觀因素，根據各需求點間宏觀因素的相似性將需求點進行分類，使相似性較大的需求點聚集在同一個區域，具有較大差異的需求點劃分在不同的區域。為了確保所選因素量化的可行性，除了需求點坐標外，本文還選取了5項反映該區域物流發展水平的主要指標，包括市場繁榮度、信息、區位商、貨運比重和工業比重[11]。各指標含義如下：

（1）坐標：坐標主要是用于根據各需求點的相對位置確定其歸類。

（2）市場繁榮度：城市批發零售貿易業的產品銷售額 / 該城市的國內生產總值。

（3）信息：（城市移動電話人數+城市固定電話戶數+使用網絡人數） / 該城市人口總數。

（4）區位商：（城市交通、倉儲、郵電業從業人數/該城市總從業人數） / （全國交通、倉儲、郵電業從業人數/全國總從業人數）。城市區位商反映了該城市的物流專業化水平。商值大于1，表示物流部門從事基本經濟活動；值小于1，表示全部物流部門都屬于非基本經濟活動，不利于城市的發展。

（5）貨運比重和工業比重分別指該城市的貨運總量和工業產值占山東本省相應項目的比重。

表5顯示了各需求點相應的指標值及其分區結果，其中第5至第9列的數據來源于2011年山東省統計年鑒。最后一列是用SPSS軟件根據上述7項指標用系統聚類法歸類的結果。

從表中可以看出配送區域分類的結果，最佳配送區域劃分數量為3，其中需求點威海市、煙臺市構成區域1，需求點青島市、日照市構成區域2，需求點濰坊市、東營市、濱州市、淄博市、萊蕪市、泰安市、濟南市、德州市、聊城市、菏澤市、濟寧市、棗莊市、臨沂市構成區域3。

計算各區域內的最佳配送中心。根據表2、表3、表4的數據，利用EXCEL分別求出7個備選點作為配送中心時所對應的總費用，結果如表6所示。從表6的結果可以看出，3個區域的配送中心分別應該建在威海市、青島市和濟南市，總費用為

1 393 432.72元，具體的配送方案如圖5所示。

表7列舉了帶服務半徑約束的精確解法與現在普遍適用的分區域法的各種參數，分別從配送中心的選擇地點、固定建設成本、存儲成本、運輸成本以及總費用等方面進行對比分析。可以看出，配送中心選擇的地點有很大的差異。帶服務半徑約束的精確解法相比分區域解法，不僅總費用要少很多，而且能夠更高效地為客戶提供服務，服務水平明顯提高。導致這種差異的因素主要有以下幾個方面：其一，固定建設費用。分區域解法在劃分區域的時候并沒有將各城市的固定建設成本考慮進去，這導致了配送中心選擇地點的時候很可能將地點設在建設成本很高的備選點，如本例中青島市；其二，運輸費用，帶服務半徑約束的精確解法由于考慮了距離的因素，也就變相地縮短了配送中心的配送路程，從而最終使得總運輸路徑減少，運輸費用比區域劃分法要少很多。綜合幾方面的考慮，本文引入服務半徑建立的模型要比現今很多企業正在使用的分區域法更適合企業。

3 結 論

本文重點就選址配送問題，建立了帶有服務半徑約束的規劃模型，通過數學例子對模型進行了數值計算。然后用分區域法對同一例子進行了求解。并將結果進行了對比分析。結果表明帶服務半徑約束的選址模型比企業普遍使用的區域劃分選址方法成本更低，服務更高效。對于企業來說，不僅能夠節省相關的成本，而且能夠更好地為客戶服務，符合物流企業“一切以客戶為中心”的戰略要求。尤其是在油價上漲的當下，本文提出的模型更有利于企業長遠、持續的發展。

但在建模及求解過程中，本文沒有對配送中心的容量（承載量）加以限定。而且在配送過程中，我們假定車輛是一次配送完成，不涉及車輛調度的具體問題，并且對道路的狀況、客戶需求不確定情況等方面都沒有考慮，與現實有一定的差異。這些都需要在今后的研究中加以解決，從而更好地為企業的決策者服務。

參考文獻：

[1] J. Brimberg， P. Hansen， N. Mladenovic， E. Taillard. Improvements and comparison of heuristics for solving the multisource Weber problem[J]. Operations Research， 2000，48：444-460.

[2] B. Kafer， S. Nickel. Error bounds for the approximate solution of restricted planar location problems[J]. European J. Oper. Res.， 2001，135：67-85.

[3] K. Klamroth. Planar Weber location problems with line barriers[J]. Optimization， 2001，49：517-527.

[4] B. Boffey， D. Yates， R. D. G. Galvao. An algorithm to locate perinatal facilities in the municipality of Rio de Janeiro[J]. J. Oper. Res. Soc.， 2003，54：21-31.

[5] J. E. Beasley. Lagrange an heuristics for location problems[J]. European J. Oper. Res.， 1993，65：383-399.

[6] B. Goldengorin， D. Ghosh， G. Sierksma. Branch and peg algorithms for the simple plant location problem[J]. Comput. Oper. Res.， 2003，30：967-981.

[7] J. Harkness， C. Re Velle. Facility location with increasing production costs[J]. European J. Oper. Res.， 2003，145：1-13.

[8] T. Grunert. Lagrangean tabu search， in： C.C. Ribeiro， P. Hansen （Eds.）， Essays and Surveys in Metaheuristics[M]. Kluwer Academic Publishers， Boston， 2002：379-397.

[9] P. Chardaire， J. L. Lutton， A. Sutter. Upper and lower bounds for the two-level simple plant location problem[J]. Ann. Oper. Res.， 1999，86：117-140.

[10] E. Gourdin， M. Labbe， G. Laporte. The incapacitated facility location problem with client matching[J]. Oper. Res.， 2000，48：671-685.

篇10

鑒于即期客戶較難準確預測，傳統的艙位分配存在著很大的不確定性，綜合運用市場細分和收益管理的方法，考慮空箱調運問題，圍繞即期客戶和合同客戶這兩大客戶群建立航運電商環境下兩艘對開班輪的艙位分配優化模型.以中日韓航線為例，計算為即期客戶和合同客戶預留的艙位數；根據在航運電商環境下預測值與實際值差距縮小的特征，分析傳統環境下與航運電商環境下集裝箱班輪艙位分配方案的差異.在航運電商環境下計算所得的總收益大于傳統環境下的總收益，顯示該優化模型的有效性和電商平臺的優越性.結論如下：航運電商的發展能有效提高班輪公司收益；電商平臺下的艙位分配趨勢使預測精度大大提高，預留的艙位數與實際到達的客戶需求出入較小；電商客戶在航運電商環境下會得到大力發展，合同客戶的數量會逐漸下降.

關鍵詞：

航運電商； 集裝箱班輪； 收益管理； 艙位分配

中圖分類號： U695.22； F551

文獻標志碼： A

0 引 言

在當今航運市場競爭越發激烈、航運市場環境越發黯淡時，隨著互聯網的風起云涌，電子商務出現革命性的飛躍.它改變著世界貿易環境和企業運作方式，成為航運企業提高自身競爭力的有力法寶.航運電商已將傳統的訂艙和比價推上“線上交易”平臺.這些新的電商平臺不僅使海運業供需雙方長期以來的交易模式發生改變，而且使交易雙方成本降低、效率提升、服務水平提高.行業集中度和標準化水平的提高促使海運物流行業從原先的價格和規模競爭升級到服務、體驗和整合能力競爭.航運企業的信息化水平將直接影響供應鏈的有效建立，進而影響企業的競爭力.通過電子商務，航運企業能夠及時獲取訂艙信息，以便實時調整航線、班期、配載和運價，及時調整合同客戶和即期客戶的艙位分配，從而提高效率、降低成本.航運電商正成為航運業突破市場低迷與劇烈動蕩、轉變商業模式的有效手段.

集裝箱班輪的艙位分配一直都是國內外學者研究的熱點問題.TING等[1]基于收益管理的思想，考慮客戶滿意度和航運企業收益最大化兩個目標，提出一種模糊多目標規劃方法求解集裝箱班輪航位分配問題.HA[2]利用泛太平洋西向航線的訂貨數據，應用期望邊際收益（Expected Marginal Revenue）和閾曲線（Threshold Curve）模型，對集裝箱班輪公司的艙位控制策略進行較為深入的研究.MARAGOS[3]和SPYRIDON[4]分析班輪貨運的特點，研究多種情況（單航段、多航段、多航段多種類貨物、臨時取消訂艙、超訂）下集裝箱艙位動態分配和定價問題，建模的方式有整數規劃、線性規劃、動態規劃等，采用啟發式算法求解.隨后，ZURHEIDE等[5]對艙位分配問題進行持續的研究.FENG等[6]以裝載港貨量一定為前提，優化傳統的艙位分配模型，使其更適用于復雜密集的亞洲港口網絡的港到港艙位分配問題.卜祥智等[7]針對海運收益管理的特征，建立考慮長期運力合同、空箱調運的班輪運力分配和路徑選擇隨機規劃模型，然后應用穩健優化方法對此模型進行求解.楊華龍等[89]利用概率統計方法，計算出在一個多港掛靠循環航次中所包括的各個航段應為普通客戶預留的艙位數量，建立包含空箱調運問題的艙位分配隨機規劃模型，通過確定各航段為長期合同客戶預留的艙位數量的上下限，將隨機規劃模型轉化為可以求解的確定性規劃模型.施欣[10]結合對集裝箱海運空箱調運過程的剖析，建立相應的系統優化模型，并通過數字仿真揭示成本、收益等經濟參數以及船舶裝載能力對集裝箱空箱調運策略的影響機制.陳繼紅[11]以班輪運力配置模型為基礎，建立基于非線性目標規劃的班輪聯盟艙位租賃決策優化模型，用于分析和研究聯盟情況下集裝箱班輪系統艙位租賃、配置優化與決策問題.王琳等[12]對非合作博弈和聯合決策情形下的系統效率進行比較，通過數值算例分析遠期合同艙位優惠價格對系統效率的影響，給出協調整個系統的方法，有效地提高系統總效率.李冰州等[13]進一步研究考慮集裝箱二維特性（容量和重量）的最優艙位分配策略，還考慮最優超訂水平.殷明等[14]認為：班輪運輸是海洋運輸的一種方式，為海上集裝箱提供定期的運輸服務，帶有濃厚服務性色彩；它向社會提供的不是實物形態的產品，而是一種勞務產品，即集裝箱貨物的空間位移.郭詠春等[15]探討碳約束配額、燃油價格、碼頭裝卸效率等對成本及碳排放量的影響，為船公司運營和政府決策提供參考.

綜上：現有文獻有的只考慮重箱而忽略空箱調運；有的只研究確定情況下的需求，對于不確定需求沒有給出有效解法；有的僅僅考慮如何減少空箱調運成本，并沒有考慮整個航運公司的收益管理問題；所有文獻都沒有考慮航運電商對艙位分配的影響.本文在現有文獻的基礎上，運用概率統計的方法，基于市場細分和收益管理理論，考慮空箱預留和航運電商環境下不同客戶群的差異化定價進行艙位分配，以謀求收益的最大化.

1 艙位分配模型構建

1.1 問題描述

在一條由若干個港口組成的固定航線上，班輪公司安排兩艘集裝箱班輪分別從該航線兩端相向對開，依次掛靠沿線的各個港口.班輪公司的客戶群大體分為兩類，合同客戶和即期客戶.合同客戶指已經與班輪公司簽訂長期合同的客戶，以一些大的貨主和貨運公司為主；即期客戶指那些零散的、不確定的客戶.

假設班輪公司的客戶群在航運電商環境下分為電商客戶和合同客戶， 在傳統環境下分為普通客戶和合同客戶.本文的即期客戶指航運電商環境下的電商客戶或傳統環境下的普通客戶.

合同客戶由于貨物的穩定性和數量較大可以享受班輪公司為其制定的折扣價格，而即期客戶定價相對較高.班輪公司為維持運營，在每個航次上都會為合同客戶預留一定數量的艙位，其余的則留給即期客戶.如何確定為合同客戶和即期客戶在每個港口預留的艙位數，既滿足合同客戶的需求，又最大限度地滿足即期客戶的需求，盡可能多地降低艙位的虛耗和需求的溢出，以使獲益最大，是班輪公司需要考慮的問題.

1.2 參數設置

Rc為來自合同客戶的單位運輸收益，Re為來自電商客戶的單位運輸收益，Ro為來自普通客戶的單位運輸收益，Rb為空箱的單位運輸收益，Q為每艘班輪的艙位數量，de為電商客戶實際的艙位需求量，do為普通客戶實際的艙位需求量，dc為合同客戶的艙位需求量，dbj為在港口j的空箱需求量，Qe為班輪為電商客戶預留的艙位數，Qo為班輪為普通客戶預留的艙位數，re為電商客戶預期的邊際收入，X為分配給合同客戶的艙位數，Y為空箱調運數.

1.3 模型假設

（1）對開的兩艘班輪艙位數相同.

（2）這條固定航線共有n個港口，i，j=1，2，…，n， i

（3）合同客戶、電商客戶和普通客戶在正向航段（ij）和反向航段（ji）上的艙位需求都服從正態分布，即dc～N（d-c，σc），de～N（d-e，σe）和do～N（d-o，σo），其中d-c，d-e，d-o為期望值，σc，σe，σo為標準差.

（4）下列參數已知：Rc，Re，Ro和Rb，以及dc，de和do三者各自的均值和標準差.

（5）當合同客戶的邊際收入與即期客戶預期的邊際收入相等時收益最大.

1.4 模型構建

式（11）表示即期客戶與合同客戶的收益之和減去空箱運輸費用，所得集裝箱班輪運輸收益最大；

式（12）表示第1艘班輪從港口i出發，分配給合同客戶的艙位數與空箱數之和不超過在港口i可接受即期客戶的艙位數；

式（13）表示第2艘班輪從港口j出發，分配給合同客戶的艙位數與空箱數之和不超過在港口j可接受即期客戶的艙位數；

式（14）表示在正向航段（ij）上，為使各港口進出的集裝箱數保持平衡，空箱調運數不小于港口j的空箱需求數，保證港口有空箱可用；式（15）表示在反向航段（ji）上，空箱調運數不小于港口i的空箱需求數；式（16）表示在正向航段（ij）上，分配給合同客戶的

艙位數不能超過合同客戶實際的集裝箱艙位需求，目的是盡可能多地滿足即期客戶的艙位需求；式（17）表示在反向航段（ji）上，分配給合同客戶的艙位數不能超過合同客戶實際的集裝箱艙位需求；式（18）表示決策變量的整數約束.

2 算例分析

2.1 案例

有一條固定航線（見圖1），由5個停靠港口組成，依次為上海港―青島港―釜山港―神戶港―東京港.在這條航線上有相向而行的兩艘班輪，合理分配艙位以使兩艘班輪的總收益最大.

2.2 已知條件

這兩艘班輪的容量都是5 000 TEU，其他已知條件見表1和2.

2.3 兩種環境下艙位的優化結果

相對于傳統的艙位分配，通過航運電商平臺預定艙位波動幅度更小，艙位分配更加合理.根據航運電商環境下預測值與實際值差距縮小的特征，當de=do時分別取各航段σe的平均值為10，20和30 TEU，運用MATLAB，根據表1和2給出的已知數據，求出傳統環境下和航運電商環境下兩艘班輪在每一航段應為合同客戶預留的艙位數、各港口可接受的即期客戶的訂艙數以及空箱調運的情況.求解模型得到兩艘集裝箱班輪在各航段不同σ值所對應的艙位優化分配結果，見表3和4.

2.4 對比分析

根據上面的優化結果，可以計算出航運電商環境下和傳統環境下集裝箱班輪公司該航次運費總收益，見圖2.在傳統環境下，即使進行艙位的優化分配，最后計算出的總收益也只有29 448 717美元；在航運電商環境下，即使當σe=30 TEU時總收益也能達到31 244 778美元.對比兩種情況所計算的總收益可知，班輪公司通過電商平臺至少可以多賺取1 796 061美元的收益.

由圖2可知，在市場細分條件下通過航運電商平臺進行的艙位分配優于傳統平臺下的艙位分配，且隨著σe的增大總效益呈下降趨勢，即在航運電商環境下預測精度越低期望收益越小.

由圖3和4中合同客戶和即期客戶的平均數量可知，隨著σe逐漸減小（即預測精度逐漸提高），合同客戶數量逐漸下降，

即期客戶數量逐漸上升.因此，在航運電商環境下進行集裝箱班輪的艙位分配，一方面要保持電商平臺預測精準性，合理擁有合同客戶，另一方面要積極發展電商客戶.

3 結束語

電子商務在近幾年發展迅速，電商對航運的影響也日益顯著，特別是電商訂艙平臺的開發使廣大客戶受益的同時，大大推了進傳統航運業向現代航運業轉型.本文圍繞即期客戶和合同客戶這兩大客戶群建立艙位優化分配模型，代入已知的各航段的運費率和艙位需求，首先求出傳統環境下兩艘班輪

分別為普通客戶預留的艙位數以及可以接受的合同客戶的艙位數，再求出航運電商環境下不同σe值所對應的艙位分配結果.根據最后的優化結果對航運電商平臺與傳統平臺總收益進行對比，在航運電商環境下計算所得的總收益大于傳統環境下的總收益，并遠遠大于只考慮合同客戶的總收益，顯示出該優化模型的有效性和電商平臺的優越性；通過對航運電商平臺艙位分配的分析可知，隨著σe值的下降，班輪總收益呈上升趨勢，同時電商客戶增加，合同客戶相應減少.從中可以看出電商平臺下的艙位分配趨勢使預測精度大大提高，預留的艙位數與實際到達的客戶需求出入很小；電商客戶在航運電商環境下會得到大力發展，合同客戶數相反會得到抑制以致逐漸下降.

本文只研究航運電商環境下單一固定航線上的兩種客戶群.今后可以進一步研究多式聯運，探討多班輪與多航線之間的相互作用與影響，對電商的概念和對象可以進一步拓展，并考慮客戶群和集裝箱的種類或一些特定情況下的集裝箱艙位分配問題.

參考文獻：

[1] TING S C， TZENG G H. Fuzzy muliobjective programming approach to allocating containership slots for liner shipping revenue management[C]//Austria， Mikulas Luptacik， Rudolf Vetschera. Semmering： the 16th International Conference on MCDM， 2002： 116.

[2] HA D. Capacity management for the maritime industry （shipping，itineraries）[D]. Knoxville， USA： University of Tennessee， 1994.

[3] MARAGOS S A. Yield management for the maritime industry （shipping， itineraries）[D]. Cambridge， USA： Massachusetts Institute of Technology， 1994.

[4] SPYRIDON A M. Yield management for the maritime industry[D]. Cambridge， USA： Massachusetts Institute of Technology， 1994.

[5] ZURHEIDE S， FISCHER K. A revenue management slot allocation model for liner shipping networks[J]. Maritime Economics & Logistics， 2012， 14（3）： 334361.

[6] FENG CM.，CHANG CH. Optimal slot allocation with empty container reposition problem for Asia ocean carriers[J]. International Journal of Shipping and Transport Logistics， 2010， 2（1）： 2243.

[7] 卜祥智， 陳榮秋， 趙泉午. 考慮長期運力合同的班輪收益管理運輸路徑優化模型[J]. 中國管理科學， 2007， 15（6）： 3945.

[8] 楊華龍， 劉迪， 夏秋. 集裝箱班輪多港掛靠循環航次艙位分配[J]. 重慶交通大學學報（自然科學版）， 2013， 31（6）： 12481251.

[9] 楊華龍， 夏秋， 劉迪. 基于市場細分的集裝箱班輪運輸艙位分配[J]. 中國航海， 2013， 36（1）： 132135， 142.

[10] 施欣. 集裝箱海運空箱調運優化分析[J]. 系統工程理論與實踐， 2003， 23（4）： 7076， 89.

[11] 陳繼紅. 集裝箱班輪聯營系統艙位租賃與分配決策優化模型[J]. 數學的實踐與認識， 2011， 41（17）： 4855.

[12] 王琳， 全雄文. 集裝箱班輪遠期艙位分配博弈研究[J]. 物流技術， 2009， 28（4）： 5760.

[13] 李冰州， 陳旭， 武振業. 集裝箱海運二維收益管理能力分配隨機模型[J]. 系統管理學報， 2007， 16（4）： 447453.