## 4 Metaheuristic Solution
### Additional Optimization Process  
The additional optimization process (AOP) is executed depending on the repetition frequency coefficient. It was found empirically that the best values of the repetition frequency vary from 5 to 10; values lower than 5 mean faster convergence to a locally optimal solution. AOP is applied only for the best solution found within an iteration (see phase 1 in Figure 2) in order to further improve the solution, which is then used for updating the pheromone trails (see phase 3 in Figure 2). AOP is a deterministic approach which incorporates two independent steps as follows:  
* Single route optimization (SRO),
* Mutual routes optimization (MRO). SRO is launched for each route separately. It is based on the consecutive identification of nodes to be exchanged within every route. As a result of the exchange, a new solution is created and evaluated. If it surpasses the original solution, the new solution replaces the original. This process is shown in pseudocode in Algorithms 1. Variable \(n\) represents the number of nodes to be replaced. It starts from 1 and continues to \(n_{max}\); it was found empirically that \(n_{max}\) does not have to be bigger than 2. If \(n>1\), then \(n\) successive nodes are selected. In this way, all possible combinations of \(n\) successive nodes are removed and placed to all different possible positions on the route. Figure 2: Flowchart for the ACO algorithm. The principle is illustrated in Figure 3 in an example with 50 nodes and 4 vehicles. The lengths of individual routes are displayed. Figure 3a shows the situation before the SRO. The nodes identified for exchange are indicated on the blue route. Figure 3b shows the situation after the SRO, where these nodes are replaced on the routes, i.e., the order of nodes to be visited by the vehicles is changed. As a result, the quality of this new solution was improved from 138.65 to 123.42. While the SRO finds a better solution by replacing nodes belonging to the same route, MRO incorporates a similar process for nodes from different routes. During this process, nodes to be transferred from one route to another are identified for every combination of pairs of routes. This process is shown in pseudocode in Algorithms 2. It is executed independently for all possible pairs (combinations) of routes. The principle of MRO is illustrated in Figure 4. It uses the solution obtained after SRO was applied (see Figure 3b). In Figure 4a, nodes identified for removal from the blue and azure routes are emphasized. These nodes are then inserted into the red route. Consequently, the quality of this new solution was further improved from 123.42 to 117.78. Figure 3: Single route optimization principle. (**a**) Before SRO (**b**) After SRO. Each newly created route in the SRO process replaces the original, provided that the new route is better than the original, i.e., its length is shorter according to Formula (3). \[L_{new}^{i}<L_{orig}^{i}, \tag{3}\]  
where \(L_{orig}^{i}\) is the length of the original route, \(L_{new}^{i}\) is the length of the newly created route, \(i\) identifies a route in the solution (\(i=1\) to \(M\) where \(M\) is the number of vehicles/routes). In the MRO process, the acceptance criterion depends on the type of problem. For MDVRP, when the total distance is minimized, the two newly created routes influenced by the process replace the originals when either Formula (4) or (5) are satisfied. The choice of formula depends on the setting of the algorithm. For M-MDVRP, when the longest route is minimized, Formula (6) must be satisfied. \[L_{new}^{i}<L_{orig}^{i}\text{ and }L_{new}^{j}<L_{orig}^{j}, \tag{4}\]  
\[L_{new}^{i}+L_{new}^{j}<L_{orig}^{i}+L_{orig}^{j}, \tag{5}\]  
\[\max(L_{new}^{i},L_{new}^{j})<\max(L_{orig}^{i},L_{orig}^{j}), \tag{6}\]  
Figure 4: Mutual routes optimization principle. (**a**) Before MRO (**b**) After MRO.