🚁 Multi-Drone Routing Optimization Challenge

An intense optimization challenge from the HackerRank × Goldman Sachs Hackathon
Routing multiple drones through time-varying no-fly zones with battery, payload, and deadline constraints.

---

📋 Problem Overview

The Challenge

Design an optimal routing system for a fleet of delivery drones that must:

• ✈️ Deliver packages from a central warehouse to various locations
• 🚫 Navigate around time-dependent no-fly zones (circles & rectangles)
• 🔋 Manage battery constraints with strategic charging station usage
• 📦 Respect payload limits (energy cost = distance × (1 + payload))
• ⏰ Meet strict delivery deadlines
• 🎯 Maximize a complex scoring function

Scoring Function

score = (successful_deliveries × 100) - (total_energy × 0.1) - (makespan × 0.05)

Key Insight: Deliveries dominate the score massively. One failed delivery costs ~100 points, while energy and time are secondary factors.

---

🧠 Solution Architecture

Initial Baseline: 39.57/100

Started with a greedy approach:

• Nearest-neighbor routing
• Earliest-free-drone scheduling
• Simple NFZ waiting logic
• Basic 2-opt optimization

Critical Bugs Found:

• ❌ Drones permanently removed after first failure
• ❌ Broken 2-opt with dead code (if False)
• ❌ No NFZ detour routing (only waiting)
• ❌ Insufficient search space (K=8 candidates)

Optimized Solution: 42.02/100

Phase 1: Correctness & Bug Fixes

✅ Fixed dead drone removal bug
✅ Corrected 2-opt edge calculation
✅ Added reachability pre-filtering
✅ Implemented proper stall detection

Phase 2: Algorithmic Improvements

✅ NFZ Waypoint Routing
   - Perpendicular detours around circles
   - Corner bypass for rectangles
   - Dynamic wait vs detour decision

✅ Advanced Route Optimization
   - Fixed 2-opt local search
   - Or-opt relocations
   - Multiple ordering heuristics (NN, deadline, weight)

✅ Intelligent Caching
   - segment_nfz() memoization
   - compute_wait() result caching
   - 17s → 400ms speedup on large inputs

Phase 3: Search Space Expansion

✅ Regret-based insertion heuristics
✅ Geographic clustering candidates
✅ Expanded candidate pool (K=8 → K=12)
✅ Brute-force permutations for small sets (≤5)

---

📊 Performance Analysis

Metric	Baseline	Optimized	Improvement
Score	39.57	42.02	+6.2%
Runtime (large)	17s	0.4s	42.5× faster
Deliveries	~40%	~45%	+12.5%
NFZ Handling	Wait only	Detour + Wait	Smarter

---

🚀 Key Optimizations

1. NFZ Detour Routing

Instead of always waiting for no-fly zones to deactivate:

# Try perpendicular waypoint for circles
waypoint = center + perpendicular_vector * (radius + safety_margin)

# Try corner bypass for rectangles
corners = [top_left, top_right, bottom_right, bottom_left]
best_corner = min(corners, key=lambda c: dist(start, c) + dist(c, end))

2. Or-Opt Local Search

After 2-opt, relocate each stop to its optimal position:

for i in range(len(route)):
    node = route[i]
    for j in range(len(route)):
        if j != i:
            # Try inserting node at position j
            new_route = route[:i] + route[i+1:]
            new_route.insert(j, node)
            if cost(new_route) < cost(route):
                route = new_route

3. Intelligent Caching

seg_cache = {}  # Memoize NFZ segment intersections
wait_cache = {}  # Cache wait time calculations

# 17s → 0.4s on 80-delivery instances

---

🎯 What Would Get to 90-100?

The gap from 42 → 90+ requires fundamentally different approaches:

Missing Techniques (Elite Level)

1. Large Neighborhood Search (LNS)

   • Destroy 20-30% of routes
   • Rebuild with regret insertion
   • Iterate until time budget exhausted

2. Metaheuristics

   • Simulated Annealing with adaptive temperature
   • Tabu Search with aspiration criteria
   • Genetic Algorithms with route crossover

3. Global Optimization

   • Beam search over route assignments
   • Monte Carlo Tree Search for scheduling
   • Column generation for set partitioning

4. Advanced NFZ Handling

   • Visibility graphs around obstacles
   • Time-space A* pathfinding
   • Corridor-based routing

5. Parallel Drone Coordination

   • Global workload balancing
   • Deadline-aware partitioning
   • Concurrent route optimization

---

🛠️ Installation & Usage

Prerequisites

Python 3.8+

Run the Solution

# Basic usage
python solution_current.py < input.json > output.json

# With timing
time python solution_current.py < test_cases/large.json > result.json

Input Format

{
  "map_size": [1000, 1000],
  "drones": [
    {"id": "drone_1", "max_payload": 1.0}
  ],
  "deliveries": [
    {"id": "d1", "x": 100, "y": 200, "weight": 0.3, "deadline": 500}
  ],
  "no_fly_zones": [
    {
      "shape": "circle",
      "center": [500, 500],
      "radius": 50,
      "T_start": 0,
      "T_end": 300
    }
  ],
  "charging_stations": [
    {"x": 250, "y": 250}
  ]
}

Output Format

{
  "flight_manifest": [
    {
      "drone_id": "drone_1",
      "path": [
        {"x": 500, "y": 500, "t": 0, "action": "PICKUP", "delivery_ids": ["d1"]},
        {"x": 100, "y": 200, "t": 450.5, "action": "DELIVER", "delivery_id": "d1"},
        {"x": 500, "y": 500, "t": 900.0, "action": "RETURN"}
      ]
    }
  ]
}

---

📈 Complexity Analysis

Time Complexity

• Baseline: O(D² × P!) where D = deliveries, P = pool size
• Optimized: O(D² × K) with K=12 candidate pool + caching
• Elite (LNS): O(T × D² × log D) where T = time budget iterations

Space Complexity

• O(D + N + C) where N = NFZ count, C = cache size
• Cache grows to ~O(D²) for segment intersections

---

🏆 Lessons Learned

1. Bugs Are Expensive

The "dead drone" bug alone cost ~50 deliveries. One line of code = 500 points.

2. Local ≠ Global

Greedy algorithms plateau fast. The jump from 42 → 90 requires global search strategies.

3. Domain Knowledge Matters

Understanding NFZ geometry (tangent lines, corner routing) saves massive time vs naive waiting.

4. Time Budgets Are Real

Had to balance search depth vs timeout. Elite solutions use anytime algorithms that improve until time runs out.

5. Caching Is Critical

17s → 0.4s speedup from memoization. Competitive programming demands this.

---

🔮 Future Improvements

If I had more time, I would implement:

• Large Neighborhood Search with adaptive destroy/repair
• Simulated Annealing with geometric cooling schedule
• Beam Search for parallel route exploration
• Visibility Graph for NFZ-aware shortest paths
• Column Generation for optimal drone assignment
• Multi-start Randomization with elite solution pool
• Adaptive Time Budgeting (fast initial, iterative improvement)

---

📚 References

Algorithms Used

• 2-opt & Or-opt: Lin-Kernighan local search variants
• Nearest Neighbor: Classic TSP construction heuristic
• Regret Insertion: I1 heuristic from Solomon (1987)
• Liang-Barsky: Line-rectangle intersection algorithm

Relevant Papers

• Solomon, M. M. (1987). "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints"
• Shaw, P. (1998). "Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems"
• Pisinger, D. & Ropke, S. (2007). "A General Heuristic for Vehicle Routing Problems"

---

🤝 Contributing

This was a hackathon challenge, but I'm open to discussions on optimization strategies! Feel free to:

• Open issues with alternative approaches
• Share your own solutions
• Suggest improvements to reach 90-100 score

---

📝 License

MIT License - Feel free to use this code for learning and competition purposes.

---

👨‍💻 Author

Your Name

• LinkedIn: Your Profile
• GitHub: @yourusername
• Email: ruturajsonkamble29@gmail.com

---

🙏 Acknowledgments

• HackerRank × Goldman Sachs for the challenging problem
• The competitive programming community for inspiration
• Coffee ☕ for keeping me going through the optimization marathon

---

⭐ Star this repo if you found it interesting!

"The gap between 42 and 100 taught me more than reaching 100 would have."