# Problem Statement for 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.
- We are given the time it takes to complete each task as $t_{1},t_{2}...t_{n}$
- 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})}{Distance[i]+t_{i}}$$ ,where $Distance$ can be Source-Task Or Task-Task Distance and $t_{i}$ is timr it takes to perform the task.

### Algorithm
* Start with i=0.
- find $\epsilon$ for all i and $Distance=Source-Task$, where i<n
- $$\epsilon_{i}=\frac{R(T_{i})}{ST[i]+t_{i}}$$
- Choose the $i^{th}$ task , with the highest $\epsilon$
- Change $T=T-t_{i}$ and $D=D-Distance$
* With j=i ,
- for each task($task_{m}$)[Where m in range(i+1,n)]:
- find $\epsilon$ for all i and $distance=TT[j][i]+TD[i]$, where i<n
- If $distance<=D$:
- Choose $Distance=TT[j][i]$
- Choose the $task_{i}$ with the highest $\epsilon$
- Change $T=T-t_{i}$ and $D=D-Distance$
* Repeat untill no state with real $\epsilon$ is left.
* To end , subtract Source-Destination Task for the last chossen Task:
- Change $D=D-TD[j]$