## 1 Introduction  
In many optimization problems arising in the decision science area, given a finite set \(E\) of elements having a vector cost \(c\) associated with them, the objective function is to find a feasible subset \(F\subseteq E\), such that the difference in value between the most costly and the least costly selected elements is minimized. Such problems are denoted as balanced optimization problems (BOPs). One of the first approaches to solve a BOP is presented in [1], where the authors consider the set \(E\) as an \(n\times n\) assignment matrix, the cost \(c_{e}\) as the value contained in a generic cell \(e\) of the assignment matrix, and the subset \(F\) the selected cells of the defined assignment, thus obtaining the balanced assignment problem. Successively, Ref. [2] introduced the minimum deviation problem, which minimizes the difference between the maximum and average weights in a solution. In the same paper, the authors proposed a general solution scheme also suitable for BOPs. Since then, numerous real-world applications have been defined and solved as BOPs, always with the goal of minimizing the deviation between the highest and lowest cost, or making the performance indices of interest as equal as possible. In the latter case, the most proposed applications in the literature as BOPs include, though are not limited to, production line operations in manufacturing systems (e.g., see [3; 4; 5; 6] among others) and supply chain management [7; 8]. Other BOPs were proposed in the class of flow and routing problems on networks, where the goal is to design either a single path or a subset of paths in which the arcs or nodes belonging to the solution have a homogeneous value of their relative weights, such as travel time, length, etc. (see [9; 10; 11], among others). This paper deals with a variant of the Shortest Path Problem (\(SPP\)) that fits into the class of BOPs. This problem, recently introduced in the literature [12], is denoted Cost Balanced Path Problem (\(CBPP\)). The \(CBPP\) is defined on a directed weighted graph \(G(N,A)\), where \(N\) is the set of nodes and \(A\) is the set of directed arcs. For each arc \((i,j)\in A\) there is a weight \(c_{ij}\in\mathbb{R}\); the weights represent either the increment (in case of positive weight) or the decrement (in case of negative weight) of the cost to balance along the path. The problem is to select in graph \(G\) a path \(p\) from an origin node \(o\) to a destination node \(d\) that minimizes the absolute value of the sum of the weights of path \(p\). More formally, the objective function of the \(CBPP\) is given by:  
\[MIN\ \ |c(p)|=|\sum_{(i,j)\in p}c_{ij}| \tag{1}\]  
In [12] the authors demonstrate that the \(CBPP\), as many variants of the \(SPP\)[13], is NP-hard in its general form. Moreover, they demonstrate that, in the following two particular cases, the \(CBPP\) can be solved in polynomial time:  
* When all costs are non-negative or non-positive (i.e., \(c_{ij}\geq 0\) or \(c_{ij}\leq 0\), \(\forall(i,j)\in A\)). In this case, the problem is equivalent to the \(SPP\);
* When the cost of the arc is a function of the elevation difference of the two nodes associated with the arc. The reader may observe that the objective function (1) imposes minimization of an always positive value. For this reason, zero is a lower bound for the CBPP. This implies that any solution with zero objective function value, coincident with the lower bound, will always be optimal. The \(CBPP\) can be used for modelling various real problems that require the decision-maker to choose a path in a graph from an origin node to a destination one balancing some elements. Among others, the problems of route design for automated guided vehicles, the vehicles' loading in pick-up and delivery, and storage and retrieval problems in warehouses and yards deserve attention.