{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "_vJc5hFgTOJ8",
    "outputId": "1f2b400d-da3d-41a5-a9a2-b9bc9d47a494"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alternative 1:\n",
      "  Total Profit = 88\n",
      "  Route:\n",
      "    Day 1: 0 -> 3 -> 2 -> 0\n",
      "    Day 2: 0 -> 1 -> 4 -> 0\n",
      "    Day 3: 0 -> 5 -> 0\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import numpy as np\n",
    "from typing import List, Tuple, Set\n",
    "from collections import namedtuple\n",
    "from sklearn.metrics import jaccard_score\n",
    "import pandas as pd\n",
    "import itertools # Import itertools\n",
    "\n",
    "# Define structure for nodes\n",
    "Node = namedtuple('Node', ['id', 'profit', 'time_window'])\n",
    "\n",
    "# Simulated nodes with id, profit, and time window\n",
    "nodes = [\n",
    "    Node(0, 0, (0, 100)),\n",
    "    Node(1, 10, (5, 50)),\n",
    "    Node(2, 15, (10, 60)),\n",
    "    Node(3, 20, (0, 40)),\n",
    "    Node(4, 25, (20, 70)),\n",
    "    Node(5, 18, (30, 90))\n",
    "]\n",
    "\n",
    "# Simulated travel time matrix\n",
    "travel_times = {\n",
    "    (i, j): random.randint(5, 15) if i != j else 0\n",
    "    for i in range(len(nodes)) for j in range(len(nodes))\n",
    "}\n",
    "\n",
    "# Parameters\n",
    "NUM_DAYS = 3\n",
    "MAX_TIME_PER_DAY = 40\n",
    "POP_SIZE = 10\n",
    "NUM_GENERATIONS = 20\n",
    "EPSILON = 0.05\n",
    "NUM_ALTERNATIVES = 3\n",
    "JACCARD_THRESHOLD = 0.3\n",
    "\n",
    "# Helper functions\n",
    "def is_day_feasible(day_route: List[int]) -> bool:\n",
    "    time = 0\n",
    "    current_node = 0\n",
    "    for node in day_route:\n",
    "        time += travel_times[(current_node, node)]\n",
    "        if time < nodes[node].time_window[0]:\n",
    "            time = nodes[node].time_window[0]\n",
    "        elif time > nodes[node].time_window[1]:\n",
    "            return False\n",
    "        current_node = node\n",
    "    time += travel_times[(current_node, 0)]\n",
    "    return time <= MAX_TIME_PER_DAY\n",
    "\n",
    "def is_multi_day_feasible(route_by_day: List[List[int]]) -> bool:\n",
    "    return all(is_day_feasible(day) for day in route_by_day)\n",
    "\n",
    "def compute_profit(route_by_day: List[List[int]]) -> int:\n",
    "    return sum(nodes[i].profit for day in route_by_day for i in day)\n",
    "\n",
    "def jaccard_similarity_multi(route1: List[List[int]], route2: List[List[int]]) -> float:\n",
    "    flat1 = set(i for day in route1 for i in day)\n",
    "    flat2 = set(i for day in route2 for i in day)\n",
    "    all_nodes_set = set(range(len(nodes)))\n",
    "    binary_flat1 = [1 if node in flat1 else 0 for node in all_nodes_set]\n",
    "    binary_flat2 = [1 if node in flat2 else 0 for node in all_nodes_set]\n",
    "    return jaccard_score(binary_flat1, binary_flat2)\n",
    "\n",
    "\n",
    "def generate_initial_population() -> List[List[List[int]]]:\n",
    "    population = []\n",
    "    all_nodes = list(range(1, len(nodes)))\n",
    "    while len(population) < POP_SIZE:\n",
    "        random.shuffle(all_nodes)\n",
    "        split = np.array_split(all_nodes, NUM_DAYS)\n",
    "        candidate = [list(day) for day in split if is_day_feasible(list(day))]\n",
    "        if len(candidate) == NUM_DAYS:\n",
    "            population.append(candidate)\n",
    "    return population\n",
    "\n",
    "def crossover(parent1: List[List[int]], parent2: List[List[int]]) -> List[List[int]]:\n",
    "    child = []\n",
    "    for d in range(NUM_DAYS):\n",
    "        combined = list(set(parent1[d] + parent2[d]))\n",
    "        random.shuffle(combined)\n",
    "        sub_day = [n for n in combined if n not in itertools.chain(*child)]\n",
    "        child.append(sub_day[:len(sub_day)//2])\n",
    "    return child\n",
    "\n",
    "def mutate(route: List[List[int]]) -> List[List[int]]:\n",
    "    day_from, day_to = random.sample(range(NUM_DAYS), 2)\n",
    "    if route[day_from]:\n",
    "        node = random.choice(route[day_from])\n",
    "        route[day_from].remove(node)\n",
    "        if node not in route[day_to]:\n",
    "            route[day_to].append(node)\n",
    "    return route\n",
    "\n",
    "def genetic_algorithm(base_route: List[List[int]], base_profit: int, existing_routes: List[List[List[int]]]) -> List[List[int]]:\n",
    "    population = generate_initial_population()\n",
    "    best_candidate = base_route\n",
    "    for _ in range(NUM_GENERATIONS):\n",
    "        new_population = []\n",
    "        for _ in range(len(population)):\n",
    "            p1, p2 = random.sample(population, 2)\n",
    "            child = crossover(p1, p2)\n",
    "            child = mutate(child)\n",
    "            if is_multi_day_feasible(child):\n",
    "                profit = compute_profit(child)\n",
    "                if profit >= (1 - EPSILON) * base_profit:\n",
    "                    if all(jaccard_similarity_multi(child, r) >= JACCARD_THRESHOLD for r in existing_routes):\n",
    "                        new_population.append(child)\n",
    "                        if profit > compute_profit(best_candidate):\n",
    "                            best_candidate = child\n",
    "        if not new_population:\n",
    "            break\n",
    "        population = new_population\n",
    "    return best_candidate\n",
    "\n",
    "# Main MGA loop\n",
    "base_route = max(generate_initial_population(), key=compute_profit)\n",
    "base_profit = compute_profit(base_route)\n",
    "alternatives = [base_route]\n",
    "routes_set = [base_route]\n",
    "\n",
    "while len(alternatives) < NUM_ALTERNATIVES:\n",
    "    alt = genetic_algorithm(base_route, base_profit, routes_set)\n",
    "    if alt and alt not in routes_set:\n",
    "        alternatives.append(alt)\n",
    "        routes_set.append(alt)\n",
    "    else:\n",
    "        break\n",
    "\n",
    "# Output results\n",
    "for i, r in enumerate(alternatives):\n",
    "    flat = [n for day in r for n in day]\n",
    "    print(f\"Alternative {i+1}:\\n  Total Profit = {compute_profit(r)}\\n  Route:\")\n",
    "    for d, day in enumerate(r):\n",
    "        print(f\"    Day {d+1}: 0 -> {' -> '.join(map(str, day))} -> 0\")\n",
    "    if i > 0:\n",
    "        print(f\"  Jaccard w/ Base = {jaccard_similarity_multi(r, base_route):.2f}\\n\")"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
