多阶段绿色车辆路径问题的算法设计与优化

发布时间：2019-03-29 10:48

【摘要】：面对规模庞大的在线交易系统以及巨大的竞争压力,物流公司需要不断提升自身的服务质量以及降低成本。车辆路径问题为物流公司规划合理的配送路线,对降低物流公司的运输成本和提高其服务质量都具有很重要的意义。本文重点研究了多阶段车辆路径问题和绿色车辆路径问题。针对多阶段车辆路径问题,本文设计一种混合式的启发式算法,能够对超过两阶段的大规模车辆路径问题进行求解。为了提高搜索解的质量,本文提出一种负载平衡策略,使得解的搜索过程可以快速从负载不平衡状态变迁到平衡状态。该算法把多阶段车辆路径问题分解成不同的子问题,利用最后一个阶段的独立性,并结合并行优化的思想,本文设计混合策略模拟退火算法来解决最后阶段的车辆路径问题,并采用线性规划对中间阶段进行精确求解。实验结果表明,在66组基准数据集上,目标值与最优解平均偏差2.4%,其中56.06%的数据集能求出最优解;与现有的精确算法相比,与其最终解平均偏差2.8%;相比现有的精确算法,该算法能够处理更大规模的问题以及任意阶段数量的车辆路径问题。在以能耗为优化目标的绿色车辆路径问题中,本文提出并行混合策略模拟退火算法。本文从实际的角度出发,选择了车辆负载和行驶距离作为影响车辆能耗速率的关键因素,并建立能耗速率与车辆负载以及车辆行驶的距离之间关系。在此基础上,建立绿色车辆路径问题的模型。利用在多阶段车辆路径的研究成果,负载平衡策略被有效的运用到解决绿色车辆路径问题的算法设计中。在同样迭代次数的条件下,并行计算有效的扩大解的搜索范围。实验结果表明,相比优化前的算法,目标值平均减少了42.49%,方差平均减少了86.41%。
[Abstract]:Facing large-scale online trading system and huge competitive pressure, logistics companies need to continuously improve their service quality and reduce costs. The vehicle routing problem is a reasonable distribution route for logistics companies. It is of great significance to reduce the transportation cost and improve the service quality of logistics companies. This paper focuses on the multi-stage vehicle routing problem and the green vehicle routing problem. For the multi-stage vehicle routing problem, a hybrid heuristic algorithm is designed in this paper, which can solve the large-scale vehicle routing problem with more than two stages. In order to improve the quality of the search solution, a load balancing strategy is proposed in this paper, so that the search process of the solution can quickly change from the load imbalance state to the equilibrium state. The algorithm decomposes the multi-stage vehicle routing problem into different sub-problems. Using the independence of the last stage and the idea of parallel optimization, this paper designs a hybrid strategy simulated annealing algorithm to solve the vehicle routing problem in the final stage. Linear programming is used to solve the intermediate stage accurately. The experimental results show that the average deviation between the target value and the optimal solution is 2.4% on 66 sets of benchmark data sets, and 56.06% of the data sets can find the optimal solution, and the average deviation between the target value and the optimal solution is 2.8%, compared with the existing accurate algorithm, and the average deviation between the target value and the optimal solution is 2.8%. Compared with the existing accurate algorithms, the proposed algorithm can deal with large-scale problems and vehicle routing problems with arbitrary number of phases. In this paper, a parallel hybrid strategy simulated annealing algorithm is proposed for the green vehicle routing problem with energy consumption as the optimization objective. In this paper, the vehicle load and driving distance are selected as the key factors affecting the energy consumption rate from the practical point of view, and the relationship between the energy consumption rate and the vehicle load as well as the vehicle driving distance is established. On this basis, the model of green vehicle routing problem is established. Using the research results of multi-stage vehicle routing, the load balancing strategy is effectively applied to the algorithm design of solving the green vehicle routing problem. Under the condition of the same number of iterations, parallel computing extends the search range of efficient solutions. The experimental results show that the target value and variance decrease by 42.49% and 86.41%, respectively, compared with the algorithm before optimization.
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP301.6

【参考文献】