# On the Use of Biased-Randomized Algorithms for Solving Non-Smooth Optimization Problems
## 5 Applications in Transportation  
Transportation and distribution are two fields belonging to the operational level of decisions in logistics. The vehicle routing problem [53; 54] and the arc-routing problem (ARP) [55; 56] are two well-known optimization problems in the area of transportation and freight distribution. A traditional VRP consists of a graph formed by a set of nodes and a set of arcs. One of the nodes represents a depot and the rest represent customers, which are connected to each other by the set of arcs. A network of routes must be designed to visit each customer in order to meet a known demand. A single vehicle departing and returning to the depot is assigned to each route. The objective is to minimize the total cost of traversing the arcs. The traditional ARP is similar to the VRP, but the former assigns a demand to each arc and not to each node. Moreover, in the ARP, the underlying graph is not usually a complete one. These problems are _NP-hard_, i.e., as the number of customers grows, the quantity of alternative solutions increases almost exponentially. Therefore, heuristic and metaheuristic algorithms have been employed extensively to solve these OPs. The problems become even more difficult to solve in the presence of non-smooth and non-convex objective functions, as when soft constraints are considered. In this context, soft constraints would include time window constraints or capacity constraints that are allowed to be violated to some extent [9]. These soft constraints also allow decision-makers to consider more realistic models that take into account different management strategies and policies. For instance, customers would accept a delayed delivery if the supplier offers a discount. Likewise, a percentage of the deliveries can be outsourced if in-house capacity is exceeded. In the VRP case, [PERSON] et al. [43] consider a capacitated version of the problem with a non-smooth and non-convex objective function and soft constraints. These authors propose a BRA-based approach called _MIRHA_.This is a multi-start procedure consisting of two phases: a first phase in which a biased-randomized version of a constructive heuristic is designed according to a geometric probability distribution and a second (improvement) phase in which an adaptive local search procedure is implemented. Several instances from the literature are used to test the proposed algorithm and to compare it with a traditional GRASP. In general, the new algorithm outperforms the existing ones in terms of solution quality (efficiency), both in the presence of hard and soft constraints. In the case of the ARP, [PERSON] et al. [57] propose a BRA to solve the capacitated version of the problem with a non-smooth and non-convex objective function. The base heuristic considered is _SHARP_[58]. Firstly, they propose the following model:  
\[\text{Minimize}\ \ \sum_{\rho\in\mathcal{S}}c_{\rho}^{*}\] \[\text{subject to:}\] \[\mathcal{S}\in CSR\] \[\sum_{(i,j)\in\rho}q_{ij}x_{ij}^{k}\leq Q\ \ \ \ \ \ \forall\ \rho\in\mathcal{S},\forall\ k\in T\] \[x_{ij}^{k}(1-x_{ij}^{k})=0\ \ \ \ \ \forall\ (i,j)\in\rho,\ \forall\ \rho\in \mathcal{S},\forall\ k\in T\]  
where \(\rho\) represents a route in a set of routes \(\mathcal{S}\); \(CSR\) represents a complete set of routes (i.e., a solution); \(c_{\rho}^{*}\) is the total cost of using route \(\rho\); \(q_{ij}\) is the demand of arc \((i,j)\); and \(x_{ij}^{k}\) is a binary variable that takes the value 1 if and only if the arc \((i,j)\) is covered by a vehicle \(k\) in the set of vehicles \(T\). The cost function associated with any route \(\rho\) is defined as a piecewise function as follows:\[c_{\rho}^{*}=\left\{ \begin{array}{ll}c_{\rho}&\text{if }c_{\rho}\leq C\\ \\ c_{\rho}+\lambda\left(c_{\rho},C\right)&\text{otherwise}\end{array} \right. \tag{1}\]  
In the former expression, \(\lambda\left(c_{\rho},\ C\right)\) is a non-smooth function which will be applied whenever the actual route cost exceeds the threshold value allowed for any route, \(C\).