In addition to Weibo, there is also WeChat
Please pay attention
WeChat public account
Shulou
2025-02-23 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Internet Technology >
Share
Shulou(Shulou.com)06/02 Report--
What is the heuristic method to construct the initial solution of CVRP problem? aiming at this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.
Today, the editor will introduce a heuristic method for constructing CVRP (capacity-constrained vehicle routing problem). For those who don't know much about CVRP problem, you can take a look at VNS (variable neighborhood search algorithm) to solve CVRP problem. First of all, let's talk about the idea of constructing a heuristic method for the CVRP problem. The most famous method is the saving algorithm proposed by Clark and Wright in 1964.
Here we take the c102 example of solomon as an example to explain.
Suppose the number of customers is n, and the capacity of each car is 20050 represents the distribution center.
The following editor introduces this classic heuristic method in detail.
Step1: suppose there are n cars, each serving only one customer, so there are n independent circuits.
Then it is calculated that customer I and customer j are merged into one path, and the reduction of distance is the so-called saving value:
Find out which two customers I and j correspond to the maximum savings, and then merge customer I and customer j into one path, as shown in the following figure
Step2: when there are two customers on a path, such as 0120 in the figure above, and when you want to integrate a customer I on an unintegrated path into the path, there are three insertion positions, namely, 0i120, 01i20 and 012i0. The savings of these three cases need to be calculated. If there is only one customer on a path, the savings can be calculated like the above method.
Step3: when the total demand of all customers on a path exceeds the capacity of the car, it is necessary to open up a new path, then calculate the savings again according to step1 and step2, and then merge the paths until all customers are assigned to vehicles to deliver goods. The algorithm is STOP.
The answer to the question about what is the heuristic method for constructing the initial solution of the CVRP problem is shared here. I hope the above content can be of some help to you. If you still have a lot of doubts to be solved, you can follow the industry information channel for more related knowledge.
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.
Views: 0
*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.
Continue with the installation of the previous hadoop.First, install zookooper1. Decompress zookoope
"Every 5-10 years, there's a rare product, a really special, very unusual product that's the most un
© 2024 shulou.com SLNews company. All rights reserved.