Research On Models And Algorithms Of Distributive Line Division And Single Routing Problem

At present, the end distribution of logistics and distribution center mainly takes the centralized and unified way to deliver goods. This delivery mode must consider many factors integrally, such as client demands, the working capability of logistics and distribution center, road hustle degree, street changing, etc, which influence on distribution efficiency. Begin with using the"generalized workload"as the measure of actual workload of one distribution route, the thesis focuses on optimizing the end distribution-line of logistics and distribution center under the support of the GIS (Geography Information System) and enterprise's network data base system, regarding to meet the demands of customers and reducing the cost of distribution.The study can be divided into four stages: first, the concepts of"generalized workload"of single distribution line and the economical distance are put forward and applied. Second, the distributive lines are divided. Third, the optimization of single routing problem is solved. Finally, the visible outputs of variable vehicle schedules are given.The concept of"generalized workload"to measure workload of single distribution line is put forward in this thesis. The generalized workload is an important economic criterion to the distribution route division of distribution center in a district. Generalized workload (W) of a single distribution line has a bearing on economical delivery distance (S), quantity of delivery (D) and quantity of customers (N). It demands the generalized workload between different distribution routes to be approximately equal. And makes all vehicle delivers to offer the customers more satisfied service. Of all the factors of generalized workload, the customer's order quantity (quantity of delivery), the economical distance of delivery, the quantity of customers are all certain factors. Economical distance of delivery is the shortest physical distance of two customers. It is the value of vehicle delivers in shortest distance when concerning factors such as the road length, the hustle degree, the driveway quantity, and the type of the road. The concept of generalized workload is the precondition of distributive line division and the premise to balance of the logistics cost and customer service.Secondly, under the support of distribution network and its GIS, and taking equilibrium of"generalized workload"and the limitation of vehicles'capacity as the targets, the theoretically unsolvable NP difficult question which contains thousands of distribution nets is transformed to limited subsystems which are controllable and can be observed. In this thesis, we get the initial solution of distributive line division of logistics and distribution center by Nearest-Neighbor Method. Then improve it by Insertion Algorithm. The simulation results based on the GIS have proved the rationality of the improved distribution route. To make the distribution results more suitable to the logistics company's practical application, we put forward the theorem and its certification of the Second Order Nearest-Neighbor Method which is the improvement of general Nearest-Neighbor Method. When choose a new client, the subset of the client formed by two already existing nearest new one in current line has the highest level of aggregation. The customer aggregation's level of distribution route that we got is higher than that by the Nearest-Neighbor Method, and provides a good foundation for next stage of the optimization of single routing problem.Based on the distributive route division, the optimization of single routing scheduling is performed. The optimization integrally considers the difference of customer quantity, the difference of customer demands, the road congestion, and so on of single vehicle route of each deliver. It gets the vehicle route arrangement and the visible output of all vehicle scheduling in the logistics and distribution center in real time.In this thesis, we have done a lot of researches on solving dynamic network model which are the optimization problems of single-vehicle route, and had come up with a unique solution of single-vehicle distribution route: First, we use Insertion Algorithm to build initial feasible solution, and an initial path set is created; Then, we use the overall search strategy of hybrid Genetic Algorithm to optimize the initial solution. Finally, we get a satisfied solution that is optimal or sub-optimal. In the traditional genetic algorithm, the global search capability is strong but the local search capability is not good enough. However, the hill-climb algorithm has a strong local search capability that is a common search algorithm for optimization problem. This thesis combines both of them to utilize the advantages of each one. The applications show that the strategy can greatly improve the optimization performance of distribution route. To make each time and every day's single-vehicle route more fit to actual status of visible output of vehicle scheduling, the optimizing path algorithm brought forward in this thesis is based on the actual situation of distribution system in one of scenic spot in Hangzhou city. From the city's road transport network in the geographic relevance relationship, we discuss the affect of unimpeded situation of the roads as random factors on the effectiveness of single-vehicle distribution route using the shortest path algorithm (Dijkstra). The simulation results demonstrate the accurateness of the model and the implementation.The research of the thesis is based on the information and application case of tobacco network in Hangzhou city. By investigating, we created two different system models. One is division of distribution route of logistics and distribution center. And the other is optimization of single vehicle route. It solves the problems by Nearest-Neighbor Methods (one/two order), Insertion Algorithm, Hybrid GA, Hill-climb Algorithm and so on. The problem of the vehicle route of large distribution network is a typical NP problem. Along with increasing of the customer's number, the complexity and the volume of the system increases exponentially either in space or in time. It is difficult to accept for optimization of large-scale distribution and scheduling problem. According to our investigation, distribution companies must be efficiently response to client order. They must be ready in a short time. Some times even the computer's calculation time can't be too long. So it is necessary in the thesis to research on models and algorithms of distributive line division and single routing problem, and to work out the problem that calculation complexity is too high.In order to complete the design and implementation of the system, we integrate the above models and algorithms into the GIS-based distribution network, using MapInfo, VB, SQL Server 2000 and so on. Through the integration, the results of route-division and the visible outputs of vehicle scheduling can be seen directly on the electronic map. Research results have general suitableness in the fields of concentrative delivery, such as the logistics and distribution enterprises of tobacco, general merchandise, medicine and oil and so on.The major works and contributions of this dissertation are as follows: (1) On the basis of defining"generalized workload"and"economical distance of delivery", the modified second order nearest-neighbor method and insertion algorithm are proposed for solving the problem of distributive line division, which is a multi-objective decision problem. As a result, the demands of customers as well as the cost of distribution are both given attention. (2) An hybrid of genetic algorithm and hill-climb algorithm is employed for optimizing the single routing scheduling. A fitness function (F) which measures the number of customers (N), the quantity of delivery (D), and the total economical distance (S) is presented. This fitness function serves as a criteria of the single routing scheduling (F=1000*N*D/S). (3) The economical distance of a single routing scheduling in a given time is determined according to the situation of traffic jam. And the distribution scheduling and distribution line are adjusted accordingly. Further more, a probabilistic model is used instead of a deterministic one. (4) The research of the thesis has been applied to the tobacco network in Hangzhou city firstly. The effectiveness and applicability are demonstrated.