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

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

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

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

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

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

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

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