## 4 From a Heuristic to a Biased-Randomized Algorithm  
In this paper, a heuristic is extended to a biased-randomized algorithm to solve the TOP. The proposed algorithm extends the concept of'savings' introduced by [PERSON] and [PERSON] [56] to the characteristics of the TOP: (_i_) different origin and destination depots, (_ii_) some of the customers might not be covered, and (_iii_) the reward as well as the savings in time or distance are considered to construct routes. Then, the constructive heuristic is extended to utilize skewed probability distributions to introduce a non-uniform randomization effect into the procedure of constructing solutions.  
Figure 2 presents the proposed constructive heuristic. An initial dummy solution is built for each customer \(i\in N^{\prime}\); a vehicle departs from the origin depot (node 0), visits customer \(i\), and then head towards the destination depot (node \(n+1\)). If a route associated with customer \(i\) in the dummy solution does not satisfy the driving-range constraint, customer \(i\) is discarded from the solution because it cannot be served with the current settings of the problem.  
Next, the 'enriched savings' associated with each edge connecting two different customers are computed; thus, the benefits obtained by visiting both customers in the same route instead of using two different routes are calculated. The enriched savings of an edge considers the travel time required to traverse the edge and the aggregated reward generated by visiting both customers. Therefore, the enriched savings associated with an edge \((i,j)\), \(s^{\prime}_{ij}\), are defined as \(s^{\prime}_{ij}=\alpha\cdot s_{ij}+(1-\alpha)\cdot(u_{i}+u_{j})\) to account for the trade-off between time-based savings \(s_{ij}=t_{i(n+1)}+t_{0j}-t_{ij}\), and the aggregated reward, \(u_{i}+u_{j}\). Here, \(\alpha\in(0,1)\) is a parameter that depends on the rewards of customers. Experiments are used to determine the value of \(\alpha\). In general, \(\alpha\) is set close to zero in problems with high heterogeneity rewards and one in problems with homogeneous customer rewards.  
For each edge, we obtain its unique associated savings; recall that the matrix of travel times is symmetric, so the savings do not depend on the direction in which the edge is traversed. These savings are associated with arcs that connect two potential routes to be merged. Then, the list of arcs can be sorted from higher to lower savings. Routes are merged based on the sorted savings list. In each iteration of the merging process, the arc at the top of the sorted list is selected, and the two routes connected by this arc are merged into a new route if the driving-range constraint is not violated. Finally, the list of routes is decreasingly sorted according to the total reward. Routes with the highest rewards are selected, and the number of selected routes equals the size of the vehicle fleet.  
The described heuristic is extended into a probabilistic algorithm as follows: The greedy behavior of the heuristic is altered by combining it with biased-randomization techniques to introduce non-uniform random behavior [57]. In our work, we utilized geometric probability distribution with a parameter \(\beta\) (\(0<\beta<1\)). Parameter \(\beta\) of the geometric distribution controls the greediness of the randomized behavior. In our  
Figure 2: Flowchart of the Heuristic approach.  
experiments, we set the value of \(\beta\) to 0.3. This value was a result of parameter tuning experiments. Thus, the heuristic becomes randomized algorithm and utilizes the greedy behavior of the original heuristic.