# Efficient Position Change Algorithms for Prolonging Driving Range of a Truck Platoon
## 3 The Position Change Problem and the Algorithms
### Formulation of the Position Change Problem
Considering the fuel consumption reduction rate, the fuel amount at time \(t_{k+1}\), i.e., \(F_{i}(t_{k+1})\), is given as follows:  
\[F_{i}(t_{k+1}) = F_{i}(t_{k})-r\times(1-g(P(i,k)))\times(t_{k+1}-t_{k})\times s \tag{1}\] \[= F_{i}(t_{k})-r\times(1-g(P(i,k)))\times\delta\times s \tag{2}\]  
In the above equations, \(\delta\times s\) is the distance that a truck travels in a time slot. Since \(r\) is the fuel consumption rate per unit distance, the amount of fuel consumed in a time slot is \(r\times\delta\times s\) in a non-platoon driving. However, due to the platooning effect, the fuel consumption is reduced by \((1-g(P(i,k)))\) in such a way that when \(g(P(i,k))\) increases, the platoon has less fuel consumption. The set of initial amount of fuel at the beginning of driving is \(F(0)=\{F_{1}(0),F_{2}(0),...,F_{n}(0)\}\). The platoon needs to stop driving when a truck has empty fuel. Thus, if the fuel of any truck \(i\) becomes empty in a time slot \(K\), i.e., \(F_{i}(t_{K})\geq 0\) and \(F_{i}(t_{K+1})<0\), then the longest driving range of the platoon is \(K\times\delta\times s\). The objective of the problem is to produce a position change matrix \(P\) that achieves the longest driving range with the given set of the initial amount of fuels, \(F(0)\), and the time slot size \(\delta\). The optimization problem of position changes can be expressed as follows. \[\underset{P(i,k)}{\text{maximize}} K\] subject to \[t_{0}=0\] \[t_{k+1}=t_{k}+\delta,\ k\geq 0\] \[F_{i}(t_{k})\geq 0,\ \text{for}\ i\in V,\ 0\leq k\leq K\] \[F_{i}(t_{k+1})=F_{i}(t_{k})-r\times(1-g(P(i,k)))\times\delta \times s,\ \text{for}\ 0\leq j\leq K\] \[P(i,k)\in\{1,...,n\},\ \text{for}\ i\in V\] \[P(i,k)\
eq P(j,k),\text{if}\ i\
eq j\ \text{for}\ i,j\in V\]  
Our primary objective is to maximize the number of time slots, \(K\), while maintaining the remaining amount of fuels \(F_{i}(t_{k})\) non-negative. In other words, we want to increase the driving range. The variables in the above optimization problem are \(P(i,k)\), which is the position of a vehicle \(i\) at time slot \(k\). By changing the values of \(P(i,k)\), we have different objective values \(K\). There can be some remaining fuel in the vehicles, which is not enough for the next time slot. However, we ignore it and only consider the number of time slots that can be driven entirely because when \(\delta\) is small, the remaining fuel becomes very small. Now, we rigorously define \"Traveling Time Heuristic\" by using the notations defined in \[F_{i}(t_{k+1}) = F_{i}(t_{k})-r\times(1-g(P(i,k)))\times(t_{k+1}-t_{k})\times s \tag{1}\]0 \"TTH\" is described as in Algorithm 1. It can be easily proved that the proposed algorithm produces an optimal position sequence \(P(i,k)\) for all the vehicles in the platoon in the sense that it produces the longest driving range. Furthermore, when \(\delta\) goes to zero, we achieve the highest driving range possible because the platoon does not have any remaining fuel. It means that the platoon driving stops when one of the trucks has exactly zero fuel remaining. Next, we discuss some properties of \"TTH\". First of all, a simple lower bound and an upper bound of the driving range of the platoon can be constructed as follows. If the truck with the smallest initial fuel drives in the leading position all the time, the fuel depletes earliest, and the corresponding distance is given by Equation (3). Similarly, an upper bound is a case when the truck with the most initial fuel drives at the end of the platoon, and the distance is given by Equation (4). \[F_{i}(t_{k+1}) = F_{i}(t_{k})-r\times(1-g(P(i,k)))\times(t_{k+1}-t_{k})\times s \tag{1}\]1 \[F_{i}(t_{k+1}) = F_{i}(t_{k})-r\times(1-g(P(i,k)))\times(t_{k+1}-t_{k})\times s \tag{1}\]2Another thing is about the differences in the amount of fuels of the vehicles. \"TTH\" tries to reduce the differences in the amount of fuels of the vehicles.