单机器生产与车辆路径协同调度问题建模与算法研究

发布时间：2018-03-08 23:25

本文选题：生产　切入点：运输　出处：《华中科技大学》2016年博士论文　论文类型：学位论文

【摘要】：随着全球经济一体化的不断发展,供应链之间的竞争越来越激烈,供应链上合作企业之间的协同关系已渐渐成为供应链管理成败的关键因素。生产与运输作为制造业供应链中两个重要环节,受到了国内外众多企业及学术界的关注。生产与运输环节的协同调度可以有效提高企业的客户响应能力,从而增强供应链的整体竞争力。本论文对传统的车辆路径问题(Vehicle Routing Problem, VRP)问题进行拓展,从运作层面出发,研究了在面向订单制造的企业中单机器生产与车辆路径协同调度问题,主要研究成果总结如下：(1)建立了给定订单生产完成时间的车辆路径问题的数学模型,目标为最小化所有路径完成时间之和,其包括车辆在仓库的等待时间与车辆的运输时间之和。在企业实际中,订单需先生产再运输,车辆必须在仓库等待其运载的所有订单生产完毕才能出发,该问题可以被称为具有订单可得时间的车辆路径问题。首先设计一种禁忌搜索算法获取优化解,然后基于拉格朗日松弛算法,应用动态规划方法求得该问题的下界,并基于经典算例的最优解提出了另一种求解下界的算法与拉格朗日松弛算法相比较。在实验部分,通过算例验证了该禁忌搜索算法能够获得较优的解,且拉格朗日松弛算法能够提供较好的下界。将该禁忌搜索算法与企业实际操作方法进行比较,结果证明禁忌搜索算法优于企业现行操作方法。(2)建立了未给定订单生产完成时间的生产与运输协同调度问题的数学模型,目标为最小化完工时间。在该问题中,生产阶段需要对订单排序,运输阶段需要对路径排序,希冀通过生产与运输环节的有效协同提高企业的运行效率及客户服务水平。针对该问题,首先提出一个最优解性质,并在该性质的基础上提出两种订单分批算法。再从整体与分解的角度,提出一种混合遗传算法与一种二阶段算法分别对该问题进行求解。最后通过算例证明混合遗传算法优于二阶段算法及相关文献中的一种遗传算法,且能够在短时间内获得最优或近似最优的解决方案。(3)建立了未给定订单生产完成时间的生产与运输协同调度问题的数学模型,目标为最小化所有订单的交付时间之和。与前面两个问题相比,该问题通过生产与运输环节的有效协同更进一步地关注了客户服务水平的优化,目的是最小化所有客户接收订单的时间之和,而不仅仅是优化通常的路径时间。针对该问题设计一种基于邻域解的变邻域算法,首先提出一个最优解性质,并在该性质的基础上构造初始解。再从集中与分散的角度提出八种邻域结构,并将禁忌算法作为局部搜索算法用于各邻域结构的探索中。为衡量变邻域算法的效果,提出一种分解算法计算原问题的下界。最后通过构造小规模和大规模算例,将变邻域算法与分解算法、CPLEX软件及已有文献的两种启发式算法相比较,实验结果证明该变邻域算法能获得最优或近似最优的解决方案,且优于已有的两种启发式算法。
[Abstract]:With the continuous development of global economic integration, the competition between the supply chain is more and more intense, collaborative relationships between supply chain partners has gradually become a key factor in the success of supply chain management. The production and transportation as the two important part of the manufacturing supply chain, has attracted much attention of many enterprises and academic circles at home and abroad together. The scheduling of production and transportation links can effectively improve customer response capabilities, thereby enhancing the overall competitiveness of the supply chain. The vehicle routing problem of the traditional paper (Vehicle Routing Problem, VRP) in the development, starting from the operational level, in the study of the collaborative scheduling problem for single machine production and vehicle routing orders made in the enterprise, the main research results are summarized as follows: (1) established a mathematical model of a given order to complete the vehicle routing problem with time. The objective is to minimize the The path completion time and comprises a vehicle in and waiting time and vehicle transportation time of warehouse. In practice, orders for the first production and transport, the vehicle must wait for the delivery of all orders in the warehouse to finish the production of the problem, can be called the vehicle routing problem with time order the first design a tabu search algorithm to obtain the optimal solution, and then based on Lagrange relaxation algorithm, using dynamic programming method to obtain the lower bound of the problem, and based on the classic example of the optimal solution phase comparison algorithm and Lagrange relaxation algorithm for solving the lower bound of another. In the experimental part, the example shows that this taboo the search algorithm can get a better solution, and Lagrange relaxation algorithm can provide better bounds. The tabu search algorithm and the actual operation method, the results of The tabu search algorithm is better than the existing methods of operation enterprises. (2) established a mathematical model of complete production and production orders are not given the transportation time scheduling problem, the goal is to minimize the makespan. In this problem, the production stage need to order scheduling, transportation stage needs the path of sorting, through production and transportation to improve the operation efficiency of enterprises and the level of customer service collaboration. To solve this problem, first proposed the properties of an optimal solution, and puts forward two kinds of order batching algorithm based on the nature. And then from the whole decomposition point of view, this paper proposes a hybrid genetic algorithm and a two phase algorithm were used to solve this at last it is proved that a hybrid genetic algorithm is better than the two stage of the algorithm and related literature, and can be solved in a short period of time to obtain optimal or approximate optimal . (3) established a mathematical model of complete production and production orders are not given the transportation time scheduling problem, the objective is to minimize the time and delivery of all orders. Compared with the previous two questions, the problem through effective collaborative production and transport links further attention to the optimization of customer service level, purpose all customers receive the order is to minimize the sum of the time, but is not only the optimal path of the usual time. Aiming at the problems in the design of a variable neighborhood algorithm based on neighborhood solution, first proposed the properties of an optimal solution, and structure based on the nature of the initial solution. Then from the angle of centralization and decentralization of the proposed eight kinds of neighborhood the structure, and the tabu search algorithm for local search algorithm to explore the neighborhood structure. In order to measure the variable neighborhood algorithm, this paper proposes a method to calculate the original problem decomposition algorithm. Through the lower bound Structure of small scale and large scale examples, the algorithm with variable neighborhood decomposition algorithm, comparing two heuristic algorithms of CPLEX software and the existing literature, experimental results show that the solution variable neighborhood algorithm can find the optimal or near optimal, and outperforms the existing two heuristic algorithms.

【学位授予单位】：华中科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TB498;F273

【相似文献】