Description of Greedy Best Insertion

Greedy best insertion is a simple, but useful algorithm to generate initial solutions to Tabu Search. Due to its directed randomness nature, it is especially useful for multi-run heuristics. The implementation can be found here and its inner workings here.

With a randomized sequence, it inserts the nodes one by one in the most optimal location.

• Its run-algo implementation calls get-best-insertion-move and performs it on the problem object to build up the solution.

• get-best-insertion-move returns an insertion-move as defined in algo/tools.lisp. The best move includes the best vehicle and the best location in that vehicle's route. For the latter, it calls get-best-insertion-move-in-vehicle.

• get-best-insertion-move-in-vehicle generates-assess-selects insertion-moves given a node-id and vehicle-id. It returns an insertion-move with the best index.

• as it implements assess-move, it will call the :around method of assess-move as defined in the iterator, which checks for feasibility of the move by calling feasible-movep, which is defined in algo/tools.lisp.