## 2 The Heuristic Algorithms
### The Two-Step Algorithm: Constructive and Improvement (\(CH\_1 Pa\))
#### 2.1.1 \(Cha\): Constructive Heuristic  
\(CHa\) is designed to identify an acyclic path from an origin \(o\) node to a destination node \(d\) in which the sum of the arcs of the path is as close to zero as possible. This heuristic algorithm follows the scheme of the algorithm for determining the shortest path proposed by [PERSON] [21]. \(CHa\) is described in pseudocode in Algorithm 1. Looking at Algorithm 1, the reader can note that one of the differences with respect to [PERSON]'s algorithm is due to the extraction criteria of a node, as reported in line 9. In fact, we extract the lowest cost element in absolute value from \(Q\), where \(Q\) denotes the set of nodes not yet analyzed. In particular, the extraction of destination node \(d\) from \(Q\) (see again line 9 of Algorithm 1), is performed only if \(d\) is the only node with a non-infinite cost. This allows the procedure to update the predecessor of node \(d\) as many times as possible in order to try to improve the current solution. ```
1:\(Q\leftarrow\emptyset\)
2:for each node \(n\in N\)do
3:\(cost[n]\leftarrow\infty\)
4:\(prev[n]\gets NULL\)
5:\(Q\gets Q\cup\{n\}\)
6:endfor
7:\(cost[o]\gets 0\)
8:while\(Q\
eq\emptyset\)do
9:\(u\leftarrow\) node in \(Q\) with minimum \(|cost[u]|\)\(\triangleright\) (extract \(d\) from \(Q\) only if \(n^{\prime}\in Q/\{d\}:cost[n^{\prime}]<\infty\))
10:\(Q\gets Q\setminus\{u\}\)
11:for each neighbor \(n\) of \(u\)do
12:if\(n\in Q\)then
13:\(d\gets cost[u]+c_{im}\)
14:if\(|d|<|cost[n]|\)then
15:\(cost[n]\gets d\)
16:\(prev[n]\gets u\)
17:endif
18:endif
19:endfor
20:endwhile
21:return\(cost\),prev
```  
**Algorithm 1** CHa \((G(N,A),o,d)\). In our algorithm, we examine the set \(Q\) of nodes as reported in line 12 of Algorithm 1, only if it is still present in \(Q\) to avoid processing the same node several times. This is implicitly done in [PERSON]'s algorithm because if a node has already been extracted from \(Q\), it is not possible to reach it later with a lower cost. Finally, as reported in line 14 of Algorithm 1, in the cost path evaluation from the origin node \(o\), we compare the costs of reaching a node using the absolute value associated with the corresponding arc and select the minimum one. Just to give an example of \(CHa\), suppose to have to solve the \(CBPP\) from node 1 to node 6 of the graph reported in Figure 1. In the same figure are depicted two iterations of the algorithm. The first node selected from \(Q\) is node 2, with cost \(c_{2}=4\). The next selection is for node 3, with cost \(c_{3}=|-5|=5\) (that is less than the cost for reaching node 4, i.e., \(c_{4}=c_{2}+c_{2,4}=|6|=6\)). With two more iterations, reported in Figure 2, node 6 is selected from \(Q\), and a feasible solution is found. The cost for reaching node 6 is 9, and the selected path is nodes 1-2-4-6. Looking at the graph, it is possible to find a better solution, that is, the path consisting of nodes 1-3-4-6 with a cost of 3. We try to improve the obtained solution (nodes 1-2-4-6) by using the improvement algorithm described in the next section. Using a priority queue proposed in [27], the complexity of [PERSON]'s algorithm is equal to \(O(|A|+|N|log|N|)\). Considering that the number of nodes extracted from \(Q\) does not change in our implementation, using a Fibonacci heap to represent \(Q\), the computational complexity of \(CHa\) remains unchanged. The last part of the constructive algorithm consists of the identification of a path and its cost evaluation. These procedures are described in Algorithms 2 and 3, respectively. In more detail, the Algorithm 2, here denoted as \(Path\), is used to create a set \(P\) containing the nodes along the path that connects node \(o\) to node \(d\) within the tree previously created by \(CHa\). The Algorithm 3 \(CostPath\) is used to compute the sum of the costs of the arcs along the path that connects node \(o\) to node \(d\) within this tree.