Model And Algorithms For The Integrated Single Machine Scheduling And Vehicle Routing Problem

With the continuous development of global economic integration, the competition in supply chains becomes more and more fierce, and the collaborative relationship between the enterprises in internal supply chain has becoming a key factor of supply chain management. More and more enterprises realize that supply chain management is not only to reduce costs, but also to improve the customer satisfaction which is more important. As two important links in the manufacturing supply chain, production and transportation have receiving more and more attention from both enterprises and academics. Integrated scheduling of production and transportation can effectively improve the customer response capabilities of the enterprise, so as to enhance the overall competitiveness of the supply chain. This dissertation extends traditional vehicle routing problems (VRP). It studies the integrated single machine scheduling and vehicle routing problem in the Make-to-order enterprises based on the detailed scheduling level. The research results of the integrated problem can be concluded as follows:(1) The mathematical model of the integrated production and transportation is established, based on that the completion time of orders in production phase are given. The objective is to minimize the total route time including vehicle release time and vehicle travel time. In the enterprise practice, the goods are not all available at the depot at the start of the distribution and vehicles cannot depart before the available time of each onboard order. This problem is called vehicle routing problem with release dates. A tabu search algorithm is proposed to solve the problem. In order to evaluate the performance of the proposed tabu search algorithm, a Lagrangian relaxation algorithm is proposed to exploit the lower bound of the problem. Also, another lower bound based on the optimal solution of the benchmark instances is derived. In computational experiments, the tabu search algorithm and Lagrangian relaxation algorithm are proved to be useful. What's more, the tabu search algorithm can effectively solve problem in real word, comparing with the operating rules applied in practice.(2) The mathematical model of the integrated production and transportation is established, based on that the completion time of orders in production phase are unknown. The objective is to determine the decisions about production scheduling, transportation batching and vehicle routing, to minimize the maximum order delivery time (makespan). In general, short response time can be achieved by synchronization between production and outbound transportation. An optimal property for production scheduling and transportation batching is first proposed. Based on the property, backward and forward batching methods are developed, which are embedded into an improved genetic algorithm. The genetic algorithm solves the problem from an integrated perspective. For comparison purpose, a two-stage algorithm is developed, which decomposes the overall problem. Then, sub-problems are solved successively. The experiments show that the improved genetic algorithm can provide high quality solutions, comparing with the two-stage algorithm and a published genetic algorithm for related problem.(3) The mathematical model of the integrated production and transportation is established, based on that the completion time of orders in production phase are unknown. The objective is to determine the decisions about production scheduling, transportation batching and vehicle routing, to minimize the sum of arrival times at customers. Compared with above problems, this problem pays more attention on the customer service level by effective collaborative production and transportation from another perspective. The priority is given to the satisfaction of all customers, not the classical route time. A variable neighborhood search heuristic is proposed to solve the problem. In order to reduce the search space, an optimal property for production scheduling and transportation batching is also proposed. Based on the property, a feasible solution is developed, as the initial solution of a variable neighborhood search heuristic. The variable neighborhood search heuristic designs eight neighborhoods, from the perspective of the intensification and diversification. A tabu search is used to improve the neighbors in each neighborhood as a local search approach. To evluate the effective of variable neighborhood search heuristic, a decompose method is proposed to provide the lower bound of the problem. A large amount of experiments on small-scale and large-scale data sets are carried out. The results show that variable neighborhood search heuristic is able to obtain an optimal or near optimal solution in reasonable time for the formulated problem, comparing with the CPLEX software and two heuristic algorithms for related problems.