扫描法在VRP问题中的应用研究
发布时间：2019-04-27 10:49
【摘要】：随着物流业的迅速发展及信息一体化的介入,配送环节在整个物流系统的竞争中占据着决定性的作用。运输费用占据着物流费用的很大比例,设计合理有效的配送方案是降低物流费用的关键点[1]。对车辆科学的使用和调度可以缩短行驶路径、节约物流作业的时间、降低物流运作的成本,同时提高物流系统的管理效率、增强客户对物流环节的满意度[2]。因此,车辆路径问题(Vehicle Routing Problem,VRP)自从1959年被提出以来,一直成为热点研究领域[3]。目前在大规模VRP求解上还有很多问题值得探讨,为了使算法具有简单性有效性,本文以大规模单车场VRP和大规模多车场VRP为两类研究对象,针对在解决此类问题时算法较复杂的问题,对扫描法在VRP中的应用和改进展开研究。主要工作如下:1.为了解决包含大规模需求点的VRP中多个配送中心的选址问题,本文基于优化的思想,将扫描法应用在选址问题中提出了二次重心法,建立了一种数学模型,并用算例进行算法的仿真,验证了本文算法的有效性。2.针对大规模单车场和大规模多车场VRP中需求点覆盖区域过大的问题,本文以降低问题规模为阶段性目标,同时加入“需求点分布”这一考虑因素,设计了一种划分区域的环形分区法,并根据这种分区思路给出几组具体参数的举例。3.针对单车场VRP问题,本文结合环形分区法,对扫描法在单车场VRP中的应用进行了改进,提出了一种新算法,并用算例进行算法的仿真,对比了新算法与传统扫描法的路程结果,验证了本文算法的有效性。4.针对多车场VRP问题,建立了一种数学模型,分别针对非开放型VRP和开放型VRP问题设计了两种扫描法应用在此类问题中的两阶段算法,并对比了新算法与传统两阶段算法的路程结果,验证了本文算法的有效性。
[Abstract]:With the rapid development of logistics industry and the involvement of information integration, distribution plays a decisive role in the competition of the whole logistics system. Transportation cost accounts for a large proportion of logistics costs. Designing a reasonable and effective distribution scheme is the key point to reduce logistics costs [1]. The use and scheduling of vehicle science can shorten the driving path, save the time of logistics operation, reduce the cost of logistics operation, at the same time improve the management efficiency of logistics system and enhance the customer's satisfaction with logistics [2]. Therefore, vehicle routing problem (Vehicle Routing Problem,VRP) has been a hot research field since it was proposed in 1959. At present, there are still many problems to be discussed in solving large-scale VRP. In order to make the algorithm simple and effective, this paper takes large-scale single-yard VRP and large-scale multi-depot VRP as two kinds of research objects. In view of the complexity of the algorithm in solving this problem, the application and improvement of scanning method in VRP are studied. The main work is as follows: 1. In order to solve the location problem of multiple distribution centers in VRP with large-scale demand points, based on the idea of optimization, this paper puts forward the secondary center of gravity method and establishes a mathematical model based on the scan method, which is applied to the location problem. A numerical example is used to simulate the algorithm, and the validity of the proposed algorithm is verified. 2. In order to solve the problem of large coverage area of demand point in large-scale single-depot and large-scale multi-depot VRP, this paper takes reducing the problem scale as the stage goal and adding the consideration of "demand point distribution" at the same time. In this paper, a circular partition method for dividing regions is designed, and some examples of some specific parameters are given according to this idea. In order to solve the VRP problem of single vehicle yard, this paper improves the application of scanning method in VRP of single vehicle yard, and presents a new algorithm, and simulates the algorithm with an example, and compares the distance result between the new algorithm and the traditional scanning method, and makes a comparison between the new algorithm and the traditional scanning method, and makes a comparison between the new algorithm and the traditional scanning method. The validity of the proposed algorithm is verified. 4. In this paper, a mathematical model for the multi-depot VRP problem is established, and two-stage algorithms for the non-open VRP problem and the open-type VRP problem are designed, respectively, which are applied to this kind of problem. The results of the new algorithm and the traditional two-stage algorithm are compared to verify the effectiveness of the proposed algorithm.
【学位授予单位】：延安大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：F259.2;TP301.6
本文编号：2466915
[Abstract]:With the rapid development of logistics industry and the involvement of information integration, distribution plays a decisive role in the competition of the whole logistics system. Transportation cost accounts for a large proportion of logistics costs. Designing a reasonable and effective distribution scheme is the key point to reduce logistics costs [1]. The use and scheduling of vehicle science can shorten the driving path, save the time of logistics operation, reduce the cost of logistics operation, at the same time improve the management efficiency of logistics system and enhance the customer's satisfaction with logistics [2]. Therefore, vehicle routing problem (Vehicle Routing Problem,VRP) has been a hot research field since it was proposed in 1959. At present, there are still many problems to be discussed in solving large-scale VRP. In order to make the algorithm simple and effective, this paper takes large-scale single-yard VRP and large-scale multi-depot VRP as two kinds of research objects. In view of the complexity of the algorithm in solving this problem, the application and improvement of scanning method in VRP are studied. The main work is as follows: 1. In order to solve the location problem of multiple distribution centers in VRP with large-scale demand points, based on the idea of optimization, this paper puts forward the secondary center of gravity method and establishes a mathematical model based on the scan method, which is applied to the location problem. A numerical example is used to simulate the algorithm, and the validity of the proposed algorithm is verified. 2. In order to solve the problem of large coverage area of demand point in large-scale single-depot and large-scale multi-depot VRP, this paper takes reducing the problem scale as the stage goal and adding the consideration of "demand point distribution" at the same time. In this paper, a circular partition method for dividing regions is designed, and some examples of some specific parameters are given according to this idea. In order to solve the VRP problem of single vehicle yard, this paper improves the application of scanning method in VRP of single vehicle yard, and presents a new algorithm, and simulates the algorithm with an example, and compares the distance result between the new algorithm and the traditional scanning method, and makes a comparison between the new algorithm and the traditional scanning method, and makes a comparison between the new algorithm and the traditional scanning method. The validity of the proposed algorithm is verified. 4. In this paper, a mathematical model for the multi-depot VRP problem is established, and two-stage algorithms for the non-open VRP problem and the open-type VRP problem are designed, respectively, which are applied to this kind of problem. The results of the new algorithm and the traditional two-stage algorithm are compared to verify the effectiveness of the proposed algorithm.
【学位授予单位】：延安大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：F259.2;TP301.6
【参考文献】
相关期刊论文 前3条
1 严俊梅;冯祈善;;作业成本法在物流成本管理中的应用[J];湖南医科大学学报(社会科学版);2008年04期
2 张大威;;物流配送中心选址方法研究[J];现代商贸工业;2010年16期
3 於世为;郭海湘;诸克军;;基于GA-TS的开放式车辆路径优化算法及应用[J];系统管理学报;2012年02期
相关硕士学位论文 前2条
1 石华t@;改进的蚁群算法在实际VRP中的应用研究[D];山东大学;2012年
2 孙世权;多配送中心车辆路径优化问题的研究[D];西安电子科技大学;2012年
，本文编号：2466915
本文链接：https://www.wllwen.com/guanlilunwen/wuliuguanlilunwen/2466915.html
