Simulirano kaljenje je S-metaheuristika zasnovana na lokalnom pretraživanju koja dozvoljava posećivanje lošijih rešenja u cilju nalaženja globalnog optimuma. Inspirisana je procesom kaljenja čelika. Metoda započinje izborom početnog rešenja (na slučajan način ili nekom heuristikom) i postavljanjem parametra koji predstavlja temperaturu na relativno visoku vrednost $T_0$. U svakoj iteraciji na slučajan način se bira sused $x'$ iz (unapred određene) okoline tekućeg rešenja $x$. Ako je izabrano rešenje $x'$ bolje od $x$ (u pogledu vrednosti funkcije cilja), ono postaje tekuće i nastavlja se sa pretraživanjem njegove okoline. Ukoliko je lošije od tekućeg, $x_0$ se prihvata sa određenom verovatnoćom. Verovatnoća prihvatanja lošijeg rešenja obično zavisi od temperature, kao i stepena degradacije lošijeg rešenja, i opada sa povećanjem broja iteracija algoritma. Pri kraju izvrsavanja verovatnoća prihvatanja lošijeg resenja je minimalna, tj. vrlo verovatno se neće prihavtiti lošije rešenje jer se smatra da je već dostignut određen kvalitet rešenja i na ovaj način se izbegava moguće pogoršavanje tekućeg rešenja. Jedan od mogućih načina definisanja verovatnoće je:

$$ p(T)=e^{-\delta/T},\ \delta=f(x')-f(x) $$

Za svaku vrednost temperature, izvršava se nekoliko iteracija u kojima se na slučajan način bira novo rešenje iz okoline tekućeg sa ciljem stabilizovanja rešenja na trenutnoj temperaturi. Potom se, nakon određenog broja iteracija vrši snižavanje temperature, čime se smanjuje verovatnoća prihvatanja lošijeg rešenja kako pretraga napreduje. Pri veoma niskoj temperaturi algoritam teži lokalnom pretraživanju.

%Generisanje inicijalnog resenja, postavljanje parametara, definisanje okoline 
x=x_0; 
T=T0; %postavljanje inicijalne temperature

while T>Tf %dok je temperatura veca od minimalne
		for i=1:iter %iter - broj iteracija na istoj termperaturi
				x'= generisi_nasumicno_resenje_u_okolini_tekuceg(x);
				delta = f(x')-f(x);
				if delta<=0  %nasli smo bolje resenje
						x=x';
				else 
						resenje x' prihvatamo za tekuce sa verovatnocom p(T);
				end
		end
T=T*v; %snizavanje temperature (hladjenje)
end 			

Problem rutiranja vozila sa ograničenim kapacitetima

(Capacitated Vehicle Routing Problem - CVRP)

Pretpostavimo da imamo $n$ klijenata sa odgovarajućim potrebаma koje treba uslužiti. Na raspolaganju je $m$ vozila jednakih kapaciteta $Q$ i jedno skladište $s$. Zadatak je odrediti rutu svakog vozila tako da ukupni transportni trošak bude minimalan, poštujući sledeća ograničenja:

1. Svaki klijent mora biti uslužen od strane tačno jednog vozila.
2. Suma potreba svih korisnika koje uslužuje isto vozilo ne sme biti veća od $Q$.
3. Svako vozilo svoju rutu započinje i završava u skladištu $s$.

Na slici 1 dat je primer dopustivog rešenja instance koja ima 7 korisnika, 3 vozila i kapacitet svakog vozila je 50. Skladište je locirano u nultom čvoru i ono predstavlja početnu i krajnju tačku svake rute. Broj koji se nalazi pored svakog čvora (korisnika) označava njegovu potrebu.

Neka je $G=(V,E)$ kompletan usmeren graf sa skupom čvorova $V=\{0,1,2,...,n\}$ i skupom grana $E=\{(i,j): i,j \in V,i\neq j\}$. Svakoj grani pridružena je nenegativna težina $c_{ij}$ koja predstavlja rastojanje (transportni trošak) od korisnika $i$ do korisnika $j$. Matrica rastojanja je simetrična, tj. važi $c_{ij}=c_{ji}, \ \forall i,j\in V, i\neq j$ i zadovoljava nejednakost trougla, $c_{ij}+c_{jk}\geq c_{ik}, \forall i,j,k \in V.$ Skladište je predstavljeno nultim čvorom. Svakom korisniku $i \in V$ pridružena je težina $d_i$ koja predstvalja njegovu potrebu za određenom robom. Budući da nulti čvor predstavlja skaldište, važi da je $d_0=0$. Na raspolaganju je $m$ vozila kapaciteta $Q$ i zadatak je naći optimalnu rutu svakog vozila, tj. $m$ ruta kojima se minimizuje ukupni transportni trošak pri čemu uslovi 1,2. i 3. moraju biti ispunjeni.

Uvodimo skup binarnih promenljivih:

$$ x_{rij}=\left\{\begin{matrix} 1, \text{grana } (i,j) \text{ je deo rute vozila } r \\ 0, \text{inače} \end{matrix}\right. $$