隨機顧客和需求的配送優(yōu)化-模型與算法.pdf

1、在物流配送優(yōu)化調(diào)度中，配送模式規(guī)劃和配送路徑優(yōu)化是兩大核心問題，對應(yīng)到組合優(yōu)化研究領(lǐng)域分別為聚類分析和路徑問題。這些問題自提出至今已有幾十年時間，廣大研究者在這些領(lǐng)域開展了大量研究工作，并取得了豐富成果。然而，在日常物流配送的實際應(yīng)用中，顧客需求往往不是固定不變的，更多情況下需要在顧客需求的存在性和需求量不確定的情況下對配送模式和配送路徑進行先驗優(yōu)化，但目前關(guān)于顧客和需求不確定的配送優(yōu)化問題研究十分有限。
　　 針對顧客和需求不

2、確定背景下物流配送優(yōu)化研究中存在的不足，論文在確定性聚類分析，確定性旅行商問題和確定性車輛路徑問題已有研究成果的基礎(chǔ)上，分別深入探討顧客需求存在性和需求量為隨機元素時配送優(yōu)化中的概率聚類問題，概率旅行商問題，以及隨機顧客和需求的車輛路徑問題三個子問題。通過對三個子問題建立數(shù)學(xué)模型并分析問題特征，給出相應(yīng)的啟發(fā)式求解算法。
　　 首先，提出顧客需求存在性隨機的概率聚類問題(CPSE)，在分析了CPSE問題特點后，給出了CPSE問題

3、的數(shù)學(xué)模型。受基于經(jīng)典聚類問題(BCP問題)的K-means算法啟發(fā)，以K-means為原型，給出將其拓展到CPSE問題的PK-means算法。針對K-means族算法初始類簇代表點隨機選擇策略存在解穩(wěn)定性和收斂性較差的弊端，提出針對BCP問題的基于鄰域密度初始類簇代表點選擇策略和針對CPSE問題的基于期望鄰域密度初始類簇代表點選擇策略，并分別將其應(yīng)用于DK-means算法和DPK-means算法。仿真實驗證實了對于顧客需求存在性隨機的

4、聚類分析問題，有必要將其與經(jīng)典確定性聚類問題區(qū)別研究，且有必要設(shè)計特別針對CPSE問題的聚類算法。實驗結(jié)果同時驗證了提出的DPK-means算法在求解CPSE問題時的有效性，以及其相對于簡單PK-means算法的改進效果。
　　 其次，針對實際物流配送的路徑優(yōu)化過程中顧客需求具有不確定性的特點，將顧客需求的存在性作為隨機元素，討論了一種較經(jīng)典旅行商問題(TSP)更為普遍，也更為復(fù)雜的概率旅行商問題(PTSP)。通過對PTSP問題

5、定義和建模，發(fā)現(xiàn)目標(biāo)函數(shù)計算復(fù)雜度過高是制約問題求解的瓶頸。受到TSP問題鄰域搜索思想的啟發(fā)，給出了針對PTSP的兩種鄰域搜索策略及鄰域搜索過程中計算目標(biāo)函數(shù)改變量的遞歸推導(dǎo)公式，采用這些遞歸公式可以將鄰域搜索的計算復(fù)雜度從O(n4)降為O(n2)，有效提高局部搜索效率。此外，為了適應(yīng)更多求解算法的設(shè)計要求，還給出兩種PTSP先驗路徑目標(biāo)函數(shù)近似估計的方法，結(jié)合仿真實驗分析了近似估計中參數(shù)取值與估計精度之間的關(guān)系。在驗證了PTSP解與T

6、SP解之間關(guān)系后，給出了一種求解PTSP的全局優(yōu)化HGSA算法，通過仿真實驗驗證了算法的有效性。
　　 最后，針對實際物流配送中顧客和需求均具有不確定性的特點，將顧客的存在性和具體需求量作為隨機元素，在受車輛裝載能力約束的前提下，討論了較經(jīng)典帶容量約束車輛路徑問題(CVRP)更為普遍，也更為復(fù)雜的顧客和需求量隨機的車輛路徑問題（VRPSCD）。通過對VRPSCD問題定義和建立模型，發(fā)現(xiàn)目標(biāo)函數(shù)中路徑成本期望的計算復(fù)雜度過高是制約