⚡

车辆路径求解器Skill vehicle-routing-solver

车辆路径求解器是一个专门用于物流优化的AI工具，能够解决复杂的车辆路径规划问题。该技能支持多种约束条件，包括容量限制、时间窗口、多仓库管理和取送货场景。通过先进的算法优化配送路线，降低运输成本，提高物流效率。主要功能包括CVRP建模、VRPTW处理、多仓库路径优化、实时路线调整和可视化地图生成。适用于物流公司、电商配送、外卖平台等需要高效路径规划的行业。 关键词：车辆路径规划，物流优化，VRP求解器，配送路线优化，时间窗口约束，多仓库管理，取送货问题，运输调度，路径可视化，OR-Tools，运筹学，智能物流

运输调度 1 次安装 5 次浏览 更新于 2/25/2026

name: vehicle-routing-solver description: 用于物流优化的车辆路径问题求解器，支持时间窗口、容量约束和多仓库场景。 allowed-tools: Bash(*) Read Write Edit Glob Grep WebFetch metadata: author: babysitter-sdk version: “1.0.0” category: operations-research backlog-id: SK-IE-004

车辆路径求解器

您是车辆路径求解器 - 一个专门解决车辆路径问题的技能，包括容量约束、时间窗口、多仓库以及取送货场景。

概述

该技能支持AI驱动的车辆路径规划，包括：

  • CVRP（带容量约束的VRP）建模
  • VRPTW（带时间窗口的VRP）处理
  • 多仓库路径优化
  • 取送货问题求解
  • 路径可视化和地图绘制
  • 实时路径调整
  • 司机分配优化

前提条件

  • Python 3.8+ 并安装OR-Tools
  • 地理数据处理库
  • 地图API访问（可选）

能力

1. 带容量约束的VRP（CVRP）

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def solve_cvrp(distance_matrix, demands, vehicle_capacities, depot=0):
    """
    求解带容量约束的车辆路径问题
    """
    manager = pywrapcp.RoutingIndexManager(
        len(distance_matrix), len(vehicle_capacities), depot
    )
    routing = pywrapcp.RoutingModel(manager)

    # 距离回调函数
    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # 容量约束
    def demand_callback(from_index):
        from_node = manager.IndexToNode(from_index)
        return demands[from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # 空余容量
        vehicle_capacities,
        True,  # 从零开始累积
        'Capacity'
    )

    # 求解
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    search_parameters.time_limit.seconds = 30

    solution = routing.SolveWithParameters(search_parameters)
    return extract_routes(manager, routing, solution)

2. 带时间窗口的VRP（VRPTW）

def solve_vrptw(distance_matrix, time_matrix, time_windows,
                demands, vehicle_capacities, depot=0):
    """
    求解带时间窗口的车辆路径问题
    """
    manager = pywrapcp.RoutingIndexManager(
        len(distance_matrix), len(vehicle_capacities), depot
    )
    routing = pywrapcp.RoutingModel(manager)

    # 距离回调函数
    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # 带时间窗口的时间维度
    def time_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return time_matrix[from_node][to_node]

    time_callback_index = routing.RegisterTransitCallback(time_callback)

    routing.AddDimension(
        time_callback_index,
        30,  # 允许等待时间
        480,  # 每辆车最大时间（8小时）
        False,
        'Time'
    )

    time_dimension = routing.GetDimensionOrDie('Time')

    # 添加时间窗口约束
    for location_idx, (early, late) in enumerate(time_windows):
        if location_idx == depot:
            continue
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(early, late)

    # 最小化总时间
    for i in range(len(vehicle_capacities)):
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.Start(i))
        )
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.End(i))
        )

    # 求解
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )

    solution = routing.SolveWithParameters(search_parameters)
    return extract_routes_with_times(manager, routing, solution, time_dimension)

3. 多仓库VRP

def solve_multi_depot_vrp(distance_matrix, demands, depots,
                          vehicles_per_depot, vehicle_capacity):
    """
    求解多仓库车辆路径问题
    """
    num_vehicles = sum(vehicles_per_depot)

    # 为每辆车创建起点和终点索引
    starts = []
    ends = []
    for depot_idx, depot in enumerate(depots):
        for _ in range(vehicles_per_depot[depot_idx]):
            starts.append(depot)
            ends.append(depot)

    manager = pywrapcp.RoutingIndexManager(
        len(distance_matrix), num_vehicles, starts, ends
    )
    routing = pywrapcp.RoutingModel(manager)

    # ... 添加回调函数和约束

    return routing

4. 取送货问题

def solve_pdp(distance_matrix, pickups_deliveries, vehicle_capacities):
    """
    求解取送货问题
    pickups_deliveries: (取货节点, 送货节点) 列表
    """
    manager = pywrapcp.RoutingIndexManager(
        len(distance_matrix), len(vehicle_capacities), 0
    )
    routing = pywrapcp.RoutingModel(manager)

    # 添加取送货约束
    for pickup, delivery in pickups_deliveries:
        pickup_index = manager.NodeToIndex(pickup)
        delivery_index = manager.NodeToIndex(delivery)
        routing.AddPickupAndDelivery(pickup_index, delivery_index)
        routing.solver().Add(
            routing.VehicleVar(pickup_index) ==
            routing.VehicleVar(delivery_index)
        )
        routing.solver().Add(
            routing.CumulVar(pickup_index, 'Distance') <=
            routing.CumulVar(delivery_index, 'Distance')
        )

    return routing

5. 路径可视化

def visualize_routes(routes, locations, output_file='routes.html'):
    """
    生成交互式路径地图
    """
    import folium

    # 创建以位置为中心的地图
    center_lat = sum(loc[0] for loc in locations) / len(locations)
    center_lon = sum(loc[1] for loc in locations) / len(locations)

    m = folium.Map(location=[center_lat, center_lon], zoom_start=12)

    colors = ['red', 'blue', 'green', 'purple', 'orange']

    for route_idx, route in enumerate(routes):
        color = colors[route_idx % len(colors)]

        # 添加路径线
        route_coords = [locations[node] for node in route]
        folium.PolyLine(route_coords, color=color, weight=3).add_to(m)

        # 添加标记
        for stop_idx, node in enumerate(route):
            folium.Marker(
                locations[node],
                popup=f"路线 {route_idx}, 站点 {stop_idx}",
                icon=folium.Icon(color=color)
            ).add_to(m)

    m.save(output_file)
    return output_file

流程集成

该技能与以下流程集成：

  • transportation-route-optimization.js
  • warehouse-layout-slotting-optimization.js

输出格式

{
  "problem_type": "VRPTW",
  "status": "optimal",
  "total_distance": 1523,
  "total_time": 420,
  "routes": [
    {
      "vehicle_id": 0,
      "route": [0, 3, 5, 2, 0],
      "distance": 450,
      "load": 85,
      "arrival_times": [0, 45, 90, 150, 200],
      "departure_times": [0, 55, 105, 165, 200]
    }
  ],
  "unserved_customers": [],
  "metrics": {
    "vehicle_utilization": 0.85,
    "time_window_violations": 0
  }
}

工具/库

库 描述 使用场景
OR-Tools 约束求解器 所有VRP变体
VROOM 开源工具 快速启发式算法
OpenRouteService 路径API 实际距离计算
Folium 可视化 路径地图

最佳实践

  1. 使用实际距离 - 考虑实际道路网络
  2. 考虑服务时间 - 装卸货持续时间
  3. 平衡路线 - 公平的工作量分配
  4. 处理不确定性 - 缓冲时间窗口
  5. 迭代求解 - 使用热启动
  6. 验证可行性 - 检查所有约束

约束

  • 遵守车辆容量限制
  • 尊重客户时间窗口
  • 考虑司机规定（休息时间、最大工作时长）
  • 记录所有路径规划假设