linear programing for mini project.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "47966861",
   "metadata": {},
   "source": [
    "# 1.Tổng quan People and Parcel Share a Ride\n",
    "- N người, đánh số i từ [1,N]. Đón người i ở điểm i, trả ở điểm i+N+M. Nếu đón người i phải có đường đi trực tiếp từ i->i+N+M\n",
    "- M hàng, đánh số j từ [1,M]. Nhận hàng j ở điểm j+N, trả ở điểm j+2N+M. Nếu nhận hàng j thì trong đường đi về sau phải đi qua j+2N+M.\n",
    "- K xe, đánh số k từ [0,K-1]. Khởi hành ở 0, kết thúc sẽ ở 0. \n",
    "- parcel_quantities: danh sách số lượng hàng mỗi loại.\n",
    "- taxi_capacities: danh sách trọng tải hàng mỗi xe.\n",
    "- Yêu cầu tối ưu: min(max(route length of each taxi))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "853bfb87",
   "metadata": {},
   "source": [
    "# 2. Thiết lập nhập dữ liệu N,M,K,PQ,TC"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "6f874748",
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.linear_solver import pywraplp\n",
    "\n",
    "def read_input():\n",
    "    #\n",
    "    N, M, K = map(int, input().split())\n",
    "    \n",
    "    # nhập vào danh sách số lượng hàng mỗi loại\n",
    "    parcel_quantities = list(map(int, input().split()))\n",
    "    \n",
    "    # Read taxi capacities  \n",
    "    taxi_capacities = list(map(int, input().split()))\n",
    "    \n",
    "    # Read distance matrix\n",
    "    distance_matrix = []\n",
    "    for _ in range(2 * N + 2 * M + 1):\n",
    "        row = list(map(int, input().split()))\n",
    "        distance_matrix.append(row)\n",
    "        \n",
    "    return N, M, K, parcel_quantities, taxi_capacities, distance_matrix\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "376b3a36",
   "metadata": {},
   "source": [
    "# 3. Thiết lập biến quyết định\n",
    "- X[i,j,k]: i thuộc [0,2N+2M],: xe k có đi từ i đến j. Với 0 là điểm depot\n",
    "- Y[i,k]: i thuộc [0,N-1]: xe k có chở người i, Đón khách i ở i+1, trả khách i ở i+N+1+M\n",
    "- Z[i,k]: i thuộc [0,M-1]: Xe k có chở hàng loại i, Đón hàng i ở i+1+N, trả hàng ở i + 1 + N + N + M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "2597ba9f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_variables(solver, N, M, K):\n",
    "   \n",
    "    # X[i,j,k] = 1 if taxi k travels from i to j\n",
    "    X = {}\n",
    "    for i in range(0, 2 * N + 2 * M + 1):\n",
    "        for j in range(0, 2 * N + 2 * M + 1):\n",
    "            for k in range(K):\n",
    "                X[i, j, k] = solver.BoolVar(f'X[{i},{j},{k}]')\n",
    "    \n",
    "    # Y[i,k] = 1 if passenger i is served by taxi k\n",
    "    Y = {}\n",
    "    for i in range(N):\n",
    "        for k in range(K):\n",
    "            Y[i, k] = solver.BoolVar(f'Y[{i},{k}]')\n",
    "    \n",
    "    # Z[i,k] = 1 if parcel i is carried by taxi k\n",
    "    Z = {}\n",
    "    for i in range(M):\n",
    "        for k in range(K):\n",
    "            Z[i, k] = solver.BoolVar(f'Z[{i},{k}]')\n",
    "            \n",
    "    # T[k] = total distance traveled by taxi k\n",
    "    T = [solver.NumVar(0, solver.infinity(), f'T[{k}]') for k in range(K)]\n",
    "    \n",
    "    # D = maximum distance among all taxis\n",
    "    D = solver.NumVar(0, solver.infinity(), 'D')\n",
    "    \n",
    "    return X, Y, Z, T, D"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12234a99",
   "metadata": {},
   "source": [
    "# Thiết lập ràng buộc\n",
    "- mỗi hành khách phải được phục vụ bởi chỉ 1 taxi: tổng của Y[i,k] cho k chạy = 1\n",
    "- nếu Y[i,k]==1 thì X[i+1, i + 1 + N + M, k] == Y[i, k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "6e5537ee",
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_constraints(solver, N, M, K, X, Y, Z, T, D, parcel_quantities, taxi_capacities, distance_matrix):\n",
    "    # Maximum distance constraint\n",
    "    for k in range(K):\n",
    "        solver.Add(T[k] <= D)\n",
    "\n",
    "    # Each passenger must be served by exactly one taxi\n",
    "    for i in range(N):\n",
    "        solver.Add(sum(Y[i, k] for k in range(K)) == 1)\n",
    "        # Link passenger pickup and dropoff\n",
    "        for k in range(K):\n",
    "            solver.Add(X[i+1, i+1 + N + M, k] == Y[i, k])\n",
    "\n",
    "    # Taxi capacity constraints for parcels\n",
    "    for k in range(K):\n",
    "        solver.Add(sum(parcel_quantities[i] * Z[i, k] for i in range(M)) <= taxi_capacities[k])\n",
    "\n",
    "    # Each parcel must be carried by exactly one taxi\n",
    "    for i in range(M):\n",
    "        solver.Add(sum(Z[i, k] for k in range(K)) == 1)\n",
    "        # Link parcel pickup and delivery\n",
    "        for k in range(K):\n",
    "            solver.Add(sum(X[j, N+i+1, k] for j in range(2 * N + 2 * M + 1)) == Z[i, k])\n",
    "            solver.Add(sum(X[N + i + 1, j, k] for j in range(2 * N + 2 * M + 1)) == Z[i, k])\n",
    "            solver.Add(sum(X[j, 2*N + M + i + 1, k] for j in range(2 * N + 2 * M + 1)) == Z[i, k])\n",
    "            solver.Add(sum(X[2*N + M + i + 1,j, k] for j in range(2 * N + 2 * M + 1)) == Z[i, k])\n",
    "\n",
    "    # All taxis must start and end at depot\n",
    "    for k in range(K):\n",
    "        solver.Add(sum(X[0, j, k] for j in range(1, 2 * N + 2 * M + 1)) == 1)\n",
    "        solver.Add(sum(X[i, 0, k] for i in range(1, 2 * N + 2 * M + 1)) == 1)\n",
    "\n",
    "    # Flow conservation constraints\n",
    "    for k in range(K):\n",
    "        for j in range(2 * N + 2 * M + 1):\n",
    "            solver.Add(sum(X[i, j, k] for i in range(2 * N + 2 * M + 1) if i != j) ==\n",
    "                      sum(X[j, i, k] for i in range(2 * N + 2 * M + 1) if i != j))\n",
    "\n",
    "    # Calculate total distance for each taxi\n",
    "    for k in range(K):\n",
    "        solver.Add(T[k] == sum(distance_matrix[i][j] * X[i, j, k]\n",
    "                              for i in range(2 * N + 2 * M + 1)\n",
    "                              for j in range(2 * N + 2 * M + 1)))\n",
    "\n",
    "   # Ensure pickup before delivery for parcels (corrected logic)\n",
    "   \n",
    "\n",
    "    # Subtour elimination constraints using MTZ formulation\n",
    "    # Biến U[i] đại diện thứ tự thăm của node i (1 <= i <= 2 * N + 2 * M)\n",
    "    U = [solver.NumVar(0, 2 * N + 2 * M, f'U[{i}]') for i in range(1, 2 * N + 2 * M + 1)]\n",
    "\n",
    "    for k in range(K):\n",
    "        for i in range(1, 2 * N + 2 * M + 1):\n",
    "            for j in range(1, 2 * N + 2 * M + 1):\n",
    "                if i != j:\n",
    "                    solver.Add(U[i - 1] - U[j - 1] + (2 * N + 2 * M) * X[i, j, k] <= (2 * N + 2 * M - 1))\n",
    "\n",
    "\n",
    "    return solver\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "8d27ffee",
   "metadata": {},
   "outputs": [],
   "source": [
    "def extract_routes(X, K, N, M):\n",
    "    routes = []\n",
    "    for k in range(K):\n",
    "        route = []\n",
    "        current_point = 0  # Start at the depot\n",
    "        visited = set([0])  # Mark the depot as visited\n",
    "\n",
    "        while True:\n",
    "            found_next = False\n",
    "            for j in range(2 * N + 2 * M + 1):  # Check all nodes\n",
    "                if X[current_point, j, k].solution_value() > 0.5 and j not in visited:\n",
    "                    route.append(j)  # Add the next node to the route\n",
    "                    visited.add(j)  # Mark the node as visited\n",
    "                    current_point = j  # Move to the next node\n",
    "                    found_next = True\n",
    "                    break\n",
    "            if not found_next:\n",
    "                break  # No more nodes to visit, end the route\n",
    "        routes.append(route)\n",
    "    return routes\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c53b57e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_solution_matrix(X, K, N, M):\n",
    "    for k in range(K):\n",
    "        print(f\"Taxi {k}:\")\n",
    "        matrix = []\n",
    "        for i in range(2 * N + 2 * M + 1):\n",
    "            row = []\n",
    "            for j in range(2 * N + 2 * M + 1):\n",
    "                row.append(int(X[i, j, k].solution_value()))  # Convert solution value to int for clarity\n",
    "            matrix.append(row)\n",
    "        for row in matrix:\n",
    "            print(row)\n",
    "        print(\"\\n\")  # Separate matrices for each taxi\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "54bc26e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def main():\n",
    "    # Create solver\n",
    "    solver = pywraplp.Solver.CreateSolver('SCIP')\n",
    "    \n",
    "    N, M, K = map(int, input().split())\n",
    "    parcel_quantities = list(map(int, input().split()))\n",
    "    taxi_capacities = list(map(int, input().split()))\n",
    "    distance_matrix = []\n",
    "    for _ in range(2 * N + 2 * M + 1):\n",
    "        distance_matrix.append(list(map(int, input().split())))\n",
    "        \n",
    "        \n",
    "    for i in range(2*N+2*M+1):\n",
    "        distance_matrix[i][i] = 100\n",
    "    X, Y, Z, T, D = create_variables(solver, N, M, K)\n",
    "    \n",
    "    # Set objective: minimize maximum distance\n",
    "    solver.Minimize(D)\n",
    "    \n",
    "    # Add constraints\n",
    "    add_constraints(solver, N, M, K, X, Y, Z, T, D, parcel_quantities, taxi_capacities, distance_matrix)\n",
    "    \n",
    "    # Solve the problem\n",
    "    status = solver.Solve()\n",
    "    \n",
    "    # Output results\n",
    "    if status == pywraplp.Solver.OPTIMAL:\n",
    "        print(K)\n",
    "        routes = extract_routes(X, K, N, M)\n",
    "        for route in routes:\n",
    "            print(len(route) + 2)  # +2 for start and end depot\n",
    "            print(f\"0 {' '.join(map(str, route))} 0\")\n",
    "        print_solution_matrix(X, K, N, M)     \n",
    "    else:\n",
    "        print('No optimal solution found.')\n",
    "\n",
    "main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cbd9da25",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0c2757a0",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}