🚛 Logistics Solver - оптимизация логистических маршрутов

Решение задачи маршрутизации транспортных средств (Vehicle Routing Problem, VRP) для сбора товаров из магазинов и доставки на склад с учётом ограничений совместимости грузов.

---

📋 Описание задачи

Дано:

• Склад (начальная и конечная точка всех маршрутов)
• Магазины с товарами трёх типов: Н (непродовольственные), П (продукты), М (мясо/молоко)
• K машин, одновременно выезжающих на маршруты
• Вместимость каждой машины: строго не более W коробок

Примечания:

• ✅ Машина может забирать товары любых категорий и в любом количестве
• ✅ Можно забрать все товары из магазина или только часть
• ✅ Машина может посещать несколько магазинов: M₁ → M₂ → M₃ → ... → склад

Ключевое ограничение:

• ⚠️ Товары П и М нельзя перевозить вместе в одной машине (разное оборудование)
• ✅ Допустимые комбинации: только П, только М, только Н, П+Н, М+Н
• ❌ Недопустимо: П+М, П+М+Н

Цель: составить маршруты для K машин так, чтобы все товары из всех магазинов были доставлены на склад.

---

🎯 Особенности

• ✅ Интерактивный веб-интерфейс на Streamlit с редактируемыми таблицами
• ✅ Автоматическая упаковка товаров в машины с учётом ограничений
• ✅ Оптимизация маршрутов с помощью алгоритмов 2-opt и 3-opt
• ✅ Дробление заказов между машинами для максимальной эффективности
• ✅ Визуализация на сетке с манхэттенскими маршрутами
• ✅ Детализация по каждому маршруту с отдельными картами
• ✅ Экспорт результатов в Excel
• ✅ Подробная статистика по загрузке и расстояниям

---

🚀 Быстрый старт

Установка

# Клонировать репозиторий
git clone https://github.com/AlexeyLars/logistics-solver.git
cd logistics-solver

# Создать виртуальное окружение (рекомендуется)
python -m venv venv
source venv/bin/activate  # Linux/Mac
# или
venv\Scripts\activate     # Windows

# Установить зависимости
pip install -r requirements.txt

Запуск

streamlit run app.py

Приложение откроется в браузере по адресу http://localhost:8501

---

💡 Использование

1️⃣ Настройка координат и заказов

В интерфейсе приложения:

• Координаты: редактируйте таблицу с координатами точек (X, Y)
• Заказы: введите количество товаров каждого типа (Н, П, М) для каждого магазина
• Все данные редактируются прямо в таблицах

2️⃣ Настройка параметров

В боковой панели:

• Количество машин (по умолчанию: 6)
• Вместимость машины (по умолчанию: 120 коробок)
• 3-opt оптимизация (для более глубокой оптимизации)

3️⃣ Решение задачи

Нажмите "🚀 Решить задачу" и получите:

• Оптимальные маршруты для каждой машины
• Общую карту всех маршрутов
• Отдельные карты для каждого маршрута
• Детальную статистику
• Возможность экспорта в Excel

4️⃣ Использование как библиотека

from src.solver import LogisticsSolver

# Данные
points = [(6, 8), (19, 9), (25, 6)]  # Склад + магазины
stores = {
    1: {"П": 20, "М": 0, "Н": 6},
    2: {"П": 0, "М": 4, "Н": 12}
}

# Решение
solver = LogisticsSolver(
    points=points,
    stores_inventory=stores,
    num_vehicles=6,
    capacity=120
)
routes = solver.solve()

# Экспорт
excel = solver.export_to_excel(routes)
with open("routes.xlsx", "wb") as f:
    f.write(excel.getvalue())

---

🔬 Алгоритм решения

Этап 1: Разделение задач

Магазины группируются по совместимости товаров:

• Магазины с только П → группа П
• Магазины с только М → группа М
• Магазины с П и М → разделяются на две подзадачи
• Товары Н → гибкая группа (распределяются после основных)

Этап 2: Упаковка грузов (Bin Packing)

• Товары сортируются по убыванию объёма
• Используется алгоритм First Fit Decreasing
• Автоматический подбор распределения машин между группами П и М
• Разрешается дробление заказов между машинами

Пример дробления:

Магазин с (П=50, М=0, Н=30):
├─ Машина 1 забирает: П=50, Н=20
└─ Машина 2 забирает: Н=10

Этап 3: Построение маршрутов

• Старт со склада
• Метод ближайшего соседа (Nearest Neighbor)
• Расстояния по манхэттенской метрике: |x₁-x₂| + |y₁-y₂|
• Возврат на склад

Этап 4: Оптимизация маршрутов

2-opt: Переворот сегментов для уменьшения расстояния

До:    A → B → C → D → E
       A → [C → B] → D → E  (переворот)
После: A → C → B → D → E    (стало короче)

3-opt (опционально): Перестановка трёх сегментов для более глубокой оптимизации

---

📁 Структура проекта

logistics-solver/
├── app.py                  # Главный файл Streamlit приложения
├── src/
│   ├── __init__.py        # Инициализация пакета
│   ├── solver.py          # Основной класс решения задачи
│   ├── data_processor.py  # Валидация и обработка данных
│   └── visualizer.py      # Визуализация на сетке с манхэттенскими маршрутами
├── tests/
│   ├── __init__.py
│   └── test_solver.py     # Тесты алгоритмов
├── examples/
│   ├── example_data.txt   # Примеры входных данных
│   ├── usage_example.py   # Пример использования как библиотеки
│   └── routes_visualization.png
├── requirements.txt        # Зависимости проекта
├── README.md              # README
└── LICENSE                # MIT лицензия

🛠️ Технологии

• Python 3.8+
• Streamlit - интерактивный веб-интерфейс
• Pandas - обработка и редактирование данных
• Matplotlib - визуализация маршрутов на сетке
• Openpyxl - экспорт результатов в Excel
• NumPy - математические операции

---

📈 Производительность

• Решает задачи с 30+ точками за несколько секунд
• 2-opt оптимизация: O(n²) итераций
• 3-opt оптимизация: O(n³) итераций (рекомендуется для <50 точек)
• Поддержка задач до 100+ точек с базовой оптимизацией

---

🤝 Поддержка и вклад в проект

Если у вас возникли вопросы или предложения - cоздайте Issue.

Приветствуются pull requests - для крупных изменений сначала откройте issue для обсуждения.

1. Создайте fork репозитория и feature branch (git checkout -b feature/AmazingFeature)
2. Закоммитьте изменения (git commit -m 'Add some AmazingFeature')
3. Сделайте push в branch (git push origin feature/AmazingFeature)
4. Откройте Pull Request

---

📝 Лицензия

Проект распространяется под лицензией MIT. См. файл LICENSE для деталей.

---

📚 Дополнительные ресурсы

• Vehicle Routing Problem
• 2-opt Algorithm
• Streamlit Documentation
• Bin Packing Problem

---

⭐ Если проект оказался полезен, поставьте звезду!