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

Optimització a la Indústria

Següent ►
►

Al final del mòdul 5 vam dir que deixàvem d'esmolar eines per sortir al món. Aquesta lliçó és la primera sortida: veurem on viu l'optimització a la indústria real —logística, manufactura, energia, planificació de personal— i, sobretot, resoldrem de cap a cap "un dia a l'operativa de Rutalia" encadenant peces que ja vas construir: el clustering de 05-05, l'algorisme hongarès de 03-06 i el TSP del mòdul 2, al qual afegirem una tècnica nova i lleugera (la millora 2-opt). L'objectiu ja no és entendre un algorisme, sinó una cosa més difícil i més valuosa: modelar — traduir un problema de negoci als algorismes correctes, triar entre alternatives i mesurar la millora a cada pas.

Contingut

  1. El mapa de l'optimització industrial
  2. El cas central: un dia a l'operativa de Rutalia
  3. Pas 1 — Agrupar comandes en zones de repartiment (clustering)
  4. Pas 2 — Assignar repartidors a zones (algorisme hongarès)
  5. Pas 3 — Ordenar les parades dins de cada zona (TSP + 2-opt)
  6. Mesurar la millora: el pipeline complet amb mètriques
  7. Més enllà del cas: torns com a PL, i el VRP com a generalització real
  8. La lliçó d'enginyeria: "prou bo avui"

El mapa de l'optimització industrial

L'optimització industrial no és un algorisme: és una disciplina de modelatge. A cada sector el problema de negoci sona diferent, però a sota gairebé sempre hi ha un problema canònic que ja coneixes d'aquest curs:

Domini Problema de negoci Problema canònic Algorisme del curs
Logística En quin ordre visito les meves parades? TSP / VRP PD i B&B (02-02, 02-03), genètics (02-04), formigues (02-05)
Logística Com omplo furgonetes sense malbaratar espai? Bin packing FFD i voraços (02-02)
Manufactura Quina barreja de productes fabrico amb recursos limitats? Programació lineal Símplex amb scipy.linprog (02-01)
Manufactura En quin ordre passo treballs per les màquines? Scheduling (job shop) Voraços, backtracking, B&B (02-02, 02-03)
Energia Quines centrals engego cada hora? Unit commitment (PLE) PL entera (02-01) + heurístiques (02-04)
Energia / telecom Quina xarxa mínima connecta tots els nodes? Arbre d'expansió mínim Kruskal/Prim (03-04)
Personal Quantes persones per torn i qui cobreix cada tasca? Cobertura / assignació PL/PLE (02-01), hongarès (03-06)
Transport Quant de cabal suporta la meva xarxa i on és el coll d'ampolla? Flux màxim / tall mínim Edmonds-Karp (03-05)

Fixa't en el patró: la columna difícil no és l'última (els algorismes ja els tens), sinó la tercera. Reconèixer el problema canònic dins del problema de negoci és el 80 % de la feina. Un especialista en optimització passa més temps preguntant "quines restriccions són dures de veritat i quines són negociables?" que no pas programant.

flowchart LR
    A[Problema de negoci] --> B[Modelatge:<br>variables, restriccions, objectiu]
    B --> C[Problema canònic<br>reconegut]
    C --> D[Algorisme exacte<br>si la mida ho permet]
    C --> E[Heurística / metaheurística<br>si no]
    D --> F[Mesurar contra la<br>situació actual]
    E --> F
    F -->|no millora o trenca restriccions| B

Aquest bucle de tornada (mesurar → remodelar) és el que distingeix l'optimització real dels exercicis de llibre: el primer model gairebé mai no captura totes les restriccions que el negoci donava per òbvies.

El cas central: un dia a l'operativa de Rutalia

Situació: són les 7:00 i Rutalia té 60 comandes pendents per a avui, escampades per la ciutat, i 4 repartidors disponibles, cadascun amb un coneixement diferent de cada part de la ciutat. L'operativa actual —la que volem batre— és artesanal: un coordinador reparteix les comandes "a ull" per ordre d'arribada i cada repartidor improvisa la seva ruta.

El pla algorísmic encadena tres decisions, cadascuna amb el seu algorisme:

  1. Quines comandes van juntes? → clustering k-means (05-05) amb k = 4 zones.
  2. Quin repartidor porta cada zona? → assignació òptima amb l'algorisme hongarès (03-06).
  3. En quin ordre visita cada repartidor les seves parades? → TSP heurístic: veí més proper (02-02) + millora 2-opt (nova en aquesta lliçó).

Cada pas redueix el cost total i ho mesurarem. Primer, les dades fictícies (coordenades en km sobre la quadrícula de la ciutat que fem servir des de 01-03):

import random
import math

random.seed(42)

# 60 comandes: id i coordenades (km) en una ciutat de 10x10.
# Les generem al voltant de 4 focus de demanda, com els perfils
# de zona que vam descobrir amb clustering a 05-05.
focus = [(2, 2), (8, 3), (3, 8), (7.5, 7.5)]
comandes = []
for i in range(60):
    fx, fy = focus[i % 4]
    comandes.append({
        "id": f"P-{i+1:03d}",
        "x": fx + random.gauss(0, 1.0),
        "y": fy + random.gauss(0, 1.0),
    })

DIPOSIT = (5.0, 5.0)   # magatzem central, el paper del DEP al TSP de 02-02

def dist(a, b):
    return math.hypot(a[0] - b[0], a[1] - b[1])

La mètrica de negoci seran els quilòmetres totals recorreguts (tots els repartidors: sortida del dipòsit, totes les seves parades i tornada). Menys quilòmetres = menys combustible, menys hores i més lliuraments per jornada.

La línia base. Per saber si millorem necessitem un punt de comparació honest: simulem l'operativa "a ull" repartint les comandes en 4 blocs per ordre d'arribada (sense criteri geogràfic) i visitant-les en aquest mateix ordre.

def cost_ruta(parades):
    """Km d'una ruta DIPOSIT -> parades en ordre -> DIPOSIT."""
    if not parades:
        return 0.0
    punts = [DIPOSIT] + [(p["x"], p["y"]) for p in parades] + [DIPOSIT]
    return sum(dist(punts[i], punts[i + 1]) for i in range(len(punts) - 1))

# Línia base: 4 blocs de 15 comandes per ordre d'arribada
blocs = [comandes[i::4] for i in range(4)]
base = sum(cost_ruta(b) for b in blocs)
print(f"Línia base (repartiment a ull): {base:.1f} km")

Amb la llavor fixa, la línia base volta els 330 km. Tot el que fem a partir d'aquí es compara contra aquest número.

Pas 1 — Agrupar comandes en zones de repartiment (clustering)

A 05-05 vas implementar k-means i k-means++ des de zero; aquí el fem servir com a peça, sense reexplicar-ne la mecànica. La decisió de modelatge és una altra: per què clustering i no, per exemple, un repartiment equitatiu de 15 comandes per cap?

  • Perquè el cost dominant del repartiment són els desplaçaments entre comandes: les comandes properes han d'anar juntes.
  • Perquè k-means minimitza exactament això: la dispersió intragrup.
  • El preu: els grups poden quedar desequilibrats (18 comandes en una zona, 11 en una altra). A Rutalia avui ho acceptem; si fos inacceptable, caldria un model amb restricció de capacitat (ho reprenem quan parlem del VRP).
def kmeans(punts, k, iters=100):
    """k-means clàssic (vist a 05-05), versió compacta."""
    centroides = random.sample(punts, k)
    for _ in range(iters):
        grups = [[] for _ in range(k)]
        for p in punts:
            j = min(range(k), key=lambda c: dist(p, centroides[c]))
            grups[j].append(p)
        nous = [
            (sum(p[0] for p in g) / len(g), sum(p[1] for p in g) / len(g))
            if g else centroides[j]
            for j, g in enumerate(grups)
        ]
        if nous == centroides:
            break
        centroides = nous
    return centroides

coords = [(p["x"], p["y"]) for p in comandes]
centroides = kmeans(coords, k=4)

# Reconstruïm les zones com a llistes de comandes
zones = [[] for _ in range(4)]
for p in comandes:
    j = min(range(4), key=lambda c: dist((p["x"], p["y"]), centroides[c]))
    zones[j].append(p)

pas1 = sum(cost_ruta(z) for z in zones)
print(f"Després del clustering (rutes encara sense ordenar): {pas1:.1f} km")
for j, z in enumerate(zones):
    print(f"  Zona {j}: {len(z)} comandes, centroide ({centroides[j][0]:.1f}, {centroides[j][1]:.1f})")

Només agrupant bé —sense haver ordenat encara cap ruta— el total baixa típicament fins a uns 210 km: cada repartidor ja no travessa la ciutat sencera. Primera lliçó de modelatge: la decisió de nivell superior (què va amb què) sol moure més l'agulla que l'optimització fina posterior.

Pas 2 — Assignar repartidors a zones (algorisme hongarès)

Tenim 4 zones i 4 repartidors, però no són intercanviables: cada repartidor coneix millor unes parts de la ciutat (menys temps perdut, menys incidències). Modelem aquest coneixement com una matriu de cost repartidor × zona (minuts extres estimats per jornada) i resolem l'assignació òptima amb el mètode hongarès que ja vas fer servir via scipy a 03-06.

import numpy as np
from scipy.optimize import linear_sum_assignment

repartidors = ["R-01", "R-02", "R-03", "R-04"]
# cost[i][j]: minuts extres estimats si el repartidor i opera la zona j.
# Dades fictícies: a la pràctica sortirien de l'històric de lliuraments
# per zona, amb els models de regressió de 05-03.
cost = np.array([
    [12, 35, 28, 40],
    [30, 10, 33, 25],
    [27, 32, 11, 30],
    [38, 24, 29,  9],
])

files, cols = linear_sum_assignment(cost)
total = cost[files, cols].sum()
pitjor = sum(cost[i].max() for i in range(4))  # assignació pèssima, com a referència
for i, j in zip(files, cols):
    print(f"{repartidors[i]} -> Zona {j} ({cost[i][j]} min extres)")
print(f"Cost de l'assignació òptima: {total} min (la pitjor possible: {pitjor} min)")

Aquí la matriu és amable i l'òptim (42 min) es veu a primer cop d'ull, però aquest és justament el punt: amb 4×4 ho veus a ull; amb 40 repartidors i 40 zones ja no, i l'hongarès et continua donant l'òptim exacte en O(n³). Fixa't també d'on surten els números de la matriu: d'estimacions sobre l'històric — l'optimització d'aquest mòdul consumeix les prediccions del mòdul 5. Els mòduls no eren compartiments: eren capes.

Pas 3 — Ordenar les parades dins de cada zona (TSP + 2-opt)

Cada zona té ~15 parades més el dipòsit. A 02-02 vas veure que el TSP exacte per PD (Held-Karp) és O(2ⁿ·n²): amb 15 parades encara és viable però lent, i amb 25 impossible. La recepta industrial estàndard per a mides mitjanes és més humil i molt eficaç: construir una ruta ràpida amb el veí més proper (el voraç de 02-02, contraexemple inclòs) i millorar-la amb 2-opt.

2-opt, la tècnica nova d'aquesta lliçó. La idea cap en una frase: si la ruta es creua sobre si mateixa, descreuar-la sempre l'escurça. Formalment: pren dues arestes de la ruta, (a→b) i (c→d), elimina-les i reconnecta com (a→c) i (b→d), invertint el tram entre b i c. Si la suma de les dues arestes noves és menor que la de les velles, la ruta millora. Es repeteix fins que cap intercanvi no millori (òptim local).

flowchart LR
    subgraph Abans[Abans: la ruta es creua]
        A1((a)) --> B1((b))
        B1 -. tram .-> C1((c))
        C1 --> D1((d))
    end
    subgraph Despres[Després de l'intercanvi 2-opt]
        A2((a)) --> C2((c))
        C2 -. tram invertit .-> B2((b))
        B2 --> D2((d))
    end
    Abans --> Despres
def vei_mes_proper(parades, origen=DIPOSIT):
    """Construcció voraç: sempre cap a la parada més propera (02-02)."""
    pendents = parades[:]
    ruta, actual = [], origen
    while pendents:
        seg = min(pendents, key=lambda p: dist(actual, (p["x"], p["y"])))
        pendents.remove(seg)
        ruta.append(seg)
        actual = (seg["x"], seg["y"])
    return ruta

def millora_2opt(ruta):
    """Descreua la ruta fins a assolir un òptim local 2-opt."""
    def pts(r):
        return [DIPOSIT] + [(p["x"], p["y"]) for p in r] + [DIPOSIT]
    millorat = True
    while millorat:
        millorat = False
        P = pts(ruta)
        for i in range(len(ruta) - 1):
            for j in range(i + 1, len(ruta)):
                # arestes actuals: P[i]->P[i+1] i P[j+1]->P[j+2]
                abans = dist(P[i], P[i + 1]) + dist(P[j + 1], P[j + 2])
                despres = dist(P[i], P[j + 1]) + dist(P[i + 1], P[j + 2])
                if despres < abans - 1e-9:
                    ruta[i:j + 1] = reversed(ruta[i:j + 1])  # inverteix el tram
                    P = pts(ruta)
                    millorat = True
    return ruta

total_nn, total_2opt = 0.0, 0.0
for j, zona in enumerate(zones):
    ruta = vei_mes_proper(zona)
    km_nn = cost_ruta(ruta)
    ruta = millora_2opt(ruta)
    km_2opt = cost_ruta(ruta)
    total_nn += km_nn
    total_2opt += km_2opt
    print(f"Zona {j}: veí més proper {km_nn:.1f} km -> 2-opt {km_2opt:.1f} km")
print(f"Total NN: {total_nn:.1f} km | Total després de 2-opt: {total_2opt:.1f} km")

Detalls que importen en llegir el codi:

  • La condició despres < abans - 1e-9 evita bucles infinits per errors d'arrodoniment en coma flotant: només acceptem millores estrictes.
  • Cada passada avalua O(n²) intercanvis; amb 15 parades és instantani. Amb centenars de parades, 2-opt continua servint però convé accelerar-lo (llistes de veïns propers) o escalar a metaheurístiques: els genètics (02-04) i la colònia de formigues (02-05) són exactament l'evolució natural quan 2-opt s'encalla en un òptim local pobre o la instància creix.
  • 2-opt dona un òptim local, no global — la mateixa limitació que vas veure a k-means (05-05) i al descens de gradient (05-03). És un tema recurrent del curs: gairebé tota l'optimització pràctica és "millora local + saber quan conformar-se".

Mesurar la millora: el pipeline complet amb mètriques

Recapitulem el dia de Rutalia amb números (els teus variaran una mica amb una altra llavor; l'ordre de magnitud és el que és estable):

Etapa Algorisme Lliçó Km totals Millora acumulada
Línia base "a ull" — — ~330 —
Zones coherents k-means 05-05 ~210 ~36 %
Rutes construïdes Veí més proper 02-02 ~105 ~68 %
Rutes polides 2-opt 06-01 ~92 ~72 %
Repartidor ↔ zona Hongarès 03-06 42 min extres (vs 141 en el pitjor cas) (mètrica en minuts)

Tres observacions d'enginyeria:

  • Cada capa es mesura per separat. Si demà el negoci pregunta "què passa si trec el 2-opt per simplificar?", la resposta és un número (~13 km/dia), no una opinió.
  • El guany marginal decreix. El clustering va estalviar ~120 km; el 2-opt, ~13. Aquesta corba et diu on invertir el següent esforç.
  • La línia base honesta és sagrada. Comparar-se contra una línia base artificialment dolenta infla la millora i destrueix la credibilitat del projecte. És l'equivalent operatiu de la trampa de l'exactitud de 05-02.

Més enllà del cas: torns com a PL, i el VRP com a generalització real

Planificació de torns. L'altre gran clàssic industrial es modela amb la programació lineal de 02-01. Exemple mínim: Rutalia necessita cobrir una demanda de repartidors per franja (matí 6, migdia 10, tarda 8, nit 3) amb torns de 8 hores que cobreixen dues franges consecutives (el torn de nit enllaça amb el matí). Variables: quantes persones comencen a cada franja; objectiu: minimitzar plantilla; restriccions: cada franja coberta.

from scipy.optimize import linprog

# x[i] = persones que comencen el seu torn a la franja i (cobreixen la i i la i+1)
demanda = [6, 10, 8, 3]
# Cobertura de la franja f: x[f-1] + x[f] >= demanda[f]
# linprog minimitza amb A_ub @ x <= b_ub, així que neguem tots dos costats.
A_ub = [
    [-1,  0,  0, -1],   # franja 0: la cobreixen x0 i x3 (nit que enllaça)
    [-1, -1,  0,  0],   # franja 1: x0 i x1
    [ 0, -1, -1,  0],   # franja 2: x1 i x2
    [ 0,  0, -1, -1],   # franja 3: x2 i x3
]
b_ub = [-d for d in demanda]
res = linprog(c=[1, 1, 1, 1], A_ub=A_ub, b_ub=b_ub,
              bounds=[(0, None)] * 4, integrality=[1, 1, 1, 1])
print("Inicis per franja:", res.x, "| plantilla mínima:", res.fun)

El paràmetre integrality demana solucions enteres (no pots contractar 2,5 repartidors): és la PL entera que a 02-01 vam veure que dispara la complexitat teòrica, però que els solvers moderns gestionen sense immutar-se a aquestes mides.

El VRP. El nostre pipeline (clustering + TSP per zona) és en realitat una heurística clàssica —cluster first, route second— per al Vehicle Routing Problem, la generalització industrial del TSP. El VRP afegeix el que el TSP ignora: capacitat de cada vehicle (quilos, volum), finestres de temps de lliurament ("entre les 9:00 i les 11:00"), flotes heterogènies, diverses passades pel dipòsit. És NP-dur amb agreujants, i a la pràctica gairebé ningú no el resol des de zero: es fan servir solvers especialitzats com Google OR-Tools (gratuït i omnipresent en logística), que combinen per dins construcció voraç, cerca local tipus 2-opt/3-opt i metaheurístiques — exactament les famílies que has après. Conèixer el que hi ha dins de la caixa és el que et permet configurar-la bé i detectar quan la seva resposta no té sentit.

La lliçó d'enginyeria: "prou bo avui"

A 02-02 vam calcular l'òptim exacte del TSP de 9 parades (35,22 km) perquè la mida ho permetia. Avui, amb 60 comandes i les furgonetes sortint a les 8:00, la pregunta correcta no és "quin és l'òptim?" sinó "quanta millora m'hi cap abans de les 8:00?". La regla d'or de l'optimització industrial:

Una solució un 5 % pitjor que l'òptim, disponible a temps, val infinitament més que l'òptim que arriba tard. L'òptim és el patró de mesura, no sempre l'objectiu.

I una advertència que no és retòrica: els resultats d'aquests models són recomanacions. Abans d'aplicar-los a una operativa real (rutes, torns, assignacions de persones) els han de validar els qui coneixen el terreny i les obligacions del negoci —normativa laboral, restriccions de trànsit, compromisos amb clients—, perquè el model només optimitza el que se li va posar a la funció objectiu, i la realitat sempre té restriccions que ningú no va escriure. La decisió final és humana.

Errors Comuns i Consells

  • Optimitzar sense línia base. Si no mesures la situació actual amb la mateixa mètrica, no pots afirmar que has millorat. És l'error número u en projectes reals.
  • Confondre l'òptim del model amb l'òptim del negoci. El model minimitza quilòmetres; el negoci potser valora més la puntualitat. Pregunta què s'optimitza de veritat abans d'escriure la funció objectiu.
  • Aplicar 2-opt sense tolerància numèrica. Acceptar "millores" de mida 1e-15 provoca bucles infinits per arrodoniment. Fes servir sempre despres < abans - epsilon.
  • Encadenar etapes sense revisar l'acoblament. Cluster first, route second és una heurística: un clustering òptim pot induir rutes mediocres. Si el resultat global decep, prova de variar k o de moure comandes frontereres entre zones i tornar a rutar.
  • Reinventar el VRP. Per a problemes amb capacitats i finestres de temps, avalua OR-Tools o un altre solver abans d'escriure el teu: el teu valor és en el modelatge i la validació, no a reimplementar cerca local madura.
  • Consell: fixa les llavors aleatòries (random.seed) als experiments. Sense reproduïbilitat no hi ha comparació justa entre variants.

Exercicis

  1. Sensibilitat al nombre de zones. Executa el pipeline complet amb k = 3, 4, 5 i 6 zones (amb el nombre corresponent de repartidors) i construeix la taula k → km totals després de 2-opt. Continua baixant el total en pujar k? Quin cost ocult té pujar k que els quilòmetres no reflecteixen?
  2. El voraç enganyat, revisitat. Construeix una zona de 12 parades on el veí més proper produeixi una ruta almenys un 15 % pitjor que la que s'obté després d'aplicar 2-opt (pista: recorda el contraexemple del voraç de 02-02 — parades gairebé en línia amb una trampa a prop de l'origen). Verifica-ho amb cost_ruta.
  3. Torns amb sostre. Amplia el model de torns a 6 franges de 4 hores amb demanda [4, 6, 10, 9, 7, 3], torns que cobreixen dues franges consecutives (el de la franja 5 enllaça amb la 0) i la restricció addicional que en cap franja no hi pot haver més de 12 persones actives. Resol-ho amb linprog i integrality.

Solucions

  1. Amb els focus de l'exemple, k=4 coincideix amb l'estructura real de la demanda i dona el millor equilibri; k=5 i k=6 gairebé no redueixen quilòmetres (de vegades fins i tot els pugen, perquè més zones impliquen més viatges dipòsit↔zona) i afegeixen el cost ocult d'un repartidor i un vehicle més per zona. La corba km-vs-k té forma de colze — exactament el mètode del colze que vas fer servir per triar k a 05-05: el mateix criteri estadístic resulta ser un criteri de negoci.
  2. Un patró que funciona: dipòsit a (0,0), una parada "esquer" a (0.5, 0.1) i la resta gairebé colineals a x = 1..10 (y≈0), amb una parada final a (10, 3). El veí més proper mossega l'esquer, recorre la línia i el retorn travessa tota la ciutat; també sol fer ziga-zagues entre parades gairebé equidistants. 2-opt descreua aquests retorns. Mesurant amb cost_ruta, la millora supera amb escreix el 15 %. La moralitat de 02-02 es manté: el voraç és un bon constructor, no un bon acabador.
  3. Amb cobertura circular, la restricció de demanda de la franja f és x[(f-1) % 6] + x[f] >= demanda[f] (files amb -1 en aquestes dues posicions i b_ub = -demanda[f]), i la de sostre és la mateixa parella amb signe positiu i b_ub = 12. Són 12 files en total. Amb la demanda donada, el mínim enter factible volta les 20 persones; comprova a la solució que la franja de demanda 10 queda coberta gairebé exacta i que cap no supera 12 — quan una restricció de sostre i una de demanda estrenyen alhora, el solver "desplaça" inicis de torn cap a franges vall.

Conclusió

Has vist el catàleg de l'optimització industrial i has resolt un dia complet de Rutalia encadenant tres algorismes de tres mòduls diferents: clustering (05-05) per decidir què va junt, l'hongarès (03-06) per decidir qui fa què, i veí més proper + 2-opt (02-02 i aquesta lliçó) per decidir en quin ordre — amb una mètrica mesurant cada baula i una millora total propera al 70 % sobre l'operativa artesanal. Les idees que t'has d'endur: reconèixer el problema canònic és el 80 % de la feina, les decisions de nivell alt mouen més l'agulla que el poliment fi, i "prou bo a temps" guanya l'òptim tardà. A la propera lliçó canviem de domini però no de mètode: les xarxes socials com a grafs, on el BFS, les components i el clustering que ja domines es converteixen en detecció de comunitats, mesura de la influència —amb PageRank com a cas estrella— i recomanació d'amistats.

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