DAMM-LIVERING

• GIF

  Main functions

Inspiration

The logistics industry wastes billions annually on inefficient delivery routing and truck packing. A single delivery vehicle's utilization can drop 40% due to poor item placement and unloading accessibility. DAMM, Spain's leading beer distributor, faces this daily: 500+ stops per day across Barcelona, complex time windows, three vehicle types with different loading rules, and barrels that must respect weight distribution.

We wanted to solve the Vehicle Routing Problem + 3D bin packing simultaneously, not sequentially—because routing affects packing feasibility, and packing affects route cost. Simulated Annealing offered the right balance: practical convergence speed for a hackathon timeline, enough randomization to escape local optima, and elegant modularity.

What it does

DAMM-LIVERING is a two-phase logistics optimizer:

1. SA-Route: Solves vehicle routing with real distance/time matrices (OSRM), respects delivery time windows, balances load across three vehicle types (van ≤3 palets, truck-6 4–6 palets, truck-8 ≥7 palets).

2. SA-Distribution: Packs items into 3D truck layouts (6 floors × 5 rows × 2 columns per pallet), optimizing:

   • Fragmentation: Keep products and customers cohesive → faster unloading
   • Accessibility: Respect unloading order—don't block early stops with late deliveries
   • Gravity & structure: Barrels above boxes forbidden, floors/pallets must fill sequentially

3. Real-time visualization: Interactive React frontend showing routes on OpenStreetMap, 3D pallet layouts with delivery timeline slider, KPI dashboards (distance, cost, utilization, service gaps).

Input: order CSVs + time windows + distance matrices.
Output: optimized routes per vehicle + 3D packing + delivery schedules.

How we built it

Stack: C++17 (optimization engine), Python 3.10+ (data pipeline), React + Vite + TypeScript (frontend).

// Two-phase SA template (codi/algo/sa/sa.cc)
template <typename Estado>
Estado simulated_annealing(
    Estado inicial,
    function<double(const Estado&)> costo,      // fitness function
    function<Estado(const Estado&, mt19937&)> vecino,  // neighbor operator
    ParametrosSA params,
    mt19937& rng
) {
    double T = params.T_init;
    while (T > params.T_min) {
        for (int i = 0; i < params.iter_por_temp; ++i) {
            Estado candidato = vecino(actual, rng);
            if (costo(candidato) < costo(actual) ||
                uniform_real(0,1) < exp(-delta / T)) {
                actual = candidato;
            }
        }
        T *= params.cooling_rate;
    }
    return mejor;
}

Pipeline:

1. cargar_csv.py: Merge order CSVs + time windows + distance matrices → JSON problem definition
2. damm --from-json: SA-Route optimizer (C++17)
3. items_por_camion.py: Expand items per truck (barrels → 4 box-equivalents each)
4. damm-dist: SA-Distribution (runs in parallel per truck)
5. orquestador.py: Merge results, compute delivery schedules, generate final JSON
6. Frontend: Load JSON, render routes + 3D packing + KPIs

Key optimization heuristics:

double fitness(const Solucion& s, const vector<uint16_t>& orden_ruta) {
    // F1: Product fragmentation (each material in one pallet-floor)
    // F2: Customer fragmentation (each customer in one pallet-floor)  
    // F3: Accessibility penalties (unloading order, barrels above boxes)
    return w1 * fragmentacion_producto(s) 
         + w2 * fragmentacion_cliente(s)
         + w3 * accesibilidad(s, orden_ruta);
}

Data structures: Custom 4D layout for pallet state, incremental slot tracking (ocupados/vacios vectors), hash maps for product/customer indexing to avoid O(n) grid scans.

Challenges we ran into

1. Hard constraints vs soft penalties: Early SA accepted invalid solutions (floating items, incomplete floors). We pivoted to rejecting invalid neighbors—game-changer. Neighbor generation now verifies es_valida() before accepting.

2. Slot calculation bottleneck: vecino_swap and vecino_mover scanned entire grid (480 cells) every call. With 100 retry attempts per iteration, this was killing performance. Solution: maintain vector<Pos> ocupados/vacios incrementally in the state—drops scan cost to O(1).

3. Vehicle type complexity: Three vehicle types (furgoneta/truck-6/truck-8) have different lateral access rules. Furgoneta accesses all pallets from back (row 4); even pallets access from front (row 0), odd from back. Camión 8 has full access to pallets 0–1. Required careful geometry modeling and state-specific validation logic.

4. Barrels as 4-box-equivalent items: Barrels are heavier but occupy single slots. We expand them at pipeline level (1 barrel → 4 identical items in items_por_camion.py), keeping SA-distribution model simple while respecting weight constraints.

5. Time window feasibility: Route quality depends on realistic time estimates. We integrated real OSRM matrices (meters, seconds) and computed arrival times with slack for delivery duration. Tight windows (<2h) sometimes become infeasible—flagged visually in frontend.

Accomplishments that we're proud of

• Two-phase architecture: Routes and packing optimized together. Routes influence packing density; packing accessibility influences route viability. Clean separation without losing coupling.

• Real-world data integration: OSRM distance/time matrices, Barcelona map coordinates, actual Damm depot location, real order data from test CSVs. Not synthetic benchmarks—production-ready data pipeline.

• Hard constraints with high-performance neighbors: Validity-preserving operators (vecino_swap always preserves layout structure; vecino_mover with retry loop) + incremental slot tracking = 100x faster neighbor generation than naive scanning.

• 3D interactive visualization: React frontend with Leaflet route maps + Three.js 3D pallet viewer with delivery timeline slider. Users can inspect exact item placement, unloading order, and predicted schedules per stop.

• Multi-vehicle fleet modeling: Supports three vehicle types with distinct geometry and access rules. Fleet composition configurable (vans, truck-6, truck-8 counts).

• Experimental framework (codi/experimentos.cc): 7 parameterized experiments (operator comparison, initialization strategies, grid-search SA tuning, scalability) generating CSV data. Python analysis script produces comparative plots.

What we learned

1. State representation matters: Compact state (4D layout + maps) is far better than flattened. Incremental indexing (por_material, por_cliente) is essential for fast heuristic evaluation.

2. Validity constraints are hard constraints: Soft penalty functions allowed SA to accept invalid solutions transiently. Hard rejection (immediate discarding) + retry-based neighbor generation is simpler and more robust.

3. Simulated Annealing's simplicity is deceptive: No complex data structures, no branch-and-bound, no LP relaxations—just random walks with temperature decay. Yet with good neighborhood operators and validity preservation, it converges well to practical solutions.

4. Two-phase decomposition has limits: Routes and packing interact. A slightly longer route might pack 20% more efficiently. True joint optimization would require a unified state (routes + full 3D) and massive state space. Phase separation is pragmatic.

5. Visualization changes perception: Seeing items physically stacked reveals why accessibility matters. A 50-point reduction in fitness looks good numerically; seeing barrels placed carelessly on boxes makes it visceral.

What's next for DAMM-LIVERING

• Real-time re-optimization: Traffic incidents, order cancellations, new urgent orders → re-solve only affected vehicles dynamically. Currently offline; integrating live vehicle telemetry and ETA feedback.

• Joint optimization: Unified SA state with routes + packing. State space explosion, but modern machines + parallel search might make it feasible.

• Multi-objective Pareto: Not just minimize cost; explore trade-offs between distance, time windows compliance, and sustainability (CO2 per delivery, cold-chain violations).

• Driver behavior modeling: Account for real driver preferences (avoid tight alleys, prefer main roads). Currently assumes neutral routing.

• International expansion: Generalize from Barcelona to Spanish national routes + EU logistics. Integrate local constraints (truck size regulations, congestion zones, driver rest hours).

• ML warm-start: Train neural network to predict good SA initial solutions faster than greedy construction.

• Live dashboard for dispatch: Real-time vehicle tracking, dynamic priority updates, one-click what-if simulations ("what if we add this rush order?").

Code repo: github.com/ROCU08/Damm-boicot-al-euro
Try it: make pipeline JUEGO=test/juego_lunes.csv OUT_DIR=out/ && cd frontend && npm run dev

Built With

• c++
• docker
• lua
• python