Shulou(Shulou.com)06/01 Report--

Today, I will talk to you about VNS solving the CVRP problem = how to solve the problem. Many people may not know much about it. In order to make you understand better, the editor has summarized the following content for you. I hope you can get something according to this article.

The CVRP problem is a vehicle routing problem with limited capacity, which means that the capacity of each vehicle is limited. We set the goal of the problem, which is to minimize the total distance of the vehicle under the premise of using the least number of vehicles.

1.CVRP and Mathematical Model

1.1 description of vehicle routing problem with capacity

The vehicle routing problem with capacity constraints is described as follows: there is a parking lot, there are K vehicles, the maximum load of each vehicle is Q, these vehicles serve L customers, the demand of customer I is qi, each customer can be served by any car, but can only be served once by one vehicle, and each vehicle must return to the original yard after service. Its goal is to find a suitable vehicle scheduling scheme to meet the needs of customers while minimizing the transportation cost of vehicles.

1.2 Model of vehicle routing problem with capacity

The model of vehicle scheduling problem with capacity constraints is established: the distribution center (denoted by 0), the user number is 1PEM 2,... , L; the distribution center and the customer point are represented by points I and j, and the vehicle is represented by k; No. , k; the cargo demand of user I is qi,qi < Q; the transportation cost from I to j is Cij, wijk, which indicates the remaining capacity of vehicle K from customer I to customer j

Define decision variables

The mathematical model is as follows

The objective function (1) indicates that the total cost of vehicle operation is the lowest; formula (2) means that the goods transported by each vehicle do not exceed the maximum load; formula (3) guarantees that each customer will be visited; formula (4) and formula (5) guarantee that each customer can only be accessed by one car; formula (6) means that each car is fully loaded from the distribution center. Formula (7) indicates that there are enough goods on the car to supply the customer before entering any customer; formula (8) indicates the elimination of sub-loops; and formula (9) indicates the value range of the variable.

2.VNS solving CVRP problem

Different from the exchange operator and insertion operator used in the last tweet, this paper uses the reverse operator, that is, all the elements between the two positions are arranged in reverse order.

Because the goal of this paper is to minimize the total driving distance on the premise of using the least number of vehicles. The editor believes that the CVRP problem can still be regarded as another form of TSP problem. For example, for example, there are a total of 10 customers, each customer needs a loading capacity of {4 3 6 9 10 4 6 6 5 8 7}, and the loading capacity of each vehicle is 30, assuming that the initial customer order is 1 2 3 4 5 6 7 8 9 10. Then we can calculate the volume sum in turn, once the total volume is greater than 30, the customers are divided into a group, and each group of customers are picked up by one car. Therefore, the grouping is {4 369 | 10 464 | 8 7}, divided into three groups, and each group will pick up the goods in order. Therefore, the customer of the first car is {1234}, the second car is {567 8}, and the third car is {9 10}. Do the friends understand, but this is the opinion of the editor, although it can produce a good result, but whether this method is feasible or not, we still need the advice of our friends.

After reading the above, do you have any further understanding of VNS solving the CVRP problem = how to solve it? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.