Savings algorithm

from Wikipedia, the free encyclopedia

The operations research describes a heuristic solution method in route planning as the savings algorithm (also known as the savings algorithm , the savings heuristic or the savings heuristic) . The method, first published in 1964 by Clarke and Wright, is one of the most widely used in practice.

The heuristic tries to come as close as possible to the shortest path between a starting and ending node and various intermediate nodes ( problem of the traveling salesman ). The solution can serve as a starting solution for further improvement processes , such as the k-opt heuristics .

With the savings algorithm, route formation and sequence determination take place simultaneously within the routes. A distinction can be made between two versions of the procedure: a parallel and a sequential procedure.

algorithm

A symmetrical distance matrix is ​​one of the prerequisites for the algorithm.

  1. Connect each node (customer) to the exit node (depot) via a back and forth edge (path); there are commuting tours.
  2. For all possible combinations, loosen a back and a back edge and connect the two knots with an edge.
  3. Evaluate all savings made in step 2 accordingly
  4. Sort all savings in descending order.
  5. Connect the two nodes that have the best remaining saving and at least one edge to the starting point.
  6. Repeat step 5 as long as there are still more than two edges to the starting point.
  7. If there are only two edges to the starting point, a solution is achieved.

example

Savings through the savings algorithm

This example illustrates the calculation of the savings through the saving algorithm. In the graphic opposite, i and j represent the customers and 0 the depot. The way to i costs 5 units each, the way to j costs 7 units. The way between i and j costs 3 units.

Now you calculate the possible savings for all customer pairs (in this case only one):

In this case, merging the two tours results in savings of 9 units from the graph on the left. If there are several pairs of customers, the next step is to arrange the pairs in descending order according to the possible savings and then start to combine the tours at the top.

Individual evidence

  1. ^ G. Clarke, JW Wright: Scheduling vehicles from a central delivery depot to a number of delivery points. In: Operations Research Quarterly. Volume 12, 1964, pp. 568-581.
  2. ↑ Leena Suhl, Taieb Mellouli: Optimization systems: models, processes, software, applications. 2., revised. Edition. Springer, 2009, ISBN 978-3-642-01579-3 , p. 256.
  3. ↑ Wolfgang Domschke: Fundamentals of business administration: An introduction from a decision-oriented point of view. 4th, verb. u. updated edition. Springer, 2008, ISBN 978-3-540-85077-9 , pp. 171f.
  4. ↑ Michael Neubert: Vehicle Routing. (PDF; 395 kB). Proseminar Efficient Algorithms, TU Chemnitz p. 10.

literature

  • G. Clarke, JW Wright: Scheduling vehicles from a central delivery depot to a number of delivery points. In: Operations Research Quarterly. Volume 12, 1964, pp. 568-581.

Web links