{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 611 巡回セールスマン問題\n",
"\n",
"Inspired by http://www.gurobi.com/documentation/8.0/examples/tsp_py.html"
]
},
{
"cell_type": "markdown",
"metadata": {
"ExecuteTime": {
"end_time": "2018-05-15T03:08:57.731565Z",
"start_time": "2018-05-15T03:08:57.728312Z"
},
"collapsed": true
},
"source": [
"## 読み込み"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"ExecuteTime": {
"end_time": "2018-05-16T02:29:42.288329Z",
"start_time": "2018-05-16T02:29:41.903436Z"
},
"collapsed": true
},
"outputs": [],
"source": [
"import pandas as pd\n",
"from geopy.distance import great_circle\n",
"\n",
"import gmaps\n",
"google_map_api_key = 'hogehoge'\n",
"gmaps.configure(api_key=google_map_api_key)\n",
"from ipywidgets.embed import embed_minimal_html\n",
"\n",
"import gurobipy as gp"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 関数定義"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"ExecuteTime": {
"end_time": "2018-05-16T02:29:42.303983Z",
"start_time": "2018-05-16T02:29:42.290503Z"
},
"collapsed": true
},
"outputs": [],
"source": [
"def calc_dist_from_latlng(lat1, lng1, lat2, lng2, unit='m'):\n",
" if unit == 'm':\n",
" return great_circle((lat1, lng1), (lat2, lng2)).meters\n",
" elif unit == 'km':\n",
" return great_circle((lat1, lng1), (lat2, lng2)).kilometers\n",
" else:\n",
" print('ERROR: unit')\n",
" return False"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## パラメータ定義\n",
"#### Latlag定義"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"ExecuteTime": {
"end_time": "2018-05-16T02:29:42.460322Z",
"start_time": "2018-05-16T02:29:42.306756Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"
\n",
"\n",
"
\n",
" \n",
" \n",
" | \n",
" lat | \n",
" lng | \n",
"
\n",
" \n",
" \n",
" \n",
" Office | \n",
" 35.706048 | \n",
" 139.706735 | \n",
"
\n",
" \n",
" Library | \n",
" 35.705613 | \n",
" 139.707174 | \n",
"
\n",
" \n",
" Class | \n",
" 35.705713 | \n",
" 139.705254 | \n",
"
\n",
" \n",
" Gym | \n",
" 35.706034 | \n",
" 139.716454 | \n",
"
\n",
" \n",
" Pool | \n",
" 35.704950 | \n",
" 139.708149 | \n",
"
\n",
" \n",
" Ramen | \n",
" 35.708074 | \n",
" 139.708828 | \n",
"
\n",
" \n",
"
\n",
"
"
],
"text/plain": [
" lat lng\n",
"Office 35.706048 139.706735\n",
"Library 35.705613 139.707174\n",
"Class 35.705713 139.705254\n",
"Gym 35.706034 139.716454\n",
"Pool 35.704950 139.708149\n",
"Ramen 35.708074 139.708828"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Distance matrix\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" | \n",
" Office | \n",
" Library | \n",
" Class | \n",
" Gym | \n",
" Pool | \n",
" Ramen | \n",
"
\n",
" \n",
" \n",
" \n",
" Office | \n",
" 0 | \n",
" 62.5369 | \n",
" 138.815 | \n",
" 877.558 | \n",
" 176.656 | \n",
" 294.05 | \n",
"
\n",
" \n",
" Library | \n",
" 62.5369 | \n",
" 0 | \n",
" 173.719 | \n",
" 839.227 | \n",
" 114.828 | \n",
" 311.75 | \n",
"
\n",
" \n",
" Class | \n",
" 138.815 | \n",
" 173.719 | \n",
" 0 | \n",
" 1011.91 | \n",
" 274.824 | \n",
" 416.005 | \n",
"
\n",
" \n",
" Gym | \n",
" 877.558 | \n",
" 839.227 | \n",
" 1011.91 | \n",
" 0 | \n",
" 759.513 | \n",
" 724.967 | \n",
"
\n",
" \n",
" Pool | \n",
" 176.656 | \n",
" 114.828 | \n",
" 274.824 | \n",
" 759.513 | \n",
" 0 | \n",
" 352.742 | \n",
"
\n",
" \n",
" Ramen | \n",
" 294.05 | \n",
" 311.75 | \n",
" 416.005 | \n",
" 724.967 | \n",
" 352.742 | \n",
" 0 | \n",
"
\n",
" \n",
"
\n",
"
"
],
"text/plain": [
" Office Library Class Gym Pool Ramen\n",
"Office 0 62.5369 138.815 877.558 176.656 294.05\n",
"Library 62.5369 0 173.719 839.227 114.828 311.75\n",
"Class 138.815 173.719 0 1011.91 274.824 416.005\n",
"Gym 877.558 839.227 1011.91 0 759.513 724.967\n",
"Pool 176.656 114.828 274.824 759.513 0 352.742\n",
"Ramen 294.05 311.75 416.005 724.967 352.742 0"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"IND_BUILDINGS = ['Office', 'Library', 'Class', 'Gym', 'Pool', 'Ramen']\n",
"latlng_df = pd.DataFrame([[35.706048, 139.706735],\n",
" [35.705613, 139.707174],\n",
" [35.705713, 139.705254],\n",
" [35.706034, 139.716454],\n",
" [35.704950, 139.708149],\n",
" [35.708074, 139.708828]],\n",
" index=IND_BUILDINGS, columns=['lat', 'lng'])\n",
"\n",
"dist_df = pd.DataFrame(index=IND_BUILDINGS, columns=IND_BUILDINGS)\n",
"for key, values in dist_df.iterrows():\n",
" for key2, value in values.items():\n",
" if key == key2:\n",
" #break\n",
" pass\n",
" dist_df.loc[key, key2] = calc_dist_from_latlng(latlng_df.loc[key].lat, latlng_df.loc[key].lng, \n",
" latlng_df.loc[key2].lat, latlng_df.loc[key2].lng)\n",
"display(latlng_df) \n",
"print('Distance matrix')\n",
"display(dist_df)"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"## Mixed Integer Linear programming of Travelling salesman problem\n",
"\n",
"TSP with MTZ[1]\n",
"\n",
"\\begin{align}\n",
" \\text{Minimize } \\Sigma_{i=1}^n\\Sigma_{j=1}^n c_{ij}\\delta_{ij}, \\\\\n",
" \\text{Subject to }\\Sigma_{i=1,i\\neq j}^n\\delta_{ij}&=1 &\\forall j\\in \\{1,...,n\\}, \\\\ \n",
" \\Sigma_{j=1,j\\neq i}^n\\delta_{ji}&=1 &\\forall i\\in \\{1,...,n\\}, \\\\ \n",
" x_{i} - x_{j} + (n-1)\\delta_{ij} &\\le n-2 &\\forall i\\in \\{1,...,n\\}, \\forall j \\in \\{2,...,n\\} \\\\\n",
" \\text{where } c \\in R^{n\\times n}, \\delta\\in \\{0,1\\}^{n\\times n}, 1\\le x_{i}\\le n-1 \\nonumber.\n",
"\\end{align}\n",
"\n",
"See reference for more detailed formulation.\n",
"\n",
"[1] C. E. Miller, A. W. Tucker, and R. A. Zemlin, “Integer Programming Formulation of Traveling Salesman Problems,” J. ACM, vol. 7, no. 4, pp. 326–329, 1960.\n",
"\n",
"[2] A. Langevin, F. Soumis, and J. Desrosiers, “Classification of travelling salesman problem formulations,” Oper. Res. Lett., vol. 9, no. 2, pp. 127–132, 1990.\n",
"\n",
"[3] A. Subramanyam and C. E. Gounaris, “A branch-and-cut framework for the consistent traveling salesman problem,” Eur. J. Oper. Res., vol. 248, no. 2, pp. 384–395, 2016."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"ExecuteTime": {
"end_time": "2018-05-16T02:29:42.540446Z",
"start_time": "2018-05-16T02:29:42.462424Z"
},
"scrolled": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\\ Model tsp\n",
"\\ LP format - for model browsing. Use MPS format to capture full model detail.\n",
"Minimize\n",
" 63 b_edge(Office,Library) + 139 b_edge(Office,Class)\n",
" + 878 b_edge(Office,Gym) + 177 b_edge(Office,Pool)\n",
" + 294 b_edge(Office,Ramen) + 63 b_edge(Library,Office)\n",
" + 174 b_edge(Library,Class) + 839 b_edge(Library,Gym)\n",
" + 115 b_edge(Library,Pool) + 312 b_edge(Library,Ramen)\n",
" + 139 b_edge(Class,Office) + 174 b_edge(Class,Library)\n",
" + 1012 b_edge(Class,Gym) + 275 b_edge(Class,Pool)\n",
" + 416 b_edge(Class,Ramen) + 878 b_edge(Gym,Office)\n",
" + 839 b_edge(Gym,Library) + 1012 b_edge(Gym,Class)\n",
" + 760 b_edge(Gym,Pool) + 725 b_edge(Gym,Ramen) + 177 b_edge(Pool,Office)\n",
" + 115 b_edge(Pool,Library) + 275 b_edge(Pool,Class)\n",
" + 760 b_edge(Pool,Gym) + 353 b_edge(Pool,Ramen)\n",
" + 294 b_edge(Ramen,Office) + 312 b_edge(Ramen,Library)\n",
" + 416 b_edge(Ramen,Class) + 725 b_edge(Ramen,Gym)\n",
" + 353 b_edge(Ramen,Pool)\n",
"Subject To\n",
" eq_src_dest_(OfficeRamen): b_edge(Office,Library) + b_edge(Office,Class)\n",
" + b_edge(Office,Gym) + b_edge(Office,Pool) + b_edge(Office,Ramen) = 1\n",
" eq_dest_src_(RamenOffice): b_edge(Library,Office) + b_edge(Class,Office)\n",
" + b_edge(Gym,Office) + b_edge(Pool,Office) + b_edge(Ramen,Office) = 1\n",
" eq_src_dest_(LibraryRamen): b_edge(Library,Office) + b_edge(Library,Class)\n",
" + b_edge(Library,Gym) + b_edge(Library,Pool) + b_edge(Library,Ramen)\n",
" = 1\n",
" eq_dest_src_(RamenLibrary): b_edge(Office,Library) + b_edge(Class,Library)\n",
" + b_edge(Gym,Library) + b_edge(Pool,Library) + b_edge(Ramen,Library)\n",
" = 1\n",
" eq_src_dest_(ClassRamen): b_edge(Class,Office) + b_edge(Class,Library)\n",
" + b_edge(Class,Gym) + b_edge(Class,Pool) + b_edge(Class,Ramen) = 1\n",
" eq_dest_src_(RamenClass): b_edge(Office,Class) + b_edge(Library,Class)\n",
" + b_edge(Gym,Class) + b_edge(Pool,Class) + b_edge(Ramen,Class) = 1\n",
" eq_src_dest_(GymRamen): b_edge(Gym,Office) + b_edge(Gym,Library)\n",
" + b_edge(Gym,Class) + b_edge(Gym,Pool) + b_edge(Gym,Ramen) = 1\n",
" eq_dest_src_(RamenGym): b_edge(Office,Gym) + b_edge(Library,Gym)\n",
" + b_edge(Class,Gym) + b_edge(Pool,Gym) + b_edge(Ramen,Gym) = 1\n",
" eq_src_dest_(PoolRamen): b_edge(Pool,Office) + b_edge(Pool,Library)\n",
" + b_edge(Pool,Class) + b_edge(Pool,Gym) + b_edge(Pool,Ramen) = 1\n",
" eq_dest_src_(RamenPool): b_edge(Office,Pool) + b_edge(Library,Pool)\n",
" + b_edge(Class,Pool) + b_edge(Gym,Pool) + b_edge(Ramen,Pool) = 1\n",
" eq_src_dest_(RamenRamen): b_edge(Ramen,Office) + b_edge(Ramen,Library)\n",
" + b_edge(Ramen,Class) + b_edge(Ramen,Gym) + b_edge(Ramen,Pool) = 1\n",
" eq_dest_src_(RamenRamen): b_edge(Office,Ramen) + b_edge(Library,Ramen)\n",
" + b_edge(Class,Ramen) + b_edge(Gym,Ramen) + b_edge(Pool,Ramen) = 1\n",
" eq_u(Library,Class): u(Library) + 5 b_edge(Library,Class) - u(Class) <= 4\n",
" eq_u(Library,Gym): u(Library) + 5 b_edge(Library,Gym) - u(Gym) <= 4\n",
" eq_u(Library,Pool): u(Library) + 5 b_edge(Library,Pool) - u(Pool) <= 4\n",
" eq_u(Library,Ramen): u(Library) + 5 b_edge(Library,Ramen) - u(Ramen) <= 4\n",
" eq_u(Class,Library): - u(Library) + u(Class) + 5 b_edge(Class,Library)\n",
" <= 4\n",
" eq_u(Class,Gym): u(Class) + 5 b_edge(Class,Gym) - u(Gym) <= 4\n",
" eq_u(Class,Pool): u(Class) + 5 b_edge(Class,Pool) - u(Pool) <= 4\n",
" eq_u(Class,Ramen): u(Class) + 5 b_edge(Class,Ramen) - u(Ramen) <= 4\n",
" eq_u(Gym,Library): - u(Library) + u(Gym) + 5 b_edge(Gym,Library) <= 4\n",
" eq_u(Gym,Class): - u(Class) + u(Gym) + 5 b_edge(Gym,Class) <= 4\n",
" eq_u(Gym,Pool): u(Gym) + 5 b_edge(Gym,Pool) - u(Pool) <= 4\n",
" eq_u(Gym,Ramen): u(Gym) + 5 b_edge(Gym,Ramen) - u(Ramen) <= 4\n",
" eq_u(Pool,Library): - u(Library) + u(Pool) + 5 b_edge(Pool,Library) <= 4\n",
" eq_u(Pool,Class): - u(Class) + u(Pool) + 5 b_edge(Pool,Class) <= 4\n",
" eq_u(Pool,Gym): - u(Gym) + u(Pool) + 5 b_edge(Pool,Gym) <= 4\n",
" eq_u(Pool,Ramen): u(Pool) + 5 b_edge(Pool,Ramen) - u(Ramen) <= 4\n",
" eq_u(Ramen,Library): - u(Library) + u(Ramen) + 5 b_edge(Ramen,Library)\n",
" <= 4\n",
" eq_u(Ramen,Class): - u(Class) + u(Ramen) + 5 b_edge(Ramen,Class) <= 4\n",
" eq_u(Ramen,Gym): - u(Gym) + u(Ramen) + 5 b_edge(Ramen,Gym) <= 4\n",
" eq_u(Ramen,Pool): - u(Pool) + u(Ramen) + 5 b_edge(Ramen,Pool) <= 4\n",
"Bounds\n",
" 1 <= u(Library) <= 5\n",
" 1 <= u(Class) <= 5\n",
" 1 <= u(Gym) <= 5\n",
" 1 <= u(Pool) <= 5\n",
" 1 <= u(Ramen) <= 5\n",
"Binaries\n",
" b_edge(Office,Library) b_edge(Office,Class) b_edge(Office,Gym)\n",
" b_edge(Office,Pool) b_edge(Office,Ramen) b_edge(Library,Office)\n",
" b_edge(Library,Class) b_edge(Library,Gym) b_edge(Library,Pool)\n",
" b_edge(Library,Ramen) b_edge(Class,Office) b_edge(Class,Library)\n",
" b_edge(Class,Gym) b_edge(Class,Pool) b_edge(Class,Ramen)\n",
" b_edge(Gym,Office) b_edge(Gym,Library) b_edge(Gym,Class) b_edge(Gym,Pool)\n",
" b_edge(Gym,Ramen) b_edge(Pool,Office) b_edge(Pool,Library)\n",
" b_edge(Pool,Class) b_edge(Pool,Gym) b_edge(Pool,Ramen)\n",
" b_edge(Ramen,Office) b_edge(Ramen,Library) b_edge(Ramen,Class)\n",
" b_edge(Ramen,Gym) b_edge(Ramen,Pool)\n",
"End\n",
"\n"
]
}
],
"source": [
"model = gp.Model('tsp')\n",
"\n",
"delta_var_dict = {}\n",
"cont_var_dict = {}\n",
"for src in dist_df.keys():\n",
" if src != dist_df.keys()[0]:\n",
" cont_var_dict[src] = model.addVar(lb=1, ub=len(dist_df.keys())-1, name='u({})'.format(src))\n",
" for dest in dist_df.keys():\n",
" if src == dest: continue\n",
" delta_var_dict[(src, dest)] = model.addVar(obj=round(dist_df.loc[src, dest]), vtype=gp.GRB.BINARY, \n",
" name='b_edge({},{})'.format(src, dest))\n",
"model.update()\n",
" \n",
"for src in dist_df.keys():\n",
" lhs_sd = gp.LinExpr(0)\n",
" lhs_ds = gp.LinExpr(0)\n",
" for dest in dist_df.keys():\n",
" if src == dest: continue\n",
" lhs_sd += delta_var_dict[(src, dest)]\n",
" lhs_ds += delta_var_dict[(dest, src)]\n",
" model.addConstr(lhs_sd == 1, name='eq_src_dest_({}{})'.format(src, dest))\n",
" model.addConstr(lhs_ds == 1, name='eq_dest_src_({}{})'.format(dest, src))\n",
" \n",
"for src in dist_df.keys()[1:]:\n",
" for dest in dist_df.keys()[1:]:\n",
" if src == dest: continue\n",
" model.addConstr(cont_var_dict[src] - cont_var_dict[dest] \n",
" + (len(dist_df.keys())-1)*delta_var_dict[(src, dest)] \n",
" <= len(dist_df.keys())-2, name='eq_u({},{})'.format(src, dest))\n",
"\n",
"output_file = 'tsp.lp'\n",
"model.write(output_file)\n",
"print(open(output_file).read())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 最適化実行"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"ExecuteTime": {
"end_time": "2018-05-16T02:29:42.620611Z",
"start_time": "2018-05-16T02:29:42.543505Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Optimize a model with 32 rows, 35 columns and 120 nonzeros\n",
"Variable types: 5 continuous, 30 integer (30 binary)\n",
"Coefficient statistics:\n",
" Matrix range [1e+00, 5e+00]\n",
" Objective range [6e+01, 1e+03]\n",
" Bounds range [1e+00, 5e+00]\n",
" RHS range [1e+00, 4e+00]\n",
"Found heuristic solution: objective 2837.0000000\n",
"Presolve time: 0.00s\n",
"Presolved: 32 rows, 35 columns, 180 nonzeros\n",
"Variable types: 5 continuous, 30 integer (30 binary)\n",
"\n",
"Root relaxation: objective 2.061517e+03, 21 iterations, 0.00 seconds\n",
"\n",
" Nodes | Current Node | Objective Bounds | Work\n",
" Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time\n",
"\n",
" 0 0 2061.51724 0 9 2837.00000 2061.51724 27.3% - 0s\n",
"H 0 0 2495.0000000 2061.51724 17.4% - 0s\n",
"H 0 0 2387.0000000 2061.51724 13.6% - 0s\n",
"H 0 0 2207.0000000 2061.51724 6.59% - 0s\n",
" 0 0 infeasible 0 2207.00000 2207.00000 0.00% - 0s\n",
"\n",
"Cutting planes:\n",
" Gomory: 1\n",
" Implied bound: 2\n",
" Clique: 2\n",
" MIR: 6\n",
"\n",
"Explored 1 nodes (31 simplex iterations) in 0.06 seconds\n",
"Thread count was 8 (of 8 available processors)\n",
"\n",
"Solution count 4: 2207 2387 2495 2837 \n",
"\n",
"Optimal solution found (tolerance 1.00e-04)\n",
"Best objective 2.207000000000e+03, best bound 2.207000000000e+03, gap 0.0000%\n"
]
}
],
"source": [
"model.optimize()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 最適化結果"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"ExecuteTime": {
"end_time": "2018-05-16T02:29:42.635946Z",
"start_time": "2018-05-16T02:29:42.622900Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"{'Class': 5.0,\n",
" 'Gym': 2.0,\n",
" 'Library': 4.0,\n",
" 'Pool': 2.9999999999999942,\n",
" 'Ramen': 1.0}"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"{('Class', 'Office'): 1,\n",
" ('Gym', 'Pool'): 1,\n",
" ('Library', 'Class'): 1,\n",
" ('Office', 'Ramen'): 1,\n",
" ('Pool', 'Library'): 1,\n",
" ('Ramen', 'Gym'): 1}"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"optimum_var_dict = model.getAttr('x', delta_var_dict)\n",
"\n",
"optimal_dict = {}\n",
"for src in dist_df.keys(): \n",
" for dest in dist_df.keys():\n",
" if src == dest: continue\n",
" if optimum_var_dict[src, dest] != 0:\n",
" optimal_dict[(src, dest)] = 1\n",
"\n",
"display(model.getAttr('x', cont_var_dict), optimal_dict)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 可視化\n",
"### 選択候補群"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"ExecuteTime": {
"end_time": "2018-05-16T02:29:42.816617Z",
"start_time": "2018-05-16T02:29:42.638346Z"
},
"collapsed": true
},
"outputs": [],
"source": [
"fig = gmaps.figure(center=(35.706219, 139.712076), zoom_level=16)\n",
"\n",
"marker_drawing = gmaps.symbol_layer(locations=latlng_df, fill_color='green', stroke_color='green',\n",
" scale=5, hover_text=latlng_df.index.values, \n",
" info_box_content=latlng_df.index.values)\n",
"fig.add_layer(marker_drawing)\n",
"\n",
"lines = []\n",
"for key, src_latlng in latlng_df.iterrows():\n",
" for key2, dest_latlng in latlng_df.iterrows():\n",
" if src_latlng['lat'] == dest_latlng['lat'] and src_latlng['lng'] == dest_latlng['lng']: continue\n",
" line = gmaps.Line(start=(src_latlng['lat'], src_latlng['lng']), \n",
" end=(dest_latlng['lat'], dest_latlng['lng']))\n",
" if line not in lines:\n",
" lines.append(line)\n",
" \n",
"line_drawing = gmaps.drawing_layer()\n",
"line_drawing.features = lines\n",
"fig.add_layer(line_drawing)\n",
"#fig\n",
"embed_minimal_html('../_static/html/tsp_candidate.html', views=[fig])"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"ExecuteTime": {
"end_time": "2018-05-16T02:29:42.823640Z",
"start_time": "2018-05-16T02:29:42.818977Z"
}
},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%%HTML\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 最短一巡経路"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"ExecuteTime": {
"end_time": "2018-05-16T02:29:42.931566Z",
"start_time": "2018-05-16T02:29:42.825616Z"
},
"collapsed": true
},
"outputs": [],
"source": [
"fig = gmaps.figure(center=(35.706219, 139.712076), zoom_level=16)\n",
"\n",
"marker_drawing = gmaps.symbol_layer(locations=latlng_df, fill_color='green', stroke_color='green',\n",
" scale=5, hover_text=latlng_df.index.values, info_box_content=latlng_df.index.values)\n",
"fig.add_layer(marker_drawing)\n",
"\n",
"lines = []\n",
"for key, value in optimal_dict.items():\n",
" lines.append(gmaps.Line(start=(latlng_df.loc[key[0], 'lat'], latlng_df.loc[key[0], 'lng']),\n",
" end=(latlng_df.loc[key[1], 'lat'], latlng_df.loc[key[1], 'lng'])))\n",
"\n",
"line_drawing = gmaps.drawing_layer()\n",
"line_drawing.features = lines\n",
"fig.add_layer(line_drawing)\n",
"#fig\n",
"embed_minimal_html('../_static/html/tsp_optimum.html', views=[fig])"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"ExecuteTime": {
"end_time": "2018-05-16T02:29:42.938931Z",
"start_time": "2018-05-16T02:29:42.933977Z"
}
},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%%HTML\n",
""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"author": "",
"kernelspec": {
"display_name": "Python [conda env:py3.6]",
"language": "python",
"name": "conda-env-py3.6-py"
},
"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.6.4"
},
"latex_envs": {
"LaTeX_envs_menu_present": true,
"autocomplete": true,
"bibliofile": "biblio.bib",
"cite_by": "apalike",
"current_citInitial": 1,
"eqLabelWithNumbers": true,
"eqNumInitial": 1,
"hotkeys": {
"equation": "Ctrl-E",
"itemize": "Ctrl-I"
},
"labels_anchors": false,
"latex_user_defs": false,
"report_style_numbering": false,
"user_envs_cfg": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}