不確定信息車輛路徑問題及其算法研究.pdf

1、隨著全球市場分工的進一步細化，世界范圍內(nèi)貿(mào)易的頻度與數(shù)量都呈現(xiàn)出顯著的增長，物流效率成為甄別一個企業(yè)乃至一個國家經(jīng)濟運行效率的重要指標之一。車輛路徑問題是物流運輸系統(tǒng)的核心組件，并且由于其研究方法及成果可直接應用于組合優(yōu)化領(lǐng)域，因而自誕生之日起就得到了理論與實務界的廣泛關(guān)注，取得了大量的成果。但是，受于時代經(jīng)濟與信息處理技術(shù)的限制，這些研究大多是確定型模型，即假設(shè)在安排車輛路徑之前所有的相關(guān)信息都已經(jīng)知道并且確定。現(xiàn)今，社會經(jīng)濟運行的環(huán)

2、境較之從前發(fā)生了巨大的變化，一方面，經(jīng)濟活動頻率大大增加，并且伴隨著大量的不確定信息；另一方面，通信及計算機技術(shù)的飛速發(fā)展不僅使社會經(jīng)濟秩序避免了因不確定信息的泛濫而可能引發(fā)的混亂，而且進一步促使人們利用這些不確定信息創(chuàng)造更多的財富。可以說，對不確定信息的處理策略及技術(shù)手段直接決定了經(jīng)濟實體的效率、盈利水平。針對這一新情況的產(chǎn)生、發(fā)展，本文對不確定信息車輛路徑進行研究，開展了以下工作： 首先，對不確定信息車輛路徑問題的進行了一般

3、概述。闡述了車輛路徑問題的定義、構(gòu)成、分類、模型以及求解車輛路徑問題的經(jīng)典算法；在此基礎(chǔ)上，將不確定信息車輛路徑問題劃分為非實時信息處理的不確定信息車輛路徑問題和實時信息處理的不確定信息車輛路徑問題兩大類，分析了不確定信息車輛路徑問題的內(nèi)涵、特點、研究現(xiàn)狀及相應的各種數(shù)學模型、優(yōu)化方法，指出研究中存在的問題。 其次，對求解車輛路徑問題的各類啟發(fā)式算法的研究現(xiàn)狀進行了較為詳細的綜述和歸納，闡述它們誕生的源泉思想、運作流程，并詳盡分

4、析了它們在車輛路徑問題中的應用進展。在此基礎(chǔ)上提出了新的改良算法，即最大熵分布估計算法、自感應蟻群算法和混合粒子群算法，進行了相應的理論分析與證明，為處理復雜的不確定信息車輛路徑問題提供必要的數(shù)學求解工具。 第三，逐次遞進研究了2類隨機車輛路徑問題。首先，研究僅有供（?。┴浫蝿盏能囕v路徑問題，即隨機需求車輛路徑問題。對此，結(jié)合現(xiàn)實生活中長期顧客服務記錄所隱含的統(tǒng)計性知識構(gòu)建了新的統(tǒng)計學模型，設(shè)計了求解該模型的混合粒子群算法，并通

5、過大量的仿真試驗比較分析了新算法與其他智能算法的優(yōu)劣。其次，進一步研究具有供貨和取貨雙重任務的車輛路徑問題，即同時供貨和取貨的隨機車輛路徑問題。應用上節(jié)的統(tǒng)計學思想，構(gòu)建了該類問題的整數(shù)規(guī)劃模型，提出期望程度因子、距離性比因子等概念，設(shè)計了針對該問題的自感應蟻群算法，并與其他優(yōu)化算法進行了數(shù)據(jù)測試與比較，驗證了算法的有效性。 第四，分析了模糊車輛路徑問題，綜合選擇車輛行駛時間以及顧客預約時間為模糊信息參量，克服了現(xiàn)有研究僅局限于

6、某種單模糊變量而未能系統(tǒng)考慮復合模糊變量的缺陷，并采用細分顧客類別以吸收配送者知識系統(tǒng)的方法，分別以物流企業(yè)效用最大化和顧客效用最大化兩種決策目標構(gòu)建了2類模糊車輛調(diào)度優(yōu)化模型，給出了求解該類問題的最大熵分布估計算法，并結(jié)合仿真試驗分析了決策參數(shù)的變化對2類模型計算結(jié)果的影響，給出了相關(guān)參數(shù)制定的依據(jù)。 第五，漸進深入研究了2類實時動態(tài)車輛路徑問題。首先，研究了非滿載動態(tài)車輛路徑問題，即動態(tài)旅行商問題，闡述了動態(tài)車輛路徑問題實現(xiàn)

7、的技術(shù)支持單元以及動態(tài)信息數(shù)據(jù)生成的方法，并利用仿真試驗考察了實時不確定信息車輛路徑問題各現(xiàn)場一次性優(yōu)化方法的性能。其次，研究了更具現(xiàn)實意義的滿載有時間窗動態(tài)車輛路徑問題，在服務中心處理新信息的機制以及動態(tài)規(guī)劃行駛中車輛行駛路徑的策略方面提出了新的見解，闡明物流企業(yè)對新信息的處理方法，提出動態(tài)車輛路徑問題優(yōu)化的分置策略，設(shè)計了針對該問題的改進蟻群算法以及相應的分段計算啟用規(guī)則，并結(jié)合仿真試驗與各現(xiàn)場一次性優(yōu)化方法及基本蟻群算法進行了性能