# Genetic Algorithm Implementation

$V_d \in \mathbb{N} - \{0\}$ (list of demand node / hospitals)
$V_c \in \mathbb{N} - \{0\}$ (list of collection node)
$V_n \in V_d \cup V_c$ (list of customer nodes)
$V \in V_n \cup \{0\}$ (list of all nodes, $0=$depot)

$c_{i,j}$ (moving duration between $v_i, v_j \in V$)
$t_{i}$ (service time of node $v_i \in V_n$)

$s_k \in V \times V$ ($k$-th fleet route)
$T \in \mathbb{R}$ (maximum time allowed for each $s_k$)

$g = \{s_k : k \in \mathbb{N} \}$ (genome: all fleet route to serve all customer nodes)

## Genome encoding

Suppose there are two customer nodes $v_1, v_2 \in V_n$

This is the initial genome $g$ in population looks like:

| 0 | $v_1$ | 0 | $v_2$ | 0 |
| --- | ----- | --- | ----- | --- |

**Note**: $g = \{ \{0, v_1, 0\}, \{0, v_2, 0\} \}$, $s_1 = \{0, v_1, 0\}$, $s_2 = \{0, v_2, 0\}$

This is the solution (might) looks like:

| 0 | $v_2$ | $v_1$ | 0 | 0 |
| --- | ----- | ----- | ---:| --- |

**Note**: $g = \{ \{0, v_2, v_1, 0\} \}$, $s_1 = \{0, v_2, v_1, 0\}$, $s_2 = \{0, 0\}$

**Remarks**:
- initial population consists of randomly ordered $v_i \in V_n$ with $\{0\}$ between each node. Thus, genome length is $2|V_n| + 1$
- each genome $g$ contains segments $s_k$ which separated by $\{0\}$ (depot node)
- each segment represent one trip starting from depot until come back to depot
- segment can be empty, which means the trip in that specific segment is not occurs. empty segment encoded as $\{0, 0\}$

## Fitness Function

- First split genome into segments
- For each segment $s_k$ if there are $v_m, v_n \in V_n$ such that $v_m \in V_d$ and $v_n \in V_c$, returns $0$, the whole genome is not fit
- Because each trip can not be both collecting and distributing
- For each segment $s_k$ if total number of time required $\sum c_{ij} + t_i > T$ such that $(v_i, v_j)$ is consecutive element of $s_k$, then returns $0$, the whole genome is not fit
- Because each trip not allowed to exceed $T$
- Else calculate the sum of all $c_{i,j}$ and $t_i$ of the segment

## Mutation

There are two kinds of mutations
1. combine two segments (50% chance) or (100% chance for initial populations)
2. swap two nodes in any segment (50% chance) or (0% chance for initial populations)

## Crossover

If there is segment $s_{i}^m$ in genome $g_{m}$ that same but with different order with segment $s_{j}^n$ in genome $g_{n}$, then move $s_{i}^m$ into $g_{n}$ and $s_{j}^n$ into $g_{m}$, which producing two offsprings into population.

For example:

given parents:
$g_1 = \{ \{0, v_1, v_2, 0\}, \{0, v_3, v_4, 0 \} \}$
$g_2 = \{ \{0, v_2, v_1, 0\}, \{0, v_3, 0 \}, \{0, v_4, 0\} \}$

producing offsprings:
$g_3 = \{ \{0, v_2, v_1, 0\}, \{0, v_3, v_4, 0 \} \}$
$g_4 = \{ \{0, v_1, v_2, 0\}, \{0, v_3, 0 \}, \{0, v_4, 0\} \}$

## Experimental notes

- It relatively quick to converge
- Best result for case which requires large number of fleet trips. Hence small $T$ or large $|V|$
- Not very good for small number of fleet, due to crossover is not effective, since the offspring fitness value would be same with the parent.