cuOpt 路由功能#

注意

有关功能和规格的详细信息，请访问cuOpt API 路由规范。

异构车队#

在车辆路径问题 (VRP) 中，企业客户可能拥有由不同车辆（例如卡车和摩托车）组成的车队。每种车辆类型可能具有不同的约束，例如行驶时间、时间窗口、起始和结束位置以及载货能力。因此，用户可以为 cuOpt 提供多个输入矩阵（每种车辆类型一个行驶时间矩阵）。容量值在容量输入数组中指示，其中数组的索引对应于车队中的每辆车。所有不同的车辆都需要在 vehicle_types 中共享。

多个输入矩阵#

成本矩阵需要是一个正方形矩阵，其中包含传递给 NVIDIA cuOpt 求解器的某种行驶指标。在旅行商问题 (TSP) 的许多变体中，这包括行驶时间、距离或其他业务成本。成本矩阵是一个正方形矩阵，表示问题中每两个位置对之间旅行的成本。cost_matrix_data 可以容纳任何成本矩阵；成本可以是行驶时间、行驶距离、美元成本或成本的任何加权函数。如果成本矩阵不使用行驶时间，则应使用 travel_time_matrix_data，以便成本矩阵用于优化，而行驶时间矩阵用于满足时间约束。

在异构车队的情况下，不同的车辆类型可能具有不同的行驶时间。为了支持这一点，cost_matrix_data 和 travel_time_matrix_data 都可以容纳多个矩阵，以便每种车辆类型都有一个对应的矩阵。

多个输入路径点图#

与成本矩阵类似，距离和时间详细信息可以通过路径点图经由 cost_waypoint_graph_data 或 travel_time_waypoint_graph_data 提供。每种车辆类型将有其自己的成本和时间路径点图数据。

车辆时间窗口#

时间窗口表示车辆的运营时间。每辆车有一个时间窗口。此数据表示为整数。原始数据可能包括世界协调时间 (UTC) 日期/时间格式或字符串格式，必须将其转换为浮点值。（示例：上午 9:00 - 下午 6:00 转换为 24 小时周期内从凌晨 12:00 开始的分钟数，将为 [540, 1080]）。提供给 cuOpt 求解器的所有时间/成本单位应为相同单位。如果行驶时间成本矩阵包括位置之间以分钟为单位的行驶时间，则时间窗口也必须是分钟的整数表示。车辆时间窗口使用 fleet_data 下的 update_solver_mode 设置。

注意

所有时间窗口都应 >= 0，并且所有时间窗口均为 int32 类型。因此，支持的时间窗口范围将为 [0, 2^31-1]；这在 UTC 中转换为 [1970 年 1 月 1 日，00:00:00，2038 年 1 月 19 日，03:14:07]。

车辆休息#

除了车辆时间窗口外，车辆也可能有休息时间窗口。如果时间窗口表示驾驶员一天的工作时间，则休息时间窗口可能表示他们一天中的午休时间。整数表示与时间窗口一致。如果原始输入数据采用 UTC 时间戳格式，如果车辆的工作班次为上午 9:00 - 下午 6:00，则在 24 小时周期内，这等效于 540 - 1080。如果车辆的休息时间为下午 1:00 - 1:30，则休息时间窗口将为 [780, 810]。

除了时间外，用户还可以使用 vehicle_break_locations 指定可能的休息位置。

休息有两种类型，

  • 统一休息 - 车队中的每位驾驶员可以享受相同数量的休息时间。例如，一个班次 3 次休息（咖啡、午餐、咖啡）。这通过 vehicle_break_time_windows 和 vehicle_break_durations 实现。

  • 非统一休息 - 每位驾驶员可能需要采取不同的休息时间，可能是有人请病假，或者某些工人由于工作时间过长而需要更多休息时间。这通过 vehicle_breaks 完成。请参阅 示例 以获取更多信息。

一次只能使用一种类型的休息。

奖金收集#

task_data 中的 prizes 字段可用于为每个任务设置奖金。这支持所有任务都不可行的情况，或者服务所有任务不如放弃一些低奖金任务并服务其余任务有利可图的情况，并且用户要求在尝试其他任务之前考虑具有最高奖金的任务。如果服务客户的成本相对于服务客户的奖金太高，求解器将放弃该客户以提高总体成本。

如果主要目标是尽可能多地服务客户，则建议设置非常高的奖金。奖金收集将是放弃不可行任务和优先考虑具有更高奖金的任务的有效方法。主要区别在于目标函数，总奖金将被否定，而不是添加到总成本中。如果与奖金目标对应的目标权重设置为零，则奖金收集机制将被禁用。

自定义目标#

求解器的默认目标是优化使用成本矩阵计算的成本。但是，可以使用 objectives 字段设置其他一些目标。最终目标是所有指定目标的线性组合。指定的目标权重用作系数。默认情况下，cuOpt 求解器首先优化车辆计数，然后优化最终目标。除了 travel_time_matrix_data 之外，客户还可以使用 cost_matrix_data 设置多个成本矩阵。

放弃首段/末段行程#

通过放弃首段或末段行程，cuOpt 求解器不考虑车辆从车场到第一站的行程，或从最后一站返回车场的行程。使用这些参数，路线仅包括任务位置之间的行驶成本和时间。在驾驶员可能从其家庭住址而不是指定的车场开始工作班次的情况下，往返车场的行程是不必要的。

取货和交付#

一些用例可能包括从一个地点取货并将其交付到另一个地点。每个订单有两个对应的地点：一个用于取货，一个用于交付。同一辆车必须处理同一订单的取货和交付，并且订单的取货必须在交付之前发生。

精确的时间限制#

建议使用默认时间限制（即 10 + number_of_nodes/6）秒。如果时间限制设置为 X 秒，即使解决方案质量没有提高，求解器也会继续运行 X 秒。

注意

time_limit 设置是求解器实际用于解决问题的时间，不包括 网络传输、etl、输入验证、实例正忙于处理其他请求 和其他一些开销，这些开销相对较小。因此，请求到响应的往返总时间将为 solve_time + overhead。

车辆起始和结束位置#

车队中的每辆车都必须在路径点图或成本矩阵中给定的位置集中具有起始和结束位置。这些位置必须包含在成本矩阵或路径点图中。在许多用例中，这些起始和结束位置是车场或配送中心，这样车辆在早上从其分配的车场出发，完成所有分配的任务，然后在工作日结束时返回分配的车场。起始和结束位置不一定是同一位置（例如，车辆在早上从车场 1 出发，但在晚上返回车场 2）。

车辆数量的最小约束#

默认情况下，cuOpt 尝试最大限度地减少解决方案中使用的车辆数量，并将车队规模视为上限。车队规模从 vehicle_locations 推断得出。如果给定的输入车队有 20 辆可用车辆，但只需要 10 辆即可完成所有任务，则 cuOpt 解决方案将仅包括 10 辆车辆。要设置使用的车辆数量的下限，请在 fleet_data 中设置 min_vehicles。如果已知要使用的确切车辆数量，则指定所需规模的车队并将 min_vehicles 设置为等于车队规模将保证所有车辆都将被使用。

每辆车的最大约束#

车辆可能对每辆车可以行驶的最大距离或车辆可以运行的最大时间有限制。这意味着，即使车辆的时间窗口为上午 9 点至晚上 9 点，并且驾驶员可能可以在这 12 个小时内工作，我们也可以添加一个约束，即工作日不得超过这 12 个小时中的 8 个小时。

每辆车的固定成本#

车辆可能具有不同的相关固定成本。这有助于在可以使用两辆或更多辆成本较低的车辆来避免使用一辆成本较高的车辆的情况下。这将取决于目标函数。

将订单映射到车辆，以及将车辆映射到订单#

默认情况下，cuOpt 将根据最优路线将订单分配给车辆。但是，在某些情况下，将特定订单分配给特定车辆，或者相反，将特定车辆分配给特定订单是有意义的。

  • order_vehicle_match 允许将订单分配给车辆。例如，食品配送中心希望向城市周围的杂货店发货。假设车队由冷藏卡车（可以运输冷冻食品）和货车（不能运输冷冻食品）组成。在这种情况下，我们希望将包含冷冻食品的订单分配给卡车（而不仅仅是任何车辆）。

  • vehicle_order_match 允许将车辆分配给订单。例如，一家维护公司可能拥有许多可以完成各种任务的员工（技术人员）。当客户请求服务时，公司可以派遣任何可用的技术人员来满足他们的请求。但是，如果客户请求的服务只有一名技术人员可以完成，则可以将这些订单分配给这位技术人员。

在需要将一组订单分配给一组车辆的情况下，只要映射正确完成，就可以使用任一约束。

在本页中