The Transportation Problem

The Transportation Problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use `haversine` for calculating distances between two coordinates. \n",
    "\n",
    "See https://www.movable-type.co.uk/scripts/latlong.html for the details of the haversine formula.\n",
    "\n",
    "We assume the radius of Earth is 6373 km. \n",
    "\n",
    "We use: 1km = 0.621371 miles.\n",
    "\n",
    "Also, we assume unit shipping cost per mile is $1.70.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5216.241079053197"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Example \n",
    "\n",
    "using Distances \n",
    "R = 6373 # in kilometers, radius of Earth \n",
    "coord1 = (40.670543, -73.945478) # New York City\n",
    "coord2 = (34.112101, -118.411201) # Los Angeles\n",
    "dist_km = haversine(coord1, coord2, R) # kilometer\n",
    "dist_mi = dist_km * 0.621371 # miles\n",
    "unit_cost = dist_mi * 1.70 # dollars "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "using DelimitedFiles\n",
    "\n",
    "# Read the supplier data \n",
    "supp_data, header = readdlm(\"suppliers.csv\", ',', header=true)\n",
    "supp_name = supply_data[:,2]\n",
    "supp_lat = supply_data[:,3]\n",
    "supp_long = supply_data[:,4]\n",
    "supp_amount = supply_data[:,5]\n",
    "num_supp = length(supp_name) \n",
    "\n",
    "# Read the warehouse data \n",
    "ware_data, header = readdlm(\"warehouses.csv\", ',', header=true)\n",
    "ware_name = ware_data[:,2]\n",
    "ware_lat = ware_data[:,3]\n",
    "ware_long = ware_data[:,4]\n",
    "ware_amount = ware_data[:,5]\n",
    "num_ware = length(ware_name) \n",
    "\n",
    "# First, prepare an array that will contain the unit shipping cost matrix\n",
    "cost = Array{Float64}(undef, num_supp, num_ware)\n",
    "\n",
    "# Then, for each pair (i,j) we calculate c[i,j]\n",
    "for i in 1:num_supp\n",
    "    for j in 1:num_ware \n",
    "        supp_coord = (supp_lat[i], supp_long[i])\n",
    "        ware_coord = (ware_lat[j], ware_long[j])\n",
    "        cost[i, j] = 1.70 * 0.621371 * haversine(supp_coord, ware_coord, 6373)\n",
    "    end \n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The transportation model:\n",
    "$$\\min \\sum_{i=1}^{m} \\sum_{j=1}^{n} c_{ij} x_{ij}$$\n",
    "subject to\n",
    "$$ \\sum_{j=1}^{n} x_{ij} = s_i \\qquad \\text{ for each } i=1,2,...,m $$\n",
    "$$ \\sum_{i=1}^{m} x_{ij} = d_j \\qquad \\text{ for each } j=1,2,...,n $$\n",
    "$$ x_{ij} \\geq 0 \\qquad \\text{ for all } i=1,2,...,m, \\ j=1,2,...,n $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Build a JuMP model\n",
    "\n",
    "using JuMP, GLPK\n",
    "tp = Model(with_optimizer(GLPK.Optimizer))\n",
    "\n",
    "@variable(tp, x[1:num_supp, 1:num_ware] >= 0)\n",
    "\n",
    "@objective(tp, Min, sum(cost[i,j] * x[i,j] for i in 1:num_supp, j in 1:num_ware) )\n",
    "\n",
    "@constraint(tp, supply[i in 1:num_supp], sum(x[i,j] for j in 1:num_ware) == supp_amount[i])\n",
    "\n",
    "@constraint(tp, warehouse[j in 1:num_ware], sum(x[i,j] for i in 1:num_supp) == ware_amount[j])\n",
    "\n",
    "optimize!(tp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "From El Paso TX to Houston TX: 2673.0\n",
      "From El Paso TX to San Diego CA: 1544.0\n",
      "From El Paso TX to San Antonio TX: 936.0\n",
      "From Cleveland OH to New York NY: 5056.0\n",
      "From New Orleans LA to Chicago IL: 3121.0\n",
      "From New Orleans LA to Philadelphia PA: 484.0\n",
      "From New Orleans LA to Indianapolis IN: 731.0\n",
      "From New Orleans LA to Columbus OH: 633.0\n",
      "From Nashville-Davidson TN to Philadelphia PA: 4884.0\n",
      "From Denver CO to Houston TX: 3669.0\n",
      "From Denver CO to Dallas TX: 1007.0\n",
      "From Austin TX to Houston TX: 4656.0\n",
      "From Fort Worth TX to Houston TX: 4476.0\n",
      "From Oklahoma City OK to Houston TX: 4447.0\n",
      "From Portland OR to Los Angeles CA: 4195.0\n",
      "From Portland OR to Seattle WA: 178.0\n",
      "From Kansas City MO to Chicago IL: 4351.0\n",
      "From Long Beach CA to Los Angeles CA: 3794.0\n",
      "From Long Beach CA to San Diego CA: 500.0\n",
      "From Tucson AZ to San Diego CA: 4054.0\n",
      "From St. Louis MO to Chicago IL: 3967.0\n",
      "From Charlotte NC to Philadelphia PA: 3352.0\n",
      "From Charlotte NC to Washington DC: 607.0\n",
      "From Atlanta GA to Philadelphia PA: 3940.0\n",
      "From Virginia Beach VA to New York NY: 3931.0\n",
      "From Albuquerque NM to San Diego CA: 2864.0\n",
      "From Albuquerque NM to Phoenix AZ: 983.0\n",
      "From Oakland CA to Los Angeles CA: 2216.0\n",
      "From Oakland CA to San Jose CA: 782.0\n",
      "From Oakland CA to San Francisco CA: 724.0\n",
      "From Pittsburgh PA to New York NY: 1628.0\n",
      "From Pittsburgh PA to Philadelphia PA: 2071.0\n",
      "From Sacramento CA to Los Angeles CA: 3694.0\n",
      "From Minneapolis MN to Philadelphia PA: 3684.0\n",
      "From Tulsa OK to New York NY: 2159.0\n",
      "From Tulsa OK to Detroit MI: 1514.0\n",
      "From Cincinnati OH to Philadelphia PA: 3640.0\n",
      "From Miami FL to New York NY: 3585.0\n",
      "From Fresno CA to Los Angeles CA: 3542.0\n",
      "From Omaha NE to Philadelphia PA: 3358.0\n",
      "From Toledo OH to New York NY: 3329.0\n",
      "From Buffalo NY to New York NY: 3281.0\n",
      "From Wichita KS to New York NY: 78.0\n",
      "From Wichita KS to Houston TX: 2962.0\n",
      "From St. Paul MN to Philadelphia PA: 2722.0\n",
      "From Baton Rouge LA to New York NY: 1567.0\n",
      "From Baton Rouge LA to Milwaukee WI: 628.0\n",
      "From Raleigh NC to Philadelphia PA: 2080.0\n",
      "From Richmond VA to Philadelphia PA: 2031.0\n",
      "From Jackson MS to Chicago IL: 1966.0\n",
      "From Des Moines IA to Philadelphia PA: 1932.0\n",
      "From Lincoln NE to Chicago IL: 1310.0\n",
      "From Lincoln NE to Memphis TN: 610.0\n",
      "From Madison WI to Chicago IL: 1913.0\n",
      "From Montgomery AL to Philadelphia PA: 1871.0\n",
      "From Little Rock AR to New York NY: 1758.0\n",
      "From Providence RI to New York NY: 1246.0\n",
      "From Providence RI to Boston MA: 361.0\n",
      "From Salt Lake City UT to San Diego CA: 1599.0\n",
      "From Hartford CT to New York NY: 1397.0\n",
      "From Lansing MI to New York NY: 1273.0\n",
      "From Boise City ID to San Diego CA: 1257.0\n",
      "From Tallahassee FL to Philadelphia PA: 370.0\n",
      "From Tallahassee FL to Baltimore MD: 736.0\n",
      "From Tallahassee FL to Jacksonville FL: 142.0\n",
      "From Topeka KS to Chicago IL: 1199.0\n",
      "From Salem OR to Los Angeles CA: 1078.0\n",
      "From Springfield IL to Chicago IL: 1052.0\n",
      "From Albany NY to New York NY: 1011.0\n",
      "From Columbia SC to Philadelphia PA: 981.0\n",
      "From Trenton NJ to New York NY: 887.0\n",
      "From Charleston WV to Philadelphia PA: 573.0\n",
      "From Santa Fe NM to Houston TX: 559.0\n",
      "From Harrisburg PA to Philadelphia PA: 524.0\n",
      "From Cheyenne WY to Houston TX: 500.0\n",
      "From Bismarck ND to Jacksonville FL: 493.0\n",
      "From Carson City NV to Los Angeles CA: 404.0\n",
      "From Concord NH to New York NY: 360.0\n",
      "From Jefferson City MO to Chicago IL: 355.0\n",
      "From Olympia WA to Seattle WA: 338.0\n",
      "From Annapolis MD to Philadelphia PA: 332.0\n",
      "From Dover DE to New York NY: 276.0\n",
      "From Frankfort KY to Philadelphia PA: 260.0\n",
      "From Helena MT to San Diego CA: 246.0\n",
      "From Augusta ME to Boston MA: 213.0\n",
      "From Pierre SD to Philadelphia PA: 129.0\n",
      "From Montpelier VT to New York NY: 82.0\n"
     ]
    }
   ],
   "source": [
    "# Display Non-zero solutions\n",
    "for i in 1:num_supp \n",
    "    for j in 1:num_ware \n",
    "        if value(x[i,j]) > 0 \n",
    "            println(\"From $(supp_name[i]) to $(ware_name[j]): $(value(x[i,j]))\")\n",
    "        end\n",
    "    end \n",
    "end "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.0.5",
   "language": "julia",
   "name": "julia-1.0"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.0.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}