基于电子商务的物流调度算法研究
发布时间：2019-01-30 21:28
【摘要】：物流作为企业“第三利润源泉”的一部分一直深受企业的重视,而车辆路径问题作为物流管理领域中关注的热点问题,因为它的复杂性和多样性,如何合理地安排车辆和它们的行驶路径以最低成本收送货物,是一个极具有挑战性的问题,自从1959年被提出以来引起了无数国内外学者的研究。随着电子商务的发展,物流在企业中的地位进一步提升,本文从电子商务企业的实际应用出发,对车辆路径问题进行研究。通过研究车辆路径问题(Vehicle Routing Problem,VRP)的一般模型,在对电子商务下的车辆路径问题进行分析的基础上,提出了一种基于客户满意度的多对多的带时间窗的集收送货一体的车辆调度问题(Multi-multi Pickup and Delivery Vehicle Routing Problem with Time WindowsbasedonSatisfaction,MMPDVRPTWS)。本文主要从两方面对车辆路径问题进行了研究:静态车辆调度和动态车辆调度。本文首先分析了 MMPDVRPTWS的静态情况,即在进行配送前所有的顾客需求是已知的,在配送过程中路径信息也不会改变。本文采用两阶段法对这个问题进行了求解,先用一种插入式启发算法将顾客按照其需求和位置信息进行分组,然后用一种混合遗传算法对路径进行优化。通过对遗传算法的研究,发现该算法由于其固有的特点,容易陷入局部收敛,导致局部最优解的出现。本文采用一种局部搜索算法作为遗传算法的变异算子,能够很好地防止局部最优解的出现。最后,通过实验讨论了适应度函数中目标加权值的设置,并在加权值相同的情况下与普通遗传算法的结果比较,本文提出的混合遗传算法在求解方面具有一定的优越性。接着分析了MMPDVRPTWS的动态情况,由于随着时间的推移,在车辆调度过程中会伴随着新的客户请求、客户请求的修改或取消等多种动态事件,同时路径信息的变化也会影响车辆的速度。本文通过模拟一个“工作日”内的客户需求情况,并根据当前的路径信息对未来一段时间内的路径信息做出预判,通过将一个“工作日”分成若干个“时间片”,把一个“时间片”内产生的订单再插入到车辆还未完成的序列中,并用上面提到的混合遗传算法对路径进行优化,通过实验验证了动态调度策略的可行性,并与一种变邻域搜索算法进行对比,结果显示本文提出的算法所求的解具有一定的优越性。
[Abstract]:As a part of the third profit source of enterprises, logistics has always been attached great importance to by enterprises, and the vehicle routing problem is a hot issue in the field of logistics management, because of its complexity and diversity. How to reasonably arrange vehicles and their paths to receive and deliver goods at the lowest cost is a very challenging problem, which has been studied by numerous scholars at home and abroad since 1959. With the development of E-commerce, the status of logistics in enterprises is further improved. This paper studies the vehicle routing problem from the practical application of E-commerce enterprises. By studying the general model of vehicle routing problem (Vehicle Routing Problem,VRP), based on the analysis of the vehicle routing problem under electronic commerce, This paper presents a many-to-many time-window vehicle scheduling problem (Multi-multi Pickup and Delivery Vehicle Routing Problem with Time WindowsbasedonSatisfaction,MMPDVRPTWS) based on customer satisfaction. In this paper, the vehicle routing problem is studied from two aspects: static vehicle scheduling and dynamic vehicle scheduling. This paper first analyzes the static situation of MMPDVRPTWS, that is, all customer needs are known before distribution, and the path information will not change during the distribution process. In this paper, a two-stage method is used to solve the problem. First, a plug-in heuristic algorithm is used to group customers according to their needs and location information, and then a hybrid genetic algorithm is used to optimize the path. Through the study of genetic algorithm, it is found that the algorithm is easy to fall into local convergence because of its inherent characteristics, resulting in the emergence of local optimal solution. In this paper, a local search algorithm is used as the mutation operator of genetic algorithm, which can prevent the occurrence of local optimal solution. Finally, the setting of target weighting value in fitness function is discussed through experiments, and compared with the results of common genetic algorithm under the same weighted value, the hybrid genetic algorithm proposed in this paper has some advantages in solving the problem. Then, the dynamic situation of MMPDVRPTWS is analyzed. As time goes on, there are many dynamic events in the process of vehicle scheduling, such as new customer request, customer request modification or cancellation, etc. At the same time, the change of the path information will also affect the speed of the vehicle. In this paper, we simulate the customer demand in a "working day" and predict the path information in the future according to the current path information, and divide a "working day" into several "time slices". The order generated in a "time slice" is inserted into the unfinished vehicle sequence, and the hybrid genetic algorithm mentioned above is used to optimize the path. The feasibility of the dynamic scheduling strategy is verified by experiments. Compared with a variable neighborhood search algorithm, the results show that the solution proposed in this paper has some advantages.
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：F724.6;TP18
本文编号：2418543
[Abstract]:As a part of the third profit source of enterprises, logistics has always been attached great importance to by enterprises, and the vehicle routing problem is a hot issue in the field of logistics management, because of its complexity and diversity. How to reasonably arrange vehicles and their paths to receive and deliver goods at the lowest cost is a very challenging problem, which has been studied by numerous scholars at home and abroad since 1959. With the development of E-commerce, the status of logistics in enterprises is further improved. This paper studies the vehicle routing problem from the practical application of E-commerce enterprises. By studying the general model of vehicle routing problem (Vehicle Routing Problem,VRP), based on the analysis of the vehicle routing problem under electronic commerce, This paper presents a many-to-many time-window vehicle scheduling problem (Multi-multi Pickup and Delivery Vehicle Routing Problem with Time WindowsbasedonSatisfaction,MMPDVRPTWS) based on customer satisfaction. In this paper, the vehicle routing problem is studied from two aspects: static vehicle scheduling and dynamic vehicle scheduling. This paper first analyzes the static situation of MMPDVRPTWS, that is, all customer needs are known before distribution, and the path information will not change during the distribution process. In this paper, a two-stage method is used to solve the problem. First, a plug-in heuristic algorithm is used to group customers according to their needs and location information, and then a hybrid genetic algorithm is used to optimize the path. Through the study of genetic algorithm, it is found that the algorithm is easy to fall into local convergence because of its inherent characteristics, resulting in the emergence of local optimal solution. In this paper, a local search algorithm is used as the mutation operator of genetic algorithm, which can prevent the occurrence of local optimal solution. Finally, the setting of target weighting value in fitness function is discussed through experiments, and compared with the results of common genetic algorithm under the same weighted value, the hybrid genetic algorithm proposed in this paper has some advantages in solving the problem. Then, the dynamic situation of MMPDVRPTWS is analyzed. As time goes on, there are many dynamic events in the process of vehicle scheduling, such as new customer request, customer request modification or cancellation, etc. At the same time, the change of the path information will also affect the speed of the vehicle. In this paper, we simulate the customer demand in a "working day" and predict the path information in the future according to the current path information, and divide a "working day" into several "time slices". The order generated in a "time slice" is inserted into the unfinished vehicle sequence, and the hybrid genetic algorithm mentioned above is used to optimize the path. The feasibility of the dynamic scheduling strategy is verified by experiments. Compared with a variable neighborhood search algorithm, the results show that the solution proposed in this paper has some advantages.
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：F724.6;TP18
【参考文献】
相关期刊论文 前4条
1 王仁民;闭应洲;刘阿宁;李杰;;改进变邻域搜索算法求解动态车辆路径问题[J];计算机工程与应用;2014年02期
2 杨烨;李霞;;具有可调软时间窗的动态车辆调度问题模型及算法[J];物流技术;2013年21期
3 吕雄伟;赵达;李军;;基于多态蚁群算法的多目标邮政物流车辆路径问题研究[J];计算机应用研究;2009年06期
4 谭国真,张永强,高文;考虑网络流量的最优路径求解模型和算法[J];小型微型计算机系统;2003年11期
相关博士学位论文 前1条
1 王晓博;电子商务下物流配送系统优化模型和算法研究[D];哈尔滨工业大学;2008年
相关硕士学位论文 前1条
1 胡夏云;基于蚁群算法的动态车辆调度问题的研究[D];广东工业大学;2013年
，本文编号：2418543
本文链接：https://www.wllwen.com/jingjilunwen/dianzishangwulunwen/2418543.html
