大规模车辆路径问题的优化方法研究

发布时间：2019-05-20 06:44

【摘要】：配送环节在大规模的物流网络系统中有着重要的地位，根据国外权威数据显示，超过一半的物流成本来自于配送环节，尤其是在大规模物流配送网络中。而随着交通线路的日趋复杂以及更高的客户响应需求，对科学规划路径也提出了很高的要求。因此，大规模车辆路径问题的优化研究成为合理降低物流成本的关键。本文针对大规模的车辆路径问题，考虑客户的静态和动态需求来研究车辆路径问题。主要包括两个方面：一是在考虑客户静态需求基础上，根据客户需求是否可以分割配送来研究车辆路径问题的优化方法，并基于启发式方法求解了需求允许分割下的车辆路径问题；二是考虑客户随机需求的基础上，应用马尔科夫过程和启发式算法来给出一对车辆实时动态路径规划的策略。本文的主要工作内容和创新点如下：首先，针对大规模配送系统中的客户需求进行客户聚类子问题的研究，以便在每个聚类集上的车辆配送问题研究。提出了一种新的基于人工免疫系统的聚类算法。为了得到较好地初始解，引入自组织映射方法来生成初始抗体群；在迭代聚类算法过程中，设计了一系列优化和控制进化的策略，如聚类满意度、种群规模的阈值、学习率、聚类监测点和聚类评价指标等。这些策略可以使得聚类参数阈值实现自适应量化来减少用户的主观因素影响；并通过策略的综合作用，来同时得到一种取得局部聚类和全局聚类的方法。最后，仿真实验和分析比较说明了本文方法的有效性。其次，，考虑了静态客户需求下的大规模车辆路径问题。在前一部分的研究基础上，提出了一个基于人工免疫系统(AIS)的启发式算法来求解车辆路径问题。通过引入一种新的路径覆盖方法，设计了一种新的编码和算法结构。配送路径通过先聚类后路径的方法产生，并通过网络更新机制来产生初始抗体，以机会均等下的双向学习来扩增抗体。进一步，发展了同心圆建造策略来识别不同客户类，以便形成更多的配送路径以供选择；而提出的两种精英策略(AB)和(R)来去掉较差的抗体以保持配送路径库中路径的多样性。然后，再通过求解更新后路径库中的集合覆盖模型，使得VRP解随着不断增加的路径选择而逐步实现优化过程。最后，还设计了路径合并策略来进一步增加更优的路径。这样，最终的VRP最优解通过在最终路径库中选择成本最优的路径来得到。仿真实验分析说明了所提算法的有效性。第三，在考虑客户静态需求下，针对一类客户需求允许分割的集成装载问题进行研究。分析该问题的特点，建立了一个双层规划模型来进行描述。为求解该问题，提出了一种双层的聚类算法，即把客户需求进行子聚类的算法和针对每个聚类的客户需求，再进行车辆配载聚类的算法。算法综合应用了人工免疫系统、启发式规则和伪系统聚类算法等，逐步迭代得出整个系统的最优解。最后，设计了仿真数值实验，并进一步与现有文献的研究成果进行了比较分析，得出了所提算法性能的优异性。最后，对于随机客户需求下的车辆路径问题，提出了一个成对合作重新规划路径的策略问题。该策略可以实现配送的一对车辆相互配合，通过两者之间触发有效的通讯，基于实时的客户需求更新车辆指派，来实现配送中路径重优化的动态规划效果。本章提出了一个双层马尔科夫过程来描述此策略，同时设计了启发式算法来根据实时信息动态改变车辆的访问顺序以及车辆的指派方案。仿真数值实验同样证明：本章方法与最新的文献研究成果相比较，所提算法显示出了较好的效果，有着20%-30%的成本节约。
[Abstract]:The distribution link plays an important role in the large-scale logistics network system. According to the foreign authoritative data, more than half of the logistics cost is from the distribution link, especially in the large-scale logistics distribution network. Along with the increasing complexity of the traffic line and the higher customer response, the scientific planning path has also made a very high request. Therefore, the optimization of the large-scale vehicle routing problem becomes the key to the reasonable reduction of the logistics cost. In view of the problem of large-scale vehicle routing, this paper studies the vehicle path by considering the customer's static and dynamic demand The paper mainly includes two aspects: one is to study the optimization method of the vehicle path problem based on the customer's static demand and whether the customer's demand can be divided and distributed, and the method is based on the heuristic method to solve the problem of the vehicle's path. The second is to use the Markov process and the heuristic algorithm to give the idea of the real-time dynamic path planning of a pair of vehicles on the basis of the stochastic demand of the customers. The main contents and innovation points of this paper are as follows: Next: First, a study of the customer's sub-questions for the customer's needs in a large-scale distribution system is carried out in order to ask for the distribution of the vehicles on each cluster In this paper, a new model of artificial immune system based on artificial immune system is proposed. In order to get a better initial solution, the self-organizing mapping method is introduced to generate the initial antibody population. In the iterative clustering algorithm, a series of strategies to optimize and control the evolution, such as the cluster satisfaction, the threshold of population size, the learning rate, the cluster monitoring points and the clustering evaluation, are designed. The strategy can make the clustering parameter threshold realize the self-adaptive quantization to reduce the influence of the user's subjective factors, and simultaneously obtain a local clustering and global clustering through the comprehensive action of the strategy. Finally, the simulation experiment and the analysis show the method in this paper. Effectiveness. Second, a large-scale vehicle under static customer needs is considered In this paper, a heuristic algorithm based on artificial immune system (AIS) is proposed to solve the vehicle routing problem. A new method of path coverage is introduced to design a new code. and a network updating mechanism is adopted to generate the initial antibody, so that the two-way learning under the equal opportunity Further, a concentric construction strategy is developed to identify different customer classes in order to form more distribution paths for selection; the proposed two elite strategies (AB) and (R) are used to remove the poor antibodies in order to maintain the distribution path library middle Diversity of the path. Then, by solving the set overlay model in the updated path library, the VRP solution is gradually augmented with the increasing path selection the process is now optimized. Finally, a path merge policy is also designed to further increase A better path. In this way, the final VRP best solution is optimized by selecting the cost in the final path library The path is obtained. The simulation results show that the proposed method The effectiveness of the method. Third, under consideration of the customer's static demand, an integrated package that allows segmentation for a class of customer needs The problem is studied. The characteristics of the problem are analyzed and a two-layer plan is established. The model is described. In order to solve the problem, a double-layer clustering algorithm is proposed, that is, the algorithm of sub-clustering and the customer demand for each cluster are carried out, and then the vehicle In this paper, the artificial immune system, the heuristic rule and the pseudo-system clustering algorithm are applied to the algorithm. In the end, the simulation numerical experiment is designed and compared with the research results of the existing literature, and the calculated results are obtained. In the end, a pair of cooperation is proposed to solve the problem of vehicle routing under the demand of the random customer. the strategy of the planning path is that a pair of vehicles distributed can be matched with each other, an effective communication is triggered between the two vehicles, the vehicle assignment is updated based on the real-time client demand, and the route weight in the distribution is realized In this chapter, a double-layer Markov process is proposed to describe this strategy, and a heuristic algorithm is designed to dynamically change the access sequence of the vehicle according to the real-time information The simulation results also show that the method of this chapter is compared with the latest literature research results, and the proposed algorithm shows a good effect, with 20%.
【学位授予单位】：天津大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：U116.2;F252

【相似文献】