← 返回题目列表

AtCoder · hokudai_hitachi2020_b

B. 北大日立2020 B题

中文机器翻译题面 查看原题

目录

问题总结
时间表和空间结构
纳米电网的构成
能量平衡
订单处理
电动车操作
纳米电网电池的充电/放电
评分
问题B
输入和输出格式 1
输入和输出格式 2
输入和输出格式 3
输入和输出的约束
输入和输出示例
示例代码 B

问题总结

在此问题中,您操作多辆电动汽车 (EV),以便可以高效地将客户和货物从一个地方运送到另一个地方,同时保护分布式纳米电网免于电动汽车供电过载,并在纳米电网出现电力短缺时由电动汽车提供额外电力。由于电动汽车消耗的电力与其行驶距离成正比,因此如有必要,它们需要通过纳米电网充电。每个纳米电网都配备了电池、光伏(PV)电力系统和燃料发动机。电动汽车的发电、消耗和充电/放电发生在每个纳米电网中,它们随时间变化的不平衡通过电池的充电/放电和外部供电来补偿。

该工具包可以从本页底部下载,其中包含参赛者代码示例,其中已经实现了输入/输出,例如从裁判代码读取数据。此外,关于EV的操作,已经实施了“全部停留”、“随机行走”和“多次运输”等。在实现新算法时,该示例的设计是为了让您可以通过继承策略类来专注于描述EV的操作。 (详细信息请参阅 README.md。)您可以在提交代码时使用该示例。

时间表和空间结构

  • 时间表:每个测试用例的总时间长度实际对应于一个工作日。时间变量 t 应该是整数值,范围为 0 to T_{max}。对于每个测试用例,随机分配四种不同的一日天气模式之一,并且天气模式影响生成的功率和消耗的功率之间的差异的结果时间序列(能量平衡)。在每个测试用例开始时,每个参赛者都会获得预测能量平衡的整个时间序列,并且每次 t,每个参赛者获得每个纳米电网的电池充电容量、到目前为止分配的订单集,以及上一步中的以下值:实际能量平衡、多余的丢弃电量和外部提供的电量。根据这些信息,要求每位参赛者每次决定下一步如何操作多辆电动汽车 t.
  • 空间结构:让 G = (V, E) 是一个带有顶点集的简单无向图 V 和边缘设置 E,代表发生电动汽车运输和电动汽车充电/放电的道路网络。纳米网格位于一些顶点。一条边代表连接其两个端点的道路,并具有与道路距离相对应的正整数权重。该图是由下面的算法生成的。
生成图的算法 G 对于所有测试用例,该图 G = (V, E) 由以下算法生成。
  • 输入:|V|, |E|, \mathrm{MaxDegree}=5
  • 生成顶点的算法:
    • 求最大非负整数 R 这样 |V| = R^{2} + r 适用于非负整数 r.
    • 对于每个满足的格点 0 \leq x, y < R 在 xy 平面,绘制一个点 (x, y).
    • 移动每个点,例如 (x, y) \leftarrow (x + dx, y + dy) 其中 dx 和 dy 是从间隔中均匀采样的随机数 [0, 1].
    • 剩余 r 点绘制在 (x', y') 其中 x' 和 y' 是从间隔中均匀采样的随机数 [0, R].
    • 分配一个单独的 ID,范围为 1 to |V| 到每个点并将每个点标识到具有分配的ID的顶点。
  • 生成的算法 |V|-1 边及其权重,以保证结果图的连通性:
    • 生成完整的图表 G_{\text{comp}} 已设置顶点 V。对于每对顶点 u, v \in V,指定对应点之间的欧氏距离 u 和 v 到边权重 W_{u,v}.
    • 生成 最小生成树 为 G_{\text{comp}} 并添加 |V|-1 最小生成树中到图的边 G。对于每条边 \left\{ u, v \right\},分配 \lceil 2 \times W_{u, v} \rceil 到边权重 d_{u,v}.
  • 生成剩余的算法 |E|-(|V|-1) 边及其权重:
    • 剩余 |E|-(|V|-1) 边缘由以下算法生成。
      • 更新 \mathrm{cost}(u,v) 基于以下算法。
      • 找到一对顶点 u 和 v 最小化 \mathrm{cost(u,v)} 在未由添加到图中的边连接的所有顶点对中 G 到目前为止并添加边缘 \left\{ u, v \right\} 将货币对连接到图表 G.
      • 分配 \lceil 2 \times W_{u, v} \rceil 到边权重 d_{u,v}.
    • 这里 \mathrm{cost}(u,v) 基本上是由对应的点之间的欧氏距离确定的 u 和 v 但有偏差,因此一对顶点 u 和 v 其中一个度数较小并且一对垂直和水平排列而不是对角排列的顶点很可能被选择。由于存在偏差,所得图表预计会接近平面图。接下来,我们将展示计算算法 \mathrm{cost}(u,v).
      • 计算度数 顶点的 \mathrm{degree}(u) 顶点的 u\in V。学位 \mathrm{degree}(u) 顶点的 u\in V 由入射到顶点的边数定义。
      • 为每个顶点指定颜色 u\in V 如下:第一个添加的颜色 R^{2} 顶点根据其原始格点确定 (x,y) 基于以下规则。其余颜色 r 顶点被随机分配为 0 or 1.
        • If x+y 是偶数: \mathrm{color}(u) = 0
        • If x+y 是奇数: \mathrm{color}(u) = 1
      • 偏差因子 f(u,v) 由以下规则确定:
        • If \mathrm{color}(u) = \mathrm{color}(v) : \mathrm{f}(u,v) = 5
        • If \mathrm{color}(u) \neq \mathrm{color}(v) : \mathrm{f}(u,v) = 1
      • 偏差因子 g(u) 由以下规则确定:
        • If \mathrm{degree}(u) \lt \mathrm{MaxDegree} : g(u)=1
        • If \mathrm{degree}(u) \geq \mathrm{MaxDegree} : g(u)=\infty
      • 计算 \mathrm{cost}(u,v) 如下:
        • \mathrm{cost}(u,v) = W_{u,v}\times \mathrm{degree}(u) \times \mathrm{degree}(v) \times f(u,v) \times g(u) \times g(v).
  • 选择纳米网格所在顶点的算法:
    • 统一随机选择 N_{\mathrm{grid}} 不同的顶点 V 并在每个选定的顶点上找到一个纳米网格。纳米网格所在的顶点集表示为 V_{\mathrm{grid}}.

纳米电网的构成

每个纳米电网由电池、光伏(PV)电力系统、燃油发动机、电动汽车充电/放电站和电力消费者组成,并具有以下属性。

  • 顶点 ID:顶点的ID u 纳米网格位于何处 u \in V_{\mathrm{grid}} (V_{\mathrm{grid}}:纳米网格所在的顶点集(参见“生成图的算法 G".) )

  • 充电容量:纳米电网中电池的充电容量。其初始值为 C_{\mathrm{init}}^{\mathrm{grid}} 其最大值为 C_{\mathrm{max}}^{\mathrm{grid}},对于所有纳米网格来说都是相同的。对于每一次 t,充电容量会根据发电量和消耗量之间的差异(能量平衡)而变化,并且也会根据电动汽车的放电量和充电量之间的差异而变化(详细信息请参见 纳米电网电池的充电/放电 。)。如果最终的充电容量超过 当时的 C_{\mathrm{max}}^{\mathrm{grid}} 当时 t,充电容量设置为 C_{\mathrm{max}}^{\mathrm{grid}} 当时 t+1 并丢弃多余的量。相反,如果当时得到的容量为负值 t,短缺由外部供给,充电容量设置为 0 当时 t+1。如果是后者,则按照短缺量的比例扣除分数(具体参见 评分.)

  • 能量平衡:除了每次给电动汽车充电/放电的电力之外,发电量和消耗量之间的差异 t。其每次的预测值 t 在每个测试用例的开头提供给参赛者。其实际值为由于环境的随机波动以及暴雨、突发晴空等天气突变引起的预测值与随机值之和(具体参见 能量平衡 如下。)

  • 最大充电/放电速度: 电池充电/放电的最大速度 V_{\max}^{\mathrm{grid}},这对于所有纳米网格都是相同的。

能量平衡

除每次电动汽车充电/放电的电力外,发电量和消耗量之间的差异 t.

  • 能量平衡的时间序列模式:对于每个测试用例,随机分配四种不同的一日天气模式之一,即晴天有/没有倾盆大雨和雨天有/没有突然晴朗的天空,并在测试用例开始时告知每个参赛者。对于每个纳米网格,其中一个 N_{\mathrm{pattern}} 不同的预期需求模式是随机分配的,并在每个测试用例开始时通知给每个参赛者。在每个测试用例开始时,向每个参赛者提供预测能量平衡的整个时间序列。光伏发电系统的发电量取决于天气情况,因此晴天无暴雨天气情况下一个工作日能量平衡预测值之和最大,有雨无突发晴天情况下一个工作日能量平衡预测值之和最小。

  • 能量平衡的时间序列:能量平衡的时间序列是预测一与随机波动之和 \delta 以及由于倾盆大雨和突然晴朗的天空造成的变化。

    • 总时间间隔 0 \leq t < T_{\max} 分为 N_{\mathrm{div}} 等长度的子区间,并且每个细分区间的能量平衡预测值是恒定的。
    • 每次 t, \delta 从正态分布中采样,平均值为 0 和方差 \sigma^{2}_{\mathrm{ele}}。在每个测试用例开始时向每个参赛者告知方差,但值 \delta 不会提前通知每位参赛者。
    • 倾盆大雨:如果天气模式为 1 (晴,有倾盆大雨),有概率发生倾盆大雨 p_{\mathrm{event}} 对于每个 N_{\mathrm{div}} 子区间。每个子区间的概率是恒定且独立的。如果发生倾盆大雨,则能量平衡减去 \Delta_{\mathrm{event}} 为 15 为每个子区间随机且独立选择的纳米电网百分比,因为光伏 (PV) 电力系统产生的电力减少。
    • 突然晴朗的天空:如果天气模式是 3 (雨天突然晴空),突然晴空发生的概率 p_{\mathrm{event}} 对于每个 N_{\mathrm{div}} 子区间。如果天空突然晴朗,则能量平衡会增加 \Delta_{\mathrm{event}} 为 15 为每个子区间随机且独立选择的纳米电网百分比,因为光伏 (PV) 电力系统产生的电力增加。

天气情况 1 和 3,大雨或突发晴天的时间不会提前告知每位参赛者。

订单处理

从一个顶点运输货物的命令 u \in V 到另一个顶点 v \in V 每次根据以下算法随机生成 t 并且每个参赛者被要求通过在顶点拾取来处理订单 u 并将其传递到顶点 v 通过操作电动汽车。下面我们称 u 起始顶点和 v 目标顶点。

  • 订单属性:

    • 订单 ID (1,...)
    • 加载时间 (0 \leq t \leq T_{\mathrm{last}}(<T_{\max}))
    • 起始顶点 (1,...,|V|)
    • 目标顶点 (1,...,|V|)
    • 状态 (0 如果没有电动汽车接受订单并且 1 如果其中一辆电动汽车已取货但尚未交付。)
  • 生成订单的算法:每次 t 满意 0 \leq t \leq T_{\mathrm{last}}(<T_{\max}),随机生成一个新订单,概率为 p_{\mathrm{trans}}^{\mathrm{const}}。它的起始顶点是从顶点集中随机选择的 V 及其目标顶点是从除起始顶点之外的所有顶点中随机选择的。

  • 未完成订单的处罚:对于每个未完成的订单 t=T_{\max},处罚 交通得分减去 P^{\mathrm{trans}} (详情参见 评分.).

电动车操作

要求每位参赛者操作多辆电动汽车 (EV),以有效地将客户和货物从一个地方运送到另一个地方,同时保护分布式纳米电网不会使电动汽车的电力供应过载,并在纳米电网出现电力短缺时由电动汽车提供额外的电力。

  • 电动汽车数量:电动汽车数量 N^{\mathrm{EV}} 是从区间中均匀随机选择的 [N_{\min}^{\mathrm{EV}}, N_{\max}^{\mathrm{EV}}] 并在每个测试用例开始时通知每个参赛者。

  • 电动汽车的初始位置:在每个测试用例的开头, N^{\mathrm{EV}} 顶点是随机选择的,并且在每个选定的顶点上放置一个 EV。

  • EV 属性:每个 EV 具有以下属性:

    • ID (0, 1,... , N^{\mathrm{EV}}-1)
    • 充电容量: C^{\mathrm{EV}}_{t} 非负整数值,初始化为 C^{\mathrm{EV}}_{t=0},并且有上限 C^{\mathrm{EV}}_{\max} 所有电动汽车通用
    • 当前位置:在顶点或边上
    • 位于每个 EV 上的订单 ID:位于每个 EV 上的订单数量上限为 N_{\max}^{\mathrm{trans}},这对于所有电动汽车来说都很常见。
    • 最大充电/放电速度: V_{\max}^{\mathrm{EV}},这对于所有电动汽车来说都很常见。
  • 电动汽车操作:每次 t,每位参赛者为每个 EV 选择以下操作之一:

    • stay:让 EV 停留在同一个地方。在这种情况下,电动汽车不消耗电力,即 C^{\mathrm{EV}}_{t+1}-C^{\mathrm{EV}}_{t}=0.
    • move w: 让EV向前移动到顶点 w \in V 按距离 1。下一步电动汽车的充电容量减少 \Delta^{\mathrm{EV}}_{\mathrm{move}} 除非最终的充电容量为负。如果是这种情况,则如果满足以下条件,则操作被拒绝,EV 保持在相同位置并且其充电容量不会改变。

      • 假设操作 选择 move w 。那么,每位参赛者将获得 WA (错误答案)如果违反以下条件之一。
        • w \in V
        • 假设 EV 的当前位置为 on u \in V, \left\{ u, w \right\} \in E 成立。
        • 假设 EV 的当前位置为 on \left\{ u, v \right\}, w = u or w = v 成立。
    • pickup a: 选择ID的顺序 a 由 EV 提供。在此操作中,EV 不消耗电力(当承载订单的 EV 到达订单的目的地顶点时,订单会自动交付)。

      • 假设操作 选择 pickup a 。那么,每位参赛者将获得 WA (错误答案)如果违反以下条件之一。
        • EV 已开启 u \in V
        • 有一个ID的订单 a 具有起始顶点 u 并状态 0.
        • 电动车的订单数量少于 N_{\max}^{\mathrm{trans}}.
    • charge_from_grid \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}}:通过以下方式给电动汽车充电 \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}}。 EV下一步的充电容量 C^{\mathrm{EV}}_{t+1} 变为 C^{\mathrm{EV}}_{t+1} \leftarrow C^{\mathrm{EV}}_{t} + \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge},t}。可以从单个纳米电网为多辆电动汽车充电。

      • 假设操作 选择 charge_from_grid 选择为 \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}}。那么,每位参赛者将获得 WA (错误答案)如果违反以下条件之一。
        • EV 位于纳米网格所在的顶点 u \in V_{\mathrm{grid}}.
        • \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}} 是一个自然数。
        • 每辆EV的充电量不超过最大充放电速度: \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}} \leq V_{\max}^{\mathrm{EV}}
        • 每辆电动汽车的最终充电容量不超过上限 C^{\mathrm{EV}}_{\max}: C^{\mathrm{EV}}_{t} + \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}} \leq C^{\mathrm{EV}}_{\max}
    • charge_to_grid \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}}:通过电动汽车为纳米电网充电 \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}}。 EV下一步的充电容量 C^{\mathrm{EV}}_{t+1} 变为 C^{\mathrm{EV}}_{t+1} \leftarrow C^{\mathrm{EV}}_{t} - \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge},t}。可以通过多辆电动汽车为纳米电网充电。还可以从纳米电网为电动汽车充电,并同时从其他电动汽车为纳米电网充电。

      • 假设操作 选择 charge_to_grid 选择为 \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}}。那么,每位参赛者将获得 WA (错误答案)如果违反以下条件之一。
        • EV 位于纳米网格所在的顶点 u \in V_{\mathrm{grid}}.
        • \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}} 是一个自然数。
        • 每辆EV的充电量不超过最大充放电速度: \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}} \leq V_{\max}^{\mathrm{EV}}
        • 每个 EV 的最终充电容量不为负: C^{\mathrm{EV}}_{t} - \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}} \geq 0

纳米电网电池的充电/放电

对于每个纳米电网,电池的充电容量随时间变化,具体取决于发电功率和消耗功率之间的差异以及电动汽车的充电/放电量。对于每一次 t,产生的电力和消耗的电力之间的差值之和以及从纳米电网到电动汽车的充电/放电量之间的总差对应于纳米电网中的电力过剩或短缺。如果发生电量过剩,则按照电量过剩不超过电池的最大充电速度且最终的电池充电容量不超过其上限的量对电池进行充电。如果多余的电量超过电池的最大充电速度,则丢弃多余的电量并按最大充电速度对电池进行充电。如果所得到的电池充电容量超过其上限,则在下一步中将充电容量设置为上限,并且丢弃多余的量。相反,如果发生电量不足,则通过对电池进行放电来补偿电量不足,前提是电量不足不低于电池的最大放电速度并且所得到的电池充电容量不为负。如果电量不足低于电池的最大放电速度,则通过以最大放电速度对电池进行放电以及从外部供给电力来弥补电量不足。如果所得的电池充电容量为负,则在下一步中将电池的充电容量设置为零,并从外部补充不足。在所有情况下,每辆电动车均按照每位参赛者规定的量进行充电或放电。

确定下一步中对电池的充电/放电量的算法由以下4个步骤组成。

  • 步骤 1:计算某个时刻每个纳网的电量过剩或不足 t \Delta^{\mathrm{grid}}_{\mathrm{total}}.
    \Delta^{\mathrm{grid}}_{\mathrm{total}} = \Delta^{\mathrm{grid}}_{\mathrm{gen},t} - \sum_{i \in \mathrm{all EV}} \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}i}_{\mathrm{charge},t} + \sum_{i \in \mathrm{all EV}} \Delta^{\mathrm{EV}i \rightarrow \mathrm{grid}}_{\mathrm{charge},t}
    这里,各变量定义如下。

    • \Delta^{\mathrm{grid}}_{\mathrm{gen},t}:当时纳米电网发电量和消耗量之间的差异 t,这是生成功率和消耗功率之间的预测差值之和 \Delta^{\mathrm{grid,predict}}_{\mathrm{gen},t},随机波动 \delta_{t},以及由于倾盆大雨和突然晴朗的天空造成的变化。请注意,在每个测试用例开始时,将生成的功率和消耗的功率之间的预测差异的时间序列通知给每个参赛者,但直到该时间才通知随机波动 t (在下一个时间步通知 t+1).
    • \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}i}_{\mathrm{charge},t}: 充值金额 i来自参赛者当时规定的纳米电网的第 EV t
    • \Delta^{\mathrm{EV}i \rightarrow \mathrm{grid}}_{\mathrm{charge},t}:从纳米电网到纳米电网的充电量 i- 参赛者当时规定的第 EV t

  • 步骤 2:如果 \Delta^{\mathrm{grid}}_{\mathrm{total}} \geq \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{\max}-C^{\mathrm{grid}}_{t} \right\},
    当时纳米电网的带电容量 t+1 由以下等式确定:
    C^{\mathrm{grid}}_{t+1} \leftarrow C^{\mathrm{grid}}_{t}+\min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{\max}-C^{\mathrm{grid}}_{t} \right\}
    从物理上讲,这意味着如果多余的电量超过最大充电/放电速度或电池的剩余容量,则多余的电量将被丢弃。

  • 步骤 3:如果 \Delta^{\mathrm{grid}}_{\mathrm{total}} < - \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{t} \right\},
    当时纳米电网的带电容量 t+1 由以下等式确定:
    C^{\mathrm{grid}}_{t+1} \leftarrow C^{\mathrm{grid}}_{t} - \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{t} \right\}
    如果电量不足无法通过对电池放电来补偿,则剩余电量不足:
    L_t = - \Delta^{\mathrm{grid}}_{\mathrm{total}} - \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{t} \right\}(>0)
    由外部提供。在这种情况下,电力管理的分数将按供应电量的比例扣除一个系数 \gamma。 (详细请参见 评分.)。

  • 第 4 步: 除步骤2和步骤3中的情况之外的其他情况,
    当时纳米电网的带电容量 t+1 由以下等式确定:
    C^{\mathrm{grid}}_{t+1} \leftarrow C^{\mathrm{grid}}_{t} + \Delta^{\mathrm{grid}}_{\mathrm{total}}

评分

在这个问题中,每位参赛者发现 N_{\mathrm{solution}} 问题的解决方案,并基于每个解决方案的交通得分下面的方程 (S_{\mathrm{trans}}^{(1)},...,S_{\mathrm{trans}}^{(N_{\mathrm{solution}})})以及每个解决方案的电力管理得分(S_{\mathrm{ele}}^{(1)},...,S_{\mathrm{ele}}^{(N_{\mathrm{solution}})}) 被计算。 请注意,订单及其起始和目的地顶点的生成时间,以及倾盆大雨和突然晴朗的天空的时间各不相同 N_{\mathrm{solution}} 试验。其他的,比如图表、纳米电网所在的顶点集、电动汽车的数量、预测能量平衡的时间序列对于所有的都是相同的 N_{\mathrm{solution}} 试验。

  • 交通得分:交通得分 S_{\mathrm{trans}} 通过以下等式计算。
    S_{\mathrm{trans}}=\sum_{i \in O_{\mathrm{trans}}} \left( T_{\max} - T_{\mathrm{wait},i} \right) - \sum_{i \in \overline{O_{\mathrm{trans}}}} P_i^{\mathrm{trans}}
    在这里, O_{\mathrm{trans}} 是由 处理的所有订单的集合 T_{\max}, \overline{O_{\mathrm{trans}}} 是所有订单的集合 不 处理者 T_{\max}, T_{\mathrm{wait},i} 是处理所花费的时间 i- 第一个订单(=[订单交付时间] - [订单生成时间]),以及 P_i^{\mathrm{trans}} 是对未完成任务的处罚 i-th 阶(惩罚不取决于 i 是一个常数 P_i^{\mathrm{trans}}=P^{\mathrm{trans}}).

  • 用电管理得分:用电管理得分 S_{\mathrm{ele}} 通过以下等式计算。
    S_{\mathrm{ele}}=\sum_{i=1}^{N_{\mathrm{EV}}} C_{t=T_{\max}}^{\mathrm{EV}i} + \sum_{i=1}^{N_{\mathrm{grid}}} C_{t=T_{\max}}^{\mathrm{grid}i} - \gamma \sum_{t=0}^{T_{\max}-1} \sum_{i=1}^{N_{\mathrm{grid}}} L_{i,t}
    这里,方程中的第一项和第二项是当时所有电动汽车和纳米电网的充电容量 t=T_{\max}。 L_{i,t} 是从外部提供的电源 i当时第-格 t 和 \gamma 是惩罚的比例常数, L_{i,t}。的价值 L_{i,t} 设置为 L_{i,t} = - \Delta^{\mathrm{grid}}_{\mathrm{total}} - \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{t} \right\}(L_{i,t}>0) 如果步骤 3 执行于 纳米电网电池的充电/放电 并设置为 L_{i,t}=0 在其他情况下。

  • 最终得分:根据方程, N_{\mathrm{solution}} 交通和电力管理得分对 \left( =(S_{\mathrm{ele}}^{(1)},S_{\mathrm{trans}}^{(1)}),...,(S_{\mathrm{ele}}^{(N_{\mathrm{solution}})},S_{\mathrm{trans}}^{(N_{\mathrm{solution}})}) \right) 绘制在二维平面上,如下图所示。对于给定的参考点,每个测试用例的最终分数由以下区域确定。 这里,如果其中一个分数低于参考点的分数,则将该分数设置为参考点的相应分数。这样最终的分数就不会是负数。参考点的具体位置参见“输入输出约束”

  • 积分榜:比赛期间,提交的总分是通过将提交的 16 个测试用例的最终得分相加来确定的。其中,晴无大雨、晴有大雨、雨无骤晴、雨骤晴的个数分别固定为6、2、6、2。
    比赛结束后将进行系统测试。为此,将对参赛者最后一次提交的作品的最终分数进行求和来评分 200 以前未见过的测试用例。
    请参阅下表了解详细信息 200 测试用例。

预测的能量平衡(已披露) 预测的能量平衡(未公开) 总计
晴无倾盆大雨 60 15 75
晴有倾盆大雨 20 5 25
下雨但没有突然晴朗的天空 60 15 75
下雨,天空突然晴朗 20 5 25
总计 160 40 200

的 200 测试用例, 160 使用 6(=N_\mathrm{pattern} \times 2(晴天、雨天)) 工具包中已公开的预测能量平衡类型。剩余的 40 测试用例使用 6(=N_\mathrm{pattern} \times 2(晴天、雨天)) 未向参赛者透露的预测能量平衡类型。 \Delta_{\mathrm{event}}, p_{\mathrm{event}},并且纳米电网遭受倾盆大雨或突然晴空袭击的百分比在 50(=25[晴有倾盆大雨]+25[雨天突然晴朗]) 测试用例。
我们非常抱歉,系统测试规范发生了变化,与 yuusanlondon 先生 12 月 18 日收到的问题的答案不同。 经考虑,大赛主办方决定按照本规范确定最终名次。我们感谢您的理解。
(12/29后记)未公开的预测能量平衡的生成方法或生成器不会发布。生成未公开的预测能量平衡的模式,使得使用未公开的预测能量平衡的电力管理的满分与使用公开的预测能量平衡的电力管理的满分相当。 (注意,满分是指应用理想控制方法时得分的上限。)

问题B

问题 B 是 交互问题 与问题A类似。 要求每位参赛者考虑交通和电力管理之间的权衡,并找到 N_{\mathrm{solution}} 每个测试用例的解决方案,以便每个解决方案与权衡曲线尽可能接近,并且整个解决方案覆盖权衡曲线的广泛范围。每个参赛者和主机(评委)都按照以下协议进行交互。

迭代过程 参赛者 法官
输出 N_{\mathrm{solution}}
输出 G
输出天气 \mathrm{DayType}
输出能量平衡相关信息
输出纳米电网的信息
输出EV信息
输出交通信息
输出分数信息
输出 T_\mathrm{max}
为 i=1,...,N_{\mathrm{solution}} do
为 t=0,...,T_\mathrm{max}-1 do
- -
输出 \mathrm{info}_t (当时电动汽车和纳米电网的状况 t)
每个 EV 的输出操作
结束
输出 \mathrm{info}_t (当时电动汽车和纳米电网的状况 t=T_\mathrm{max})
交通输出得分 S_{\mathrm{trans}} 和用电管理得分 S_{\mathrm{ele}}
结束

试验次数,图表 G, 天气 \mathrm{DayType},与能量平衡、纳米电网、电动汽车及其运输相关的信息、得分、 T_\mathrm{max} 在每个测试用例的开头仅输出一次。每次审判时,参赛者都应该与评委互动 T_\mathrm{max} 次。 请注意 \mathrm{info}_t 和当时的分数 t=T_\mathrm{max} 必须由参赛者代码读取(否则可能是TLE)。

输入和输出格式 1

在每个测试用例的开头,试验次数,图表 G, 天气 \mathrm{DayType},与能量平衡、纳米电网、电动汽车及其运输相关的信息、得分、 T_\mathrm{max} 通过标准输入提供。 请注意,该信息仅在每个测试用例开始时提供一次,因为它对于所有试验都是通用的。

N_{\mathrm{solution}}
|V| |E|
u_1 v_1 d_1
:
u_{|E|} v_{|E|} d_{|E|}
\mathrm{DayType}
N_\mathrm{div} N_\mathrm{pattern} \sigma^{2}_{\mathrm{ele}} p_{\mathrm{event}} \Delta_{\mathrm{event}}
\mathrm{pw}_{1,1}^{\mathrm{predict}} \mathrm{pw}_{1,2}^{\mathrm{predict}} ... \mathrm{pw}_{1,N_\mathrm{div}}^{\mathrm{predict}}
:
\mathrm{pw}_{N_\mathrm{pattern},1}^{\mathrm{predict}} \mathrm{pw}_{N_\mathrm{pattern},2}^{\mathrm{predict}} ... \mathrm{pw}_{N_\mathrm{pattern},N_\mathrm{div}}^{\mathrm{predict}}
N_\mathrm{grid} C_{\mathrm{init}}^{\mathrm{grid}} C_{\mathrm{max}}^{\mathrm{grid}} V_{\max}^{\mathrm{grid}}
x_1 \mathrm{pattern}_1 
: 
x_{N_\mathrm{grid}} \mathrm{pattern}_{N_\mathrm{grid}} 
N_\mathrm{EV} C_{\mathrm{init}}^{\mathrm{EV}} C_{\mathrm{max}}^{\mathrm{EV}} V_{\max}^{\mathrm{EV}} N_{\max}^{\mathrm{trans}} \Delta_{\mathrm{move}}^{\mathrm{EV}}
\mathrm{pos}_1
:
\mathrm{pos}_{N_\mathrm{EV}}
p_{\mathrm{trans}}^{\mathrm{const}} T_\mathrm{last}
P^{\mathrm{trans}} \gamma S_{\mathrm{ele}}^{\mathrm{ref}} S_{\mathrm{trans}}^{\mathrm{ref}}
T_\mathrm{max}
  • 在 1st线, N_{\mathrm{solution}} 是每个测试用例的试验次数。
  • 在下面的行中,顶点数 |V| 和边数 图表的 |E| 提供了 G 。
  • 如下 |E| 线,提供了图的边缘及其权重。的 i第 行表示存在一条边连接 u_{i} 和 v_{i} 与边缘权重 d_i.
  • 如下 1 线、天气模式 提供了 \mathrm{DayType} ,它是 \mathrm{DayType} 0 (晴无倾盆大雨), 1 (晴,有倾盆大雨), 2 (有雨但没有突然晴朗的天空),或 3 (下雨,天空突然晴朗)。
  • 如下 1 线,预测能量平衡恒定的等长子区间数 N_\mathrm{div},预测能量平衡时间序列的可能模式数量 N_\mathrm{pattern},差值随机波动的方差 \sigma^{2}_{\mathrm{ele}}, 发生倾盆大雨或突然晴天的概率 p_{\mathrm{event}} (p_{\mathrm{event}}=0.0 在这种情况下 \mathrm{DayType}=0 or 2),以及暴雨或突然晴空时能量平衡的变化 \Delta_{\mathrm{event}}.
  • 如下 N_\mathrm{pattern} 行,提供了预测能量平衡的时间序列。的 j- 第一个元素 i第 行 (\mathrm{pw}_{i,j}^{\mathrm{predict}}) 表示预测的能量平衡 j-第一个子区间,如果 i第一个模式。
  • 如下 1 线,纳米网格的数量 N_\mathrm{grid} 以及每个纳米电网的电池充电容量的初始值 C_{\mathrm{init}}^{\mathrm{grid}} (t=0)、电池充电容量上限 C_{\mathrm{max}}^{\mathrm{grid}},以及电池的最大充电/放电速度 提供了 V_{\max}^{\mathrm{grid}} 。
  • 如下 N_\mathrm{grid} 行,提供了每个纳米网格的信息。在 N_\mathrm{grid} 行, i第行表示纳米网格位于顶点 x_i 其预测能量平衡的时间序列模式为 \mathrm{pattern}_i.
  • 如下 1 线,电动车数量 N_\mathrm{EV},其初始充电容量 C_{\mathrm{init}}^{\mathrm{EV}},其最大充电容量 C_{\mathrm{max}}^{\mathrm{EV}},以及它们的最大充电/放电速度 V_{\max}^{\mathrm{EV}},每辆EV可以承载的最大订单数 N_{\max}^{\mathrm{trans}},以及每辆电动汽车行驶单位距离所需的电量 \Delta_{\mathrm{move}}^{\mathrm{EV}}.
  • 如下 N_\mathrm{EV} 行,提供了每个EV的位置。在 N_\mathrm{EV} 线, i第行表示 i-th EV 位于顶点 \mathrm{pos}_i.
  • 如下 1 行,生成新订单的概率 p_{\mathrm{trans}}^{\mathrm{const}} 以及最后一次可以生成新订单的时间 T_\mathrm{last}.
  • 如下 1 行,未完成订单的处罚 P^{\mathrm{trans}},比例常数 \gamma 外来供电处罚,用电管理参考分数 S_{\mathrm{ele}}^{\mathrm{ref}},以及运输 S_{\mathrm{trans}}^{\mathrm{ref}} 。
  • 最后一行,每个测试用例每次试验的总时间步长 T_{\max} 。

输入和输出格式 2

每次 t,参赛者获得电动汽车和纳米电网的状态 来自标准输入的 \mathrm{info}_t 。

x_1 y_1 \mathrm{pw}_{1}^{\mathrm{actual},t-1} \mathrm{pw}_{1}^{\mathrm{excess},t-1} \mathrm{pw}_{1}^{\mathrm{buy},t-1}
:
x_{N_\mathrm{grid}} y_{N_\mathrm{grid}} \mathrm{pw}_{N_\mathrm{grid}}^{\mathrm{actual},t-1} \mathrm{pw}_{N_\mathrm{grid}}^{\mathrm{excess},t-1} \mathrm{pw}_{N_\mathrm{grid}}^{\mathrm{buy},t-1}
\mathrm{carinfo}_1
:
\mathrm{carinfo}_{N_\mathrm{EV}}
N_\mathrm{order}
\mathrm{id}_1 w_1 z_1 \mathrm{state}_1 \mathrm{time}_1
...
\mathrm{id}_{N_\mathrm{order}} w_{N_\mathrm{order}} z_{N_\mathrm{order}} \mathrm{state}_{N_\mathrm{order}} \mathrm{time}_{N_\mathrm{order}}
  • 在 N_\mathrm{grid} 行, i第行表示顶点纳米电网电池的充电容量 x_i is y_i,和 \mathrm{pw}_{i}^{\mathrm{actual},t-1}, \mathrm{pw}_{i}^{\mathrm{excess},t-1},和 \mathrm{pw}_{i}^{\mathrm{buy},t-1} 表示上一个时间步的实际能量平衡、多余的电量丢弃以及外部提供的电量 分别为 t-1。在 t=0, \mathrm{pw}_{i}^{\mathrm{actual},t-1}, \mathrm{pw}_{i}^{\mathrm{excess},t-1},和 \mathrm{pw}_{i}^{\mathrm{buy},t-1} 全部显示为 0.
    请注意 \mathrm{pw}_{i}^{\mathrm{actual},t-1}, \mathrm{pw}_{i}^{\mathrm{excess},t-1},和 \mathrm{pw}_{i}^{\mathrm{buy},t-1} 对应于 \Delta^{\mathrm{grid}}_{\mathrm{gen},t-1}, \Delta^{\mathrm{grid}}_{\mathrm{total},t-1} - \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{\max}-C^{\mathrm{grid}}_{t-1} \right\},和 - \Delta^{\mathrm{grid}}_{\mathrm{total},t-1} - \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{t-1} \right\}分别(参见 纳米电网电池的充电/放电 ).
    如果上次未执行“步骤 2”和“步骤 3” t−1, \mathrm{pw}_{i}^{\mathrm{excess},t-1} 和 \mathrm{pw}_{i}^{\mathrm{buy},t-1} 分别为 0。
  • 如下 N_\mathrm{EV} 组 4 行, i第组 \mathrm{carinfo}_i 表示的状态 i-th EV。详细信息请参阅以下信息。
  • 如下 1 行,截至时间未完成订单数 t N_\mathrm{order} 。
  • 如下 N_\mathrm{order} 行, i第行表示带ID的订单起止点 \mathrm{id_i} 是 w_i 和 z_i分别为,订单的状态为 \mathrm{state}_i 并且订单是当时生成的 \mathrm{time}_1,其中 \mathrm{state}_i=0 表示没有电动汽车拾取它并且 \mathrm{state}_i=1 表示其中一辆电动汽车已取货,但尚未交付。

在这里, \mathrm{carinfo}_i 按以下格式提供。

\mathrm{charge}_i
u_i v_i \mathrm{dist\_from}\_u_i \mathrm{dist\_to}\_v_i
N_{\mathrm{adj},i} a_{i,1} a_{i,2} \ldots a_{i,N_\mathrm{adj}}
N_{\mathrm{order},i} o_{i,1} o_{i,2} \ldots o_{N_{\mathrm{order}, i}}
  • 第一行表示充电容量 i-th EV 是 \mathrm{charge}_i.
  • 第二行表示当前位置 i-th。如果 u_i \ne v_i 成立, i-th EV 处于连接边缘 u_i 和 v_i,以及到顶点的距离 u_i is \mathrm{dist\_from}\_u_i 以及 v_i is \mathrm{dist\_to}\_v_i。如果 u_i = v_i 成立, i-th EV 位于顶点 u_i (在这种情况下,两者 \mathrm{dist\_from}\_u_i 和 \mathrm{dist\_to}\_v_i 显示为 0).
  • 第三行表示有 N_{\mathrm{adj},i} 可能的顶点 i EV通过操作移动 move 和 a_{i,1}, a_{i,2}、\ldots 和 a_{i,N_\mathrm{adj}} 是可能的顶点。
  • 第四行表示有 N_{\mathrm{order},i} 订单放在 i-th EV 和订单 ID 为 o_{i,1}, o_{i,2}, \ldots, o_{N_{\mathrm{order}, i}}.

在响应输入时,要求参赛者输出每个 EV 的操作 每次 \mathrm{command}_i (1 \leq i \leq N_\mathrm{EV}) 每次 t (0 \leq t \lt T_{\max})。每个操作应由新行分隔,并且输出应以新行结束。

\mathrm{command}_{1}
\mathrm{command}_{2}
:
\mathrm{command}_{N_\mathrm{EV}}

在这里, \mathrm{command} 应采用以下格式。有五种可能的操作 每个 EV 的 stay, move w, pickup a, charge_from_grid,和 charge_to_grid 。参赛者应为每个 EV 选择其中一个,并按如下方式在一行中输出:

  • stay
  • move w
  • pickup a
  • charge_from_grid \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}}
  • charge_to_grid \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}}

每个操作都有限制(参见 EV 电动汽车操作 了解详细信息)。当这些约束之一被违反时,法官的行为是不确定的。

输入和输出格式 3

每台电动车运行后 输出 t=T_\mathrm{max}-1 , \mathrm{info}_t at t=T_\mathrm{max} 是通过法官的标准输入提供的(格式为 \mathrm{info}_t 与输入/输出格式2)中写入的格式相同。然后,在下一行,法官给出交通得分 S_{\mathrm{trans}} 和用电管理得分 S_{\mathrm{ele}} 按以下格式添加到标准输入。

S_{\mathrm{trans}} S_{\mathrm{ele}}

输入和输出的约束

  • 以下数字中,描述为 “[浮动]” 以浮点数形式给出,其他以整数形式给出。

每个测试用例开头提供的输入和输出格式1

  • N_{\mathrm{solution}} = 5
  • |V| = 225
  • 1.5 |V| \leq |E| \leq 2 |V|
  • 1 \leq u_{i}, v_{i} \leq |V|, u_i \ne v_i (1 \leq i \leq |E|)
  • 1 \leq d_i \leq \lceil 2\sqrt{2|V|} \rceil (1 \leq i \leq |E|)
  • 图表 G 保证简单且连接。
  • \mathrm{DayType} \in \left\{ 0, 1, 2, 3 \right\}
  • N_\mathrm{div} = 20
  • N_\mathrm{pattern} = 3
  • \sigma^{2}_{\mathrm{ele}} = 100
  • p_{\mathrm{event}} \in \left\{ 0.0, 0.1 \right\} “[浮动]”
  • \Delta_{\mathrm{event}} = 1000
  • -1000 \lt \mathrm{pw}_{i,j}^{\mathrm{predict}} \lt 1000 (1 \leq i \leq N_\mathrm{pattern}, 1 \leq j \leq N_\mathrm{div})
  • N_\mathrm{grid} = 20
  • C_{\mathrm{init}}^{\mathrm{grid}} = 25000
  • C_{\mathrm{max}}^{\mathrm{grid}} = 50000
  • V_{\max}^{\mathrm{grid}} = 800
  • 1 \leq x_i \leq |V| (如果 i \neq j, x_i \neq x_j. 1 \leq i \leq N_\mathrm{grid})
  • 1 \leq \mathrm{pattern}_i \leq N_\mathrm{pattern} (1 \leq i \leq N_\mathrm{grid})
  • N_{\min}^{\mathrm{EV}} = 15
  • N_{\max}^{\mathrm{EV}} = 25
  • N_{\min}^{\mathrm{EV}} \leq N_\mathrm{EV} \leq N_{\max}^{\mathrm{EV}}
  • C_{\mathrm{init}}^{\mathrm{EV}} = 12500
  • C_{\mathrm{max}}^{\mathrm{EV}} = 25000
  • V_{\max}^{\mathrm{EV}} = 400
  • N_{\max}^{\mathrm{trans}} = 4
  • \Delta_{\mathrm{move}}^{\mathrm{EV}} = 50
  • 1 \leq \mathrm{pos}_i \leq |V| (1 \leq i \leq N_\mathrm{EV})
  • p_{\mathrm{trans}}^{\mathrm{const}} = 0.7 “[浮动]”
  • T_\mathrm{last} = 900
  • P^{\mathrm{trans}} = 3000
  • \gamma = 2.0 “[浮动]”
  • S_{\mathrm{ele}}^{\mathrm{ref}} = -1,500,000
  • S_{\mathrm{trans}}^{\mathrm{ref}} = -1,900,000
  • T_\mathrm{max} = 1000
  • 为每个时间步提供输入和输出格式2

    • 1 \leq x_i \leq |V| (如果 i \neq j, x_i \neq x_j. 1 \leq i \leq N_\mathrm{grid})
    • 0 \leq y_i \leq C_{\mathrm{max}}^{\mathrm{grid}} (1 \leq i \leq N_\mathrm{grid})
    • -10000 \lt \mathrm{pw}_{i}^{\mathrm{actual},j} \lt 10000 (1 \leq i \leq N_\mathrm{grid}, -1 \leq j \leq T_\mathrm{max}-2)
    • 0 \leq \mathrm{pw}_{i}^{\mathrm{excess},j} \lt 10000, (1 \leq i \leq N_\mathrm{grid}, -1 \leq j \leq T_\mathrm{max}-2)
    • 0 \leq \mathrm{pw}_{i}^{\mathrm{buy},j} \lt 10000, (1 \leq i \leq N_\mathrm{grid}, -1 \leq j \leq T_\mathrm{max}-2)
    • 0 \leq \mathrm{charge}_i \leq C_{\mathrm{max}}^{\mathrm{EV}} (1 \leq i \leq N_\mathrm{EV})
    • 1 \leq u_i, v_i \leq |V| (1 \leq i \leq N_\mathrm{EV})
    • 0 \leq \mathrm{dist\_from}\_u_i \leq \lceil 2\sqrt{2|V|} \rceil (1 \leq i \leq N_\mathrm{EV})
    • 0 \leq \mathrm{dist\_to}\_v_i \leq \lceil 2\sqrt{2|V|} \rceil (1 \leq i \leq N_\mathrm{EV})
    • 1 \leq N_{\mathrm{adj},i} \leq 5(\mathrm{MaxDegree}) (1 \leq i \leq N_\mathrm{EV})
    • 1 \leq a_{i,j} \leq |V| (1 \leq i \leq N_\mathrm{EV}, 1 \leq j \leq N_{\mathrm{adj},i})
    • 0 \leq N_{\mathrm{order},i} \leq N_{\max}^{\mathrm{trans}} (1 \leq i \leq N_\mathrm{EV})
    • 1 \leq o_{i,j} \leq T_\mathrm{last} (1 \leq i \leq N_\mathrm{EV}, 1 \leq j \leq N_{\mathrm{order},i})
    • 0 \leq N_\mathrm{order} \leq T_\mathrm{last}
    • 1 \leq \mathrm{id}_i \leq T_\mathrm{last} (1 \leq i \leq N_\mathrm{order})
    • 1 \leq w_i \leq |V| (1 \leq i \leq N_\mathrm{order})
    • 1 \leq z_i \leq |V| (1 \leq i \leq N_\mathrm{order})
    • w_i \ne z_i (1 \leq i \leq N_\mathrm{order})
    • \mathrm{state}_i \in \left\{ 0, 1 \right\} (1 \leq i \leq N_\mathrm{order})
    • 0 \leq \mathrm{time}_i \leq T_\mathrm{last} (1 \leq i \leq N_\mathrm{order})

    每个测试用例末尾提供输入和输出格式3

    • S_{\mathrm{trans}} “[浮动]”
    • S_{\mathrm{ele}} “[浮动]”

    输入和输出示例


    注意:此示例旨在解释评委和参赛者如何通过输入和输出进行交互。为了简化说明,一些参数值(例如顶点数)设置得较小,并且它们可能超出输入和输出约束中的范围。例如,顶点数设置为 4 在此示例中但设置为 每个测试用例中的 225 。

    时间步长 法官 参赛者 说明
    1
    4 4
    1 2 1
    2 3 2
    3 4 3
    4 1 1
    0
    2 2 1 0 10
    5 -2
    -4 4
    2 10 20 4
    1 1
    4 2
    2 5 10 2 2 1
    2
    4
    0.5 3
    3 0.5 -100 -100
    4
    
    初始参数值由 Judge 在每个测试用例的开头提供
    线 1: N_{\mathrm{solution}} is 1.
    线 2:图 G 包括 |V| = 4 顶点和 |E| = 4 边缘。
    以下 4 行(行 3 - 线 6) 表示图形的边缘。
    线 3:边缘 1 连接顶点 1 和 2 其距离为 1.
    线 4:边缘 2 连接顶点 2 和 3 其距离为 2.
    线 5:边缘 3 连接顶点 3 和 4 其距离为 3.
    线 6:边缘 4 连接顶点 4 和 1 其距离为 1.
    线 7:此测试用例中的天气模式是 0 “晴朗无倾盆大雨”。
    线 8: N_{\mathrm{div}} is 2, N_\mathrm{pattern} is 2, \sigma^{2}_{\mathrm{ele}} is 1, p_{\mathrm{event}} is 0, \Delta_{\mathrm{event}} is 10.
    以下 2 行(行 9 - 线 10) 表示预测的能量平衡。
    线 9:具有需求模式的纳米电网的预测能量平衡 1 is 5 为 1-st 时间间隔和 -2 为 2-nd 时间间隔。
    线 10:具有需求模式的纳米电网的预测能量平衡 1 is -4 为 1-st 时间间隔和 4 为 2-nd 时间间隔。
    线 11: N_\mathrm{grid} = 2, C_{\mathrm{init}}^{\mathrm{grid}} = 10, C_{\mathrm{max}}^{\mathrm{grid}} = 20 和 V_{\max}^{\mathrm{grid}} = 4.
    线 12:纳米电网 1 位于顶点 1 并且它具有需求模式 1.
    线 13:纳米电网 2 位于顶点 4 并且它具有需求模式 2.
    线 14: N_\mathrm{EV} = 2, C_{\mathrm{init}}^{\mathrm{EV}} = 5, C_{\mathrm{max}}^{\mathrm{EV}} = 10, V_{\max}^{\mathrm{EV}} = 2, N_{\max}^{\mathrm{trans}} = 2,和 \Delta_{\mathrm{move}}^{\mathrm{EV}} = 1.
    以下 2 行(行 15 - 线 16) 表示电动车当时的位置 t=0.
    线 15:电动汽车 1 位于顶点 2 时间 t=0.
    线 16:电动汽车 2 位于顶点 4 时间 t=0.
    线 17: p_{\mathrm{trans}}^{\mathrm{const}} = 0.5 和 T_\mathrm{last} = 3.
    线 18: P^{\mathrm{trans}} = 3, \gamma = 0.5, S_{\mathrm{ele}}^{\mathrm{ref}} = -100 和 S_{\mathrm{trans}}^{\mathrm{ref}} = -100.
    线 19: T_{\max} = 4.
    0
    1 10 0 0 0
    4 10 0 0 0
    5
    2 2 0 0
    2 1 3
    0
    5
    4 4 0 0
    2 1 3
    0
    1
    1 1 4 0 0
    
    move 1
    charge_from_grid 2
    时间输入数据 0 由法官提供。
    第1行:纳米网格顶点的带电容量 1 时间 0 is 10。所有其他三个值在时间上都是无关紧要的 0 并设置为 0.
    第2行:纳米网格顶点的带电容量 4 时间 0 is 10。所有其他三个值在时间上都是无关紧要的 0 并设置为 0.
    以下 4 行(行 3 - 线 6) 指示 EV 的状态 1.
    第3行:EV的充电容量 1 is 5 时间 0.
    第 4 行:EV 1 位于顶点 2 时间 0.
    第5行:有 N_{\mathrm{adj},1} = 2 朝向哪个 EV 的顶点 1 可以“移动”并且顶点是 1 和 3.
    第 6 行:EV 订单数 1 is N_{\mathrm{order},i} = 0.
    以下 4 行(行 7 - 线 10) 指示 EV 的状态 2.
    第7行:EV的充电容量 2 is 5 时间 0.
    第 8 行:EV 2 位于顶点 4 时间 0.
    第9行:有 N_{\mathrm{adj},1} = 2 朝向哪个 EV 的顶点 2 可以“移动”并且顶点是 1 和 3.
    第 10 行:EV 订单数 2 is N_{\mathrm{order},i} = 0.
    第 11 行:有 N_\mathrm{order} = 1 未完成订单。
    第12行:订单的起始和目标顶点 分别为 1 是 1 和 4 。该订单不在任何电动汽车上,并且是在某个时间生成的 0.
    参赛者的输出
    第 1 行:操作 EV 1 向顶点移动 1。如果电动汽车的充电容量 1 小于 1,电动车 1 无法按照操作移动。在这种情况下,EV的充电容量 1 is 5 因此 EV 1 向顶点移动 1 按距离 1 通过消耗电力 1 在下一个时间步骤中。由于连接顶点的边的道路距离 1 和 2 is 1,EV 的位置 1 是顶点 1 在下一个时间步骤中。
    第 2 行:EV 2 通过纳米电网充电 2。此操作不违反约束,因为 EV 2 位于顶点 4 纳米电网所在位置,带电量 2 不超过电动汽车和纳米电网电池的最大充电速度。由于电动汽车的充电容量 2 is 7,小于 EV 的最大充电容量(10),EV 的充电容量 2 is 7 在下一个时间步骤中。
    1
    1 14 5 1 0
    4 6 -4 0 2
    4
    1 1 0 0
    2 2 4
    0
    7
    4 4 0 0
    2 1 3
    0
    1
    1 1 4 0 0
    pickup 1
    charge_from_grid 2
    时间输入数据 1 由法官提供。
    第1行:顶点纳米网格的带电容量 1 时间 1 is 14。实际电量平衡、溢出电量、当时外部供给电量 0 是 5, 1, 0 。
    第2行:顶点纳米网格的带电容量 4 时间 1 is 6。实际电量平衡、溢出电量、当时外部供给电量 0 是 -4, 0, 2 。

    以下 4 行(行 3 - 线 6) 指示 EV 的状态 1.
    第3行:EV的充电容量 1 is 4 时间 1.
    第 4 行:EV 1 位于顶点 1 时间 1.
    第5行:有 N_{\mathrm{adj},1} = 2 朝向哪个 EV 的顶点 1 可以“移动”并且顶点是 2 和 4.
    第 6 行:EV 订单数 1 is N_{\mathrm{order},i} = 0.
    以下 4 行(行 7 - 线 10) 指示 EV 的状态 2.
    第7行:EV的充电容量 2 is 7 时间 1.
    第 8 行:EV 2 位于顶点 4 时间 1.
    第9行:有 N_{\mathrm{adj},1} = 2 朝向哪个 EV 的顶点 2 可以“移动”并且顶点是 1 和 3.
    第 10 行:EV 订单数 2 is N_{\mathrm{order},i} = 0.
    第 11 行:有 N_\mathrm{order} = 1 未完成订单。
    第12行:订单的起始和目标顶点 分别为 1 是 1 和 4 。该订单不在任何电动汽车上,并且是在某个时间生成的 1.
    参赛者的输出
    第 1 行:找到订单 1 电动汽车 1。电动车 1 此操作不消耗电力。
    第 2 行:EV 2 通过纳米电网充电 2。此操作不违反约束,因为 EV 2 位于顶点 4 纳米电网所在位置,带电量 2 不超过电动汽车和纳米电网电池的最大充电速度。由于电动汽车的充电容量 2 is 9,小于 EV 的最大充电容量(10),EV 的充电容量 2 is 9 在下一个时间步骤中。
    2
    1 18 5 1 0
    4 2 -4 0 2
    4
    1 1 0 0
    2 2 4
    1 1
    9
    4 4 0 0
    2 1 3
    0
    2
    1 1 4 1 0
    2 4 1 0 2
    move 4
    pickup 2
    时间输入数据 2 由法官提供。
    第1行:顶点纳米网格的带电容量 1 时间 2 is 18。实际电量平衡、溢出电量、当时外部供给电量 1 是 5, 1, 0 。
    第2行:顶点纳米网格的带电容量 4 时间 2 is 2。实际电量平衡、溢出电量、当时外部供给电量 1 是 -4, 0, 2 。

    以下 4 行(行 3 - 线 6) 指示 EV 的状态 1.
    第3行:EV的充电容量 1 is 4 时间 2.
    第 4 行:EV 1 位于顶点 1 时间 2.
    第5行:有 N_{\mathrm{adj},1} = 2 朝向哪个 EV 的顶点 1 可以“移动”并且顶点是 2 和 4.
    第 6 行:EV 订单数 1 is N_{\mathrm{order},i} = 1 并且订单 ID 为 1.
    以下 4 行(行 7 - 线 10) 指示 EV 的状态 2.
    第7行:EV的充电容量 2 is 9 时间 2.
    第 8 行:EV 2 位于顶点 4 时间 2.
    第9行:有 N_{\mathrm{adj},1} = 2 朝向哪个 EV 的顶点 2 可以“移动”并且顶点是 1 和 3.
    第 10 行:EV 订单数 2 is N_{\mathrm{order},i} = 0.
    第11行:有 N_\mathrm{order} = 2 未完成订单。 分别为
    第12行:订单的起始和目标顶点 分别为 1 是 1 和 4 。订单位于 EV 上并在某个时间生成 0.
    第13行:订单的起始和目标顶点 分别为 2 是 4 和 1 。该订单不在任何 EV 上,并且是在某个时间生成的 2.
    参赛者的输出
    第 1 行:操作 EV 1 向顶点移动 4。如果电动汽车的充电容量 1 小于 1,电动车 1 无法按照操作移动。在这种情况下,EV的充电容量 1 is 4 因此 EV 1 向顶点移动 4 按距离 1 通过消耗电力 1 在下一个时间步骤中。由于连接顶点的边的道路距离 1 和 4 is 1,EV 的位置 1 是顶点 4 在下一个时间步骤中。
    第 2 行:找到订单 2 电动汽车 2。电动车 2 此操作不消耗电力。
    3
    1 17 -1 0 0
    4 6 4 0 0
    3
    4 4 0 0
    2 1 3
    0
    9
    4 4 0 0
    2 1 3
    1 2
    1
    2 4 1 1 2
    stay
    move 1
    时间输入数据 3 由法官提供。
    第1行:顶点纳米网格的带电容量 1 时间 3 is 17。实际电量平衡、溢出电量、当时外部供给电量 2 是 -1, 0, 0 。
    第2行:顶点纳米网格的带电容量 4 时间 3 is 6。实际电量平衡、溢出电量、当时外部供给电量 2 是 4, 0, 0 。
    以下 4 行(行 3 - 线 6) 指示 EV 的状态 1.
    第3行:EV的充电容量 1 is 3 时间 3.
    第 4 行:EV 1 位于顶点 4 时间 3.
    第5行:有 N_{\mathrm{adj},1} = 2 朝向哪个 EV 的顶点 1 可以“移动”并且顶点是 1 和 3.
    第 6 行:EV 订单数 1 is N_{\mathrm{order},i} = 0。由于订单的目标顶点 1 is 4 和电动汽车 1 到达顶点,顺序 1 已交付。
    以下 4 行(行 7 - 线 10) 指示 EV 的状态 2.
    第7行:EV的充电容量 2 is 9 时间 3.
    第 8 行:EV 2 位于顶点 4 时间 3.
    第9行:有 N_{\mathrm{adj},1} = 2 朝向哪个 EV 的顶点 2 可以“移动”并且顶点是 1 和 3.
    第 10 行:EV 订单数 2 is N_{\mathrm{order},i} = 1 订单 ID 为 2.
    第11行:有 N_\mathrm{order} = 1 未完成订单。 分别为
    第12行:订单的起始和目标顶点 分别为 2 是 4 和 1 。订单位于 EV 上并在某个时间生成 2.
    参赛者的输出
    第 1 行:EV 1 保持在同一顶点。
    第 2 行:操作 EV 2 向顶点移动 1。如果电动汽车的充电容量 2 小于 1,电动车 2 无法按照操作移动。在这种情况下,EV的充电容量 2 is 9 因此 EV 2 向顶点移动 1 按距离 1 通过消耗电力 1 在下一个时间步骤中。由于连接顶点的边的道路距离 4 和 1 is 1,EV 的位置 2 是顶点 1 在下一个时间步骤中。
    4
    1 15 -2 0 0
    4 10 5 1 0
    3
    4 4 0 0
    2 1 3
    0
    8
    1 1 0 0
    2 2 4
    0
    0
    3.0 34.0
    时间输入数据 4 由法官提供。
    第1行:顶点纳米网格的带电容量 1 时间 4 is 15。实际电量平衡、溢出电量、当时外部供给电量 3 是 -2, 0, 0 。
    第2行:顶点纳米网格的带电容量 4 时间 4 is 6。实际电量平衡、溢出电量、当时外部供给电量 3 是 5, 1, 0 。
    以下 4 行(行 3 - 线 6) 指示 EV 的状态 1.
    第3行:EV的充电容量 1 is 3 时间 4.
    第 4 行:EV 1 位于顶点 4 时间 4.
    第5行:有 N_{\mathrm{adj},1} = 2 朝向哪个 EV 的顶点 1 可以“移动”并且顶点是 1 和 3.
    第 6 行:EV 订单数 1 is N_{\mathrm{order},i} = 0.
    以下 4 行(行 7 - 线 10) 指示 EV 的状态 2.
    第7行:EV的充电容量 2 is 8 时间 4.
    第 8 行:EV 2 位于顶点 4 时间 4.
    第9行:有 N_{\mathrm{adj},1} = 2 朝向哪个 EV 的顶点 2 可以“移动”并且顶点是 2 和 4.
    第 10 行:EV 订单数 2 is N_{\mathrm{order},i} = 0。由于订单的目标顶点 2 is 1 和电动汽车 2 到达顶点,顺序 2 已交付。
    第11行:有 N_\mathrm{order} = 0 未完成订单。 分别为
    以下 1 线(线 12) 表示交通和电力管理的分数。
    第 12 行:交通得分为 3.0 电力管理是 34.0.
    如何评分:生成两个订单;他们已交付,等待时间为 分别为 3 和 2 。因此,交通得分的计算公式为: (4-3)+(4-2)-0=3.0。在最后一个时间步中,两辆电动汽车的充电容量为 3 和 8 分别为,纳米网格的充电容量为 分别为 15 和 10 。因此,充电容量总量为 36。另外,来自外部的供电总量为 4 (电量 2 被提供给顶点上的纳米网格 4 从外部时间 0 和 1.) 并将金额乘以 从电力管理得分中减去 \gamma 。因此,电力得分计算如下: 36-0.5 \times 4=34.0.

    示例代码 B

    通过以下方式提供了用于在本地参赛者环境中生成输入样本(测试用例)、评分和测试的软件工具包 链接。还提供了适合初学者的示例代码。
    由于发现了小错误,该工具包已更新。 (12月18日)
    也可以在 Windows 上使用的工具包(Cygwin 和 WSL)已发布。还添加了英文版自述文件(简短版本)。与约束相关的错误也已修复。 (12月18日)
    README 英文版(完整版)已发布。此外,日文版自述文件中的一个小错误也已得到修复。 (12月21日)
    该工具包已根据裁判系统中有关提交用Python等编写的源代码的修复进行了更新。此外,还包括了用Python编写的示例代码。使用方法请参阅README。(1月6日)
    工具包已更新。(有关 DEBUG_LEVEL 等的修复)示例代码也已更新。 (1月12日)

    • 输入样本(测试用例)生成器
    • 测试仪
    • 初学者示例代码