CN110097234A - Industrial cigarette transport intelligent dispatching method and system - Google Patents

Abstract

Aiming at the actual characteristics of industrial cigarette transportation, the present invention considers commercial company connectivity and dynamic unloading time, etc., and constructs a path optimization method suitable for industrial cigarette transportation, so as to minimize the total industrial enterprise transportation cost on the basis of satisfying commercial company marketing orders. The present invention considers the particularity of the pricing mode of industrial cigarettes, and objectively analyzes key factors such as the actual connectivity and loading rules among commercial companies through the analysis and mining of historical logistics data, avoiding the influence of human subjective factors and discovering the hidden loading rules in the data . The present invention constructs a multi-objective intelligent evolutionary algorithm with enhanced learning capabilities based on the primary and secondary hierarchical framework, reduces the transportation cost of the carrier as much as possible without increasing the logistics costs of industrial enterprises, establishes an intelligent dispatching system for industrial enterprises, and greatly improves logistics efficiency , Reduce the logistics cost of industrial enterprises.

Description

Intelligent scheduling method and system for industrial cigarette transportation

technical field

The invention relates to the technical field of logistics transportation scheduling optimization, in particular to an intelligent scheduling method and system for industrial cigarette transportation.

Background technique

Cigarette transportation costs in industrial enterprises are the largest single item of logistics costs. Cigarette transportation costs account for about 75% of the total cigarette logistics costs in industrial enterprises. Among them, cigarette transportation is dominated by road transportation, which accounts for more than 90% of transportation costs. Therefore, for industrial enterprises, reducing cigarette transportation costs is an important area for enterprises to reduce costs and increase efficiency; reducing cigarette road transportation costs is the top priority, and there is a lot of room for tapping potential.

At present, there are many types of models and many arrival points in the logistics transportation of finished products in industrial enterprises. The loading of orders and the selection of transportation routes all rely on manual experience. The organization of logistics transportation lacks scientific and reasonable planning, and there are low vehicle satisfaction rates and unnecessary waste of freight. The problems are mainly manifested in:

1. At present, the dispatching of finished product logistics and transportation adopts manual methods, and the dispatching and loading of vehicles depends on the personal experience of the dispatcher. With the development of my country's transportation industry, the road network is becoming more and more complex, and the route selection method based on manual experience is difficult to keep up with the external environment. Due to the pace of development, it is difficult to achieve the optimal allocation of goods, vehicles and transportation routes. It is difficult to judge scientificity and rationality, and it is easy to generate unnecessary transportation costs.

2. Manual scheduling takes up a lot of workload. Under the decentralized scheduling mode, each cigarette factory needs to arrange multiple dispatchers to be responsible for this work. When large batches are delivered in a centralized manner, continuous overtime work is required, and the labor cost is high.

3. There are many links such as warehouse transfer and dumping at the delivery point, resulting in waste of resources and increased indirect logistics costs. The on-site dispatch of vehicles in the factory area lacks effective management and information support.

4. The transportation routes of finished cigarettes are mainly divided according to the provincial boundaries. The order volume in the transportation routes is uneven, and there is a lack of scientific and reasonable route planning, resulting in waste of resources, high transportation costs and low efficiency.

Reasonable logistics and transportation scheduling optimization is an important way to reduce the cigarette transportation costs of industrial enterprises, and it has become a topic of common exploration both inside and outside the industry. Logistics transportation scheduling optimization has many successful cases in the domestic auto parts industry, fast-moving goods industry, e-commerce logistics and other fields. Due to the challenges of multi-batch and small-batch timely delivery, research on intelligent logistics optimization scheduling has been carried out one after another, using theoretical research such as planning methods and optimization algorithms, combined with GIS, information network and other technologies, to analyze the model selection and vehicle loading in logistics transportation. , Path optimization provides intelligent and decision-making support, and has achieved remarkable results.

Domestic scholars' research on cigarette logistics and transportation mostly focuses on the optimization of transportation routes and the scheduling of transportation vehicles, in order to achieve the purpose of improving transportation efficiency and reducing logistics costs. Hu Hongchun et al. (2007) mainly aimed at the route optimization of large-scale distribution vehicles with real road environment and multiple demand points in the same city. Introducing the relevant ideas of game theory and using the cluster algorithm, the multi-objective optimization of logistics distribution vehicle routes was carried out for nearly 30,000 cigarette retailers in Jinan Tobacco Distribution Center [1]. Wang Yong (2009) and others mainly studied the problem of the division of tobacco logistics and distribution areas. Aiming at the distribution model adopted by the tobacco industry as the research object, the distribution area planning is carried out, a cost-based operations research model is established, and the genetic algorithm is used to encode and solve the function model to determine the respective distribution areas of the distribution center and the transfer station [2]. Binghuo and Hemu (2014) focused on the urgent problems of tobacco logistics, emphasizing the use of cloud computing, big data, BI (business intelligence) and other information technologies to create an intelligent dispatching and control platform for industry logistics and integrate various logistics resources in the industry. Optimize configuration, intelligent scheduling, and reduce supply chain logistics operating costs [3]. Xu Zhi (2014) proposed to use the heuristic tabu search algorithm to optimize the dynamic path according to the constraints of vehicles, costs, orders, roads, and time according to the daily orders. With the help of GPRS, 3G and other wireless networks, GPS positioning technology solves the problems of cigarette logistics. The distribution route is unreasonable, the vehicle load cannot be reasonably utilized, and there is a lack of abnormal monitoring and handling mechanisms for distribution in transit [4]. Huang Gewen et al. (2015) mainly emphasized the integration of cloud computing, Internet of Things, big data, GIS, GPS, video sensors and other information sensing and transmission equipment according to the characteristics of cigarette transportation and distribution, and developed a tobacco logistics and transportation scheduling system based on cloud computing. , in order to realize the intelligent identification, positioning, tracking, monitoring and management of tobacco distribution vehicles, solve the problem through intelligent algorithms, optimize the distribution lines, and form a network that provides comprehensive services to improve logistics efficiency, intelligent optimization and other management[5] . Zhang Huimin (2018) mainly aimed to optimize the distribution area routes of Fujian Zhangzhou Tobacco Logistics Company, combined with the specific conditions of tobacco logistics manual experience distribution routes, researched and proposed an improved flexible route interception optimization algorithm to establish a new model of flexible delivery, to achieve The goal of maximizing the utilization rate of tobacco transport vehicles and minimizing the distribution mileage [6].

Regarding the research on vehicle transportation scheduling algorithm, Liu and Shen (1999) developed an economical construction heuristic algorithm and an improved heuristic algorithm, and proposed the vehicle routing problem with time windows and heterogeneous fleets for the first time [14]. Belfiore et al. (2007) proposed to solve such problems by decentralized search [15]. Tao Yinqiang et al. (2008) comprehensively considered the problem that different models have different marginal costs and travel costs in the multi-vehicle routing problem, and at the same time considered the compatibility of the models and tasks, and the multi-vehicle multi-cost with time window constraints is very For the fully loaded vehicle routing problem, a mathematical model is established with the goal of minimizing the total cost [7]. Shi Chaochun et al. (2009) established a multi-distribution center vehicle scheduling model with a time window on the basis of analyzing the penalty function of the time window. The design of the model was solved by scanning algorithm and improved genetic algorithm, and finally the effectiveness of the algorithm was verified by simulation [ 8]. Wang et al. (2013) aimed at minimizing the deviation degree of the customer's time window and minimizing the distribution cost, and established a mathematical model of the problem and its solution algorithm based on the standard example proposed by Solomon [9]. Ma Yuhong et al. (2013) proposed a new multi-segment chromosome hybrid coding algorithm for the large-scale multi-distribution center multi-vehicle scheduling problem [10]. Adelzadeh et al. (2014) designed a mathematical model with fuzzy time windows and heterogeneous vehicles considering different capacities, speeds and costs, applied a three-stage algorithm to decompose the problem into several common vehicle routing problems, and proposed to use an improved Simulated annealing algorithm solution [16]. Sun Zhuangzhi et al. (2014) used a variety of professional algorithms such as central clustering, tabu search, and local search to study the cigarette distribution scheduling problem with the Beijing cigarette market as the background [11]. Xiao Zhengzhong et al. (2017) used the boundary assignment method for cross-regional multi-distribution center vehicle scheduling to transform the problem into a single distribution center vehicle scheduling problem, combined with genetic algorithm and ant colony algorithm to solve the optimal scheduling scheme for cross-regional distribution, and used Guizhou Province The simulation analysis of cigarette distribution in the logistics center of Qiandongnan Tobacco Company shows the effectiveness of the algorithm[12]. Li Mingyu et al. (2017) established a vehicle routing problem model with time windows and heterogeneous fleets, and considered multiple attributes of time windows, heterogeneous fleets, and vehicle quantity restrictions, and proposed an improved tabu search algorithm to solve the problem[13 ].

At present, many commercial enterprises in the tobacco industry have taken the lead in realizing intelligent scheduling in the cigarette distribution link, and have achieved good results through the dynamic optimization of delivery routes in the city. Some industrial enterprises have also begun to carry out research on the optimization of delivery scheduling, combined with the implementation of logistics informatization projects, to explore the automation and intelligence of transportation scheduling. In terms of dispatching algorithms, most of them are fixed heuristic rules and do not take into account the mining application of historical logistics data. Moreover, due to the inconsistencies in the influencing factors such as storage layout and management and control mode of industrial enterprises, it is still in its infancy, and has not yet formed a mature, stable, and highly applicable cigarette transportation intelligent optimization scheduling model and algorithm research program.

Contents of the invention

Therefore, according to the characteristics of cigarette logistics and transportation in industrial enterprises, combined with the historical logistics big data of industrial enterprises, theoretically analyze the transportation constraints and constraints of industrial finished cigarettes, establish a vehicle scheduling model for industrial cigarette transportation, and design an intelligent evolutionary algorithm for transportation scheduling. Optimize the allocation of link resources, and build a delivery scheduling system that replaces manual experience with intelligent processing on the basis of the existing China Tobacco comprehensive management platform, to further improve the efficiency of logistics operations, reduce logistics costs, and improve the integration and intelligence of supply chain logistics level.

In order to achieve the above object, the present invention provides an intelligent scheduling method for industrial cigarette transportation, comprising the following steps:

Step 1: Construct a business company set V (V={2,3,...i,...j,...,n}), each business company is in the business company set, the formula is expressed as i∈V or j∈V, and the The delivery point is represented by 1, and the delivery point and the commercial company are combined V ₀ (V ₀ =V∪{1}), and an undirected connected graph G=(V ₀ ,E) is constructed, where E is every two nodes i and side of j Each edge {i,j}∈E, each edge {i,j} corresponds to dist _ij , a path starts from delivery point 1, passes through one or more commercial companies, and finally ends at delivery point 1 , that is, a path is an access sequence {1,V _i ,V _j ,….,1}, and n paths are initialized: V ₁ →V _i →V ₁ , that is, each path is single-point transportation, and finally returns to the sending Cargo point V ₁ , calculate the minimum single-point transportation fee and/or combined transportation fee of all commercial companies;

Step 2: Calculate the pairing priority of the commercial company, and under the premise of satisfying the rationality constraints of loading, sequentially fuse the two associated paths to complete the construction of the scheduling plan;

Among them, the formula for calculating the matching priority of commercial companies is as follows:

dist _max is the furthest driving distance in the marketing contract, d _max is the heaviest order in the marketing contract; Both are pairing priorities.

The shorter the distance dist _ij between two commercial companies V _i and V _j , the matching priority higher. Among them, dist _1i and dist _j1 are the real driving distances from the distribution center DC to the commercial companies V _i and V _j respectively;

When the average weight of commercial companies is smaller, the pairing priority The higher, where d _i and d _j are the order weights of commercial companies i and j respectively, and q ₁ is the minimum tonnage for single-point transportation;

The higher the loading confidence, the matching priority higher, where It refers to the confidence level of spelling, and its value ranges from 0 to 1;

Step 3: Repeat step 2 until all commercial companies are configured to obtain a feasible scheduling plan,

Step 4: Use the double-layer local search strategy to optimize the initial plan, so as to reduce the carrier's transportation costs as much as possible without increasing the expenditure of industrial enterprises, as follows:

Loop executes the following search strategy for all single-point routes in the feasible solution that are lower than the guaranteed tonnage: the sequence of loading sequence routes obtained above, each sequence is a feasible solution.

The first layer of local search: Based on the mileage-saving sorting, insert this line into other optimal mileage-saving lines that meet the constraints. If successful, jump out of the local search of this layer; if not successful, continue to the second layer of local search;

The second layer of partial search: Based on the mileage saving sorting, insert the commercial company warehouses of other consolidated routes into this unconsolidated route, and at the same time, do not destroy the various constraints of the original route;

Step 5: Based on the above-mentioned business customer consolidation plan, use the LKH algorithm (Lin-Kernighan Heuristic) to optimize the access sequence, and reduce the total mileage of the carrier on the premise of meeting the time window.

Further, in step 1, the specific steps of calculating the minimum single-point transportation cost and/or combined transportation cost of all commercial companies are as follows:

Define the following decision variables:

Where i∈V, j∈J _k , j∈M, k∈K, K={1,2,…,m} is the vehicle set, and the cigarette transportation scheduling method is constructed as follows:

Minimize:

s.t.

a _i ≤ T _i ≤ b _i , i∈V (10)

Among them, the transportation fee is composed of two types of pricing fees: single-point transportation and combined transportation:

Fees for single point shipping:

Consolidated shipping costs:

Equation (1) ensures that each customer can and can only be accessed by one vehicle;

Formula (2) stipulates that the number of vehicles of each type departing from the delivery point will not exceed the number of this type;

Equation (3) ensures that the total number of pieces of supplier materials served by each vehicle will not exceed the maximum number of load-bearing pieces;

Equation (4) ensures that the total weight of the supplier's materials for each vehicle service will not exceed the maximum carrying weight;

Equation (5) is the connectivity constraint between commercial companies;

Equation (6) is the passability constraint between vehicle models and commercial companies;

Equation (7) eliminates constraints for subpaths;

Equation (8) expresses that vehicles both originate and end at the delivery point, and each vehicle must return to the delivery point.

Equation (9) is the expression of the time when the vehicle arrives at each customer;

Equation (10) is the time window constraint of commercial companies;

Equations (11) and (12) are model Boolean decision variables.

Through the above method, the goal is to minimize the cost of transporting all commercial customers, that is, to ensure that the sum of the two types of transport costs for single-point transport and combined transport is minimized. Among them, the guaranteed minimum tonnage of single-point transportation is q1, and the guaranteed minimum tonnage of joint load transportation is q2. Since q2<q1., under the premise of satisfying the model constraints, the combined transportation of fragmented orders of commercial companies (ie d _j <q2) will be the largest Minimize and reduce the transportation cost of industrial cigarettes.

Among them, d _j is the total number of materials in the commercial company, w _j is the weight of the materials in the commercial company, the maximum number of load-carrying pieces of D _k model k, the maximum load-carrying weight of W _k model k, the maximum available quantity of N _k model k, Car model k can access the connectivity parameters of commercial companies, dist _1j is the actual driving distance from the delivery point to different commercial companies, dist _i,j is the real driving distance between different commercial companies, c _j is the transportation unit price from the delivery point to different commercial companies, a _ij Connectivity parameters between commercial companies, u _j commercial company j unloading time, [a _j , b _j ] commercial company j’s latest time window for hitting the barrier, each commercial company has a limit of the latest arrival time, so each commercial company The company has its corresponding time window [a _j , b _j ]. The previous time window a _j defines the earliest start time of the vehicle service commercial company j, which is generally not strictly limited; the next b _j defines the vehicle service commercial company j’s latest end time.

Further, considering the carpooling restriction, introduce the inter-commercial company connectivity a _ij , the measure a _ij of the inter-commercial company connectivity, which is a Boolean variable, allowing the connection to be set to 1, otherwise set to 0, the inter-commercial company connectivity a _ij refers to whether the arrival warehouses of commercial companies in the area are connected on the route consolidation, which is directly related to whether the vehicles can be effectively consolidated and the cost control. If you encounter a candidate assembly point with a connectivity of 0, even if the assembly scheme may satisfy the weight, time and other constraints, such a scheme will not be output because the connectivity constraint is not satisfied. It can be seen that reasonable connectivity settings play a key role in the control of logistics costs and the rationality of the consolidation plan. Since the connectivity between commercial companies involves the profit of the carrier, in reality, the determination of the consolidation plan given by the industrial enterprise is a process of repeated games. Therefore, the research results of the carrier will be quite different from the reality. The present invention can more objectively reflect the actual connectivity between commercial companies by performing statistical analysis on historical waybill data. There are two cases for the determination of the connectivity between commercial companies: the first case is that the commercial companies V _i and V _j have appeared in the same waybill data, that is, the carrier’s historical behavior accepts the two loads, and at this time it can be regarded as the commercial company is connected; the case Second, commercial companies V _i and V _j have never appeared in the same waybill, such as setting up a new commercial company or not appearing in the same contract pool, based on the classic saving algorithm and sweep algorithm, through the farthest distance and maximum value accepted by the carrier based on history The angle is regarded as the connectivity threshold for judgment, as follows:

1) Each waybill in the historical waybill data represents a route, that is, the consolidating sequence of the carrier's transportation route to the commercial company: route={1,V _i ,V _j ,...,1}. The geographical distance between V _i and V _j is dist _ij , and the azimuth angle (Azimuth angle) is azim _ij ;

2) If V _i and commercial company V _j have appeared in the same historical dispatch waybill contract set at the same time , that is, it is considered that the commercial companies are connected, and a _ij = 1 can be set;

3) Based on the connectivity of historical waybills, count the furthest connectivity distance of each commercial company V _i and its maximum connectivity azimuth

4) If the commercial company V _j has not been in the same waybill with V _i before, but its geographical distance is less than the longest historical connection distance of V _i And the azimuth is smaller than the historical maximum connected azimuth Then it is judged that the connectivity between the two is also 1;

5) Repeat the above steps until the connectivity determination of each commercial company is completed, and the basic connectivity data matrix is formed as follows:

6) As shown in Table 1, the connectivity matrix of the five commercial companies, 0 indicates that the two routes cannot be combined, and 1 indicates that it can be combined.

7) Table *Example of Connectivity Matrix for Business Firms

business company 1 2 3 4 5 1 1 0 1 0 0 2 0 1 0 1 0 3 1 0 1 0 0 4 0 1 0 1 1 5 0 0 0 1 1

Further, in step 2, the premise of the rationality constraint of the consolidation is as follows:

Commercial companies i and j do not appear on the loaded path at the same time, that is, at least one point is not loaded;

The unstowed commercial company i does not appear on the interior point of the already loaded path, that is, the unstowed point must be directly connected with the cigarette factory on the arranged path;

The order weight of the unloaded commercial company i shall not be greater than the remaining capacity of the vehicle on the path to be merged;

The fusion of unloaded commercial company i shall not cause delays in the arrival time of other commercial companies;

The number of route points for new loading shall not exceed the maximum number of loading points;

The total logistics weight of the newly loaded path shall not exceed the maximum passable vehicle type of the corresponding commercial company;

The path of the new stowage must satisfy the connectivity constraints;

Furthermore, the route passing through the commercial company V _i will be loaded with the commercial company V _j with a high probability, that is, there is a loading association rule The spelling confidence The calculation steps are as follows:

The marketing contract that the carrier needs to transport every day is: contract={V ₁ ,V ₂ ,…,V _i ,…,V _n }; each waybill record in its historical waybill is the consolidating sequence of the commercial company: route= {1,V _i ,V _j ,….,1}, the sequence route is a non-empty subsequence of its marketing contract;

Calculate the assembly confidence of its 2-itemset association rules in each assembly sequence one by one: assembly rules The confidence level of Defined as the ratio of the number of commercial companies <V _i , V _j > to the number of companies that only contain <V _i > in the historical assembly sequence; note that the date that only contains commercial company V _i should be excluded from the historical assembly sequence Marketing contract, to avoid the impact of commercial company V _i 's consolidation confidence calculation due to the absence of V _j 's contract;

Cycle through the above steps to calculate the 2-itemset of each loading sequence route. Pay attention to the symmetry of the rules, it is easy to know The loading confidence of is equal to the rule Confidence in the assembly of , which can save the amount of calculation of the confidence in the assembly.

association rules The value range of the concatenation confidence degree of is a number between 0 and 1. like Indicates that as long as commercial companies V _i and V _j appear in the marketing contract on the same date, they will be combined for transportation; if it is 0, it indicates that the two have never been combined for transportation. The intelligent evolution algorithm proposed in the present invention will also construct and optimize the loading scheme based on this value.

Further, the specific process of the LKH algorithm is as follows:

5) Obtain the access path for the obtained customer loading plan.

6) Let S and E be the set of empty edges to be canceled and the set of empty edges to be supplemented

7) Let i=1, randomly select side s1 and side e1 to enter S and E respectively

8) Keep increasing r, and keep selecting si and ei to enter S and E until an access path with lower mileage and satisfying the time window constraint can be obtained, and go to 3) until there are no unselected edges.

The present invention also provides an intelligent dispatching system for industrial cigarette transportation, including a transportation dispatching unit, an on-site dispatching unit, a basic data management unit, a capacity resource management unit, an Internet of Things application unit, and a report display unit. The transportation dispatching unit acquires a data management unit and The data of the capacity resource management unit calls the intelligent transportation scheduling algorithm to automatically generate multiple intelligent loading plans through one-click scheduling according to the contracts pushed by the marketing batches. Each plan includes the number of contracts, the number of shipments, and the total transportation. Key information elements such as cost and transportation mileage, and send the generated stowage plan to the on-site dispatch unit to facilitate the dispatcher to choose a suitable stowage plan. At the same time, the stowage plan is sent to the carrier through the Internet of Things application unit, and the carrier The dispatcher of the carrier confirms the dispatching of vehicles or gives feedback on abnormal situations. The vehicle type requires the arrangement of vehicles and drivers, and automatically sends a message reminder to the driver. After the carrier confirms the dispatching of the vehicles, the system automatically generates a complete transportation load list and enters the intelligent reservation queuing system Make shipping shipments.

Different from the prior art, the above technical solution has the following beneficial effects:

First, according to the actual characteristics of industrial cigarette transportation, considering the connectivity of commercial companies and dynamic unloading time, etc., a route optimization problem model suitable for industrial cigarette transportation is constructed, so that the total transportation cost of industrial enterprises can be minimized on the basis of satisfying the marketing orders of commercial companies .

Second, considering the particularity of the pricing model of industrial cigarettes, through the analysis and mining of historical logistics data, objectively analyze key factors such as the actual connectivity between commercial companies and the rules of loading, avoiding the influence of human subjective factors and discovering hidden loading in the data law.

Third, build a multi-objective intelligent evolutionary algorithm with reinforcement learning capabilities based on the primary and secondary hierarchical framework, and reduce the transportation costs of carriers as much as possible without increasing the logistics costs of industrial enterprises. Based on this theoretical achievement, an intelligent scheduling information for industrial enterprises is established. The system greatly improves the logistics efficiency and reduces the logistics cost of industrial enterprises.

Description of drawings

Fig. 1 is a frame diagram of an intelligent scheduling system for industrial cigarette transportation in an embodiment of the present invention.

Fig. 2 is a schematic diagram of an intelligent scheduling solution in an embodiment of the present invention.

Fig. 3 is a detailed scheme of intelligent dispatching and a loading circuit diagram in an embodiment of the present invention.

Fig. 4 is a schematic diagram of carrier vehicle adjustment in the embodiment of the present invention.

Figure 5 LIO algorithm main level evolution framework.

Detailed ways

In order to explain in detail the technical content, structural features, achieved goals and effects of the technical solution, the following will be described in detail in conjunction with specific embodiments and accompanying drawings.

Cigarette transportation costs in industrial enterprises are the largest single item of logistics costs. Cigarette transportation costs account for about 75% of the total cigarette logistics costs in industrial enterprises. Among them, cigarette transportation is dominated by road transportation, which accounts for more than 90% of transportation costs. Therefore, for industrial enterprises, reducing cigarette transportation costs is an important area for enterprises to reduce costs and increase efficiency; reducing cigarette road transportation costs is the top priority, and there is a lot of room for tapping potential.

Reasonable logistics and transportation scheduling optimization is an important way to reduce the cigarette transportation costs of industrial enterprises, and it has become a topic of common exploration both inside and outside the industry. Logistics transportation scheduling optimization has many successful cases in the domestic auto parts industry, fast-moving goods industry, e-commerce logistics and other fields. Due to the challenges of multi-batch and small-batch timely delivery, research on intelligent logistics optimization scheduling has been carried out one after another, using theoretical research such as planning methods and optimization algorithms, combined with GIS, information network and other technologies, to analyze the model selection and vehicle loading in logistics transportation. , Path optimization provides intelligent and decision-making support, and has achieved remarkable results.

In this embodiment, aiming at the characteristics of cigarette logistics and transportation in industrial enterprises, combined with the historical logistics big data of industrial enterprises, theoretically analyze the transportation constraints and constraints of industrial finished cigarettes, establish a vehicle scheduling model for industrial cigarette transportation, and design an intelligent evolutionary algorithm for the transportation scheduling link. Resource allocation is optimized, and on the basis of China Tobacco's comprehensive management platform, a delivery scheduling system that replaces manual experience with intelligent processing is built to further improve logistics operation efficiency, reduce logistics costs, and improve the integration and intelligence of supply chain logistics.

Based on the above analysis, the logistics scheduling of tobacco industry enterprises can be classified as Vehicle Routing Problem (VRP). This problem was first proposed by Dantzig and Ramser in 1959. It refers to a certain number of customers, each with a different number of The demand for goods, the distribution center provides goods to customers, and different numbers and types of vehicles are responsible for distributing goods, organizing appropriate driving routes, the goal is to meet the needs of customers, and under certain constraints, such as the shortest distance , minimum cost, minimum time-consuming and other purposes.

This problem can be defined as an undirected connected graph G=(V ₀ ,E), where V={1,2,…,n} is the node set, E is the edge of every two nodes, Commercial companies are expressed as 1, 2, 3, ..., n+1. For convenience, the delivery point is represented by node 1. V (V = {2, 3, ..., n}) represents the set of commercial companies. V ₀ (V ₀ ＝V∪{1}) represents the union of shipping points and commercial companies. For each commercial company j ∈ V, there is a definite demand d _j . Vehicles are heterogeneous models, the delivery capacity of each model is D _k , and the maximum carrying weight of each model is W _k . Here the commercial company is required The number of pieces in a single order shall not exceed the maximum delivery capacity of the vehicle, and the order weight shall not exceed the maximum carrying weight of the vehicle. If the total number of orders of a commercial company exceeds the maximum delivery capacity of the vehicle, it is necessary to pre-split the order in the early stage. Each model has a limit on the number of vehicles N _k , and considering the platform restrictions of commercial companies, set the model access connectivity of each commercial company only It means that the vehicle type k can visit commercial company j. The distance between commercial company j and j′ adopts the shortest driving distance of Baidu, but does not satisfy the triangle inequality. A path starts from the delivery point, passes through some commercial companies (at least one), and finally ends at the delivery point. That is, a path is an access sequence {1, V ₁ , V ₂ ,...,1}, all V _j are different. Each edge {i,j}∈E, the corresponding distance is dist _ij . Each commercial company has the latest arrival time limit, so each commercial company has its corresponding time window [a _j ,b _j ]. Time window The previous session a _j defines the earliest start time of the vehicle service commercial company j, generally without strict restrictions; the next session b _j defines the latest end time of the vehicle service commercial company j. The unloading time of commercial company j is u _j . Furthermore, taking into account the carpooling constraint, commercial inter-firm connectivity a _{i,j} is introduced, as detailed below. For ease of reference, the symbols and parameter variables used in the present invention are organized in the following table 1

Shown:

Table 1: Model parameter variable table

First, in order to facilitate the solution of the HVRPTW problem, the following decision variables are defined:

Where i∈V, j∈J _k , j∈M, k∈K, the model for constructing the cigarette transportation scheduling problem is as follows:

Minimize:

s.t.

a _i ≤ T _i ≤ b _i , i∈V (10)

The optimization goal of this mathematical model is to minimize the cost of transporting all commercial customers. Among them, the transportation cost of the objective function is composed of two types of pricing costs: single-point transportation and combined transportation: where

Fees for single point shipping:

Consolidated shipping costs:

Equation 1) ensures that each customer can and can only be accessed by one vehicle; Equation 2) stipulates that the number of vehicles of each type departing from the delivery point will not exceed the number of this type; Equation 3) ensures that each vehicle service The total number of supplier material pieces will not exceed the maximum number of carrying pieces; Equation 4) ensures that the total weight of supplier materials served by each vehicle will not exceed the maximum load weight; Equation 5) is the connectivity constraint between commercial companies; Equation 6) is the passability constraint between the vehicle model and the commercial company; Equation 7) is the sub-path elimination constraint; Equation 8) expresses that all vehicles start and end at the delivery point, and each vehicle must return to the delivery point. Equation 9) is the expression of the time when the vehicle arrives at each customer; Equation 10) is the time window constraint of the commercial company; Equations 11) and 12) are the Boolean decision variables of the model.

Previous studies mostly started from theoretical models, and less consideration was given to the results of manual scheduling in historical logistics data, or even to summarize manual solutions, due to the dynamic changes and randomness of the environment, it is difficult to quantify experience through specific values, which makes the construction of theoretical models difficult. Due to the lack of some model constraints or imprecise input data in the scheduling scheme, the theoretical scheduling scheme cannot directly meet the actual needs. The present invention analyzes and excavates the long-term consolidation plan in the big data of historical waybills, and proposes the main factors affecting the dispatching scheme, in order to objectively reflect the actual connectivity between commercial companies and the hidden consolidation rules and constraints. Through the implementation of the intelligent dispatching algorithm, combined with the reasonable fine-tuning of the dispatching plan by the carrier, the final actual consolidation plan will give feedback on the key influencing factors, thus forming a regulation of the intelligent dispatching algorithm and realizing the autonomous learning and optimization capabilities of the algorithm .

The transportation of industrial enterprises is mainly based on the outsourcing model. Commercial companies are usually divided into different tenders based on geographical regions. On the premise of meeting the arrival time of commercial customers, the same carrier is allowed to load across bids. Generally speaking, the combined mileage of any two points must be less than the single-point transportation mileage of two vehicles. Consolidated shipping should be preferred. However, as mentioned above for the pricing model, the carrier’s settlement fee is billed in the ton-kilometer model, and consolidation and single-point transportation have different guaranteed tonnages (single-point transportation has a higher guaranteed minimum tonnage), which makes carriers usually prefer Single-point transportation, dislikes long-distance consolidation with high empty load rates such as distance, light, near-heavy, or consolidation schemes with large differences in the orientation of commercial companies, even if multiple single-point transportation will increase its total mileage.

In view of this feature, this embodiment proposes a measure of the connectivity between commercial companies a _ij , which is a Boolean variable, which allows connectivity to be set to 1, otherwise it is set to 0. Connectivity refers to whether the arrival warehouses of commercial companies in the area are connected on the route consolidation, which is directly related to whether the vehicles can be effectively consolidated and the cost control. If you encounter a candidate assembly point with a connectivity of 0, even if the assembly scheme may satisfy the weight, time and other constraints, such a scheme will not be output because the connectivity constraint is not satisfied. It can be seen that reasonable connectivity settings play a key role in the control of logistics costs and the rationality of the consolidation plan. Since the connectivity between commercial companies involves the profit of the carrier, in reality, the determination of the consolidation plan given by the industrial enterprise is a process of repeated games. Therefore, the research results of the carrier will be quite different from the reality.

The present invention can more objectively reflect the actual connectivity between commercial companies by performing statistical analysis on historical waybill data. There are two situations for the determination of the connectivity between commercial companies: the first case is that commercial companies V _i and V _j have appeared in the same waybill data, that is, the historical behavior of the carrier accepts the consolidation of the two, and it can be regarded as commercial company connectivity. Scenario 2: Commercial companies V _i and V _j have never appeared in the same waybill, such as setting up a new commercial company or not appearing in the same contract pool. In this case, there is no historical data to refer to. Based on the classic saving algorithm and sweep algorithm, the judgment is made based on the farthest distance and maximum angle accepted by the carrier as the connectivity threshold. details as follows:

1) Each waybill in the historical waybill data represents a route, that is, the consolidating sequence of the carrier's transportation route to the commercial company: route={1,V _i ,V _j ,...,1}. The geographical distance between V _i and V _j is dist _ij , and the azimuth angle (Azimuth angle) is azim _ij .

2) If V _i and commercial company V _j have appeared in the same historical dispatch waybill contract set at the same time , which means that the commercial companies are considered to be connected, and a _ij =1 can be set.

3) Based on the connectivity of historical waybills, count the furthest connectivity distance of each commercial company V _i and its maximum connectivity azimuth

4) If the commercial company V _j has not been in the same waybill with V _i before, but its geographical distance is less than the longest historical connection distance of V _i And the azimuth is smaller than the historical maximum connected azimuth Then it is judged that the connectivity between the two is also 1.

5) Repeat the above steps until the connectivity determination of each commercial company is completed, and the basic connectivity data matrix is formed as follows:

As shown in Table 2, the connectivity matrix of the five commercial companies, 0 indicates that the two routes cannot be combined, and 1 indicates that the combination is possible.

Table 2 Example of connectivity matrix for business firms

business company 1 2 3 4 5 1 1 0 1 0 0 2 0 1 0 1 0 3 1 0 1 0 0 4 0 1 0 1 1 5 0 0 0 1 1

Before industrial enterprises adopt intelligent algorithms for cigarette transportation, they have accumulated a large number of historical manual loading schemes, among which many hidden loading rules are very important but difficult to simply summarize. One of the regularities of historical vehicle pooling is that some commercial companies are always assigned to the same vehicle, the same model and even the same driver. The reason may be that the geographic locations of commercial companies are close, or that certain routes are more suitable for this model or drivers are more familiar. This kind of loading rule is difficult to summarize manually and also difficult to calculate with formulas. With the wide use of the logistics system and the continuous collection and storage of a large amount of logistics data, the present invention extracts its implicit internal knowledge through the association rule method of data mining.

The law of commercial company loading can be described as: the line passing through commercial company V _i will be loaded with commercial company V _j with a relatively high probability, that is, there is a loading association rule The method of the present invention is based on the method of association rules to carry out the calculation of the confidence degree of spelling, and the steps are as follows:

1) The marketing contract that the carrier needs to transport every day is: contract={V ₁ ,V ₂ ,…,V _i ,…,V _n }; each waybill record in its historical waybill is the consolidating sequence of the commercial company: route={1, V _i , V _j , . . . , 1}. The loading sequence route is a non-empty subsequence of its marketing contract.

2) Calculate the loading confidence of its 2-itemset association rules in each assembly sequence one by one: assembly rules The confidence level of It is defined as the ratio of the number of companies containing <V _i , V _j > to the number of companies only containing <V _i > in the history sequence. Note that date marketing contracts that only include commercial company V _i should be excluded from the historical consolidation plan, so as to avoid affecting the calculation of commercial company V _i ’s consolidation confidence due to the lack of contract of V _j .

3) Repeat the above steps to calculate the 2-itemset of each sequence sequence route. Pay attention to the symmetry of the rules, it is easy to know The loading confidence of is equal to the rule Confidence in the assembly of , which can save the amount of calculation of the confidence in the assembly.

association rules The value range of the concatenation confidence degree of is a number between 0 and 1. like Indicates that as long as commercial companies V _i and V _j appear in the marketing contract on the same date, they will be combined for transportation; if it is 0, it indicates that the two have never been combined for transportation. The intelligent evolution algorithm proposed in the present invention will also construct and optimize the loading scheme based on this value.

Based on the factor analysis of the above-mentioned industrial enterprise cigarette distribution model and logistics historical data, and considering many factors such as customer response time, reasonable carpooling connectivity, the interests of both industrial enterprises and carriers, the present invention designs an intelligent evolution algorithm (Logistics Intelligent Optimization, LIO for short) schedules the delivery of cigarettes. On the basis of theoretical research, develop an intelligent logistics optimization scheduling system, realize historical data analysis and self-feedback of intelligent optimization, and realize intelligent scheduling of cigarette shipments for industrial enterprises.

The intelligent evolutionary algorithm proposed in this embodiment is divided into primary and secondary levels for optimization: in the main level, the probability-based evolutionary algorithm is used to learn from the iterative process to improve the optimization effect; in the sub-level, the basic data and historical logistics data analysis are combined As a result, solutions are constructed and evaluated for paired sequences. This algorithm framework distinguishes primary and secondary levels and has strong versatility. Even if the external constraints change, it only needs to fine-tune the sub-levels to be applicable.

The Saving algorithm proposed by Clarke and Write has been widely used in VRP optimization problems, and has the advantages of simplicity, high efficiency and strong applicability. The basic process is as follows: (1) Calculate the distance between each arrival point and construct a distance matrix; (2) Recursively combine and calculate the mileage saved between each node; (3) Sort the savings by order; (4) Combine Node demand for routing.

The core factor of the Saving algorithm is the matching priority calculation between commercial companies. The classic saving method only considers the distance factor between cargo points, and its priority calculation formula is as follows:

Among them, dist _1i and dist _j1 are the real driving distances from the distribution center DC to the commercial companies V _i and V _j respectively, and dist _ij is the driving distance between the two commercial companies. This formula will increase the matching priority of adjacent commercial companies, which will help carriers reduce transportation costs.

The invention designs an improved commercial company pairing priority calculation formula aiming at the industrial enterprise pricing mode and various realistic constraints. As mentioned earlier, the core that affects the cost of industrial enterprises is the effective consolidation of scattered contracts, that is, the priority matching of commercial companies with a lower than the guaranteed tonnage, so as to reduce the additional guaranteed expenditure of industrial enterprises as much as possible. Therefore, increasing the matching priority considering the order volume of the business company is as follows. Among them, q ₁ is the minimum tonnage of single-point transportation. When the average weight of commercial companies is smaller, the matching priority in the construction process increases.

Confidence of spelling mentioned above in this embodiment It can effectively reflect the historical mosaic rules that are difficult to generalize, and help to improve the operability of the mosaic scheme. Based on this, the present invention adds it to one of the matching priority factors. The higher the mosaic confidence, the higher the pairing priority. Also higher to take full advantage of expert loadout experience.

The three matching priority influencing factors of the present invention are comprehensively calculated from the perspectives of mileage saving, guaranteed tonnage, and loading rules. However, the dimensions of each factor are different. In order to increase the robustness of priority calculation, the above factors are normalized. The final formula is as follows:

Among them, dist _max is the farthest driving distance in the marketing contract; d _max is the heaviest order in the marketing contract. Since the value range of the loading confidence is [0,1], there is no need to adjust it.

Based on the business company pairing priorities described above, the construction of solutions and the evaluation of target costs can be performed. Proceed as follows:

Step 1: Initialize n routes: V ₁ →V _i →V ₁ , that is, each route is single-point transportation, and finally returns to the shipping point V ₁ .

Step 2: Construction of the scheduling plan: based on the business company pairing priority calculated by the formula (*), the two associated paths are sequentially fused under the premise of satisfying the following rationality constraints of loading:

a) Commercial company warehouses i and j do not appear on the loaded path at the same time, that is, at least one point is not loaded.

b) The warehouse i of the unstowed commercial company does not appear on the inner point of the route that has been loaded, that is, the unstowed point must be directly connected to the cigarette factory on the route that has been arranged.

c) The weight of the unloaded commercial company warehouse i must not be greater than the remaining capacity of the vehicles on the path to be fused.

d) There must be no delay in the arrival time of other commercial companies in the fusion of the warehouse i of the unloaded commercial company.

e) The number of route points for new loading shall not exceed the maximum number of loading points.

f) The total logistics weight of the newly loaded path shall not exceed the maximum passable vehicle type of the corresponding commercial company.

g) The newly loaded path must satisfy the connectivity constraints.

Step 3: Repeat step 2 until all commercial company warehouses are configured to obtain a feasible scheduling plan.

Based on the matching priority of commercial companies and the above construction steps, a feasible scheduling scheme can be obtained. However, there may still be routes with a single loading point and lower than the guaranteed tonnage, which means that there is still room for optimization of the feasible solution. Therefore, the present invention proposes to perform a two-layer local search on the above-mentioned feasible solutions under the premise of satisfying the weight, connectivity, time window, etc., so as to optimize the above-mentioned initial solution. In addition, the objective function of the model of the present invention is only related to the loading plan, and the access sequence will not affect the overall logistics cost of the industrial enterprise, but will affect the total mileage and transportation cost of the carrier. Therefore, it is necessary to sort the visiting order of the arriving commercial companies, which is another typical traveling salesman combinatorial optimization problem. Considering the time window factor, the number of commercial companies on the same line is limited. Therefore, the present invention uses the efficient heuristic Lin-Kernighan algorithm [18] to optimize the line, so as to reduce the carrier's transportation costs as much as possible without increasing the expenditure of industrial enterprises.

Specific steps are as follows:

Step 4: Loop to execute the following search strategy for all single-point routes in the feasible solution that are lower than the guaranteed tonnage:

a) The first layer: Based on the mileage-saving sorting, insert this line into other best mileage-saving lines that satisfy the constraints. If successful, jump out of the LS loop; if unsuccessful, continue to the second layer of local search.

b) The second layer: Based on the mileage saving ranking, insert the commercial company warehouses of other routes that are not consolidated into this route, and at the same time, the various constraints of the original route cannot be broken.

Step 5: Based on the above-mentioned commercial customer consolidation plan, the LKH algorithm is used to optimize the access sequence, and the total mileage of the carrier is reduced under the premise of meeting the time window.

Based on the above construction process, a single feasible solution can be obtained, but due to the lack of diversity of solutions, its optimization effect in different scenarios cannot be guaranteed. The present invention introduces a probability-based evolutionary algorithm (Evolutionary Algorithm) framework, through evolutionary learning of a set of feasible solutions, to increase the diversity of LIO algorithm solutions, and gradually approach the optimal solution, thereby ensuring the optimization quality of the algorithm in different scenarios.

The LIO algorithm in this paper will be decomposed into two interrelated sub-optimization levels, primary and secondary: the main level is based on the evolutionary algorithm framework proposed by MariaBattarra et al. The deconstruction algorithm proposed in the previous section constructs the paired sequence and evaluates the fitness function. This evolution process can improve the search experience accumulated by the LIO algorithm in the evolution process, and ensure that the population can adaptively adjust the pairing priority of commercial companies, so that it can focus on searching in the ideal solution space, achieve a balance between global and local optimization, and ensure that Construct a satisfactory scheduling solution in acceptable time. Its main-level evolution framework is shown in Figure 5:

The LIO intelligent optimization framework is flexible and practical. Through the preprocessing of the commercial company's geographic information and basic parameter data, combined with the analysis results of marketing order data and historical logistics data, the single-point direct delivery in the transportation operation is sequentially delivered based on the constructive strategy. Combined into multi-point loading, the total transportation cost after the combination is reduced as much as possible; at the same time, considering the influence of billing rules, the dispatching route constructed meets the requirements of vehicle capacity, latest arrival time, maximum number of loading points, and maximum availability of commercial company warehouses. Carry out maximum consolidating under limited conditions such as passing vehicles, and at the same time give the best arrival sequence for the route after consolidating, so as to reduce the transportation cost of the carrier without increasing the transportation cost of industrial enterprises. It is worth noting that in the LIO intelligent algorithm, not only the distance from the delivery point to the warehouse of each commercial company is considered, but also the real high-speed distance between all multiple commercial companies is obtained through the Baidu API interface. Combined with the average driving speed of the vehicle, it can be accurately evaluated The real driving time of the vehicle ensures that the arrival time of the commercial company in the carpooling plan does not appear later than the arrival time of the commercial company given by the marketing, and provides accurate data support for multi-point carpooling. In addition, since the actual driving time is also affected by uncertain factors such as weather and road conditions, in the LIO intelligent algorithm, the maximum number of load points can be further restricted according to the demand, so as to further ensure the quality of customer service.

Based on the research of LIO intelligent evolution algorithm, the intelligent logistics optimization scheduling system is developed to realize the intelligent scheduling of cigarette delivery. The system automatically generates multiple intelligent transportation and stowage plans with one key. The system consists of contract management, plan management, intelligent scheduling, Vehicle adjustment is composed of 4 modules, forming a series of complete automated, standardized, and programmed intelligent transportation scheduling processes from contract receipt -> transportation planning -> intelligent dispatching -> transportation stowage.

As shown in Figure 1, the intelligent scheduling system for industrial cigarette transportation is positioned as a business execution system in the integrated logistics management platform, which performs intelligent scheduling optimization on the waybill scheduling and on-site scheduling operations in the factory area. The system forms an organic whole with various logistics systems by realizing business collaboration and efficient integration with various internal logistics systems. The system receives contract order data from the integrated logistics management platform, and obtains basic data such as carriers, delivery points, arrival points, and capacity resources; and releases the waybill formed by intelligent transportation optimization scheduling to the integrated logistics management platform. The system is integrated with related IoT devices at the delivery points of each factory, including the park access control system (license plate recognition), large-screen display system, and voice call system, to support on-site job scheduling and management at the delivery points of the factory.

The intelligent logistics optimization dispatching system invokes the intelligent transportation dispatching algorithm. According to the contracts pushed by marketing batches, multiple intelligent stowage plans can be automatically generated through one-click dispatching. Each plan includes the number of contracts, the number of shipments, and the total transportation cost. , transportation mileage and other key information elements, it is convenient for the dispatcher to choose the appropriate stowage plan, as shown in Figure 2.

The system also supports manual fine-tuning of the intelligent stowage scheme. Each loading line shows the transportation line and the number of consolidation in a graphical way, as shown in Figure 3, which is convenient for the carrier to plan and arrange vehicle transportation.

After the system generates an intelligent stowage plan with one click, the dispatcher selects a suitable stowage plan and releases it to the carrier's dispatcher for vehicle dispatch confirmation, as shown in Figure 4. The carrier checks the relevant stowage plan of the unit, confirms the stowage plan or gives feedback on abnormal situations. Arrange vehicles and drivers according to the requirements of the model, and automatically send a message reminder to the driver. After the carrier confirms the vehicle scheduling, the system will automatically generate a complete transportation load list, and enter the intelligent reservation queuing system for transportation and delivery.

According to the order data of a tobacco company in 2017 (2017.2-2017.11) and the distribution of commercial company warehouses, all the waybills of A, B, and C cigarette factories were compared and analyzed. Using commercial company data, transport capacity data, and algorithm parameters as input data to solve the problem through the LIO intelligent evolution algorithm, compare and analyze the LIO scheduling scheme with the manual scheduling scheme, and compare the total logistics costs and total mileage of the two to verify the LIO intelligent scheduling Algorithm effectiveness.

For the whole year of 2017 (January-December), a certain tobacco company spent about 260 million yuan on cigarette transportation, including 190 million yuan on self-produced cigarettes and about 70 million yuan on cooperatively processed cigarettes. Among the transportation costs of self-produced cigarettes, cigarette factory A accounted for the highest cost of 36.4%; B and C accounted for 31.9% and 31.8% respectively. The actual comparison uses the order data in 2017 (2017.2-2017.11). The transportation cost of self-produced cigarettes is about 143 million yuan, the A cigarette factory is about 56.56 million yuan, accounting for about 40% of the highest, and the B cigarette factory is 41.55 million yuan. , accounting for 29%, C cigarette factory is 44.8 million, accounting for 31%.

Comparing and analyzing the results of LIO intelligent optimization algorithm and manual dispatching, because the transportation during the zero-hour operation period is relatively special, the data was preprocessed and the waybills in January and December 2017 were excluded in two special time periods. The analysis of the comparison results is shown in the following table: Among them, the LIO solution saves more than 8.58 million yuan in logistics costs compared with the manual solution, which can reduce logistics costs by about 6.01% compared with February-November 2017; in addition, in terms of the mileage of the carrier, Compared with the manual dispatching plan from February to November 2017, it can reduce 2.48 million kilometers (9.22%). It can be seen that the LIO intelligent scheduling algorithm can not only effectively reduce the logistics cost, but also reduce the total mileage of the carrier.

Table 2: Comparison of LIO scheme and manual scheme

Table 3 Comparison Results

cost comparison reduce the quantity Reduce percentage % Shipping cost comparison (yuan) 8582444.59 6.01 Mileage comparison (km) 2479978.775 9.22

This embodiment closely revolves around the current situation of industrial cigarette transportation and delivery scheduling, uses theoretical foundations such as operations research, intelligent optimization algorithms, and data mining, adopts qualitative and quantitative methods, and uses mathematical modeling, algorithm design, and system factories as means , carry out research and practice on transportation scheduling and other businesses, transform theoretical research results through information technology, and develop and implement intelligent transportation scheduling systems. The intelligent transportation scheduling system automatically selects the optimal loading and transportation route for the order, and generates a transportation loading plan with one click, thereby forming an integrated and intelligent operation of logistics scheduling and processing, which will greatly improve logistics efficiency and reduce costs.

A China Tobacco finished cigarette delivery schedule was carried out as a pilot operation. Through the intelligent scheduling optimization research based on the LIO intelligent evolution algorithm, the following results were achieved:

1) Reduce transportation expenses caused by unscientific and reasonable transportation scheduling and stowage, and reduce the annual freight cost by 1 to 2 percentage points.

2) Through operations research theory and intelligent algorithm research, solidify the dispatching rules into the system, reduce the dependence of transportation dispatching on manual experience, and reduce the influence of human factors on the quality of dispatching results.

3) Greatly improve the efficiency of transportation scheduling, further improve the logistics response speed, the scheduling work of several hours a day can be reduced to a few minutes, saving a certain amount of labor costs.

The LIO intelligent evolutionary algorithm is designed for the industry characteristics of industrial tobacco logistics. It is different from the common logistics optimization software (mostly commercial solvers) in the market. It is aimed at the logistics characteristics of the tobacco field, combined with the specific constraints of industrial enterprise cigarette transportation and delivery scheduling, Based on the analysis of logistics big data, a set of data-driven intelligent scheduling algorithms independently developed and designed. This intelligent scheduling algorithm is different from the classic operational research optimization technology adopted by commercial solvers, but is based on the latest data mining and evolutionary learning technology in the field of artificial intelligence. It is an intelligent scheduling technology with autonomous evolution and deep learning capabilities, which has reached the domestic and international level. leading level. In addition, the LIO intelligent evolutionary algorithm is also embedded with many engineering optimization technologies to further ensure that even in the face of massive scheduling tasks, fast calculations can be completed within minutes, and the solution speed far exceeds that of manual and common commercial solvers. Come super efficient.

In the preliminary planning and design stage, fully considering the industry promotion ability of the project results, the expansion space is reserved for the intelligent optimization scheduling system to ensure its high flexibility and adaptability, so as to achieve basic data configuration and simple parameter constraints. It can be efficiently applied and promoted in other industrial enterprises in the industry through adjustment.

Due to the limitation of time and research methods, some issues have not been studied in depth, and will be further studied in the future, mainly including:

(1) Currently, the intelligent transportation scheduling algorithm optimization model established by the present invention only fully considers the static constraint conditions, and does not fully consider the dynamic constraint conditions.

(2) The model established by the present invention is based on actual problems, but there are still some ideal factors in the modeling process, which need to be verified and continuously improved in combination with actual business operations.

It should be noted that in this article, relational terms such as first and second are only used to distinguish one entity or operation from another entity or operation, and do not necessarily require or imply that there is a relationship between these entities or operations. There is no such actual relationship or order between them. Furthermore, the term "comprises", "comprises" or any other variation thereof is intended to cover a non-exclusive inclusion such that a process, method, article, or terminal equipment comprising a set of elements includes not only those elements, but also includes elements not expressly listed. other elements identified, or also include elements inherent in such a process, method, article, or end-equipment. Without further limitations, an element defined by the words "comprising..." or "comprising..." does not exclude the presence of additional elements in the process, method, article or terminal device comprising said element. In addition, in this article, "greater than", "less than", "exceeding" and so on are understood as not including the original number; "above", "below", "within" and so on are understood as including the original number.

Although the above-mentioned embodiments have been described, those skilled in the art can make additional changes and modifications to these embodiments once they know the basic creative concept, so the above-mentioned are only the implementation of the present invention For example, it is not intended to limit the scope of patent protection of the present invention. Any equivalent structure or equivalent process transformation made by using the description and drawings of the present invention, or directly or indirectly used in other related technical fields, is also included in this patent. Inventions within the scope of patent protection.

references

[1] Hu Hongchun, Wu Yaohua, Liao Li. Optimization and application of logistics distribution vehicle routes [J]. Journal of Shandong University (Journal of Engineering), 2007 (8): 112-117.

[2] Wang Yong, Chi Jie, Fan Jianxin. Research on optimization of tobacco logistics distribution area division based on genetic algorithm [J]. Journal of Chongqing Jiaotong University (Natural Science Edition), 2009, 28(3):619-621.

[3] Binghuo, Hemu. On the logistics construction of the tobacco supply chain [J]. Chinese Journal of Tobacco, 2014, 20(2).

[4] Xu Zhi, Chen Jun, Tang Ping. Research and Implementation of Dynamic Route Optimization and In-transit Monitoring of Cigarette Retail Logistics [J]. Chinese Journal of Tobacco, 2014 (02): 71-73.

[5] Huang Gewen, Cai Yanguang, Tang Yalian. Design and Implementation of Tobacco Logistics Transportation Scheduling System Based on Cloud Computing [J]. Industrial Control Computer, 2015, 22(10): 114-117.

[6] Zhang Huimin. Research and Application of Logistics Route Optimization in Tobacco Commercial System [J]. Chinese Tobacco Journal, 2018, 24(3).

[7] Tao Yinqiang, Niu Huimin. Model and algorithm for multi-vehicle and multi-cost vehicle routing problem with time window [J]. Transportation System Engineering and Information. 2008(01).

[8] Shi Chaochun, Wang Xu, Ge Xianlong. Research on Vehicle Scheduling Problem with Multiple Distribution Centers with Time Window. Computer Engineering and Application. 2009(34).

[9] Wang Zheng, Hu Xiangpei, Wang Xuping. Interference Management Model and Algorithm for Delivery Vehicle Scheduling under Travel Time Delay [J]. System Engineering and Theory Practice. 2013(02).

[10] Ma Yuhong, Yao Tingting, Zhang Haoqing. Multi-distribution center multi-model vehicle scheduling problem based on partition and genetic algorithm design [J]. Science and Technology Herald. 2013 (02).

[11] Sun Zhuangzhi, Yan Liehu, Yao Xuewei. Cigarette distribution scheduling system based on route optimization algorithm [J]. Chinese Journal of Tobacco, 2014, 20(05): 128-133.

[12] Xiao Zhengzhong, Tan Jian, Zhou Yufeng, Zeng Jun. Research on intelligent optimization of vehicle dispatching in cross-regional multi-distribution centers [J]. Chinese Tobacco Journal, 2017, 23(04): 114-120.

[13] Li Mingyu, Liang Liping, Lu Yanxia. Vehicle Routing Problem Model Based on Improved Tabu Search Algorithm [J]. Highway Traffic Science and Technology, 2017, 34(10): 108-114.

[14] LIU F H, SHEN S Y. The Fleet Size and Mix Vehicle Routing Problem with Time Window [J]. Journal of the Operational Research Society, 1999, 50(7):721-732.

[15]DULLAERT W, JANSSENS G K, S RENSEN K, et al. New Heuristics for the Fleet Size and Mix Vehicle Routing Problem with Time Windows[J]. Central European Journal of Operations Research, 2007, 15(4):351-368.

[16] Adelzadeh, M., Asl, V.M., Koosha, M.A Mathematical Model and a Solving Procedure for Multi-depot Vehicle Routing Problem with Fuzzy Time Window and Heterogeneous Vehicle [J]. Manuf. Technol. 2014, 75, 793–802.

[17] He-Yau Kang, Amy H.I.Lee. An Enhanced Approach for the Multiple Vehicle Routing Problem with Heterogeneous Vehicles and a Soft Time Window [J]. Symmetry, 2018(10).

[18]K.Helsgaun,An Effective Implementation of the Lin-KernighanTraveling Salesman Heuristic.European Journal of Operational Research,126(1):106-130(2000).)

[19] Battarra, Maria, Stefano Benedettini, and Andrea Roli. "Leveraging saving-based algorithms by master–slave genetic algorithms." Engineering Applications of Artificial Intelligence 24.4(2011):555-566.

Claims (8)

1. industrial cigarette transports intelligent dispatching method, which comprises the following steps:

Step 1: building commercial company collection V (V={ 2,3 ... i ... j ..., n }), each commercial company commercial company collect in, Formula is expressed as i ∈ V or j ∈ V, delivery point is indicated with 1, delivery point and commercial company's union V₀(V₀=V ∪ { 1 }), construct nothing To connected graph G=(V₀, E), E is the side of every two node i and jCalculate transport The minimum single-point freight of all commercial companies and/or spelling carry freight；

Step 2: calculating the pairing priority of commercial company, under the premise of meeting spelling load reasonability constraint, successively fusion is related Two paths of connection, complete the building of scheduling scheme；

Wherein, the pairing priority calculation formula of commercial company is as follows:

dist_maxFor farthest operating range in marketing contract, d_maxMost to reformulate list in marketing contract；It Wei not match Priority；

Step 3: it repeats step 2 and is finished until all commercial companies configure, obtain feasible schedule scheme,

Step 4: initial scheme optimization being carried out using the double-deck local searching strategy, is made most while not increasing industrial enterprise's expenditure It may be decreased carrier transport expense；

Step 5: spelling load scheme based on above-mentioned commercial accounts, access order is optimized using LKH algorithm, is meeting time window Under the premise of, reduce common carrier total kilometres.

2. industry cigarette according to claim 1 transports intelligent dispatching method, which is characterized in that in step 1, calculate fortune The minimum single-point freight of defeated all commercial companies and/or spelling carry freight, and specific step is as follows:

It is defined as follows decision variable:

Wherein i ∈ V, j ∈ J_k, j ∈ M, k ∈ K, K={ 1,2 ..., m } are vehicle collection, and building cigarette transportation dispatching method is as follows:

Minimize:

s.t.

a_i≤T_i≤b_i,i∈V (10)

Wherein, freight is transported and is spelled the defeated two classes valuation expense of carrying by single-point and collectively constitutes:

The expense of single-point transport:

Spell the defeated expense of carrying:

Formula (1) ensures that every client can and be only capable of being accessed by a vehicle；

Formula (2) regulation from delivery point each type of vehicle fleet size without departing from the type quantity；

Formula (3) ensures that supplier's material number of packages total amount of each car service does not exceed maximum carrying number of packages；

Formula (4) ensures that supplier's weight of material total amount of each car service does not exceed maximum load capacity；

Connectivity constraint of the formula (5) between commercial company；

Passability constraint of the formula (6) between vehicle and commercial company；

Formula (7) is that subpath eliminates constraint；

Formula (8) statement vehicle all originates and terminates at delivery point, and each car will return to delivery point；

Formula (9) is the temporal expression that vehicle reaches each client；

Formula (10) is commercial company's time windows constraints；

Formula (11) and (12) are model Boolean Decision variable；

By the above method, target is to transport the cost minimization of all commercial accounts, that is, ensures single-point transport and spell carrying Defeated two classes freight summation is minimum, wherein the tonnage of guaranteeing the minimum of single-point transport is q1, spell the defeated tonnage of guaranteeing the minimum of carrying be q2. by In q2 < q1., order (the i.e. d scrappy to commercial company under the premise of meeting model constraint_j< q2) it carries out spelling carrying contribute maximization Reduce industrial cigarette transportation cost；

Wherein, d_jThe total number of packages of commercial company's material, w_jFor commercial company's weight of material, D_kVehicle k maximum carries number of packages, W_kVehicle k Maximum load capacity, N_kVehicle k maximum available,Vehicle k may have access to commercial company's connectivity parameters, dist_1jDelivery point To the true operating range of different commercial companies, dist_i,jTrue operating range, c between different commercial companies_jDelivery point arrives different quotient The transport unit price of industry company, a_ijConnectivity parameters between commercial company, u_jCommercial company's j unloading time, [a_j,b_j] business public affairs Department j hits column time window the latest, and there is the limitation of arrival time the latest in each commercial company, therefore each commercial company has it corresponding Time window [a_j,b_j] the previous a of time window_jThe earliest start time of vehicle service commercial company j is defined, it is general without stringent limit System；Next b_jDefine the late finish time of vehicle service commercial company j.

3. industry cigarette according to claim 2 transports intelligent dispatching method, which is characterized in that consider share-car limitation, draw Enter connectivity a between commercial company_ij, the measurement a of connectivity between commercial company_ij, it is Boolean variable, connection is allowed to be set as 1, Otherwise it is set as 0, a of connectivity between the commercial company_ijRefer to that commercial company's arrival warehouse in region is spelled in route to carry above Whether it is connected to, determine that there are two types of situations for connectivity between commercial company: situation is first is that commercial company V_iWith V_jOnce it appeared in same Waybill data, i.e. common carrier historical behavior receive the two and spell load, can be considered that commercial company is connected at this time；Situation two, commercial company V_iWith V_jSame waybill had not been appeared in, new commercial company is such as set or has not appeared in same contract pond, based on classics Saving algorithm and sweep algorithm, are considered as with maximum angle by the maximum distance received based on common carrier history and are connected to threshold value Determined, specific as follows:

1) every waybill indicates that a paths, i.e. carrier transport route spell commercial company and carry sequence in history waybill data: Route={ 1, V_i,V_j..., 1 }, V_iWith V_jBetween geographic distance be dist_ij, azimuth (Azimuth angle) is azim_ij；

If 2) V_iWith commercial company V_jWaybill contract set is dispatched with same history is once appeared in simultaneouslyIn, that is, it is public to regard this business It is connection between department, a can be set_ij=1；

3) it is based on history waybill connectivity, counts each commercial company V_iFarthest connection distanceAnd its largest connected azimuth

If 4) commercial company V_jBefore not with V_iIn same waybill, but its geographic distance is less than V_iHistory be farthest connected to distanceAnd azimuth is less than the largest connected azimuth of historyThen judge the two connectivity also It is 1；

5) circulation above-mentioned steps are finished until the connection sex determination of each commercial company, form connectivity basic data matrix.

4. industry cigarette according to claim 1 transports intelligent dispatching method, which is characterized in that in step 2, pairing is preferential In the calculating process of grade:Two commercial company V_iWith V_jBetween operating range dist_ijIt is shorter, Match priorityIt is higher, wherein dist_1i,dist_j1Respectively delivery point arrives commercial company V_iAnd V_jTrue operating range；

When the weight mean value of commercial company is smaller, priority is matchedIt is higher, wherein d_i,d_jRespectively For the order weight of commercial company i, j, q₁Tonnage of guaranteeing the minimum is transported for single-point；

It is higher to spell mounting reliability, matches priorityIt is higher, whereinRefer to spelling mounting letter Degree, value range are 0~1；

It is as follows to spell load reasonability constraint premise:

Commercial company i and j are not appeared in simultaneously on the path of prestowage, i.e. at least 1 non-prestowage of point；

Non- prestowage commercial company i is not appeared in the path of prestowage on point, i.e., with loading point must on having arranged path with Cigar mill is connected directly；

The order weight of non-prestowage commercial company i is not greater than the residual capacity of path vehicle to be fused；

The fusion of non-prestowage commercial company i is there is not allowed that the delay of other commercial company's arrival times；

The path points of new prestowage must not exceed maximum can prestowage points；

The total logistics weight in path of new prestowage must not exceed corresponding commercial company's maximum and can pass through vehicle；

The path of new prestowage must satisfy connectivity constraint.

5. industry cigarette according to claim 1 transports intelligent dispatching method, which is characterized in that pass through commercial company V_i's Route, will be with greater probability and commercial company V_jIt spells and carries, that is, exist and spell load correlation ruleThe spelling loads reliabilitySteps are as follows for calculating:

Common carrier is per the marketing contract transported day by day are as follows: contract={ V₁,V₂,…,V_i,…,V_n}；Every in its history waybill Waybill record is that the spelling of commercial company carries sequence: route={ 1, V_i,V_j..., 1 }, it is its marketing which, which carries sequence route, The non-empty subsequence of contract；

Each spelling mounting reliability spelled and carry its 2- item collection correlation rule in sequence is calculated one by one: being spelled and is carried ruleConfidence level ForHistory is defined as to spell in load sequence comprising commercial company < V_i,V_j>number with only comprising<V_i> number The ratio between；Pay attention to spelling from history in load scheme and exclude only comprising commercial company V_iDate market contract, avoid because of V_jContract lack It loses and influences commercial company V_iSpelling carry confidence calculations；

Circulation above-mentioned steps calculate every and spell the 2- item collection for carrying sequence route, and the symmetry of attention rule is apparent from's It spells mounting reliability and is equal to ruleSpelling load reliability, can save spell mounting reliability calculation amount,

Correlation ruleSpelling mounting reliability value range be number between 0~1.

6. industry cigarette according to claim 1 transports intelligent dispatching method, which is characterized in that step 4 is specific as follows:

It recycles to single-points all in feasible solution and executes following search strategy lower than the route for tonnage of guaranteeing the minimum:

First layer local search: based on mileage sequence is saved, which is inserted into other best saving mileage lines for meeting constraint Road, if success, jumps out the local search of this layer；If unsuccessful, continue second layer local search；

Second layer local search: based on mileage sequence is saved, other commercial company warehouse insertions for spelling load route are not spelled this time Carry route, while all kinds of constraints of non-breakable former route.

The spelling of aforementioned acquisition carries sequence route, and each sequence is a feasible solution.

7. industry cigarette according to claim 1 transports intelligent dispatching method, which is characterized in that LKH algorithm detailed process It is as follows:

1) load scheme is spelled for the client obtained, obtains its access path；

2) finding out all in access path in collection is collection S while cancelling empty, and all outside access path in collection is collection while supplementing empty；

3) i=1 is enabled, empty selects a line in collection S and while supplementing empty in collection E from wait cancel at random；

4) be continuously increased i, and constantly random selection meet access path constraint it is new wait cancel it is empty while and newly divide while supplementing empty Jin Ru not be empty in collection S and collection E while supplementing empty wait cancel, until it is lower and meet the visit of time windows constraints to obtain mileage travelled It asks the way diameter, and turns 3) until the side of no non-selected mistake.

8. industrial cigarette transports intelligent dispatching system, which is characterized in that including transportation dispatching unit, spot dispatch unit, basis Data Management Unit, transport capacity resource administrative unit, Internet of Things applying unit and report display unit, the transportation dispatching unit obtain The data of Data Management Unit and transport capacity resource administrative unit are taken, call intelligent vehicle scheduling algorithm according to marketing batch push Contract automatically generates multiple intelligent prestowage schemes in such a way that a key is dispatched, and each scheme includes contract number, fortune The key messages elements such as single number, total Transportation Expenditure, transport mileage, and the prestowage scheme of generation is sent to spot dispatch list Member facilitates dispatcher to select suitable prestowage scheme, while prestowage scheme is sent to common carrier by Internet of Things applying unit, And vehicle scheduling confirmation or abnormal conditions feedback are carried out by common carrier dispatcher, vehicle requires to arrange vehicle and driver, and automatic Prompting message is sent to driver, after common carrier carries out vehicle scheduling confirmation, system automatically generated completely transports prestowage list, enters Intelligent reservation queuing system carries out transport delivery.