## 1 Introduction
Another interesting application of the \(CBPP\) concerns electric vehicles with limited battery levels, considering, for example, that maintaining a lithium battery at a charge value of about 80% helps to extend its life. In this case, given a graph, the positive or negative values associated with arcs represent, respectively, energy consumption or recharging obtained on downhill roads or through charging stations. Identifying a path in this graph so that the car arrives at its destination with a similar level of charge as at the start would extend the average life of a battery. In [12], the authors proposed a mixed-integer linear programming model for solving the \(CBPP\) and tested it by using different sets of random instances. Experimental tests on the model showed that the computation time of instances that do not have zero as the optimal solution is significantly higher. For these more complex instances, it is, therefore, necessary to develop heuristic algorithms. Unfortunately, at least to the authors' knowledge, no solution approaches for the \(CBPP\) have been proposed in the literature. Instead, heuristic algorithms have been presented for some problems closely related to the \(CBPP\). One of the most relevant and similar problem to the \(CBPP\) is the cost-balanced Travelling Salesman Problem (\(TSP\)) introduced in [14], in which the main objective is to find a Hamiltonian cycle in a graph with total travel cost as close to zero as possible. In [15], the authors propose a variable neighborhood search algorithm, which is a local search with multiple neighborhood structures, to solve the cost-balanced \(TSP\). The balanced \(TSP\) is widely described in [16], where an equitable distribution of resources is the main objective. The authors cited many balanced combinatorial optimization problems studied in the literature, and proposed four different heuristics, derived by the double-threshold algorithm and the bottleneck one, to solve the balanced \(TSP\). To solve the same problem, in [17] an adaptive iterated local search is proposed with a perturbation and a random restart that can help in escaping local optimum. In [18], a multiple balanced TSP is analyzed to model and optimize the problems with multiple objectives (salesmen). The goal is to find \(m\) Hamiltonian cycles in a graph \(G\) by minimizing the difference between the highest edge cost and the smallest edge cost in the tours. Another problem on graphs closely related to the \(CBPP\) is the search for the balanced trees [19], defined as the most appropriate structures (precisely the balanced tree structures) for managing networks with the aim of balancing two or more objectives. In [20], the authors face the problem of finding two paths in a tree with positive and negative weights. They presented two polynomial algorithms with the goal of minimizing, respectively, the sum of the minimum weighted distances from every node of the tree to the two paths, and the sum of the weighted minimum distances from every node of the tree to the two paths. To cover the above-mentioned lack of efficient solution methods for the \(CBPP\), the main aim of this paper is to propose a heuristic algorithm able to solve large instances of the problem. Since it is not possible to make comparisons with other heuristics proposed in the literature for the \(CBPP\), to validate the computational results, an iterative heuristic algorithm is presented. Thus, in the present paper, two heuristic approaches are described, tested, and compared. The first is a two-step heuristic algorithm that implements a constructive heuristic algorithm in the first step (\(CHa\)) followed by an improvement phase (\(1 Pa\)). The constructive step is a modified version of the well-known Dijkstra algorithm to solve \(SPP\)[21], made necessary to deal with both positive and negative costs and the need to minimize the absolute value of the cost of the path.