【作者】 彭碧涛；

【导师】 周永务；

【作者基本信息】 华南理工大学 ， 工业工程与管理工程， 2013， 博士

【摘要】 在现代社会经济运行中，物流占据越来越重要的地位，如何有效的降低物流成本，提高物流配送效率，正成为企业面临的重要经营管理问题。高效的运作，不仅有利于企业效益的改善、用户满意度的提高，而且对于整个生态环境的改善、低碳社会的形成，也起着至关重要的作用。物流配送车辆路径问题作为物流运作管理的核心问题之一，对于提高物流效率非常关键，受到了广泛的关注，该问题经过几十年的研究，也取得了丰富的研究成果。但是，目前的研究很少考虑货物的装载约束，然而在实际配送过程中，配送的货物存在长、宽和高的三维外形约束、并且货物在配送过程中要满足“先进后出”的原则、货物需要底面支撑、以及配送过程中需要考虑装载的稳定性等，因此不考虑货物装载约束下求得的最优解可能在现实配送中根本无法成功操作。本文研究了考虑货物装载的车辆路径问题，即三维装载约束下车辆路径问题，通过对问题进行描述、建模，综合利用基本启发式和现代启发式算法等工具，对基本的三维装载约束下车辆路径问题和扩展的几类重要三维装载约束下车辆路径问题进行了系统的研究，主要研究内容和创新成果如下：1.给出了三维装载约束下车辆路径问题的描述和数学模型，在此基础上设计了货物的装载算法、三维空间处理算法、客户的选择算法，结合禁忌搜索优化算法，实现了多种混合式禁忌搜索算法。通过对已有测试集进行实验，与现有算法结果相比较，验证了算法的有效性；同时构建了新的测试数据集，分析和验证了算法的特征。2.研究了带时间窗的三维装载约束下车辆路径问题。在基本的三维装载约束下车辆路径问题中引入了时间窗约束。构建了带时间窗的三维装载约束下车辆路径问题的数学模型；在此基础上，利用不同的时间窗选择算法、启发式算法和禁忌搜索算法求解上述问题；最后设计了问题的测试数据集，比较和分析不同的求解算法的性能。3.研究了动态交通状况下三维装载约束下车辆路径问题。在带时间窗的考虑三维装载约束下车辆路径问题的基础上，引入新的约束条件：动态旅行时间。通过引入动态交通模型，构成了一类新的三维装载约束下车辆路径问题-----时变的三维装载约束下车辆路径问题。首先对问题进行描述，建立了问题的数学模型；然后提出了问题的启发式求解算法和基于禁忌搜索的智能求解算法；最后设计测试数据集，通过实验检验算法的有效性；同时对比分析了在不同算法参数、不同支撑面积下的计算结果，以及数据测试的时间效率。4.研究多车型的三维装载约束下车辆路径问题。在实际的物流配送过程中，企业的配送车队往往是由具有多种车型、多种体积、多种载重量和使用成本的一组异质的车辆所组成。通过设计车辆车型的选择算法，有效实现了在多车型情况下，求解三维装载约束下车辆路径问题；最后设计测试数据集，通过实验检验算法的有效性；同时对比分析了在不同算法参数、不同支撑面积下的计算结果，以及数据测试的时间效率。本文综合运用运筹学和智能优化等理论和方法，对几类三维装载约束下车辆路径问题模型及其算法进行了系统的研究。本文的研究扩展了车辆路径问题的研究空间，丰富了车辆路径问题的理论体系，同时为企业的物流配送、车辆调度提供了借鉴和参考。更多还原

【Abstract】 In the modern social economy, logistics becomes more and more important. How toeffectively lower logistics cost, improve the efficiency of logistics distribution, is becoming akey and important problem that the companies must face. Efficient operation is not onlybeneficial to the improvement of the enterprise efficiency and customer satisfaction, but alsoplay an important role for the formation of the whole ecological environment and low carbonsociety. Logistics distribution vehicle routing problem as one of the core problems in logisticsmanagement, is crucial for improving the efficiency of logistics, and has received thewidespread attention. After decades of research, the problem has been abundant researchresults. But past research seldom consider the goods loading constraints. In fact, during theprocess of actual delivery, due to the three dimensional shape constraints, length, width andheight, and the principle of “First In Late Out”, minimumal bottom support area, and thestability of distribution need to be considered. The optimal resuts can be infeasible withoutconsidering the loading constraints.The paper research the vehicle routing problem with three dimensional loadingconstraints. By descripting and modeling problems, comprehensive utilization of theheuristics and modern heuristic algorithms, the basic vehicle routing problem withthree-dimension loading costrint and several important extend problems are researched. Themain research results are list as follows:1. We present the description and mathematical model of vehicle routing problem withthree dimensional loading constraints. And then, we devised loading algorithms of goods,three-dimension space process algorithms, and customer selection algorithms. Next, wepropose the hybrid tabu search algorithms. At last, we build problem test data sets, andsystematically analyze and dicuss the performance of the algorithm. The results show thathybrid tabu search algorithm can get better solutions comparing to current algorithms onseveral test data.2. We research vehicle routing problem with three dimensions loading constraints and time windows. On the basis of basic vehicle routing problem with three dimension loadingconstraints, the time windows constraint is introduced. Firstly, we present the description andmathematical model. And then, using different time windows selection algorithms, differentheuristic algorithms and tabu seach algorithm, the problem is solved. Fially, we build problemtest data sets, and systematically analyze and dicuss the performance of the algorithm.3. We research time dependent vehicle routing problem with three dimensional loadingconstraints. On the basis of vehicle routing problem with three dimensional loadingconstraints and time windows, we introduce new constraint, dynamic travel time length, anddesign the segemented time function to describle the speed. Firstly, we give the descriptionand mathematical models of the problem. And then, we present heuristic algorithms andintelligent algorithms based on tabu search. Finally, we build problem test data sets, andsystematically analyze and dicuss the performance of the algorithm.4. We research heterogeneous fleet vehicle routing problem with three dimensionalloading constraints. Considering the actual logistics distribution process, the enterprises’distribution teams are usually composed of several vhelcie types, different sizes, differentloads and different deposit costs. Through designing vehicle model selection algorithms, weeffectively solve the heterogeneous fleet vehicle routing problem with three dimensionalloading constraints. Finally, we build problem test data sets, and systematically analyze anddicuss the performance of the algorithm.This paper systematically research several vehicle routing problems with threedimensional loading constraints, integrated using the theories and methods of operationresearch and intelligent optimization. This paper extends the research fields of vehicle routingproblem, enrichs the theoretical system of vehicle routing problem, and provides reference forthe enterprise logistics distribution and vehicle scheduling at the same time.更多还原