【作者】 曾华；

【导师】 吴耀华；

【作者基本信息】 山东大学 ， 系统工程， 2012， 博士

【副题名】模型与算法

【摘要】 在物流配送优化调度中,配送模式规划和配送路径优化是两大核心问题,对应到组合优化研究领域分别为聚类分析和路径问题。这些问题自提出至今已有几十年时间,广大研究者在这些领域开展了大量研究工作,并取得了丰富成果。然而,在日常物流配送的实际应用中,顾客需求往往不是固定不变的,更多情况下需要在顾客需求的存在性和需求量不确定的情况下对配送模式和配送路径进行先验优化,但目前关于顾客和需求不确定的配送优化问题研究十分有限。针对顾客和需求不确定背景下物流配送优化研究中存在的不足,论文在确定性聚类分析,确定性旅行商问题和确定性车辆路径问题已有研究成果的基础上,分别深入探讨顾客需求存在性和需求量为随机元素时配送优化中的概率聚类问题,概率旅行商问题,以及随机顾客和需求的车辆路径问题三个子问题。通过对三个子问题建立数学模型并分析问题特征,给出相应的启发式求解算法。首先,提出顾客需求存在性随机的概率聚类问题(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求解的差异性。更多还原

【Abstract】 Distribution model planning and distribution routing are two major problems of logistics distribution optimization and scheduling. In combinatorial optimization, these two problems are researched as clustering problem and routing problem. Both of the two problems have been proposed for decades. Researchers have already explored deep in these fields and acquired valuable results. In daily logistics distribution, the requirements of customers are not constant. On the contrary, mostly people have to complete the optimization with uncertainty before exact requirements and demands are available. But by now, researches on distribution optimization with uncertain customers and demands are still rare.Based on the existing researches on distribution optimization, especially on the certain clustering, certain traveling salesman problem and certain vehicle routing problem, this thesis focuses on three subproblems of uncertain distribution optimization, in which customers and demands are stochastic. These subproblems includ clustering problem with stochastic object existence, probabilistic traveling salesman problem, and vehicle routing problem with stochastic customers and demands. After problem formulation and modeling, some heuristic algorithms are proposed for each subproblem respectively.Firstly, a new uncertain clustering problem model with stochastic object existence named CPSE is proposed. Based on the K-means algorithm of classic certain clustering problem, a new heuristic algorithm named PK-means is proposed for CPSE. Since clustering results of K-means family algorithms depend on initial clustering centers strongly. To overcome this shortcoming, an improved initialization of clustering centers based on neighbor density is proposed, then it is used in both DK-means algorithm for certain clustering and DPK-means algorithm for CPSE. Experimental results show that, it is necessary to research CPSE separated from nomal certain clustering problme, and design particular algorithms for CPSE. In addition, the experimental results also prove the efficiency of DPK-means for CPSE and its improvement compared with DK-means.Secondly, this thesis considers customer requirements as random element, since in most logistics distribution application, customer requirements are uncertain when people scheduling routes. An uncertain routing problem named probabilistic traveling salesman problem (PTSP) is proposed. Compared with nomal classic traveling salesman problem (TSP), PTSP is much more difficult to solve. After problem formulation and modeling, author found the bottleneck of PTSP solving is complex and costly object function computing. Samilar to the neighborhood search idea of TSP, two neighborhood search methods for PTSP is proposed. With derivation of cost change evaluation, the compute complexity of PTSP’s neighborhood search is efficiently decressed from O(n4) to O(n2). Moreover, for common algorithms designing, two approximate evaluations for expected tour length are proposed, and their parameters are analysised with experiments. After discuss the relationship between PTSP solutions and TSP solutions, a new global optimization algorithm named HGSA is proposed. Experimental results indicate that HGSA is more efficient to solve PTSP.Finally, considering the uncertainty of customers and demands in actual logistics distribution, with the capacity restriction of vehicles, an vehicle routing problem with stochastic customers and demands (VRPSCD) is discussed. VRPSCD is much more difficult than classic capacitated vehicle routing problem (CVRP) to solve. After problem formulation and modeling, it is found that the bottleneck to solve VRPSCD is high compute complexition of object value eveluation. Based on neighborhood search idea of CVRP, an approximated evaluation method to compute the change of expected object function value in VRPSCD neighborhood search is proposed. To fit more algorithms designing, sampling approximation for VRPSCD’s expected object value is proposed, and the relationship between sampling scale and approximation precision is discussed with experiments. At last, with different customer requirement probabilistic distributions, VRPSCD solutions and CVRP solution with historic average demands are compared with experiments.更多还原