{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 电话叫车问题 (DARP)\n", "\n", "**类别：** 路径优化\n", "\n", "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n", "\n", "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/dial-a-ride-problem-darp)。\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 问题描述\n", "\n", "**在电话叫车问题 (DARP)** 中,一组车辆必须将客户从一个地点运送到另一个地点。车辆从一个共同的配送中心出发并最终返回配送中心,且具有最大载客能力。客户必须被恰好一辆车接送。客户在其接送地点均需要装车时间,且其接送时间必须落在给定的时间窗口内。每个客户接送时间之间的延迟不得超过某个上限。目标是为每辆卡车分配一个客户序列,同时最小化总延迟和总行驶距离。\n", "\n", "### 学到的要点\n", "\n", "- 添加 **列表决策变量** 来建模车辆的客户访问序列\n", "- 使用 **递归 lambda 函数** 定义数组,计算车辆载客量和节点离开时间\n", "- 添加 **多个目标**,并将延迟建模为第一优先级的软约束\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 数据\n", "\n", "我们提供来自 [Chassaing 等人数据集](https://perso.isima.fr/~lacomme/Maxime/Real_life_instances/Real_life_instances.php) 的电话叫车问题 (DARP) 实例。每个数据文件都是一个 JSON 文件,包含:\n", "\n", "- 车辆数量\n", "- 节点数量\n", "- 最大行驶时间(对所有客户相同)\n", "- 车辆载客能力\n", "- 用于计算两个不同节点之间行驶时间的缩放因子\n", "- 车辆的速度\n", "- 客户数量\n", "- 每对节点之间的距离矩阵\n", "- 关于配送中心的信息:标识符、装车时间、客户数量、路线开始时间和最迟结束时间\n", "- 关于每位客户的信息:乘客数量,以及接送点和送达点的索引、时间窗口、装卸时间与最大行驶时间\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 建模思路\n", "\n", "电话叫车问题 (DARP) 的 OptAgent 模型使用列表决策变量来表示每辆车访问的节点序列,并使用浮点决策变量表示车辆在配送中心的出发时间以及各节点的额外等待时间。对所有路线添加 `partition` 约束,确保每个接送或送达节点恰好被访问一次。\n", "\n", "车辆载客量和节点离开时间都通过递归数组计算。对于每个客户,使用 `find` 找到接送点和送达点所属的车辆,使用 `index` 获取它们在路线中的位置,从而约束同车服务且接送先于送达。\n", "\n", "模型按声明顺序进行字典序多目标优化:\n", "\n", "1. 最小化所有路线的节点迟到与返回配送中心迟到\n", "2. 最小化超过客户最大乘车时间的总时长\n", "3. 最小化缩放后的总行驶距离\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Python 实现\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import json\n", "from pathlib import Path\n", "\n", "from optagent import OptModel, solve\n", "\n", "\n", "\n", "\n", "def read_input_darp(instance_file):\n", " instance = json.loads(Path(instance_file).read_text(encoding=\"utf-8\"))\n", " nb_clients = instance[\"nbClients\"]\n", " nb_nodes = instance[\"nbNodes\"]\n", " quantities = [0] * nb_nodes\n", " starts = [0.0] * nb_nodes\n", " ends = [0.0] * nb_nodes\n", " loading_times = [0.0] * nb_nodes\n", " max_travel_times = [0.0] * nb_nodes\n", "\n", " for client_index, client in enumerate(instance[\"clients\"]):\n", " delivery_index = client_index + nb_clients\n", " quantities[client_index] = client[\"nbClients\"]\n", " quantities[delivery_index] = -client[\"nbClients\"]\n", " for node_index, visit in (\n", " (client_index, client[\"pickup\"]),\n", " (delivery_index, client[\"delivery\"]),\n", " ):\n", " starts[node_index] = visit[\"start\"]\n", " ends[node_index] = visit[\"end\"]\n", " loading_times[node_index] = visit[\"loadingTime\"]\n", " max_travel_times[node_index] = visit[\"maxTravelTime\"]\n", "\n", " distances = instance[\"distanceMatrix\"]\n", " factor = 1.0 / (instance[\"scale\"] * instance[\"speed\"])\n", " distance_depot = [distances[0][node + 1] for node in range(nb_nodes)]\n", " time_depot = [distance * factor for distance in distance_depot]\n", " distance_matrix = [\n", " [distances[i + 1][j + 1] for j in range(nb_nodes)]\n", " for i in range(nb_nodes)\n", " ]\n", " time_matrix = [\n", " [distance * factor for distance in row] for row in distance_matrix\n", " ]\n", " return {\n", " \"nb_clients\": nb_clients,\n", " \"nb_nodes\": nb_nodes,\n", " \"nb_vehicles\": instance[\"nbVehicles\"],\n", " \"depot_tw_end\": instance[\"depot\"][\"twEnd\"],\n", " \"capacity\": instance[\"capacity\"],\n", " \"scale\": instance[\"scale\"],\n", " \"quantities\": quantities,\n", " \"starts\": starts,\n", " \"ends\": ends,\n", " \"loading_times\": loading_times,\n", " \"max_travel_times\": max_travel_times,\n", " \"distance_depot\": distance_depot,\n", " \"time_depot\": time_depot,\n", " \"distance_matrix\": distance_matrix,\n", " \"time_matrix\": time_matrix,\n", " }\n", "\n", "\n", "def build_darp_model(data):\n", " nb_clients = data[\"nb_clients\"]\n", " nb_nodes = data[\"nb_nodes\"]\n", " nb_vehicles = data[\"nb_vehicles\"]\n", " depot_tw_end = data[\"depot_tw_end\"]\n", " model = OptModel()\n", " routes = [\n", " model.list(\n", " nb_nodes,\n", " default=[\n", " node\n", " for client in range(nb_clients)\n", " if client % nb_vehicles == vehicle\n", " for node in (client, client + nb_clients)\n", " ],\n", " )\n", " for vehicle in range(nb_vehicles)\n", " ]\n", " depot_starts = [\n", " model.float(0, depot_tw_end)\n", " for vehicle in range(nb_vehicles)\n", " ]\n", " waiting = [\n", " model.float(0, depot_tw_end)\n", " for node in range(nb_nodes)\n", " ]\n", " model.constraint(model.partition(routes))\n", "\n", " # 注意：quantities 已经提前记录好了每个节点会让车辆载客量变化多少\n", " quantities = model.array(data[\"quantities\"])\n", " starts = model.array(data[\"starts\"])\n", " ends = model.array(data[\"ends\"])\n", " loading_times = model.array(data[\"loading_times\"])\n", " max_travel_times = model.array(data[\"max_travel_times\"])\n", " distance_depot = model.array(data[\"distance_depot\"])\n", " time_depot = model.array(data[\"time_depot\"])\n", " distance_matrix = model.array(data[\"distance_matrix\"])\n", " time_matrix = model.array(data[\"time_matrix\"])\n", " waiting_array = model.array(waiting)\n", " route_times = []\n", " route_lateness = []\n", " home_lateness = []\n", " route_distances = []\n", "\n", " for vehicle, route in enumerate(routes):\n", " count = route.count()\n", " positions = model.range(0, count)\n", " \n", " # 容量限制\n", " route_quantities = model.array(\n", " positions,\n", " model.lambda_function(\n", " lambda i, previous: previous + quantities[route[i]]\n", " ),\n", " 0,\n", " )\n", " model.constraint(\n", " model.and_(\n", " positions,\n", " model.lambda_function(\n", " lambda i: route_quantities[i] <= data[\"capacity\"]\n", " ),\n", " ),\n", " )\n", "\n", " # 递推进行节点时间计算：max(Ei​,Ai​)+Wi​+Li​, 其中 Ei​ 是时间窗开始，Ai​ 是实际到达时间，Wi​ 是额外等待，Li​ 是装卸/服务时间。\n", " route_time = model.array(\n", " positions,\n", " model.lambda_function(\n", " lambda i, previous: model.max(\n", " starts[route[i]],\n", " model.iif(\n", " i == 0,\n", " depot_starts[vehicle] + time_depot[route[i]],\n", " previous + time_matrix[route[i - 1], route[i]],\n", " ),\n", " )\n", " + waiting_array[route[i]]\n", " + loading_times[route[i]]\n", " ),\n", " 0,\n", " )\n", " route_times.append(route_time)\n", "\n", " route_lateness.append(\n", " model.sum(\n", " positions,\n", " model.lambda_function(\n", " lambda i: model.max(\n", " 0,\n", " route_time[i]\n", " - loading_times[route[i]]\n", " - ends[route[i]],\n", " )\n", " ),\n", " )\n", " )\n", " home_lateness.append(\n", " model.iif(\n", " count > 0,\n", " model.max(\n", " 0,\n", " route_time[count - 1]\n", " + time_depot[route[count - 1]]\n", " - depot_tw_end,\n", " ),\n", " 0,\n", " )\n", " )\n", " route_distances.append(\n", " model.sum(\n", " model.range(1, count),\n", " model.lambda_function(\n", " lambda i: distance_matrix[route[i - 1], route[i]]\n", " ),\n", " )\n", " + model.iif(\n", " count > 0,\n", " distance_depot[route[0]] + distance_depot[route[count - 1]],\n", " 0,\n", " )\n", " )\n", "\n", " routes_array = model.array(routes)\n", " route_times_array = model.array(route_times)\n", " client_lateness = []\n", " for client in range(nb_clients):\n", " # 保证“同车接送，而且先接后送”\n", " pickup_vehicle = model.find(routes_array, client)\n", " delivery_node = client + nb_clients\n", " delivery_vehicle = model.find(routes_array, delivery_node)\n", " # 1）同一个客户必须由同一辆车接送\n", " model.constraint(\n", " pickup_vehicle == delivery_vehicle,\n", " )\n", " pickup_route = routes_array[pickup_vehicle]\n", " delivery_route = routes_array[delivery_vehicle]\n", " pickup_index = model.index(pickup_route, client)\n", " delivery_index = model.index(delivery_route, delivery_node)\n", " # 2）必须先 pickup，再 delivery\n", " model.constraint(\n", " pickup_index < delivery_index,\n", " )\n", " pickup_times = route_times_array[pickup_vehicle]\n", " delivery_times = route_times_array[delivery_vehicle]\n", " pickup_time = pickup_times[pickup_index]\n", " delivery_time = (\n", " delivery_times[delivery_index]\n", " - loading_times[delivery_node]\n", " )\n", " client_lateness.append(\n", " model.max(\n", " delivery_time - pickup_time - max_travel_times[client], 0\n", " )\n", " )\n", "\n", " total_lateness = model.sum(route_lateness + home_lateness)\n", " total_client_lateness = model.sum(client_lateness)\n", " total_distance = model.sum(route_distances) / data[\"scale\"]\n", " model.minimize(total_lateness)\n", " model.minimize(total_client_lateness)\n", " model.minimize(total_distance)\n", "\n", " # 注意：在当前建模下，延后 depot 出发不会改善当前三个目标\n", " expressions = {\n", " \"total_lateness\": total_lateness,\n", " \"total_client_lateness\": total_client_lateness,\n", " \"total_distance\": total_distance,\n", " **{f\"route_{i}\": route for i, route in enumerate(routes)},\n", " **{f\"depot_start_{i}\": start for i, start in enumerate(depot_starts)},\n", " **{f\"waiting_{i}\": value for i, value in enumerate(waiting)},\n", " }\n", " return model, expressions\n", "\n", "\n", "def main(instance_file, output_file=None, time_limit=20):\n", " data = read_input_darp(instance_file)\n", " model, expressions = build_darp_model(data)\n", " solution = solve(model, time_limit_s=float(time_limit))\n", " values = {name: expression.value for name, expression in expressions.items()}\n", " lines = [\n", " f\"Total route lateness = {values['total_lateness']}; \"\n", " f\"Total client lateness = {values['total_client_lateness']}; \"\n", " f\"Total distance = {values['total_distance']:.2f}; \"\n", " f\"Status = {solution.feasible}\"\n", " ]\n", " for vehicle in range(data[\"nb_vehicles\"]):\n", " visits = \", \".join(\n", " f\"{node} ({values[f'waiting_{node}']:.2f})\"\n", " for node in values[f\"route_{vehicle}\"]\n", " )\n", " lines.append(\n", " f\"Vehicle {vehicle + 1} ({values[f'depot_start_{vehicle}']:.2f}): \"\n", " f\"{visits}\"\n", " )\n", " result_text = \"\\n\".join(lines)\n", " print(result_text)\n", " if output_file is not None:\n", " Path(output_file).write_text(result_text + \"\\n\", encoding=\"utf-8\")\n", " return solution\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 本地运行\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "INSTANCE_DIR = Path.cwd() / \"instances\"\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "solution = main(INSTANCE_DIR / \"a5-40.json\", time_limit=10)\n" ] }, { "cell_type": "code", "execution_count": null, "id": "3b7ffdc1", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": ".venv", "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.14.6" } }, "nbformat": 4, "nbformat_minor": 5 }