能否用Google ComputeRoutes API解决多车辆VRP问题？

我想用Google ComputeRoutes API（支持Node.js）解决车辆路径规划问题（VRP）。目前已经实现了单车辆的最优路径规划，但现在需要用多车辆完成多个目的地的配送任务，请问这可行吗？

现有单车辆实现代码 #

const data = {
  origin: locationOrigin,
  destination: locationOrigin,
  intermediates: [] as WayPoint[],
  travelMode: "DRIVE",
  routingPreference: "TRAFFIC_AWARE",
  computeAlternativeRoutes: false,
  optimizeWaypointOrder: true,
};

way = {} as Way;
orders.forEach((order: any) => {
  const waypoint = {
    placeId: order.order.address.placeId,
  };
  intermediates.push(waypoint);
});

data.intermediates = intermediates;

console.log("data ", data);

await doRequest(data, "routes")
  .then((data: any) => {
    console.log("yeei ", data);
    console.log(
      "optimizedIntermediateWaypointIndex ",
      data.routes.optimizedIntermediateWaypointIndex
    );
    way = createWaysWithWaypoints(
      data.routes[0],
      orders,
      riders[0],
      data.routes[0].optimizedIntermediateWaypointIndex,
      wayscount
    );
    ways.push(way);
    console.log("ways ", ways);
  })
  .catch((error: any) => {
    errorMessage = error;
    console.log(`Error message: ${error.message}`);
    console.log(`Error code: ${error.code}`);

    if (error.response) {
      console.log(`Response status: ${error.response.status}`);
      console.log(
        `Response data: ${JSON.stringify(error.response.data)}`
      );
    }

    if (error.request) {
      console.log(`Request method: ${error.request.method}`);
      console.log(`Request path: ${error.request.path}`);
    }

    return {
      statusCode: 400,
      headers: {
        "Access-Control-Allow-Headers": "*",
        "Access-Control-Allow-Origin": "*",
        "Access-Control-Allow-Methods": "*",
      },
      body: JSON.stringify(error.message),
    };
  });

doRequest 请求函数代码 #

function doRequest(data: any, opt: string) {
  let result = "";
  return new Promise(function (resolve, reject) {
    var options = {
      host: "routes.googleapis.com",
      path: "/directions/v2:computeRoutes",
      method: "POST",
      headers: {
        "Content-Type": "application/json",
        "X-Goog-Api-Key": "xyz",
        "X-Goog-FieldMask":
          "routes.optimizedIntermediateWaypointIndex,routes.duration,routes.distanceMeters,routes.polyline.encodedPolyline,routes.routeLabels,routes.legs.distanceMeters,routes.legs.duration",
      },
    };

    let post_req = http.request(options, function (res: any) {
      let body = "";
      res.on("data", function (chunk: any) {
        body += chunk;
        console.log("Response: ", body);
      });

      res.on("end", () => {
        console.log("body ", JSON.parse(body));
        resolve(JSON.parse(body));
      });

      res.on("error", function (e: any) {
        console.log("Got error: " + e.message);
      });
    });
    post_req.write(JSON.stringify(data));
    post_req.end();
  });
}

回答 #

可行，但Google ComputeRoutes API本身不直接支持多车辆的VRP任务分配，它仅能处理单车辆的路径优化（包括途经点排序）。要实现多车辆配送，你需要在自己的代码中完成「任务拆分-分配-单车辆路径规划」的流程，具体步骤如下：

1. 任务拆分与分配逻辑 #

你需要先把所有配送订单分配给不同的骑手/车辆，分配逻辑可以基于以下维度：

• 订单的地理位置聚类（比如把同一区域的订单分给同一辆车）
• 车辆的载重/容量限制
• 配送时间窗要求
• 总路径时长/距离的均衡性

2. 对每辆车单独调用ComputeRoutes #

分配完成后，对每个骑手的订单列表，复用你现有的单车辆路径规划代码，循环调用ComputeRoutes API。示例修改代码如下：

// 假设已完成订单分配，ordersByRider是按骑手分组的订单数组，结构为[rider1Orders, rider2Orders, ...]
let wayscount = 0;
const ways: Way[] = [];

for (const [riderIndex, riderOrders] of ordersByRider.entries()) {
  const rider = riders[riderIndex];
  const intermediates: WayPoint[] = [];
  
  riderOrders.forEach((order: any) => {
    intermediates.push({ placeId: order.order.address.placeId });
  });

  const data = {
    origin: locationOrigin, // 可改为骑手的实际出发位置
    destination: locationOrigin, // 可改为骑手的实际结束位置
    intermediates,
    travelMode: "DRIVE",
    routingPreference: "TRAFFIC_AWARE",
    computeAlternativeRoutes: false,
    optimizeWaypointOrder: true,
  };

  try {
    const routeData = await doRequest(data, "routes");
    console.log(`骑手${rider.id}的路径规划结果:`, routeData);
    
    const way = createWaysWithWaypoints(
      routeData.routes[0],
      riderOrders,
      rider,
      routeData.routes[0].optimizedIntermediateWaypointIndex,
      wayscount
    );
    ways.push(way);
    wayscount++;
  } catch (error: any) {
    console.log(`骑手${rider.id}路径规划失败:`, error.message);
    // 复用你现有代码中的错误处理逻辑
  }
}

3. 优化分配逻辑（可选） #

如果需要更优的全局分配结果，你可以引入简单的启发式算法（比如贪心算法），或者结合坐标聚类（用Geocoding API获取订单精确坐标）来提升分配合理性。

注意事项 #

• API配额：多车辆场景会增加API调用次数，需注意Google Cloud的配额限制，避免触发限流。
• 字段掩码：确保X-Goog-FieldMask包含所有你需要的路径字段，避免数据缺失。

内容的提问来源于stack exchange，提问作者Julian