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

This article introduces the relevant knowledge of "how to realize the Column Generation algorithm of JAVA VRPTW relaxation model". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

The first version comes from GitHub and was written by a foreign god named Seminar.

His sub-problem uses the model introduced in the previous tweet to find the shortest path to reduced cost, and you only need to change the path of the example file in the following file.

The intermediate results of the run are as follows:

-Iteration: iterations

-SbTime: sub-problem solving time (s)

-Total path in nPaths:Master Problem

-MP lb:Master Problem's linear relaxation optimal solution. Because of the modeling method, the optimal solution counts the service time as the path distance, and finally subtracts 9000 to get the path distance.

-SB lb: the linear relaxation optimal solution of the subproblem.

-SB int: the integer optimal solution of the subproblem.

For the maximum time limit for solving the subproblem (s), you can set it in the following file:

The second version is written in small:

Description of running parameters:

-in: example file path

-out: output of the result file.

For example:

[- in input\ Solomon\ 100_customer\ C101.TXT-out output\]

For parameter settings, please find the following main running file:

Right-click to find the running settings to configure. (by default, enter the above parameters to run directly)

Intermediate result:

-Iteration: iterations

-SbTime: sub-problem solving time (s)

-Total path in nPaths:MasterProblem

-the linear relaxation optimal solution of MP lb:Master Problem.

-SB lb: the optimal solution of the sub-problem.

For the first version, the subproblem modeling method still depends on the dual variables of the main problem, as follows:

Where t_ij is the original cost,pi of each edge is the dual variable of Master Problem. This is how each iteration updates the cost of the sub-problem and remodels the solution.

About the editor's version:

The cost in the ESPPRC problem is updated at each iteration, and then the pulse algorithm is run to re-solve it.

This is the end of the content of "how to implement the Column Generation algorithm of JAVA VRPTW relaxation model". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.