import random
import math
import matplotlib.pyplot as plt
import numpy as np
from geopy.distance import geodesic

# --- DANE WEJŚCIOWE ---

zapotrzebowania = {
    "Kraków": 0, "Białystok": 500, "Bielsko-Biała": 50, "Chrzanów": 400, "Gdańsk": 200,
    "Gdynia": 100, "Gliwice": 40, "Gromnik": 200, "Katowice": 300, "Kielce": 30,
    "Krosno": 60, "Krynica": 50, "Lublin": 60, "Łódź": 160, "Malbork": 100,
    "Nowy Targ": 120, "Olsztyn": 300, "Poznań": 100, "Puławy": 200, "Radom": 100,
    "Rzeszów": 60, "Sandomierz": 200, "Szczecin": 150, "Szczucin": 60, "Szklarska Poręba": 50,
    "Tarnów": 70, "Warszawa": 200, "Wieliczka": 90, "Wrocław": 40, "Zakopane": 200, "Zamość": 300
}

wspolrzedne = {
    "Kraków": (50.06465, 19.9450), "Białystok": (53.1325, 23.1688),
    "Bielsko-Biała": (49.8224, 19.0480), "Chrzanów": (50.1333, 19.4000), "Gdańsk": (54.3520, 18.6466),
    "Gdynia": (54.5189, 18.5300), "Gliwice": (50.2945, 18.6714), "Gromnik": (49.8567, 20.9776),
    "Katowice": (50.2704, 19.0238), "Kielce": (50.8661, 20.6286), "Krosno": (49.6892, 21.7700),
    "Krynica": (49.4261, 20.9574), "Lublin": (51.2465, 22.5684), "Łódź": (51.7592, 19.4550),
    "Malbork": (54.0400, 19.0300), "Nowy Targ": (49.4777, 20.0321), "Olsztyn": (53.7784, 20.4801),
    "Poznań": (52.4064, 16.9252), "Puławy": (51.4167, 21.9667), "Radom": (51.4027, 21.1460),
    "Rzeszów": (50.0413, 21.9990), "Sandomierz": (50.6822, 21.7499), "Szczecin": (53.4285, 14.5528),
    "Szczucin": (50.3108, 21.0693), "Szklarska Poręba": (50.8260, 15.5130), "Tarnów": (50.0138, 20.9869),
    "Warszawa": (52.2297, 21.0122), "Wieliczka": (49.9873, 20.0640), "Wrocław": (51.1079, 17.0385),
    "Zakopane": (49.2992, 19.9496), "Zamość": (50.7231, 23.2519)
}

liczba_pojazdow = 5
pojemnosc_pojazdu = 1000

# --- MACIERZ ODLEGŁOŚCI ---

macierz_odleglosci = {}
for m1 in zapotrzebowania:
    macierz_odleglosci[m1] = {}
    for m2 in zapotrzebowania:
        if m1 == m2:
            macierz_odleglosci[m1][m2] = 0.0
        else:
            macierz_odleglosci[m1][m2] = geodesic(wspolrzedne[m1], wspolrzedne[m2]).km

# --- HEURYSTYKA NAJBLIŻSZEGO SĄSIADA ---

def najblizszy_sasiad_trasy(trasa, dystanse):
    if not trasa:
        return []
    nieodwiedzeni = set(trasa)
    aktualny = "Kraków"
    wynik = []
    while nieodwiedzeni:
        next_city = min(nieodwiedzeni, key=lambda k: dystanse[aktualny][k])
        wynik.append(next_city)
        nieodwiedzeni.remove(next_city)
        aktualny = next_city
    return wynik

# --- LOSOWE POCZĄTKOWE ROZWIĄZANIE (OPTYMALIZACJA KOLEJNOŚCI W TRASACH) ---

klienci = [m for m in zapotrzebowania if m != "Kraków"]
random.shuffle(klienci)
rozwiazanie = [[] for _ in range(liczba_pojazdow)]
ladunki = [0] * liczba_pojazdow

for klient in klienci:
    for pojazd in range(liczba_pojazdow):
        if ladunki[pojazd] + zapotrzebowania[klient] <= pojemnosc_pojazdu:
            rozwiazanie[pojazd].append(klient)
            ladunki[pojazd] += zapotrzebowania[klient]
            break

for i in range(liczba_pojazdow):
    rozwiazanie[i] = najblizszy_sasiad_trasy(rozwiazanie[i], macierz_odleglosci)

# --- FUNKCJA LICZENIA DYSTANSU ---

def suma_dystansow(rozw):
    suma = 0
    for trasa in rozw:
        if not trasa:
            continue
        aktualny = "Kraków"
        for klient in trasa:
            suma += macierz_odleglosci[aktualny][klient]
            aktualny = klient
        suma += macierz_odleglosci[aktualny]["Kraków"]
    return suma

# --- SYMULOWANE WYŻARZANIE Z OPTYMALIZACJĄ KOLEJNOŚCI W TRASIE ---

najlepsze_rozw = [lista[:] for lista in rozwiazanie]
najlepszy_koszt = suma_dystansow(rozwiazanie)
aktualne_rozw = [lista[:] for lista in rozwiazanie]
aktualny_koszt = najlepszy_koszt

T = 2000
alpha = 0.995
max_iter = 30000

for _ in range(max_iter):
    sasiad = [lista[:] for lista in aktualne_rozw]
    niepuste = [i for i, trasa in enumerate(sasiad) if trasa]
    if not niepuste:
        continue
    z = random.choice(niepuste)
    do = random.randint(0, liczba_pojazdow-1)
    if z != do and sasiad[z]:
        idx = random.randint(0, len(sasiad[z])-1)
        klient = sasiad[z].pop(idx)
        lad_otr = sum(zapotrzebowania[k] for k in sasiad[do])
        if lad_otr + zapotrzebowania[klient] <= pojemnosc_pojazdu:
            sasiad[do].append(klient)
            # OPTYMALIZUJEMY KOLEJNOŚĆ w dwóch zmienionych trasach:
            sasiad[z] = najblizszy_sasiad_trasy(sasiad[z], macierz_odleglosci)
            sasiad[do] = najblizszy_sasiad_trasy(sasiad[do], macierz_odleglosci)
            koszt_sasiada = suma_dystansow(sasiad)
            if koszt_sasiada < aktualny_koszt or random.random() < math.exp(-(koszt_sasiada-aktualny_koszt)/T):
                aktualne_rozw = [lista[:] for lista in sasiad]
                aktualny_koszt = koszt_sasiada
                if aktualny_koszt < najlepszy_koszt:
                    najlepsze_rozw = [lista[:] for lista in aktualne_rozw]
                    najlepszy_koszt = aktualny_koszt
    T *= alpha
    if T < 0.1:
        break

# --- WYNIKI ---

print("\n=== NAJLEPSZE ZNALEZIONE ROZWIĄZANIE ===\n")
for nr, trasa in enumerate(najlepsze_rozw):
    ladunek = sum(zapotrzebowania[k] for k in trasa)
    if trasa:
        print(f"Pojazd {nr+1}: Kraków → {' → '.join(trasa)} → Kraków (ładunek: {ladunek}/{pojemnosc_pojazdu})")
    else:
        print(f"Pojazd {nr+1}: NIEUŻYWANY")
print(f"\nCałkowity dystans: {najlepszy_koszt:.2f} km")

# --- WIZUALIZACJA ROZWIĄZANIA ---

import matplotlib.pyplot as plt

plt.figure(figsize=(13, 9))
colors = ['green', 'purple', 'orange', 'brown', 'magenta', 'cyan', 'gray', 'lime']

# Najpierw rysujemy wszystkie miasta (punkty)
for miasto in wspolrzedne:
    lat, lon = wspolrzedne[miasto]
    plt.scatter(lon, lat, color='lightblue', s=80, zorder=3, edgecolors='navy', alpha=0.8)
    plt.annotate(miasto, (lon, lat), fontsize=8, xytext=(5,5), textcoords='offset points', zorder=5)

# Magazyn
plt.scatter(wspolrzedne["Kraków"][1], wspolrzedne["Kraków"][0],
            c='red', s=140, marker='s', label='Magazyn (Kraków)', edgecolors='black', zorder=10)

# Trasy pojazdów
for i, trasa in enumerate(najlepsze_rozw):
    if not trasa:
        continue
    kolor = colors[i % len(colors)]
    pelna_trasa = ["Kraków"] + trasa + ["Kraków"]
    xs = [wspolrzedne[m][1] for m in pelna_trasa]
    ys = [wspolrzedne[m][0] for m in pelna_trasa]
    plt.plot(xs, ys, color=kolor, linewidth=2.5, marker='o', markersize=5, alpha=0.85, label=f'Pojazd {i+1}')

plt.xlabel("Długość geograficzna (°E)", fontsize=12)
plt.ylabel("Szerokość geograficzna (°N)", fontsize=12)
plt.title("Rozwiązanie VRP – Symulowane wyżarzanie", fontsize=14, fontweight='bold')
plt.legend(bbox_to_anchor=(1.05, 1), loc='upper left')
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()


ocen python 3