Notes on algorithm implementation¶

1. Greedy Solution¶

The greedy algorithm simply starts with the closest node from the depot, adding it to the first vehicle’s route, reducing the load on the vehicle by the demand of the node.
The algorithm begins using the next vehicle as soon as the next node’s demand exceed the load on the vehicle.

Note

Run on each vehicle separately.
For all the nodes in a given vehicle’s route, the search is restricted to the selected vehicle’s route.
The move as defined here is an move & insert operation. The first node selected is removed from its current position and inserted immediately in front of the second node.

An initial feasible solution is created.
The local search algorithm is run on each vehicle separately.
For each vehicle, the algorithms iterates over every node in its route and attempts to place it at each possible position within the route of the selected vehicle.
The optimal move (the move that causes the greatest reduction in cost) is implemented.
This continues until the reduction in cost is non-negative.

Note

Search not restricted to selected vehicle’s route.
The move as defined here is an move & insert operation. The first node selected is removed from its current route and inserted into the route of the second node, immediately in front of the second node.

An initial feasible solution is created.
The local search algorithm is run on all the vehicles collectively.
The algorithms iterates over every node in every vehicle’s route and attempts to place it at each possible position within the routes of all the vehicles.
The optimal move (the move that causes the greatest reduction in cost) is implemented.
This continues until the reduction in cost is non-negative.

An initial feasible solution is created.
The local search algorithm is run on all the vehicles collectively.
The algorithms iterates over every node in every vehicle’s route and attempts to place it at each possible position within the routes of all the vehicles.
If the move is tabu then the move is not considered; however if making the move reduces the cost of the solution such that it is lower than the best cost seen so far, the move is made.
This allows the solution to once again accept moves that increase the cost of the solution, allowing the algorithm to explore a larger section of the solution space and not get stuck in a local minima.
The optimal move (the move that causes the greatest reduction/least increase in cost) is implemented.
The new links formed are added to the tabu list, preventing the newly formed links from being broken for a number of iterations (the size of tabu list is constant, so this translates to number of times a non tabu move is made).
The search stops if there are no possible moves.
This continues for a set number of iterations.

Note

The implementation of the genetic algorithm attempts to keep to its biological analogy
Each node is a nucleotide pair.
A possible solution is a chromosome and iterator pair.
A chromosome contains all the nodes in the order they are visited. It’s corresponding iterator vector is the vector containing the indices at which the chromosome is split into vehicle routes.
The vehicle routes as split by the iterator vector, and are each referred to as a gene.
If there is a node missing in the initial solutions, the algorithm will go into an infinite loop in the HGreXCrossover() function. This can happen if using the GenerateGreedySolutions() function. A check is set up to exit should this be the case.
While the MakeValid() function ensures an order of nodes visited is valid if it is possible, there is still the possibility that the ordering is not feasible. In this case the final solution might be invalid.
The main crossover operator implemented is the Heuristic Greedy Crossover (HGreX).
Reference for operator selection: Puljic, K. & Manger, R. (2013). Comparison of eight evolutionary crossover operators for the vehicle routing problem. Mathematical Communication, 18, 359–375

Initial solutions are created (random and greedy heuristic).
For a given number of generations various operators are applied to the chromosomes randomly.
Each operator is triggered with a set probability, and randomly selects the chromosome/iterator on which to apply said operator (Both the chromosomes and iterators have distinct operator functions).
The number of chromosomes is maintained as constant, removing higher cost solutions (see documentation of functions for details).
The best solution is chosen and converted to the standard form of the solution.

Note

The move as defined here is a move & insert operation. The first node selected is removed from its current route and inserted into the route of the second node, immediately after the second node.
Given that this algorithm chooses 2 random nodes and attempts insertion, it works well only for smaller problems. Changing it to choose its moves with some heuristic, or in a manner similar to local search would improve its efficiency significantly.

An initial feasible solution is created.
Two vehicles are chosen at random.
A node within each of them is also chosen at random.
The move is made if the cost of the solution decreases or based on a probability calculated based on the temperature of the solution.
A higher temperature allows a greater chance of moves increasing the cost of the solution to be accepted.
The temperature is reduced after every iteration using a geometric progression.
If the solution does not improve (is stagnant) over a number of iterations (stag_limit) a reheat operation is performed, increasing the temperature once again.
This allows the solution to once again accept moves that increase the cost of the solution, allowing the algorithm to explore a larger section of the solution space and not get stuck in a local minima.
The algorithm runs for a set number of reheats.

This refers to the possibility of using the code to run the algorithms sequentially on the same problem, using the final solution of one algorithm as the input/initial solution for the next.
The example at the end of main.cpp uses simulated annealing followed by local search.