Recently, many discrete algorithms have been proposed.

Optimization of enterprise distribution route based on saving algorithm. Structured query language

Optimization of enterprise distribution route based on scanning algorithm. Structured query language

Optimization of enterprise distribution route based on nearest insertion method. Structured query language

Mileage saving algorithm: The core idea of saving algorithm is to merge two cycles (0, …, i, 0) and (0, j, …, 0) existing in transportation problems into one cycle (0, …, i, j, …, 0). In the above-mentioned merging operation, the total transportation distance of the whole transportation problem will change. If the total transportation distance is reduced after the change, it means that the transportation distance is saved. The corresponding change value is called distance saving, as shown in the following formula.

Area scanning algorithm: The scanning algorithm is an algorithm of "grouping before routing". The so-called grouping is a set of points assigned to each car. A simple grouping method is to divide the coordinate plane with the distribution center as the origin into multiple sectors, initially assign the points of each sector to a car, and then expand the route. If there are still unallocated points after a route construction of "Grouping-Route", continue the procedure of "Grouping-Route". Repeat this process until all points are allocated.

Distance nearest interpolation algorithm: The nearest interpolation method is an algorithm proposed by Rosenkrantz and Stearns in 1977 to solve the TSP problem. The nearest insertion method is completed in four steps:

(1) Find the smallest node to form a sub-tour.

(2) Among the remaining nodes, find out the nearest node of a node in the ion circuit.

(3) Find an arc (i, j) in the sub-loop to minimize+-,then insert a node between nodes, replace the original arc (i, j) with two new arcs (i, k) and (k, j), and add the node to the sub-loop.

(4) Repeat steps (2) and (3) until all nodes are added to the sub-loop.

In this way, the sub-loop evolved into the solution of TSP.

Because the recent insertion method solves the problem of single-loop transportation, the VRP problem of multi-loop transportation can be solved by improving and modifying this method and increasing mileage limit and load limit.