🚚 AI Multi-City Route Optimization System using Memetic Genetic Algorithms

An AI-powered logistics optimization system that computes efficient delivery routes across multiple cities while respecting delivery priorities, traffic effects, and real-time changes. The system combines Memetic Genetic Algorithms (GA + 2-opt local search) with a dynamic recalculation engine and AI-generated human-readable explanations.

---

📌 Overview

In real-world logistics, a single truck often serves multiple destinations with varying urgency. Manually planning such routes is inefficient and does not scale as destinations or priorities change.

This project automatically:

• Computes optimized multi-city delivery routes
• Handles priority-based deliveries
• Adapts dynamically to real-time changes
• Scales efficiently as the number of cities increases
• Explains routing decisions using AI-generated summaries

---

🧠 Key Technologies

• Python
• FastAPI (REST API + Swagger)
• Memetic Genetic Algorithm (GA + 2-opt)
• Dynamic Warm-Start Recalculation
• Traffic-aware Cost Modeling
• Google Gemini (LLM) for AI summaries

---

🔬 Algorithmic Approach

1️⃣ Problem Formulation

The routing problem is modeled as a Priority-Weighted Traveling Salesman Problem (TSP): Total Cost = Distance Cost + Priority Penalty Priority Penalty = Σ (Priority × Visit Order × Weight)

This allows the system to intelligently trade off distance efficiency against delivery urgency.

---

2️⃣ Memetic Algorithm (Core Optimizer)

The optimizer combines:

• Genetic Algorithm for global search
• 2-opt local search for local refinement

GA Components:

• Tournament selection
• Ordered crossover (OX)
• Adaptive mutation to avoid premature convergence

2-opt removes route crossings and reduces unnecessary travel.

This hybrid approach is widely used in industrial and research-grade routing systems.

---

3️⃣ Traffic-Aware Cost Modeling

A dynamic traffic multiplier simulates congestion:

• Early stops → off-peak
• Mid-route → moderate traffic
• Late stops → rush-hour penalty

This improves realism beyond straight-line distance optimization.

---

4️⃣ Dynamic Route Recalculation Engine

To support real-time changes:

• Warm-start optimization reuses previous best routes
• Signature-based change detection avoids redundant work
• Cache hits return instantly (≈0 ms latency)
• Priority-only updates do not recompute geometry

This provides 3–6× faster recalculations.

---

5️⃣ AI-Based Human-Readable Summary

A hybrid AI strategy is used:

• Deterministic facts from the optimizer (truth)
• Large Language Model (Gemini) generates explanations

This ensures:

• No hallucinations
• Clear “why this route” explanations
• Driver- and dispatcher-friendly summaries

---

🏗️ System Architecture

Client (Swagger / Postman) ↓ FastAPI REST API ↓ Dynamic Recalculation Engine ↓ Memetic GA Optimizer (GA + 2-opt + Traffic) ↓ Distance Matrix Layer ↓ AI Summary Generator (LLM)

---

🔄 Optimization Flow

1. Validate input cities and priorities
2. Detect request changes (cache / warm start / cold start)
3. Run optimization engine
4. Apply traffic and priority cost model
5. Generate AI explanation
6. Return structured response

---

🚀 Setup Instructions

1️⃣ Install Dependencies

bash pip install fastapi uvicorn google-generativeai pip install fastapi uvicorn google-generativeai

(Optional) Enable AI Summary

export GEMINI_API_KEY=your_api_key_here

Run the API

uvicorn api.main:app --reload

Open Swagger UI

http://127.0.0.1:8000/docs

---

📡 API Usage

POST /optimize-route

Request

{ "source": "HYD", "destinations": ["BLR", "CHN", "PUN", "MUM"], "priorities": { "BLR": 5, "MUM": 2 } }

Response

{ "route": ["HYD", "CHN", "BLR", "PUN", "MUM"], "distance_km": 2146.52, "travel_time_hours": 42.93, "priority_penalty": 165, "total_cost": 2311.52, "summary": "AI-generated explanation of why this route was chosen", "meta": { "algorithm": "Memetic GA + 2-opt + Traffic Model" } }

---

📊 Performance & Scalability

Tested with increasing city counts:

Cities	Cold Start (ms)	Warm Start (ms)	Cache Hit (ms)
5	308	89	0
10	463	115	0
20	1349	318	0

Key Observations

• Near-linear scalability
• Warm-start provides 3–4× speedup
• Cache hits avoid recomputation entirely
• No invalid routes or crashes observed

---

🧪 Edge Case Handling

• Single destination
• No priority scenarios
• Conflicting priorities
• Priority-only updates
• Dynamic city addition/removal
• Cache reuse for identical requests

All cases handled safely.

---

🎥 Sample AI Summary Output

“The route HYD → CHN → BLR → PUN → MUM was selected after evaluating thousands of possible delivery sequences. The optimizer balanced overall travel distance with the urgency of high-priority destinations, applying local refinement to avoid inefficient backtracking. This plan ensures operational efficiency with an estimated travel time of 42.9 hours.”

---

🔮 Future Enhancements

• Multi-vehicle routing (Vehicle Routing Problem)
• Time-window constraints
• Real road network integration (OSRM / Google Maps)
• Multi-objective Pareto frontier visualization
• Reinforcement learning-based policy optimization
• Live traffic and weather data integration

---

🏁 Conclusion

This project demonstrates research-grade optimization combined with practical system engineering. It goes beyond basic route planning by offering scalability, adaptability, and explainable AI decision-making suitable for real-world logistics systems.

Status: Submission Ready

Authors - MonarchOfCoding