docs/algorithm_equations.md

Optimization Algorithms - Mathematical Formulations

1. OR-Tools CP-SAT (Constraint Programming)

Decision Variables: $$x_i\in \{0,1,2\}\mathrm{\forall }i\in Tx\_i\; \backslash in\; \backslash \{0,\; 1,\; 2\backslash \}\; \backslash quad\; \backslash forall\; i\; \backslash in\; T$$

where $T$ is the set of trainsets, and:

• $x_i = 0$: trainset $i$ assigned to service
• $x_i = 1$: trainset $i$ assigned to standby
• $x_i = 2$: trainset $i$ assigned to maintenance

Constraints: $$\sum _{i\in T}{\mathbb{1}}_{x_i=0}=N_{\text{service}}\backslash sum\_\{i\; \backslash in\; T\}\; \backslash mathbb\{1\}\_\{x\_i\; =\; 0\}\; =\; N\_\{\backslash text\{service\}\}$$

$$\sum _{i\in T}{\mathbb{1}}_{x_i=1}\ge N_{\text{standby}}^{\text{min}}\backslash sum\_\{i\; \backslash in\; T\}\; \backslash mathbb\{1\}\_\{x\_i\; =\; 1\}\; \backslash geq\; N\_\{\backslash text\{standby\}\}^\{\backslash text\{min\}\}$$

$$\sum _{i\in T}{\mathbb{1}}_{x_i=0}\le C_{\text{service}}^{\text{max}}\backslash sum\_\{i\; \backslash in\; T\}\; \backslash mathbb\{1\}\_\{x\_i\; =\; 0\}\; \backslash leq\; C\_\{\backslash text\{service\}\}^\{\backslash text\{max\}\}$$

Objective Function: $$\max Z=w_r\sum _{i\in T}{r}_i\cdot {\mathbb{1}}_{x_i=0}+w_b\cdot B-w_v\cdot V\backslash max\; \backslash quad\; Z\; =\; w\_r\; \backslash sum\_\{i\; \backslash in\; T\}\; r\_i\; \backslash cdot\; \backslash mathbb\{1\}\_\{x\_i\; =\; 0\}\; +\; w\_b\; \backslash cdot\; B\; -\; w\_v\; \backslash cdot\; V$$

where:

• $r_i$: readiness score of trainset $i$
• $B$: balance score
• $V$: total violations
• $w_r, w_b, w_v$: weights

---

2. Mixed Integer Programming (MIP)

Decision Variables: $$y_{i,s}\in \{0,1\}\mathrm{\forall }i\in T,s\in Sy\_\{i,s\}\; \backslash in\; \backslash \{0,\; 1\backslash \}\; \backslash quad\; \backslash forall\; i\; \backslash in\; T,\; s\; \backslash in\; S$$

where $S = {0, 1, 2}$ (service, standby, maintenance)

Constraints: $$\sum _{s\in S}{y}_{i,s}=1\mathrm{\forall }i\in T\backslash sum\_\{s\; \backslash in\; S\}\; y\_\{i,s\}\; =\; 1\; \backslash quad\; \backslash forall\; i\; \backslash in\; T$$

$$\sum _{i\in T}{y}_{i,0}=N_{\text{service}}\backslash sum\_\{i\; \backslash in\; T\}\; y\_\{i,0\}\; =\; N\_\{\backslash text\{service\}\}$$

$$\sum _{i\in T}{y}_{i,1}\ge N_{\text{standby}}^{\text{min}}\backslash sum\_\{i\; \backslash in\; T\}\; y\_\{i,1\}\; \backslash geq\; N\_\{\backslash text\{standby\}\}^\{\backslash text\{min\}\}$$

Objective Function: $$\max Z=\sum _{i\in T}\sum _{s\in S}{c}_{i,s}\cdot y_{i,s}\backslash max\; \backslash quad\; Z\; =\; \backslash sum\_\{i\; \backslash in\; T\}\; \backslash sum\_\{s\; \backslash in\; S\}\; c\_\{i,s\}\; \backslash cdot\; y\_\{i,s\}$$

where $c_{i,s}$ is the cost coefficient for assigning trainset $i$ to state $s$.

---

3. Genetic Algorithm (GA)

Chromosome Representation: $$\mathbf{x}=[x_1,x_2,\dots ,x_n]x_i\in \{0,1,2\}\backslash mathbf\{x\}\; =\; [x\_1,\; x\_2,\; \backslash ldots,\; x\_n]\; \backslash quad\; x\_i\; \backslash in\; \backslash \{0,\; 1,\; 2\backslash \}$$

Fitness Function (to minimize): $$f(\mathbf{x})=-w_r\sum _{i:x_i=0}{r}_i-w_b\cdot \frac{1}{1+{\sigma }_m^2}+w_v\cdot P(\mathbf{x})f(\backslash mathbf\{x\})\; =\; -w\_r\; \backslash sum\_\{i:\; x\_i=0\}\; r\_i\; -\; w\_b\; \backslash cdot\; \backslash frac\{1\}\{1\; +\; \backslash sigma\_m^2\}\; +\; w\_v\; \backslash cdot\; P(\backslash mathbf\{x\})$$

Equivalently (to maximize): $$f^{\mathrm{\prime }}(\mathbf{x})=w_r\sum _{i:x_i=0}{r}_i+w_b\cdot \frac{1}{1+{\sigma }_m^2}-w_v\cdot P(\mathbf{x})f\text{'}(\backslash mathbf\{x\})\; =\; w\_r\; \backslash sum\_\{i:\; x\_i=0\}\; r\_i\; +\; w\_b\; \backslash cdot\; \backslash frac\{1\}\{1\; +\; \backslash sigma\_m^2\}\; -\; w\_v\; \backslash cdot\; P(\backslash mathbf\{x\})$$

where:

• $\sigma_m^2$: mileage variance
• $P(\mathbf{x})$: penalty for constraint violations
• Note: Code uses minimization (negative fitness)

Selection (Tournament): $$P(\text{select }{\mathbf{x}}_i)=\frac{{\mathbb{1}}_{f({\mathbf{x}}_i)=\underset{j\in K}{\max }f({\mathbf{x}}_j)}}{1}P(\backslash text\{select\; \}\; \backslash mathbf\{x\}\_i)\; =\; \backslash frac\{\backslash mathbb\{1\}\_\{f(\backslash mathbf\{x\}\_i)\; =\; \backslash max\_\{j\; \backslash in\; K\}\; f(\backslash mathbf\{x\}\_j)\}\}\{1\}$$

where $K$ is a random tournament subset of size $k$.

Two-Point Crossover: $${\mathbf{c}}_1=[{\mathbf{p}}_1[1:p],{\mathbf{p}}_2[p:q],{\mathbf{p}}_1[q:n]]\backslash mathbf\{c\}\_1\; =\; [\backslash mathbf\{p\}\_1[1:p],\; \backslash mathbf\{p\}\_2[p:q],\; \backslash mathbf\{p\}\_1[q:n]]$$ $${\mathbf{c}}_2=[{\mathbf{p}}_2[1:p],{\mathbf{p}}_1[p:q],{\mathbf{p}}_2[q:n]]\backslash mathbf\{c\}\_2\; =\; [\backslash mathbf\{p\}\_2[1:p],\; \backslash mathbf\{p\}\_1[p:q],\; \backslash mathbf\{p\}\_2[q:n]]$$

where $p, q$ are random crossover points, $\mathbf{p}_1, \mathbf{p}_2$ are parents.

Mutation:

---

4. CMA-ES (Covariance Matrix Adaptation Evolution Strategy)

Sampling Distribution: $${\mathbf{x}}_k\sim \mathcal{N}(\mathbf{m},{\sigma }^2\mathbf{C})\backslash mathbf\{x\}\_k\; \backslash sim\; \backslash mathcal\{N\}(\backslash mathbf\{m\},\; \backslash sigma^2\; \backslash mathbf\{C\})$$

where:

• $\mathbf{m}$: mean vector
• $\sigma$: step size
• $\mathbf{C}$: covariance matrix

Mean Update: $${\mathbf{m}}^{(g+1)}={\mathbf{m}}^{(g)}+{\sigma }^{(g)}{\mathbf{y}}_w\backslash mathbf\{m\}^\{(g+1)\}\; =\; \backslash mathbf\{m\}^\{(g)\}\; +\; \backslash sigma^\{(g)\}\; \backslash mathbf\{y\}\_w$$

where $\mathbf{y}w = \sum{i=1}^{\mu} w_i \mathbf{y}_{i:\lambda}$ is weighted recombination.

Step Size Update: $${\sigma }^{(g+1)}={\sigma }^{(g)}\exp \left(\frac{c_{\sigma }}{d_{\sigma }}(\frac{\mathrm{\parallel }{\mathbf{p}}_{\sigma }^{(g+1)}\mathrm{\parallel }}{\mathbb{E}\mathrm{\parallel }\mathcal{N}(0,I)\mathrm{\parallel }}-1)\right)\backslash sigma^\{(g+1)\}\; =\; \backslash sigma^\{(g)\}\; \backslash exp\backslash left(\backslash frac\{c\_\backslash sigma\}\{d\_\backslash sigma\}\backslash left(\backslash frac\{\backslash |\backslash mathbf\{p\}\_\backslash sigma^\{(g+1)\}\backslash |\}\{\backslash mathbb\{E\}\backslash |\backslash mathcal\{N\}(0,I)\backslash |\}\; -\; 1\backslash right)\backslash right)$$

Covariance Matrix Update: $${\mathbf{C}}^{(g+1)}=(1-c_1-c_{\mu }){\mathbf{C}}^{(g)}+c_1{\mathbf{p}}_c{\mathbf{p}}_c^T+c_{\mu }\sum _{i=1}^{\mu }{w}_i{\mathbf{y}}_{i:\lambda }{\mathbf{y}}_{i:\lambda }^T\backslash mathbf\{C\}^\{(g+1)\}\; =\; (1-c\_1-c\_\backslash mu)\backslash mathbf\{C\}^\{(g)\}\; +\; c\_1\backslash mathbf\{p\}\_c\backslash mathbf\{p\}\_c^T\; +\; c\_\backslash mu\backslash sum\_\{i=1\}^\{\backslash mu\}w\_i\backslash mathbf\{y\}\_\{i:\backslash lambda\}\backslash mathbf\{y\}\_\{i:\backslash lambda\}^T$$

---

5. Particle Swarm Optimization (PSO)

Position and Velocity: $${\mathbf{x}}_i(t)\in {\mathbb{R}}^n,{\mathbf{v}}_i(t)\in {\mathbb{R}}^n\backslash mathbf\{x\}\_i(t)\; \backslash in\; \backslash mathbb\{R\}^n,\; \backslash quad\; \backslash mathbf\{v\}\_i(t)\; \backslash in\; \backslash mathbb\{R\}^n$$

Velocity Update: $${\mathbf{v}}_i(t+1)=w{\mathbf{v}}_i(t)+c_1{r}_1({\mathbf{p}}_i-{\mathbf{x}}_i(t))+c_2{r}_2(\mathbf{g}-{\mathbf{x}}_i(t))\backslash mathbf\{v\}\_i(t+1)\; =\; w\backslash mathbf\{v\}\_i(t)\; +\; c\_1r\_1(\backslash mathbf\{p\}\_i\; -\; \backslash mathbf\{x\}\_i(t))\; +\; c\_2r\_2(\backslash mathbf\{g\}\; -\; \backslash mathbf\{x\}\_i(t))$$

where:

• $w$: inertia weight
• $c_1, c_2$: cognitive and social coefficients
• $r_1, r_2 \sim U(0,1)$: random numbers
• $\mathbf{p}_i$: personal best position
• $\mathbf{g}$: global best position

Position Update: $${\mathbf{x}}_i(t+1)={\mathbf{x}}_i(t)+{\mathbf{v}}_i(t+1)\backslash mathbf\{x\}\_i(t+1)\; =\; \backslash mathbf\{x\}\_i(t)\; +\; \backslash mathbf\{v\}\_i(t+1)$$

Velocity Clamping (optional but recommended): $${\mathbf{v}}_i(t+1)=\text{clip}({\mathbf{v}}_i(t+1),-v_{\max },v_{\max })\backslash mathbf\{v\}\_i(t+1)\; =\; \backslash text\{clip\}(\backslash mathbf\{v\}\_i(t+1),\; -v\_\{\backslash max\},\; v\_\{\backslash max\})$$

Discrete Conversion:

---

6. Simulated Annealing (SA)

Energy Function: $$E(\mathbf{x})=-f(\mathbf{x})E(\backslash mathbf\{x\})\; =\; -f(\backslash mathbf\{x\})$$

where $f(\mathbf{x})$ is the fitness function to maximize.

Acceptance Probability:

where:

• $\Delta E = E(\mathbf{x}{\text{new}}) - E(\mathbf{x}{\text{current}})$
• $T$: current temperature

Cooling Schedule (Geometric):

Perturbation Operator: $${\mathbf{x}}^{\mathrm{\prime }}=\text{swap}(\mathbf{x},i,j)\text{where }i,j\sim U\{1,n\}\backslash mathbf\{x\}\text{'}\; =\; \backslash text\{swap\}(\backslash mathbf\{x\},\; i,\; j)\; \backslash quad\; \backslash text\{where\; \}\; i,\; j\; \backslash sim\; U\backslash \{1,\; n\backslash \}$$

---

7. Multi-Objective Optimization (NSGA-II)

Objective Vector: $$\mathbf{F}(\mathbf{x})=[f_1(\mathbf{x}),f_2(\mathbf{x}),\dots ,f_k(\mathbf{x}){]}^T\backslash mathbf\{F\}(\backslash mathbf\{x\})\; =\; [f\_1(\backslash mathbf\{x\}),\; f\_2(\backslash mathbf\{x\}),\; \backslash ldots,\; f\_k(\backslash mathbf\{x\})]^T$$

where:

• $f_1$: maximize readiness
• $f_2$: minimize mileage variance
• $f_3$: maximize branding
• $f_4$: minimize violations

Pareto Dominance: $${\mathbf{x}}_1\prec {\mathbf{x}}_2⟺\{\begin{array}{c}\mathrm{\forall }i:f_i({\mathbf{x}}_1)\ge f_i({\mathbf{x}}_2)\\ \mathrm{\exists }j:f_j({\mathbf{x}}_1)>f_j({\mathbf{x}}_2)\end{array}\backslash mathbf\{x\}\_1\; \backslash prec\; \backslash mathbf\{x\}\_2\; \backslash iff\; \backslash begin\{cases\}\; \backslash forall\; i:\; f\_i(\backslash mathbf\{x\}\_1)\; \backslash geq\; f\_i(\backslash mathbf\{x\}\_2)\; \backslash \backslash \; \backslash exists\; j:\; f\_j(\backslash mathbf\{x\}\_1)\; >\; f\_j(\backslash mathbf\{x\}\_2)\; \backslash end\{cases\}$$

Crowding Distance: $$d_i=\sum _{m=1}^k\frac{f_m^{i+1}-f_m^{i-1}}{f_m^{\max }-f_m^{\min }}d\_i\; =\; \backslash sum\_\{m=1\}^\{k\}\; \backslash frac\{f\_m^\{i+1\}\; -\; f\_m^\{i-1\}\}\{f\_m^\{\backslash max\}\; -\; f\_m^\{\backslash min\}\}$$

Selection Operator:

---

8. Ensemble Optimization

Weighted Combination: $${\mathbf{x}}^{\ast }=\arg \underset{\mathbf{x}\in \{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_m\}}{\max }f(\mathbf{x})\backslash mathbf\{x\}^*\; =\; \backslash arg\backslash max\_\{\backslash mathbf\{x\}\; \backslash in\; \backslash \{\backslash mathbf\{x\}\_1,\; \backslash ldots,\; \backslash mathbf\{x\}\_m\backslash \}\}\; f(\backslash mathbf\{x\})$$

where $\mathbf{x}_j$ is the solution from algorithm $j$.

Consensus Voting: $$x_i^{\ast }=\text{mode}\{x_i^{(1)},x_i^{(2)},\dots ,x_i^{(m)}\}x\_i^*\; =\; \backslash text\{mode\}\backslash \{x\_i^\{(1)\},\; x\_i^\{(2)\},\; \backslash ldots,\; x\_i^\{(m)\}\backslash \}$$

Weighted Average (for continuous): $${\tilde{x}}_i=\sum _{j=1}^m{w}_j\cdot x_i^{(j)}\text{where }\sum _{j=1}^m{w}_j=1\backslash tilde\{x\}\_i\; =\; \backslash sum\_\{j=1\}^\{m\}\; w\_j\; \backslash cdot\; x\_i^\{(j)\}\; \backslash quad\; \backslash text\{where\; \}\; \backslash sum\_\{j=1\}^\{m\}\; w\_j\; =\; 1$$

---

Common Constraint Penalty Function

$$P(\mathbf{x})={\alpha }_1\max (0,N_{\text{service}}-n_s{)}^2+{\alpha }_2\max (0,N_{\text{standby}}^{\min }-n_{sb}{)}^2+{\alpha }_3\sum _{i\in T}{v}_{i}P(\backslash mathbf\{x\})\; =\; \backslash alpha\_1\; \backslash max(0,\; N\_\{\backslash text\{service\}\}\; -\; n\_s)^2\; +\; \backslash alpha\_2\; \backslash max(0,\; N\_\{\backslash text\{standby\}\}^\{\backslash min\}\; -\; n\_\{sb\})^2\; +\; \backslash alpha\_3\; \backslash sum\_\{i\; \backslash in\; T\}\; v\_i$$

where:

• $n_s = \sum_i \mathbb{1}_{x_i = 0}$: actual service count
• $n_{sb} = \sum_i \mathbb{1}_{x_i = 1}$: actual standby count
• $v_i$: trainset-specific violations (e.g., maintenance requirements)
• $\alpha_1, \alpha_2, \alpha_3$: penalty coefficients

---

Balance Score (Mileage Variance Minimization)

Implementation formula (used in code): $$B=100-\min (\frac{{\sigma }_m}{1000},100)B\; =\; 100\; -\; \backslash min\backslash left(\backslash frac\{\backslash sigma\_m\}\{1000\},\; 100\backslash right)$$

Theoretical normalized formula: $$B_{\text{norm}}=1-\frac{{\sigma }_m}{{\sigma }_m^{\max }}B\_\{\backslash text\{norm\}\}\; =\; 1\; -\; \backslash frac\{\backslash sigma\_m\}\{\backslash sigma\_m^\{\backslash max\}\}$$

where: $${\sigma }_m=\sqrt{\frac{1}{\mathrm{\mid }S\mathrm{\mid }}\sum _{i\in S}(m_i-\bar{m}{)}^2}\backslash sigma\_m\; =\; \backslash sqrt\{\backslash frac\{1\}\{|S|\}\; \backslash sum\_\{i\; \backslash in\; S\}\; (m\_i\; -\; \backslash bar\{m\})^2\}$$

• $S = {i : x_i = 0}$: trainsets in service
• $m_i$: mileage of trainset $i$ (in km)
• $\bar{m} = \frac{1}{|S|}\sum_{i \in S} m_i$: mean mileage
• Factor 1000 in implementation scales std dev to reasonable range