---
# System prepended metadata

title: MKSP for travelling plane

---

# MKSP for travelling plane
## Given 
- We have n task between the two way points.
- We are given the (x,y,z) co-ordinates of the task and waypoints.
- for each task by using Distance Formula,
  - We have distance from source to the Task : ST=[$st_{1}....st_{n}$]
  - We have distance from Task to the destination : TD=[$td_{1}....td_{n}$]
  - We have distance from between Tasks : TT=$\begin{bmatrix}\delta_{11} &.  &.  &.  &\delta_{1n} \\ \delta_{21} &.  &.  &.  &\delta_{2n} \\ . &.  &.  &.  &. \\ . &.  &.  &.  &. \\ \delta_{n1} &.  &.  &.  &\delta_{nn} \\ \end{bmatrix}$
- $max\sum\limits_{i =1}^{n} R(T_{i})x_{i}$ where R is the Reward for a task $T_{i}$
- $\sum\limits_{i =1}^{n} d_{i}x_{i} < D$ , where D is the total allowed distance and $d_{i}$ is the distance travelled when for task i
- $\sum\limits_{i =1}^{n} t_{i}x_{i} < T$ , where T is the total allowed time and $t_{i}$ is the time recquired to complete of task i
**where** ,$$: x_{i}\in \{0,1\}$$
## Hueristic Algorithm
#### Assumptions
- We can only move in the forward direction,for two task $v_{i}$ and $v_{j}$ , the movement is allowed if $i<j$.
- Once we leave the ideal route , we dont return to the ideal path(waypoint)
### Initialization
- efficiency of task when we are at i($\epsilon_{i}$):
$$\frac{R(T_{i})}{\sum\limits_{k =i}^{n} [T-t_{k}]^{+}+\sum\limits_{k =i}^{n} [D-d_{k}]^{+}}$$
$Here [x]^{+}$ means that whenever the value is -ive replace it with 0 and whenever it is 0 replace it with 1.
### Algorithm
* Start with i=0.
  - find $\epsilon$ for all j and $d_{j}=TT[j,k]+TD[j]$, where j>i and j<n
  - $$\frac{R(T_{i})}{ST[i]+\sum\limits_{k =i}^{n} [T-t_{k}]^{+}+\sum\limits_{k =i}^{n} [D-d_{k}]^{+}}$$
  - Choose the $t_{j}$ with the highest $\epsilon$
  - Remove $t_{j}$ from list.
  - Change $T=T-t_{j} and D=D-d_{j}$
* With i=j , 
  - for each task($t_{m}$)[Where m in range(i,n)]:
   - find $\epsilon$ for all j and $d_{j}=TD[m]+TT[i][m]$, where j>i and j<n
   - Choose the $t_{j}$ with the highest $\epsilon$
   - Remove $t_{j}$ from list.
   - Change $T=T-t_{j} and D=D-d_{j}$
* Repeat untill no state with real $\epsilon$ is left.