{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4dc5db6d",
   "metadata": {},
   "source": [
    "# 车辆路径优化 — VRP 入门\n",
    "\n",
    "对应案例: [车辆路径](/docs/case-studies/operations/vehicle-routing-case/)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cede17d7",
   "metadata": {},
   "source": [
    "## 1. 城市坐标 & 距离矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fd37da9f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np, pandas as pd, matplotlib.pyplot as plt\n",
    "np.random.seed(42)\n",
    "n_cities=20\n",
    "coords=np.random.rand(n_cities,2)*100\n",
    "depot=np.array([50,50])\n",
    "dist=np.zeros((n_cities,n_cities))\n",
    "for i in range(n_cities):\n",
    "    for j in range(n_cities):\n",
    "        dist[i,j]=np.sqrt(sum((coords[i]-coords[j])**2))\n",
    "# Plot\n",
    "plt.figure(figsize=(10,8))\n",
    "plt.scatter(coords[:,0],coords[:,1],c='#2196F3',s=100,label='Cities')\n",
    "plt.scatter([depot[0]],[depot[1]],c='red',s=200,marker='*',label='Depot')\n",
    "for i,(x,y) in enumerate(coords):\n",
    "    plt.annotate(str(i),(x,y),fontsize=9)\n",
    "plt.legend(); plt.title('VRP: Cities & Depot'); plt.show()\n",
    "print(f'Cities: {n_cities}, Depot at {tuple(depot)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8af15853",
   "metadata": {},
   "source": [
    "## 2. 最近邻启发式"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "226314d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nearest_neighbor(dist_mat,start=0):\n",
    "    n=len(dist_mat); visited=[start]; unvisited=set(range(n))-{start}\n",
    "    while unvisited:\n",
    "        last=visited[-1]; nxt=min(unvisited,key=lambda x:dist_mat[last,x])\n",
    "        visited.append(nxt); unvisited.remove(nxt)\n",
    "    return visited\n",
    "route=nearest_neighbor(dist)\n",
    "total=sum(dist[route[i],route[i+1]] for i in range(len(route)-1))\n",
    "# Add depot: out and back\n",
    "total+=dist[0,route[0]]\n",
    "print(f'Route: {route}')\n",
    "print(f'Total distance: {total:.1f}')\n",
    "# Plot route\n",
    "r=np.array([depot]+list(coords[route])+[depot])\n",
    "plt.figure(figsize=(10,8))\n",
    "plt.plot(r[:,0],r[:,1],'o-',color='#2196F3',lw=2,markersize=10)\n",
    "plt.scatter([depot[0]],[depot[1]],c='red',s=200,marker='*',zorder=5)\n",
    "for i,(x,y) in enumerate(coords):\n",
    "    plt.annotate(str(i),(x,y),fontsize=8)\n",
    "plt.title(f'NN Route (dist={total:.1f})'); plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ccda3b3",
   "metadata": {},
   "source": [
    "## 3. 2-opt 改进"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "08d62ccd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def two_opt(route,dist_mat):\n",
    "    improved=True; best=route.copy()\n",
    "    best_d=sum(dist_mat[best[i],best[i+1]] for i in range(len(best)-1))\n",
    "    while improved:\n",
    "        improved=False\n",
    "        for i in range(1,len(best)-2):\n",
    "            for j in range(i+1,len(best)):\n",
    "                new=best[:i]+best[i:j][::-1]+best[j:]\n",
    "                new_d=sum(dist_mat[new[k],new[k+1]] for k in range(len(new)-1))\n",
    "                if new_d<best_d-1e-6:\n",
    "                    best,best_d=new,new_d; improved=True\n",
    "    return best,best_d\n",
    "opt_route,opt_dist=two_opt(route,dist)\n",
    "print(f'NN: {total:.1f} -> 2-opt: {opt_dist:.1f} ({(opt_dist/total-1)*100:+.1f}%)')\n",
    "# Plot comparison\n",
    "fig,(ax1,ax2)=plt.subplots(1,2,figsize=(16,7))\n",
    "r_nn=np.array([depot]+list(coords[route])+[depot])\n",
    "r_opt=np.array([depot]+list(coords[opt_route])+[depot])\n",
    "ax1.plot(r_nn[:,0],r_nn[:,1],'o-',color='#2196F3',lw=2); ax1.set_title(f'NN ({total:.0f})')\n",
    "ax2.plot(r_opt[:,0],r_opt[:,1],'o-',color='#4CAF50',lw=2); ax2.set_title(f'2-opt ({opt_dist:.0f})')\n",
    "for ax in [ax1,ax2]:\n",
    "    ax.scatter([depot[0]],[depot[1]],c='red',s=200,marker='*',zorder=5)\n",
    "plt.tight_layout(); plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed368faf",
   "metadata": {},
   "source": [
    "---\n",
    "*更多分析见 [案例文档](/docs/case-studies/operations/vehicle-routing-case/)*"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}