transportation-problem.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import permutations\n",
    "from sys import maxsize\n",
    "import numpy as np\n",
    "from random import randrange\n",
    "\n",
    "from inputs.in1 import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "cost = np.array(cost)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "North West Corner is an Algorithm for calculating feasible solution\n",
    "\n",
    "[Read more...](https://geekrodion.com/blog/operations/corner)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def north_west_corner(src, des):\n",
    "    supply = list(map(supplies.get, src))\n",
    "    demand = list(map(demands.get, des))\n",
    "\n",
    "    i, j, fs = 0, 0, []\n",
    "\n",
    "    while supply[len(supply) - 1] != 0:\n",
    "        s, d = supply[i], demand[j]\n",
    "        v = min(s, d)\n",
    "        fs.append([[src[i], des[j]], v])\n",
    "\n",
    "        supply[i] -= v\n",
    "        demand[j] -= v\n",
    "\n",
    "        if supply[i] == 0 and i < len(supply) - 1:\n",
    "            i += 1\n",
    "        if demand[j] == 0 and j < len(demand) - 1:\n",
    "            j += 1\n",
    "\n",
    "    return fs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fitness(sol, cost):\n",
    "    return np.sum(np.multiply(cost, sol))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "population = np.empty((0, 2), dtype=int)\n",
    "optimal_solution = None\n",
    "minimum_cost = maxsize\n",
    "\n",
    "sources = list(supplies.keys())\n",
    "destinations = list(demands.keys())\n",
    "sol_list = set()\n",
    "counter = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Creating initial population by generating permutations of supplies & demands and then running north west corner on them.\n",
    "\n",
    "(some of solutions are duplicate, so we ignore them and don't add them to initial population)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in permutations(supplies):\n",
    "    for j in permutations(demands):\n",
    "\n",
    "        feasible_solution = north_west_corner(i, j)\n",
    "\n",
    "        solution = np.zeros([len(supplies), len(demands)], dtype=int)\n",
    "\n",
    "        for k in feasible_solution:\n",
    "            solution[sources.index(k[0][0]),\n",
    "                     destinations.index(k[0][1])] = k[1]\n",
    "\n",
    "        if np.array_str(solution) not in sol_list:\n",
    "            sol_list.add(np.array_str(solution))\n",
    "\n",
    "            ft = fitness(solution, cost)\n",
    "            if ft < minimum_cost:\n",
    "                optimal_solution = solution\n",
    "                minimum_cost = ft\n",
    "\n",
    "            population = np.vstack([population, [solution, ft]])\n",
    "\n",
    "        counter += 1\n",
    "        if counter == MAX_POPULATION:\n",
    "            break\n",
    "\n",
    "    if counter == MAX_POPULATION:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Results BEFORE applying GA:\", end=\"\\n\" * 2)\n",
    "\n",
    "print(\"Minimum cost:\", minimum_cost, end=\"\\n\" * 2)\n",
    "print(\"Optimal solution:\", optimal_solution, sep=\"\\n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's free some memory ;)\n",
    "del sol_list, sources, destinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Parent Selection: Random Selection"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection():\n",
    "    global population\n",
    "\n",
    "    population = population[np.argsort(population[:, 1])]\n",
    "\n",
    "    # Truncation\n",
    "    population = population[:MAX_POPULATION]\n",
    "\n",
    "    # Parent Selection: Random Selection\n",
    "    np.random.shuffle(population)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solution_repair(sol, demand):\n",
    "\n",
    "    des_num = len(sol[0])\n",
    "    offset = [0] * des_num\n",
    "\n",
    "    tmp = np.sum(sol, axis=0)\n",
    "    for i in range(des_num):\n",
    "        offset[i] = tmp[i] - demand[i]\n",
    "\n",
    "    for i in range(des_num):\n",
    "        if offset[i] < 0:\n",
    "\n",
    "            need = True\n",
    "            j = 0\n",
    "\n",
    "            while need and (j < des_num):\n",
    "                if offset[j] > 0:\n",
    "\n",
    "                    k = 0\n",
    "                    has_extra = True\n",
    "\n",
    "                    while k < len(sol) and has_extra:\n",
    "\n",
    "                        val = min(offset[j], sol[k][j], abs(offset[i]))\n",
    "\n",
    "                        sol[k][j] -= val\n",
    "                        sol[k][i] += val\n",
    "\n",
    "                        offset[i] += val\n",
    "                        offset[j] -= val\n",
    "\n",
    "                        if offset[j] == 0:\n",
    "                            has_extra = False\n",
    "                        if offset[i] == 0:\n",
    "                            need = False\n",
    "\n",
    "                        k += 1\n",
    "\n",
    "                j += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "def crossover():\n",
    "    global optimal_solution, minimum_cost, population\n",
    "\n",
    "    pool = np.empty((0, 2), dtype=int)\n",
    "\n",
    "    if len(population) % 2 == 1:\n",
    "        num = len(population) - 1\n",
    "    else:\n",
    "        num = len(population)\n",
    "\n",
    "    for i in range(0, num, 2):\n",
    "        if np.random.rand() <= CROSSOVER_RATE:\n",
    "\n",
    "            child1 = population[i][0].copy()\n",
    "            child2 = population[i+1][0].copy()\n",
    "\n",
    "            comparison = (child1 == child2)\n",
    "            if comparison.all():\n",
    "                continue\n",
    "\n",
    "            demand = np.sum(child1, axis=0)\n",
    "\n",
    "            crossover_row = randrange(len(child1))\n",
    "\n",
    "            t1 = child1[crossover_row].copy()\n",
    "            t2 = child2[crossover_row].copy()\n",
    "            child1[crossover_row] = t2\n",
    "            child2[crossover_row] = t1\n",
    "\n",
    "            solution_repair(child1, demand)\n",
    "            solution_repair(child2, demand)\n",
    "\n",
    "            ft = fitness(child1, cost)\n",
    "            if ft < minimum_cost:\n",
    "                optimal_solution = child1\n",
    "                minimum_cost = ft\n",
    "\n",
    "            pool = np.vstack([pool, [child1, ft]])\n",
    "\n",
    "            ft = fitness(child2, cost)\n",
    "            if ft < minimum_cost:\n",
    "                optimal_solution = child2\n",
    "                minimum_cost = ft\n",
    "\n",
    "            pool = np.vstack([pool, [child2, ft]])\n",
    "\n",
    "    population = np.vstack([population, pool])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Random submatrixs are generated for mutation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_submatrix(mtx):\n",
    "    tmp = mtx[len(mtx)-1:]\n",
    "\n",
    "    i, j = np.where(tmp != 0)\n",
    "\n",
    "    ti = randrange(len(i))\n",
    "\n",
    "    SE = (i[ti] + 1, j[ti])\n",
    "\n",
    "    # because randrange(0) is false\n",
    "    if SE[1] == 0:\n",
    "        NW = (randrange(SE[0]), 0)\n",
    "    else:\n",
    "        NW = (randrange(SE[0]), randrange(SE[1]))\n",
    "\n",
    "    NE = (NW[0], SE[1])\n",
    "    SW = (SE[0], NW[1])\n",
    "\n",
    "    return NW, NE, SW, SE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mutation():\n",
    "    global optimal_solution, minimum_cost, population\n",
    "\n",
    "    pool = np.empty((0, 2), dtype=int)\n",
    "\n",
    "    for i in range(0, len(population)):\n",
    "        if np.random.rand() <= MUTATION_RATE:\n",
    "\n",
    "            solution = population[i][0].copy()\n",
    "\n",
    "            NW, NE, SW, SE = random_submatrix(solution)\n",
    "\n",
    "            val = min(solution[NW[0]][NW[1]], solution[SE[0]][SE[1]])\n",
    "\n",
    "            solution[NW[0]][NW[1]] -= val\n",
    "            solution[SE[0]][SE[1]] -= val\n",
    "            solution[NE[0]][NE[1]] += val\n",
    "            solution[SW[0]][SW[1]] += val\n",
    "\n",
    "            ft = fitness(solution, cost)\n",
    "            if ft < minimum_cost:\n",
    "                optimal_solution = solution\n",
    "                minimum_cost = ft\n",
    "\n",
    "            pool = np.vstack([pool, [solution, ft]])\n",
    "\n",
    "    population = np.vstack([population, pool])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Running genetic algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(ITERATION_NUM):\n",
    "    selection()\n",
    "    crossover()\n",
    "    mutation()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Results AFTER applying GA:\", end=\"\\n\" * 2)\n",
    "\n",
    "print(\"Minimum cost:\", minimum_cost, end=\"\\n\" * 2)\n",
    "print(\"Optimal solution:\", optimal_solution, sep=\"\\n\")"
   ]
  }
 ],
 "metadata": {
  "hide_input": false,
  "interpreter": {
   "hash": "1baa965d5efe3ac65b79dfc60c0d706280b1da80fedb7760faf2759126c4f253"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}