论文部分内容阅读
在物流配送优化调度中，配送模式规划和配送路径优化是两大核心问题，对应到组合优化研究领域分别为聚类分析和路径问题。这些问题自提出至今已有几十年时间，广大研究者在这些领域开展了大量研究工作，并取得了丰富成果。然而，在日常物流配送的实际应用中，顾客需求往往不是固定不变的，更多情况下需要在顾客需求的存在性和需求量不确定的情况下对配送模式和配送路径进行先验优化，但目前关于顾客和需求不确定的配送优化问题研究十分有限。
针对顾客和需求不确定背景下物流配送优化研究中存在的不足，论文在确定性聚类分析，确定性旅行商问题和确定性车辆路径问题已有研究成果的基础上，分别深入探讨顾客需求存在性和需求量为随机元素时配送优化中的概率聚类问题，概率旅行商问题，以及随机顾客和需求的车辆路径问题三个子问题。通过对三个子问题建立数学模型并分析问题特征，给出相应的启发式求解算法。
首先，提出顾客需求存在性随机的概率聚类问题(CPSE)，在分析了CPSE问题特点后，给出了CPSE问题的数学模型。受基于经典聚类问题(BCP问题)的K-means算法启发，以K-means为原型，给出将其拓展到CPSE问题的PK-means算法。针对K-means族算法初始类簇代表点随机选择策略存在解稳定性和收敛性较差的弊端，提出针对BCP问题的基于邻域密度初始类簇代表点选择策略和针对CPSE问题的基于期望邻域密度初始类簇代表点选择策略，并分别将其应用于DK-means算法和DPK-means算法。仿真实验证实了对于顾客需求存在性随机的聚类分析问题，有必要将其与经典确定性聚类问题区别研究，且有必要设计特别针对CPSE问题的聚类算法。实验结果同时验证了提出的DPK-means算法在求解CPSE问题时的有效性，以及其相对于简单PK-means算法的改进效果。
其次，针对实际物流配送的路径优化过程中顾客需求具有不确定性的特点，将顾客需求的存在性作为随机元素，讨论了一种较经典旅行商问题(TSP)更为普遍，也更为复杂的概率旅行商问题(PTSP)。通过对PTSP问题定义和建模，发现目标函数计算复杂度过高是制约问题求解的瓶颈。受到TSP问题邻域搜索思想的启发，给出了针对PTSP的两种邻域搜索策略及邻域搜索过程中计算目标函数改变量的递归推导公式，采用这些递归公式可以将邻域搜索的计算复杂度从O(n4)降为O(n2)，有效提高局部搜索效率。此外，为了适应更多求解算法的设计要求，还给出两种PTSP先验路径目标函数近似估计的方法，结合仿真实验分析了近似估计中参数取值与估计精度之间的关系。在验证了PTSP解与TSP解之间关系后，给出了一种求解PTSP的全局优化HGSA算法，通过仿真实验验证了算法的有效性。
最后，针对实际物流配送中顾客和需求均具有不确定性的特点，将顾客的存在性和具体需求量作为随机元素，在受车辆装载能力约束的前提下，讨论了较经典带容量约束车辆路径问题(CVRP)更为普遍，也更为复杂的顾客和需求量随机的车辆路径问题（VRPSCD）。通过对VRPSCD问题定义和建立模型，发现目标函数中路径成本期望的计算复杂度过高是制约问题求解的瓶颈。受到CVRP问题邻域搜索思想的启发，给出了针对VRPSCD版本的邻域搜索策略及邻域搜索过程中近似估计路径成本期望改变量的方法。为了适应更多求解算法的设计要求，给出VRPSCD解路径成本期望的取样近似估计法，并结合仿真实验分析了近似估计中样本规模与估计精度之间的关系。最后，在不同顾客需求概率下，结合仿真实验对比了VRPSCD求解与基于历史平均需求水平的确定性CVRP求解的差异性。