{ "cells": [ { "cell_type": "markdown", "metadata": { "pycharm": {} }, "source": [ "\n", "*This notebook contains course material from [CBE40455](https://jckantor.github.io/CBE40455) by\n", "Jeffrey Kantor (jeff at nd.edu); the content is available [on Github](https://github.com/jckantor/CBE40455.git).\n", "The text is released under the [CC-BY-NC-ND-4.0 license](https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode),\n", "and code is released under the [MIT license](https://opensource.org/licenses/MIT).*" ] }, { "cell_type": "markdown", "metadata": { "pycharm": {} }, "source": [ "\n", "< [Assignment Problems](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/05.02-Assignment-Problems.ipynb) | [Contents](toc.ipynb) | [Vehicle Routing with Time Windows](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/05.04-Vehicle-Routing-with-Time-Windows.ipynb) >

\"Open

\"Download\"" ] }, { "cell_type": "markdown", "metadata": { "pycharm": {} }, "source": [ "# Vehicle Routing\n", "\n", "A set of airplanes are initially distributed among a set of starting locations. They are to be assigned routes to collectively visit a specified set of customers then return the the planes to designated finishing locations. The optimization objective is to minimize the total great circle distance.\n", "\n", "The data consists of a set of locations with latitude and longitude information, a list of customers and their respective locations, and a set of aircraft and their starting and finishing locations. The aircraft must start and finish at different locations (if needed, dummy locations with the same latitude and longitude can be included in the list of locations).\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false, "pycharm": {} }, "outputs": [], "source": [ "%%script glpsol -m /dev/stdin -y VehicleRouting.txt --out output\n", "\n", "/* Vehicle Routing Problem\n", " Jeffrey Kantor\n", " March, 2013\n", "*/\n", "\n", "# DATA SETS (TO BE GIVEN IN THE DATA SECTION)\n", "\n", "# CUSTOMERS is a set of (name,location) pairs \n", "set CUSTOMERS dimen 2;\n", "\n", "# PLANES is a set of (name, start_location, finish_location) triples\n", "set PLANES dimen 3;\n", "\n", "# set of locations\n", "set LOCATIONS;\n", "param lat{LOCATIONS};\n", "param lng{LOCATIONS};\n", "\n", "# DATA PREPROCESSING\n", "\n", "# set of planes\n", "set P := setof {(p,sLoc,fLoc) in PLANES} p;\n", "\n", "# create a complete of nodes as (name, location) pairs\n", "set START := setof {(p,sLoc,fLoc) in PLANES} (p,sLoc);\n", "set FINISH := setof {(p,sLoc,fLoc) in PLANES} (p,fLoc);\n", "set N := CUSTOMERS union (START union FINISH);\n", "\n", "# great circle distances between locations\n", "param d2r := 3.1415926/180;\n", "param alpha{a in LOCATIONS, b in LOCATIONS} := sin(d2r*(lat[a]-lat[b])/2)**2 \n", " + cos(d2r*lat[a])*cos(d2r*lat[b])*sin(d2r*(lng[a]-lng[b])/2)**2;\n", "param gcdist{a in LOCATIONS, b in LOCATIONS} := \n", " 2*6371*atan( sqrt(alpha[a,b]), sqrt(1-alpha[a,b]) );\n", "\n", "# DECISION VARIABLES\n", "\n", "# x[p,a,aLoc,b,bLoc] = 1 if plane p flies from (a,aLoc) to (b,bLoc)\n", "var x{P, N, N} binary;\n", "\n", "# START AND FINISH CONSTRAINTS\n", "\n", "# no planes arrive at the start nodes\n", "s.t. sf1 {p in P, (a,aLoc) in N, (b,bLoc) in START} : x[p,a,aLoc,b,bLoc] = 0;\n", "\n", "# no planes leave the finish nodes\n", "s.t. sf2 {p in P, (a,aLoc) in FINISH, (b,bLoc) in N} : x[p,a,aLoc,b,bLoc] = 0;\n", "\n", "# planes must leave from their own start nodes\n", "s.t. sf3 {p in P, (a,aLoc) in START, (b,bLoc) in N : p != a} : x[p,a,aLoc,b,bLoc] = 0;\n", "\n", "# planes must return to their own finish nodes\n", "s.t. sf4 {p in P, (a,aLoc) in N, (b,bLoc) in FINISH : p != b} : x[p,a,aLoc,b,bLoc] = 0;\n", "\n", "# NETWORK CONSTRAINTS\n", "\n", "# one plane arrives at each customer and finish node\n", "s.t. nw1 {(b,bLoc) in (CUSTOMERS union FINISH)} : \n", " sum {p in P, (a,aLoc) in (CUSTOMERS union START)} x[p,a,aLoc,b,bLoc] = 1;\n", "\n", "# one plane leaves each start and customer node\n", "s.t. nw2 {(a,aLoc) in (START union CUSTOMERS)} :\n", " sum {p in P, (b,bLoc) in (CUSTOMERS union FINISH)} x[p,a,aLoc,b,bLoc] = 1;\n", "\n", "# planes entering a customer node must leave the same node\n", "s.t. nw3 {p in P, (a,aLoc) in CUSTOMERS} : \n", " sum {(b,bLoc) in (CUSTOMERS union START)} x[p,b,bLoc,a,aLoc]\n", " = sum {(b,bLoc) in (CUSTOMERS union FINISH)} x[p,a,aLoc,b,bLoc];\n", "\n", "# no self loops\n", "s.t. nw4 {p in P, (a,aLoc) in N, (b,bLoc) in N : (a=b) && (aLoc=bLoc)} :\n", " x[p,a,aLoc,b,bLoc] = 0;\n", "\n", "# SUBTOUR ELIMINATION CONSTRAINTS\n", "\n", "var y{P,N,N} integer, >= 0;\n", "\n", "# route capacity\n", "s.t. sb1 {p in P, (a,aLoc) in N, (b,bLoc) in N} : \n", " y[p,a,aLoc,b,bLoc] <= card(CUSTOMERS)*x[p,a,aLoc,b,bLoc];\n", "\n", "# allocate tokens to links from the start nodes\n", "s.t. sb2 : sum {p in P, (a,aLoc) in START, (b,bLoc) in N } y[p,a,aLoc,b,bLoc] \n", " = card(CUSTOMERS);\n", "\n", "# decrease tokens for each step on a path\n", "s.t. sb3 {(a,aLoc) in CUSTOMERS} : \n", " sum{p in P, (b,bLoc) in (CUSTOMERS union START)} y[p,b,bLoc,a,aLoc] \n", " = 1 + sum{p in P, (b,bLoc) in (CUSTOMERS union FINISH)} y[p,a,aLoc,b,bLoc];\n", "\n", "# OBJECTIVE\n", "\n", "var routeDistance{P} >= 0;\n", "s.t. ob1 {p in P} : routeDistance[p] \n", " = sum{(a,aLoc) in N, (b,bLoc) in N} gcdist[aLoc,bLoc]*x[p,a,aLoc,b,bLoc];\n", "\n", "var routeLegs{P} >= 0;\n", "s.t. ob2 {p in P} : routeLegs[p] = sum{(a,aLoc) in START, (b,bLoc) in N} y[p,a,aLoc,b,bLoc];\n", "\n", "var maxDistance >= 0;\n", "s.t. ob3 {p in P} : routeDistance[p] <= maxDistance;\n", "\n", "var maxLegs >= 0;\n", "s.t. ob4 {p in P} : routeLegs[p] <= maxLegs;\n", "\n", "minimize distance : sum{p in P} routeDistance[p];\n", "\n", "solve;\n", "\n", "# OUTPUT POST-PROCESSING\n", "\n", "for {p in P} {\n", " printf \"\\nRouting for %s\\n-------------------\\n\", p;\n", " printf \"%-20s %-20s %10s \\n\", 'Depart','Arrive','Dist.';\n", " for {k in routeLegs[p]..0 by -1} {\n", " printf {(a,aLoc) in N, (b,bLoc) in N : \n", " (x[p,a,aLoc,b,bLoc] = 1) && (y[p,a,aLoc,b,bLoc]=k)} \n", "\t \"%-12s %-5s %-12s %-5s %10.1f km\\n\",a,aLoc,b,bLoc,gcdist[aLoc,bLoc];\n", " }\n", " printf \"%42s %13s\\n\", '', '---------';\n", " printf \"%42s %10.1f km\\n\\n\", 'GC Distance Traveled:', routeDistance[p];\n", "}\n", "\n", "# DATA SECTION\n", "\n", "data;\n", "\n", "set CUSTOMERS := \n", " ( 'Atlanta', ATL )\n", " ( 'Boston', BOS )\n", " ( 'Denver', DEN )\n", " ( 'Dallas', DFW )\n", " ( 'New York', JFK )\n", " ( 'Los Angeles', LAX )\n", " ( 'Chicago', ORD )\n", " ( 'St. Louis', STL ) \n", ";\n", "\n", "set PLANES :=\n", " ( 'Plane 1', ORD, ORD_) # use a duplicate location to return place to ORD\n", " ( 'Plane 2', DFW, DRW_) # use a duplicate location to return plane to DFW\n", ";\n", "\n", "param : LOCATIONS : lat lng :=\n", " ATL 33.6366995 -84.4278639\n", " BOS 42.3629722 -71.0064167\n", " DEN 39.8616667 -104.6731667\n", " DFW 32.8968281 -97.0379958\n", " DRW_ 32.8968281 -97.0379958 # duplicate PLANES\n", " JFK 40.6397511 -73.7789256\n", " LAX 33.9424955 -118.4080684\n", " ORD 41.9816486 -87.9066714\n", " ORD_ 41.9816486 -87.9066714 # duplicate PLANES\n", " STL 38.7486972 -90.3700289\n", "; \n", "\n", "end;\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false, "pycharm": {} }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "Routing for Plane 1\n", "-------------------\n", "Depart Arrive Dist. \n", "Plane 1 ORD St. Louis STL 415.6 km\n", "St. Louis STL Atlanta ATL 779.0 km\n", "Atlanta ATL New York JFK 1222.1 km\n", "New York JFK Boston BOS 300.0 km\n", "Boston BOS Chicago ORD 1391.1 km\n", "Chicago ORD Plane 1 ORD_ 0.0 km\n", " ---------\n", " GC Distance Traveled: 4107.8 km\n", "\n", "\n", "Routing for Plane 2\n", "-------------------\n", "Depart Arrive Dist. \n", "Plane 2 DFW Dallas DFW 0.0 km\n", "Dallas DFW Los Angeles LAX 1983.2 km\n", "Los Angeles LAX Denver DEN 1385.1 km\n", "Denver DEN Plane 2 DRW_ 1032.1 km\n", " ---------\n", " GC Distance Traveled: 4400.4 km\n", "\n", "\n" ] } ], "source": [ "print(open('VehicleRouting.txt').read())" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "pycharm": {} }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": { "pycharm": {} }, "source": [ "\n", "< [Assignment Problems](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/05.02-Assignment-Problems.ipynb) | [Contents](toc.ipynb) | [Vehicle Routing with Time Windows](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/05.04-Vehicle-Routing-with-Time-Windows.ipynb) >

\"Open

\"Download\"" ] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.10" } }, "nbformat": 4, "nbformat_minor": 0 }