El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Desenvolupament del Projecte

Següent ►
►

Tens una especificació validada; ara cal convertir-la en codi sense morir en l'intent. La trampa clàssica de l'autodidacta és començar per la part "interessant" (l'algorisme sofisticat) i deixar per al final el pegament: la càrrega de dades, l'avaluació, la comparació. Resultat habitual: a les 25 hores hi ha quatre peces brillants que no encaixen i cap número per ensenyar. En aquesta lliçó farem el contrari, seguint la tècnica del tracer bullet (bala traçadora): primer un pipeline complet de cap a cap amb la solució més ximple possible, i després millores per capes, mesurant després de cadascuna. Ho veurem amb codi real sobre el projecte de referència de Rutalia especificat a 07-01; si el teu projecte és un altre, l'estructura, les fites i la disciplina de mesurament es traslladen tal qual.

Contingut

  1. Estructura del projecte Python
  2. La bala traçadora: fita 0, la línia base que ja funciona
  3. Millores per capes: fites 1 a 3 amb mesurament intermedi
  4. Experiments reproduïbles: llavors, configuració i resultats
  5. Mesurament seriós: predir el cost i comprovar-lo
  6. Proves mínimes que valen el que pesen
  7. Quan parar d'optimitzar

Estructura del projecte Python

Abans de la primera funció, crea aquesta estructura. Separa el que canvia a ritmes diferents: les dades es generen una vegada, els algorismes evolucionen per capes, l'avaluació no s'ha de tocar mai (és l'àrbitre) i els experiments són scripts que combinen tot l'anterior.

planificador-rutalia/
├── README.md               # es completa a 07-03
├── requirements.txt        # numpy, scipy, matplotlib
├── config.py               # paràmetres i llavors, GENS de lògica
├── dades/
│   ├── generador.py        # crea l'històric i les instàncies sintètiques
│   └── instancies/         # .npz generats (no s'editen a mà)
├── algorismes/
│   ├── regressio.py        # model de temps (05-03)
│   ├── clustering.py       # k-means (05-05)
│   ├── assignacio.py       # hongarès (03-06)
│   └── rutes.py            # veí més proper + 2-opt (06-01)
├── avaluacio/
│   └── metriques.py        # cost real d'un pla; l'àrbitre únic
├── experiments/
│   ├── exp_baseline.py     # fita 0
│   ├── exp_capes.py        # compara variants amb diverses llavors
│   └── resultats/          # .csv amb paràmetres + resultats
└── tests/
    └── test_basics.py

Regles que estalvien maldecaps més endavant:

  • avaluacio/ només avalua amb les dades veritables del generador, mai amb els temps predits pel teu model. Si el pla es puntua amb les mateixes prediccions que el van construir, un model dolent s'autofelicita — és la fuga de dades (leakage) de 06-04 disfressada d'optimització.
  • config.py concentra tots els números màgics (nre. de comandes, k, llavors, iteracions de 2-opt). Un experiment s'ha de poder canviar sense editar algorismes.
  • Cada mòdul es pot provar sol: rutes.py rep una matriu de temps i retorna un ordre; no sap d'on ha sortit la matriu.

Fita 0: la bala traçadora

El primer dia de feina acaba amb el sistema sencer funcionant malament. Generador de dades, pla ingenu, avaluació i número final: tot connectat.

# dades/generador.py
import numpy as np

def generar_historic(n=3000, llavor=42):
    """Trajectes històrics: [x1,y1,x2,y2,hora] -> minuts reals."""
    rng = np.random.default_rng(llavor)
    X = rng.uniform(0, 10, size=(n, 4))          # coords en km
    hora = rng.integers(7, 22, size=n)
    dist = np.hypot(X[:, 2] - X[:, 0], X[:, 3] - X[:, 1])
    punta = np.isin(hora, [8, 9, 18, 19]) * 1.6  # penalització hora punta
    y = dist / 0.35 * (1 + punta * 0.4) + rng.normal(0, 2.0, n)
    return np.column_stack([X, hora]), np.maximum(y, 1.0)

def generar_jornada(n_comandes=80, n_repartidors=5, llavor=0):
    rng = np.random.default_rng(llavor)
    comandes = rng.uniform(0, 10, size=(n_comandes, 2))
    diposit = np.array([5.0, 5.0])
    return comandes, diposit, n_repartidors
# experiments/exp_baseline.py
from dades.generador import generar_jornada
from avaluacio.metriques import cost_pla   # fa servir els temps VERITABLES

def pla_baseline(comandes, n_rep):
    """Blocs consecutius per ordre d'arribada, ruta sense ordenar."""
    mida = len(comandes) // n_rep
    return [list(range(i * mida, (i + 1) * mida)) for i in range(n_rep)]

comandes, diposit, n_rep = generar_jornada(llavor=0)
pla = pla_baseline(comandes, n_rep)
print(f"Cost total línia base: {cost_pla(pla, comandes, diposit):.0f} min")

Sortida de l'exemple: Cost total línia base: 612 min. És un número horrible i és exactament el que volíem: ja existeix la vara de mesurar, el format del pla (llista de rutes, cada ruta una llista d'índexs de comanda) i l'àrbitre. Tot el que facis a partir d'aquí, o baixa de 612, o sobra.

flowchart LR
    G[generador de dades] --> P[pla: baseline]
    P --> E[avaluacio amb temps reals]
    E --> R[numero final]
    P -. "fites 1-3: substituir<br/>per capes millors" .-> P

Fites 1 a 3: millorar per capes

Cada fita substitueix una peça del pipeline per la seva versió algorísmica, es mesura contra la taula acumulada i es desa el resultat. Mai dues capes alhora: si el número empitjora, vols saber quina capa ha estat.

Fita 1: regressió de temps (05-03)

Entrenem la regressió lineal amb descens de gradient sobre l'històric (trets: distància, indicador d'hora punta) i construïm la matriu de temps entre tots els punts de la jornada. Amb ella, cada repartidor ordena el seu bloc amb veí més proper — l'assignació continua sent la ingènua.

# algorismes/regressio.py (esquelet d'integració)
import numpy as np

def trets(X):
    dist = np.hypot(X[:, 2] - X[:, 0], X[:, 3] - X[:, 1])
    punta = np.isin(X[:, 4], [8, 9, 18, 19]).astype(float)
    return np.column_stack([np.ones(len(X)), dist, dist * punta])

def entrenar(X, y, lr=0.01, epoques=500):
    A = trets(X)
    w = np.zeros(A.shape[1])
    for _ in range(epoques):
        w -= lr * A.T @ (A @ w - y) / len(y)   # gradient de l'EQM
    return w

def matriu_temps(punts, w, hora=9):
    n = len(punts)
    parells = np.array([[*punts[i], *punts[j], hora]
                        for i in range(n) for j in range(n)])
    return (trets(parells) @ w).reshape(n, n)

Mesurem dues coses: la qualitat del model (MAE en el 20 % de test: 3,1 min, dins de l'objectiu < 4 de l'especificació) i l'efecte en el pla.

Fita 2: clustering + assignació (05-05, 03-06)

k-means agrupa les 80 comandes en 5 zones compactes; l'algorisme hongarès assigna cada grup al repartidor amb el cost de cobrir-lo (temps predit dipòsit → centroide, com a aproximació) més baix. En la nostra versió tots els repartidors surten del dipòsit, així que l'hongarès amb prou feines canvia el cost aquí — el mantenim perquè generalitza a repartidors amb punts d'inici diferents, i ho anotem amb honestedat als resultats.

# fragment d'experiments/exp_capes.py
from scipy.optimize import linear_sum_assignment
from algorismes.clustering import kmeans            # 05-05, propi
grups, centroides = kmeans(comandes, k=n_rep, llavor=0)
cost = matriu_cost_repartidor_grup(centroides, diposit, w)
files, cols = linear_sum_assignment(cost)           # hongarès (03-06)
pla = [grups[c] for c in cols]

Fita 3: 2-opt (06-01)

Sobre cada ruta, veí més proper dona l'ordre inicial i 2-opt el refina invertint segments mentre hi hagi millora, igual que al dia operatiu de 06-01 — però ara sobre la matriu de temps predits, no de distàncies.

Taula de resultats intermedis de l'exemple (instància llavor=0, avaluada sempre amb temps veritables):

Fita Variant Cost total (min) Millora vs. base Temps de còmput
H0 Blocs + ordre d'arribada 612 — < 0,01 s
H1 Blocs + NN sobre temps predits 471 −23 % 0,4 s
H2 k-means + hongarès + NN 388 −37 % 0,6 s
H3 k-means + hongarès + NN + 2-opt 342 −44 % 2,1 s

Amb una sola instància això és una anècdota; l'objectiu del ≥ 30 % de l'especificació només es declara complert després de la secció següent.

Experiments reproduïbles

Tres regles converteixen "m'ha sortit 342" en un experiment:

  1. Llavors explícites i separades. Una llavor per a les dades, una altra per als algorismes estocàstics (k-means). Totes dues a config.py, mai un np.random.seed dispers pels mòduls.
  2. Configuració fora del codi. Canviar N_COMANDES o K no ha de tocar cap algorisme.
  3. Cada execució desa paràmetres + resultat junts. Un CSV al qual s'afegeix una fila per execució; sense això, a la fita 4 no recordaràs quina configuració va produir quin número.
# experiments/exp_capes.py (bucle principal)
import csv, time
from config import LLAVORS_DADES, LLAVORS_ALGO, VARIANTS

with open("experiments/resultats/capes.csv", "a", newline="") as f:
    w = csv.writer(f)
    for sd in LLAVORS_DADES:               # 10 instàncies de jornada
        for sa in LLAVORS_ALGO:            # 5 llavors d'algorisme
            for nom, planificar in VARIANTS.items():
                t0 = time.perf_counter()
                pla = planificar(sd, sa)
                w.writerow([nom, sd, sa,
                            cost_pla_des_de(pla, sd),
                            time.perf_counter() - t0])

Agregant les 10 instàncies × 5 llavors de l'exemple: millora mitjana de l'H3 sobre la base −41 % (mínima −33 %, màxima −47 %). Ara sí: objectiu complert, amb variabilitat coneguda en lloc d'un número solt.

Mesurament seriós: predir el cost, després mesurar-lo

El mòdul 1 et va donar un superpoder que la majoria de projectes desaprofita: saber quant costarà una cosa abans d'executar-la. Fes-lo servir com a prova creuada de la teva pròpia implementació:

Peça Cost teòric (01-01/01-02) Predicció per a n=80, k=5 Mesurat coherent?
Matriu de temps O(n²) avaluacions del model 6 400 files vectoritzades: ms Sí (~0,3 s amb construcció de parells)
k-means O(iter · n · k) trivial Sí
Hongarès O(k³) 125 operacions: no res Sí
2-opt per ruta O(passades · m²), m≈16 ~256 comprovacions/passada Sí (~1,5 s total)

Si el que has mesurat es desvia ordres de magnitud del que has predit, gairebé sempre has trobat un bug (un bucle O(n³) accidental, una matriu que es reconstrueix dins d'un bucle). Verifica també l'escalabilitat empírica: duplica n i comprova que el temps de la matriu es multiplica per ~4, com mana O(n²) — la mateixa tècnica de duplicació que vas fer servir a 01-02.

Proves mínimes

No necessites una suite industrial; necessites no enganyar-te. Dos tipus de prova basten:

Casos petits verificables a mà. Una jornada de 4 comandes i 2 repartidors on l'òptim es calcula amb llapis; el teu pipeline l'ha de trobar o quedar-s'hi molt a prop.

Propietats invariants que s'han de complir per a qualsevol entrada:

# tests/test_basics.py
def test_pla_valid():
    pla = planificar_h3(llavor_dades=0, llavor_algo=0)
    visitades = [c for ruta in pla for c in ruta]
    assert sorted(visitades) == list(range(80))   # cada comanda, una vegada
    assert len(pla) == 5                           # una ruta per repartidor

def test_2opt_mai_empitjora():
    ruta, M = ruta_exemple()
    assert cost_ruta(dos_opt(ruta, M), M) <= cost_ruta(ruta, M) + 1e-9

def test_matriu_temps_positiva_i_diagonal_zero():
    M = matriu_temps(comandes_exemple(), w_entrenat)
    assert (M[~np.eye(len(M), dtype=bool)] > 0).all()

Adapta les propietats al teu domini: en un projecte de flux, "el flux es conserva a cada node"; en un d'horaris, "cap recurs no és a dos llocs alhora"; en un d'ordenació externa, "la sortida està ordenada i és permutació de l'entrada".

Quan parar d'optimitzar

El senyal de parada no és "ja no se m'acut res més", sinó qualsevol d'aquests tres:

  • Objectiu de l'especificació complert amb variabilitat mesurada. El nostre era ≥ 30 %; portem −41 % mitjà amb pitjor cas −33 %. Complert.
  • Rendiments decreixents. L'H1 va aportar 23 punts, l'H2 14 més, l'H3 7 més. Una hipotètica capa H4 (3-opt, o or-opt) costaria hores per gratar 2-3 punts: s'anota com a treball futur, no s'implementa.
  • Pressupost d'hores esgotat segons el pla de fites. El pla de 07-01 reservava 6 hores per a la fita 4 (experiments i informe); robar-les-hi per a una micromillora és un mal canvi, perquè el mesurament i la comunicació valen més nota que el 2 % extra.

Regla pràctica final: cada millora addicional ha de justificar per endavant quina mètrica mourà i quant estima moure-la. Si no saps respondre, no la comencis.

Errors Comuns i Consells

  • Error: avaluar amb els temps predits. El més perillós de tot el projecte: el pla optimitza prediccions i es puntua amb elles, així que millorar el model "millora" el resultat encara que les rutes reals empitjorin. L'àrbitre fa servir sempre les dades veritables del generador (o un conjunt d'avaluació separat).
  • Error: dues capes alhora. Si integres regressió i clustering a la mateixa sessió i el cost puja, no saps a qui culpar. Una capa, un mesurament, un commit.
  • Error: resultats per pantalla i a una altra cosa. El número que no es desa amb els seus paràmetres no existeix. El CSV de resultats és tan part del projecte com el codi.
  • Error: optimitzar el codi abans que l'algorisme. Vectoritzar una línia base O(n³) és polir el camarot del Titànic; primer la millora asimptòtica (01-02), després les constants, i només si el temps de còmput és realment un problema.
  • Consell: commits per fita amb el número al missatge. git commit -m "H2: kmeans+hongares, 388 min (-37%) llavor 0" et dona un historial que a 07-03 es converteix gairebé sol en la secció de resultats.
  • Consell: quadern de decisions. Un DECISIONS.md amb una línia per elecció ("2-opt i no 3-opt perquè O(m²) vs O(m³) i m=16") — a la propera lliçó serà or per a la taula de justificació de mètodes.

Exercicis

Com a 07-01, són fites guiades del teu propi projecte.

Exercici 1: bala traçadora

Implementa la teva fita 0 completa: generador de dades amb llavor, línia base ximple, avaluador i número final imprès. Prohibit implementar cap algorisme "bo" encara.

Exercici 2: capes amb taula

Desenvolupa les teves fites intermèdies d'una en una i construeix la teva taula de resultats acumulada (variant, mètrica, millora vs. base, temps de còmput), mesurant cada capa per separat.

Exercici 3: reproduïbilitat i proves

Executa la teva comparació final amb almenys 5 instàncies × 3 llavors desant un CSV, i escriu un mínim de 3 proves: un cas petit a mà i dues propietats invariants del teu domini.

Solucions

Exercici 1 — criteris d'autoavaluació. Prova definitiva: esborra-ho tot excepte el repositori, clona'l i executa python experiments/exp_baseline.py; ha d'imprimir el mateix número (llavor fixa). A més: l'avaluador viu al seu propi mòdul i no importa res d'algorismes/; el format de "pla/solució" ja és el definitiu. Si la teva línia base ha trigat més d'una tarda, la teva especificació de 07-01 tenia la línia base massa ambiciosa: simplifica-la i anota-ho.

Exercici 2 — solució orientativa. Una taula sana mostra millores decreixents per capa (com 23/14/7 a Rutalia) i temps de còmput que creixen de forma coherent amb l'anàlisi teòrica. Dues situacions legítimes que no has d'amagar: una capa que no millora (com el nostre hongarès amb dipòsit únic — se'n documenta el perquè) i una capa que millora la mètrica però dispara el temps (decisió de compromís: registra totes dues columnes). Senyal d'alarma: millores creixents per capa solen indicar que la línia base era artificialment dolenta o que hi ha leakage a l'avaluació.

Exercici 3 — criteris d'autoavaluació. El CSV ha de permetre reconstruir qualsevol número de la teva taula amb un groupby (variant → mitjana, mínim, màxim); si necessites "recordar" alguna cosa que no és al fitxer, hi falten columnes de paràmetres. Sobre les proves: la del cas petit ha de tenir el resultat esperat calculat a mà en un comentari, i les propietats han de fallar si introdueixes un bug deliberat (prova-ho: trenca el 2-opt invertint malament els índexs i verifica que el test ho caça). Un test que no pot fallar no protegeix res.

Conclusió

El projecte ja existeix: estructura neta amb dades, algorismes, avaluació i experiments separats; una línia base que va funcionar de cap a cap des del primer dia; tres capes algorísmiques integrades una a una — regressió de temps (05-03), clustering i assignació (05-05, 03-06), veí més proper amb 2-opt (06-01) — cadascuna amb el seu mesurament; experiments amb llavors múltiples que converteixen un número solt en un resultat amb variabilitat (−41 % mitjà, pitjor cas −33 %); proves que impedeixen l'autoengany i un criteri clar de parada. Però un projecte que només entens tu està a mig acabar: a l'última lliçó del curs (07-03) escriurem l'informe final, prepararem el repositori perquè qualsevol el pugui reproduir, avaluarem la feina amb una rúbrica honesta — i tancarem el viatge que va començar, fa set mòduls, amb una notació asimptòtica i una empresa de repartiment anomenada Rutalia.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats