开源AGV调度系统OpenTCS中的路由器(router)详解

1. 引言

openTCS是一项著名的开源运输控制系统，我在之前的文章中对该系统也做了初步介绍：

• 开源AGV调度系统 OpenTCS 5.4 开发环境配置与编译运行
• 开源AGV调度系统OpenTCS中的任务分派器(dispatcher)详解
  

2. 路由器(router)

openTCS中默认的任务路由器（Default router）是openTCS内置的重要策略模块，当然也是允许用户自定义和替换的。
默认路由器会在行驶路线上找到从一点到另一点消耗成本最低的路线。通过使用Dijkstra算法的实现来实现。它考虑已经被锁定的路径，但不考虑其他车辆的位置或被假定的未来行为。因此它不会绕过速度较慢或停在路上的车辆。

2.1 代价计算函数（Cost functions）

可用于评估驾驶过程中路径的成本函数可以通过配置进行选择。以下成本函数/配置选项可用：
DISTANCE (default):路由成本等同于路径长度；
TRAVELTIME：路由成本的计算是以在路径上行驶的预期时间，即路径长度/车辆允许的最大速度；
EXPLICIT_PROPERTIES：路径上行驶车辆的路由成本通过以下两个带键的路径属性中获取 tcs:routingCostForward and tcs:routingCostReverse。
HOPS:模型中每条路径的路由成本为1，得到的路由代价最小路径/点被选中。

2.2 2.1 Routing groups

计算车辆的路径时，对工厂中的不同车辆以不同的方式处理是可以的，如果车辆有不同的特点并且实际上路径行驶有不同的最佳路线，那么这是可取的。
为了实现这一点，模型中的路径或所用的成本函数需要反映出来这种差异。默认情况下不会这样做，因为默认路由器为所有的车辆计算路径同样的方式，除非另有指示。
要让路由器知道它应该单独计算车辆的路由，可以将键tcs:routingGroup的属性设置为任意字符串。(具有相同值集的车辆共享相同的路由表，空字符串为所有车辆的默认值。)

2.1 默认的停车位置选择

当一辆小车被派往停车点时，默认选择最接近（依据路由）且未被占用的停车点。可以通过设置以下关键属性来给车辆分配固定的位置。

• tcs:preferredParkingPosition:模型中的点名。如果此停车点已被占用，则车辆选择附近距离最近的停车点代替。
• tcs:assignedParkingPosition:模型中的点名。如果此停车点已被占用，则车辆不会前往到其他停车点，而是保持原地不动。
  assignedParkingPosition优先级高于preferredParkingPosition。

2.2 可选停车位置属性

停车位置的优先级是可以明确的，车辆也可以按照一种新的停车序列进行重新停车操作。例如将车辆停放在运输订单频繁的第一目的地附近的位置。
要给停车点设置一个优先级，可以用tcs:parkingPositionPriority键设置一个属性在点上。该属性的值应为十进制整数，值越小，则会导致停车位的优先级更高。
1.3. Default recharging location selection

2.3 默认的充电位置选择

当车辆被派往充电位置时，默认选择最接近（依据路由）且未被占用的充电位置。也可通过为以下键设置属性来给车辆分配固定位置：

• preferredRechargeLocation：如果此充电位置已被占用，则选择附近距离最近的充电位置。
• assignedRechargeLocation：如果此充电位置已被选择，则车辆不会被派往到其他充电位置。
  assignedRechargeLocation优先级高于preferredRechargeLocation。

2.4 即时运输订单分配

系统除了根据默认的流程和规则分配运输订单外，还可以显式分配运输订单(即时)。运输订单的即时分配支持具有预期车辆的运输订单。在这样的情况下，运输订单及其预期车辆通常处于可能进行分配的状态，但在常规调度程序流中被某些过滤条件阻止，因此采取这种方法将会很有用。

Although the immediate assignment of transport orders bypasses some of the filter criteria in the regular dispatcher flow, it works only in specific situations. Regarding the transport order’s state:

尽管传输订单的即时分配绕过了常规调度流程中的一些过滤条件，但它只在特定情况下起作用。考虑运输订单的状态:

• 运输订单的状态必须是可指派的（DISPATCHABLE）。
• 运输订单不能是订单序列的一部分。
• 必须设置运输订单的预定车辆。

至于(预定)车辆的状态:

• 车辆的处理状态必须为IDLE。
• 车辆状态必须为IDLE或CHARGING。
• 车辆的集成级别必须是TO_BE_UTILIZED。
• 车辆必须被报告在已知位置。
• 车辆不得处理订单序列。

除了运输订单和预定车辆的各自状态之外，分派器可能还有其他特定的原因来拒绝即时分配。

3. 默认任务分派器的配置项

默认任务分派器提供以下配置项实现可配置.
defaultdispatcher.orderCandidatePriorities

• Type: Comma-separated list of strings 逗号分隔的字符串列表
• Trigger for changes to be applied: on application start 触发要应用的更改:在应用程序启动时
• Description: Keys by which to prioritize transport order candidates for assignment.
  Possible values:
• BY_AGE: Sort by transport order age, oldest first.
• BY_DEADLINE: Sort by transport order deadline, most urgent first.
• DEADLINE_AT_RISK_FIRST: Sort orders with deadlines at risk first.
• BY_COMPLETE_ROUTING_COSTS: Sort by complete routing costs, lowest first.
• BY_INITIAL_ROUTING_COSTS: Sort by routing costs for the first destination.
• BY_ORDER_NAME: Sort by transport order name, lexicographically.

defaultdispatcher.orderPriorities

• Type: Comma-separated list of strings
• Trigger for changes to be applied: on application start
• Description: Keys by which to prioritize transport orders for assignment.
  Possible values:
  BY_AGE: Sort by age, oldest first.
  BY_DEADLINE: Sort by deadline, most urgent first.
  DEADLINE_AT_RISK_FIRST: Sort orders with deadlines at risk first.
  BY_NAME: Sort by name, lexicographically.

defaultdispatcher.vehicleCandidatePriorities

• Type: Comma-separated list of strings
• Trigger for changes to be applied: on application start
• Description: Keys by which to prioritize vehicle candidates for assignment.
  Possible values:
  BY_ENERGY_LEVEL: Sort by energy level of the vehicle, highest first.
  IDLE_FIRST: Sort vehicles with state IDLE first.
  BY_COMPLETE_ROUTING_COSTS: Sort by complete routing costs, lowest first.
  BY_INITIAL_ROUTING_COSTS: Sort by routing costs for the first destination.
  BY_VEHICLE_NAME: Sort by vehicle name, lexicographically.

defaultdispatcher.vehiclePriorities

• Type: Comma-separated list of strings
• Trigger for changes to be applied: on application start
• Description: Keys by which to prioritize vehicles for assignment.
  Possible values:
  BY_ENERGY_LEVEL: Sort by energy level, highest first.
  IDLE_FIRST: Sort vehicles with state IDLE first.
  BY_NAME: Sort by name, lexicographically.

defaultdispatcher.deadlineAtRiskPeriod
Type: Integer
Trigger for changes to be applied: on application start
Description: The time window (in ms) before its deadline in which an order becomes urgent.

defaultdispatcher.assignRedundantOrders

• Type: Boolean
• Trigger for changes to be applied: instantly
• Description: Whether orders to the current position with no operation should be assigned.

defaultdispatcher.dismissUnroutableTransportOrders

• Type: Boolean
• Trigger for changes to be applied: instantly
• Description: Whether unroutable incoming transport orders should be marked as UNROUTABLE.

defaultdispatcher.reroutingImpossibleStrategy

• Type: String
• Trigger for changes to be applied: instantly
• Description: The strategy to use when rerouting of a vehicle results in no route at all.
  The vehicle then continues to use the previous route in the configured way.
  Possible values:
  IGNORE_PATH_LOCKS: Stick to the previous route, ignoring path locks.
  PAUSE_IMMEDIATELY: Do not send further orders to the vehicle; wait for another rerouting opportunity.
  PAUSE_AT_PATH_LOCK: Send further orders to the vehicle only until it reaches a locked path; then wait for another rerouting opportunity.

defaultdispatcher.parkIdleVehicles

• Type: Boolean
• Trigger for changes to be applied: instantly
• Description: Whether to automatically create parking orders for idle vehicles.

defaultdispatcher.considerParkingPositionPriorities

• Type: Boolean
• Trigger for changes to be applied: instantly
• Description: Whether to consider parking position priorities when creating parking orders.

defaultdispatcher.reparkVehiclesToHigherPriorityPositions

• Type: Boolean
• Trigger for changes to be applied: instantly
• Description: Whether to repark vehicles to parking positions with higher priorities.

defaultdispatcher.rechargeIdleVehicles

• Type: Boolean
• Trigger for changes to be applied: instantly
• Description: Whether to automatically create recharge orders for idle vehicles.

defaultdispatcher.keepRechargingUntilFullyCharged

• Type: Boolean
• Trigger for changes to be applied: instantly
• Description: Whether vehicles must be recharged until they are fully charged.
  If false, vehicle must only be recharged until sufficiently charged.

defaultdispatcher.idleVehicleRedispatchingInterval

• Type: Integer
• Trigger for changes to be applied: when/after plant model is loaded
• Description: The interval between redispatching of vehicles.

4. 参考资料与源码

本文内容参考:官方文档

该模块源码位于:
openTCS-Strategies-Default/src/main/java/org/opentcs/strategies/basic/dispatching/DefaultDispatcher.java,代码如下:

 public DefaultDispatcher(OrderReservationPool orderReservationPool,
                           TransportOrderUtil transportOrderUtil,
                           InternalVehicleService vehicleService,
                           @ApplicationEventBus EventSource eventSource,
                           @KernelExecutor ScheduledExecutorService kernelExecutor,
                           FullDispatchTask fullDispatchTask,
                           Provider<PeriodicVehicleRedispatchingTask> periodicDispatchTaskProvider,
                           DefaultDispatcherConfiguration configuration,
                           RerouteUtil rerouteUtil,
                           OrderAssigner orderAssigner,
                           TransportOrderAssignmentChecker transportOrderAssignmentChecker) {
    this.orderReservationPool = requireNonNull(orderReservationPool, "orderReservationPool");
    this.transportOrderUtil = requireNonNull(transportOrderUtil, "transportOrderUtil");
    this.vehicleService = requireNonNull(vehicleService, "vehicleService");
    this.eventSource = requireNonNull(eventSource, "eventSource");
    this.kernelExecutor = requireNonNull(kernelExecutor, "kernelExecutor");
    this.fullDispatchTask = requireNonNull(fullDispatchTask, "fullDispatchTask");
    this.periodicDispatchTaskProvider = requireNonNull(periodicDispatchTaskProvider,
                                                       "periodicDispatchTaskProvider");
    this.configuration = requireNonNull(configuration, "configuration");
    this.rerouteUtil = requireNonNull(rerouteUtil, "rerouteUtil");
    this.orderAssigner = requireNonNull(orderAssigner, "orderAssigner");
    this.transportOrderAssignmentChecker = requireNonNull(transportOrderAssignmentChecker,
                                                          "transportOrderAssignmentChecker");
  }

  @Override
  public void initialize() {
    if (isInitialized()) {
      return;
    }

    LOG.debug("Initializing...");

    transportOrderUtil.initialize();
    orderReservationPool.clear();

    fullDispatchTask.initialize();

    implicitDispatchTrigger = new ImplicitDispatchTrigger(this);
    eventSource.subscribe(implicitDispatchTrigger);

    LOG.debug("Scheduling periodic dispatch task with interval of {} ms...",
              configuration.idleVehicleRedispatchingInterval());
    periodicDispatchTaskFuture = kernelExecutor.scheduleAtFixedRate(
        periodicDispatchTaskProvider.get(),
        configuration.idleVehicleRedispatchingInterval(),
        configuration.idleVehicleRedispatchingInterval(),
        TimeUnit.MILLISECONDS
    );

    initialized = true;
  }

  @Override
  public void terminate() {
    if (!isInitialized()) {
      return;
    }

    LOG.debug("Terminating...");

    periodicDispatchTaskFuture.cancel(false);
    periodicDispatchTaskFuture = null;

    eventSource.unsubscribe(implicitDispatchTrigger);
    implicitDispatchTrigger = null;

    fullDispatchTask.terminate();

    initialized = false;
  }

  @Override
  public boolean isInitialized() {
    return initialized;
  }

  @Override
  public void dispatch() {
    LOG.debug("Scheduling dispatch task...");
    // Schedule this to be executed by the kernel executor.
    kernelExecutor.submit(fullDispatchTask);
  }

  @Override
  public void withdrawOrder(TransportOrder order, boolean immediateAbort) {
    requireNonNull(order, "order");
    checkState(isInitialized(), "Not initialized");

    // Schedule this to be executed by the kernel executor.
    kernelExecutor.submit(() -> {
      LOG.debug("Scheduling withdrawal for transport order '{}' (immediate={})...",
                order.getName(),
                immediateAbort);
      transportOrderUtil.abortOrder(order, immediateAbort);
    });
  }

  @Override
  public void withdrawOrder(Vehicle vehicle, boolean immediateAbort) {
    requireNonNull(vehicle, "vehicle");
    checkState(isInitialized(), "Not initialized");

    // Schedule this to be executed by the kernel executor.
    kernelExecutor.submit(() -> {
      LOG.debug("Scheduling withdrawal for vehicle '{}' (immediate={})...",
                vehicle.getName(),
                immediateAbort);
      transportOrderUtil.abortOrder(vehicle, immediateAbort);
    });
  }

  @Override
  public void topologyChanged() {
    if (configuration.rerouteOnTopologyChanges()) {
      LOG.debug("Scheduling reroute task...");
      kernelExecutor.submit(() -> {
        LOG.info("Rerouting all vehicles due to topology change...");
        rerouteUtil.reroute(vehicleService.fetchObjects(Vehicle.class), ReroutingType.REGULAR);
      });
    }
  }

  @Override
  public void reroute(Vehicle vehicle, ReroutingType reroutingType) {
    LOG.debug("Scheduling reroute task...");
    kernelExecutor.submit(() -> {
      LOG.info(
          "Rerouting vehicle due to explicit request: {} ({}, current position {})...",
          vehicle.getName(),
          reroutingType,
          vehicle.getCurrentPosition() == null ? null : vehicle.getCurrentPosition().getName()
      );
      rerouteUtil.reroute(vehicle, reroutingType);
    });
  }

  @Override
  public void assignNow(TransportOrder transportOrder)
      throws TransportOrderAssignmentException {
    requireNonNull(transportOrder, "transportOrder");

    TransportOrderAssignmentVeto assignmentVeto
        = transportOrderAssignmentChecker.checkTransportOrderAssignment(transportOrder);

    if (assignmentVeto != TransportOrderAssignmentVeto.NO_VETO) {
      throw new TransportOrderAssignmentException(
          transportOrder.getReference(),
          transportOrder.getIntendedVehicle(),
          assignmentVeto
      );
    }

    orderAssigner.tryAssignments(
        List.of(vehicleService.fetchObject(Vehicle.class, transportOrder.getIntendedVehicle())),
        List.of(transportOrder)
    );
  }
}