1 配对问题

设有非空有限集合S_N, S_M, 其中N, M分别是S_N, S_M中元素的个数，即|S_N|=N; |S_M|=M, N≥M；对于集合S_M中的每一个元素x∈S_M，存在从S_M到S_N的多值映射ϕ(x)⊂S_N, x∈S_M, 满足：∀x∈S_M，∀y∈ϕ(x)，y∈S_N，并且∀x∈S_M，ϕ(x)是S_N中的非空子集。

提出的问题是：是否存在从集合S_M到集合S_N中的一一对应映射Φ，满足∀x∈S_M，Φ(x)∈S_N，Φ(x)∈ϕ(x)，即是否可以把S_M中的元素与S_N中的元素进行配对，使得每一个x∈S_M在S_N中的配对y∈S_N都是ϕ(x)⊂S_N中的某个元素。

目前在基于物联网的电动汽车快速充电有序预约调度问题，就是这样的配对问题。而且，在同一时段内满足最大数量的电动汽车成功预约到充电站并完成快速充电的问题，同时也是一个提高充电市场中需求方与供给方尽可能达成最多交易数量的经济问题。

在电动汽车有序充电调度优化方面，降低配电网网损是当前现有主要的考虑。胡泽春等^[1](2012)指出，在应对电动汽车规模化发展方面，研究电动汽车大规模接入电网的影响与控制问题具有十分重要的意义。这方面，国外研究较为丰富。例如，在Masoum^[2](2011)提出的电动汽车分类分时段进行充电以实现削峰填谷和网损最小化目标的充电地点优化基础上，Deilami^[3](2011)开展了实时协调并实现网损最小化目标的电动汽车充电优化研究。与这些研究有所不同，Wayes^[4](2012)采用博弈分析的方法对电动汽车充电的经济性问题进行了讨论，尤其是对电动汽车与智能电网互动的博弈均衡进行了分析。针对后者，Samadi^[5](2010)则提出了一个实时定价算法。在有序充电调度的另一方面，Pan^[6](2010)则提出了电池更换站优化选址的方法。

国内电动汽车有序充电调度的研究已有一些探索。鉴于电动汽车充电对电网造成的影响(马玲玲等，2013)^[7]，万路路等(2011)^[8]从配电网网损与电压水平2个方面分析了无序与优化情景下的差异情况。占恺峤等(2012)^[9]以考虑降损作为目标对电动汽车有序充电优化问题进行了研究。田文奇等(2012)^[10]则以换电站充电功率为控制对象，提出了平稳负荷波动的有序充电调度策略。徐臣等(2011)^[11]和张海龙等(2011)^[12]还分别就电动汽车充电基础设施运营模式以及充换电服务网络的运营管理进行了研究，均提出了初步的设想与框架。总体上，现有研究主要是从电网利益诉求出发，以考虑降低电网网损为最优目标。实质上，电动汽车有序充电调度问题，是一个涉及电网侧和用户侧双方的优化问题，除了实现电网侧的优化外，也需要实现用户侧的优化，只有如此才能实现多方协同均衡。针对将物联网技术应用到快速充电有序调度方面的文献还较为少见，杨永标等(2010)^[13]给出了通过物联网协调电动汽车有序充电的技术可能性。

未来，电动汽车得到普及，一个城市区域内，可能通过物联网信息平台对进入该区域的电动汽车快速充电进行实时的统一有序预约调度。某时刻，物联网信息平台知晓进入该区域的所有电动汽车以及它们的电池里面的存留电能情况。这从技术层面来看具有一定的现实可行性(唐慧强，薛飞等^[14-15])。物联网信息平台向它们发出询问：是否尽快进行快速充电？在这里，所谓“尽快”进行快速充电，是指电动汽车现在不打算进行其他的工作，而是寻找充电站进行快速充电。如果有一些电动汽车的回复是“是的”，则物联网信息平台将把这些电动汽车与该区域内的充电站进行快速充电预约。假设该区域内有N个充电站，每一个充电站i将在Δ_i(i=1, …, N)时间后结束现有正在进行的充电和正在排队的所有电动汽车的充电，从而可以为新到达该充电站的电动汽车进行充电。根据目前的技术水平，电动汽车快速充电将电池充满，一般需要30 min左右。

设E＞Δ_i, i=1, …, N，如果被预约的电动汽车在充电站等待了时间E后还未能到达预约的充电站(可能是因为堵车)，则物联网信息平台就将该电动汽车的原定预约取消，而该电动汽车需要重新进行下一轮预约。E的大小设计是仅仅满足一次充电的时间(比如，平均30 min)并且适当留一些时间用于等待(比如，30 min＜E＜60 min)。当然，每一个正在充电的电动汽车所需要的充电时间可能并不相同(与剩余电量以及拟充电量的多少有关)，这意味着充电站并不是在同一时间提供充电服务并在同一时间结束服务，从而会影响到下一轮可用于匹配的充电站的集合，但对本轮充电站集合不会造成影响。另外，假设一个平均的时间段E，有利于将该时间段内可提供服务的充电站以及需要充电服务的电动汽车纳入到同一轮次的预约匹配当中，能够降低预约计算的频度，促进有序充电的统筹安排。当然，时间段E的安排也将会影响到部分充电站的等待时常问题。因此，最优E的设计，将需要在实验模拟以及实际数据的基础上予以调试和深入研究。鉴于本问题的复杂性，仅假设一个平均的时间E。

因此，定义第一轮的预约是预约在所有充电站结束目前正在进行的，以及正在进行排队的电动汽车充电结束后的E时间段内进行的充电。不难得出，每一轮进入预约安排的充电站的集合将是全部充电站集合的子集，而且不同轮次下的充电站集合可能并不相同。如果预约的电动汽车被预约到充电站Δ_i充电，并且它在该充电站结束已有的即上一轮预约的充电完成后的不迟于时间E内到达该充电站，则充电站就按照预约为其充电，否则，就取消协议，把该电动汽车放到下一轮预约中去(该迟到的电动汽车被取消预约协议后需要重新申请预约)。

至于第二轮预约应该在何时开始进行，有多种考虑。譬如，可以在第一轮预约结束后的一段时间开始，而这段时间是上一轮预约的电动汽车最早结束充电的时间，也可以是上一轮预约的电动汽车最早结束充电的时间，也可以是这两者之间的某个时间。还可以是第一轮预约后的某个固定的时间段后的时刻。这里面的优化问题还有待进一步研究。假设该城市区域规定的汽车行驶速度为s。如果一个申请第一轮快速充电的电动汽车m，按照行驶速度s以及最方便的路线，能够在某充电站i完成上一轮预约充电的E时间段之前到达该充电站，记这样的充电站构成的集合为C_m，而其中的元素为c_mj∈C_m, m=1, …; j=1, …，c_mj是一个申请第一轮快速充电的电动汽车m，按照行驶速度s和最短路线，能够在完成上一轮预约充电的E时间段之前到达的第j个充电站。称C_m为电动汽车m“可行的充电站集合”，假设集合C_m非空。记所有申请充电的电动汽车集合为S_M, 其中M=1, …; M≤N是申请充电的电动汽车的数量。所有充电站集合为S_N，其中N=1, …是充电站的数量。

记多值映射ϕ :ϕ(m)=C_m⊂S_N。

问题是，假设该区域所有充电站的集合C。一般地，一个充电站有多个快速充电的插口，可以把同一个充电站的不同充电插口视为不同的充电站。如果目前时刻有M辆电动汽车申请尽快进行快速充电，该城市区域有N个充电站，是否存在一种预约的调度方案，将申请第一轮预约充电的所有电动汽车与某个充电站预约。即是否存在1-1对应的映射Φ，使得

$ \mathit{\Phi }\left( m \right) \in C,\mathit{\Phi }\left( m \right) \in {C_m},m = 1, \cdots ,M。$

(1)

2 解的存在性定理与算法

这样的配对问题看起来似乎比较平凡。譬如，将S_M中的每一个元素x与其映像集ϕ(x)中任意元素y∈ϕ(x)配对。但是，这样的配对可能不是1对1的，因为可能有ϕ(x₁)∩ϕ(x₂)≠ϕ, x₁≠x₂, ϕ表示空集。这种任意的配对可能导致S_M中不同的元素与S_N中相同的元素配对在一起。

如表 1所示，进入该城市物联网感知的电动汽车有2辆，1和2他们现在都申请尽快进行快速充电。该城市有2个充电站，A和B。假定E=40 min，即该城市规定充电站的等待时间不超过10 min。充电站A将在10 min后完成正在进行的充电，开始提供接下来的第一轮的充电服务；充电站B将在15 min后成正在进行的充电，开始提供接下来的第一轮的充电服务。

即使走该城市最短路线，电动汽车1目前按照城市限速的正常行驶速度到达充电站A需要时间为10分钟，到达充电站B需要时间15 min；电动汽车2目前按照城市限速的正常行驶速度到达充电站A需要时间为20 min，但是它目前按照城市限速的正常行驶速度到达充电站B需要时间65 min，不能够在充电站B享受的第一轮充电服务。

显然，C={A, B}, C₁={A, B}, C₂={A}。

如果物联信息平台简单地将电动汽车1预约到充电站A(也许考虑到电动汽车1到充电站A需要的时间比到充电站B的时间要短5 min)，那么，电动汽车2就不能够在第一轮享受任何充电服务，只有预约第二轮充电。但是，如果将电动汽车1预约到充电站B，将电动汽车2预约到充电站A，则两辆汽车都可以享受到第一轮的充电服务。因此，第二种预约方案是比较好的，它可以让现在所有的申请都得到预约。第二种方案为最优预约。

问题是，这种最优预约是否是普遍存在的？如果存在，如何计算出最优预约方案？

下面将证明的定理给出了肯定的答案。

如果存在2辆电动汽车m₁, m₂，它们的可行的充电站集合里面都仅仅含有相同的同一个充电站，即

$ {c_{{m_1}}} = {c_{{m_2}}} = \left\{ A \right\}, $

(2)

则称电动汽车m₁, m₂构成一个“拥挤集”{m₁, m₂}。

显然，在存在拥挤集的情形，电动汽车m₁, m₂不可能在相同的一轮充电服务中同时获得充电服务。因为根据假设，同一个充电站在同一轮服务中仅仅接待一辆电动汽车的充电申请(现实中的充电站可能有多个充电插口，将同一个充电站不同的充电插口形假定为不同的充电站)，下面的定理将存在拥挤集的情形剔除。因为如果电动汽车m₁, m₂构成一个“拥挤集”，物联网信息平台可以将其中的任意一辆电动汽车(m₁或者m₁m₂)的申请拒绝，通知它在下一轮充电服务中重新申请。这样就将该拥挤集{m₁, m₂}剔除了。

显然，撇开基于物联网协调的电动汽车有序快速充电这样的应用背景，可类似地定义拥挤集的概念。

定义  如果在集合S_M中存在元素x₁, x₂，满足ϕ(x₁)=ϕ(x₂)={y}则称x₁, x₂构成一个“拥挤集”{x₁, x₂}。

更一般地，如果集合S_M在完成某一次配对之后，在剔除S_M和S_N中已经配对电动汽车与充电站元素后，余下构成的电动汽车集合即S_M的子集仍不存在拥挤集，那么就称集合S_M不是拥挤的。

定理  如果集合S_M不是拥挤的，则存在从集合S_M到集合S_N中的一一对应映射Φ，满足∀x∈S_M, Φ(x)∈S_N, Φ(x)∈ϕ(x)。

证明：  下面的证明不仅证明了定理为真，而且同时还给出了具体的计算最优预约的方案，即给出了具体的算法。

为了在下面的证明中有一些直观背景，称S_M中的元素x为“电动汽车x”，称S_N中的元素为“充电站y”。

定义任意的组对(y, x), y∈ϕ(x), x∈S_M为一个“可行预约”。在现实的电动汽车充电预约中意味着把电动汽车x与充电站y进行预约。定义B(x)={(y, x), y∈ϕ(x)}为“x的可行预约集”，其中x∈S_M。

定义集合B_M={(y, x), y∈ϕ(x), x∈S_M}为“可行的预约集”或者“N个充电站和M辆电动汽车预约问题的可行预约集”。

在电动汽车有序预约快速充电的情形，如果把电动汽车x与充电站y₁进行预约，则其他充电站y, y≠y₁, y∈ϕ(x)对于电动汽车x来说就没有意义了，同时，充电站y₁也不会在同一轮充电服务中接受其他电动汽车的预约了。这意味着，一旦电动汽车x与充电站y₁进行预约，组队集合

$ \phi \left( x \right)\left| {_{{y_1}}} \right. = \left\{ {\left( {y,x} \right),y \ne {y_1},{y_1},y \in \phi \left( x \right)} \right\}, $

(3)

以及

$ \begin{array}{*{20}{c}} {{\rm{ \mathsf{ π} }}\left( {{y_1}} \right) = }\\ {\left\{ {\left( {{y_1},x'} \right),{y_1} \in \phi \left( x \right),x' \ne x,x',x \in {S_M}} \right\}。} \end{array} $

(4)

当中的任何元素就不会成为预约了。

记电动汽车x与充电站y₁进行预约后，余下的可行预约集为

$ {B_{x,M - \delta \left( {{y_1}} \right)}} = {B_M} - \phi \left( x \right)\left| {_{{y_1}}} \right. - {\rm{ \mathsf{ π} }}\left( {{y_1}} \right), $

(5)

其中，余下的可行预约集B_{x, M-δ(y1)}为有M-δ(y₁)辆电动汽车申请预约，有N－1个充电站的相同问题的可行预约集。因为，一旦电动汽车x与充电站y₁进行预约，充电站y₁就不能够与其他电动汽车进行预约了，所以余下的充电站减少了一个。因为电动汽车x与充电站y₁已经进行了预约，它就不需要考虑与其他充电站的预约问题了，因此需要预约的电动汽车数量至少减少了1辆。这里假定需要预约的电动汽车数量减少了δ(y₁)辆。

记可行预约(y₁, x₁)满足

$ \left| {{B_{{x_1},M - \delta \left( {{y_1}} \right)}}} \right| = \max \left| {{B_{x,M - \delta \left( y \right)}}} \right|, $

(6)

其中y₁∈ϕ(x₁), y∈ϕ(x)。

其中|S|表示有限集合S中元素的个数。如果满足这种条件的可行预约(y₁, x₁)不止一个，记所有满足这种条件的可行预约的集合为Λ。在Λ中任意挑选出一个可行预约(y₁, x₁)进行预约。将证明余下的可行预约集B_x1, _M－δ(y1)是一个有N－1个充电站和M－1辆电动汽车预约问题的可行预约集。

事实上，前面已经知道在完成(y₁, x₁)的预约后，余下的充电站为N－1，并且余下的等待预约的电动汽车至少减少了1辆，所以δ(y₁)≥1；如果δ(y₁)＞1，则至少存在某个x₂，使得(y₁, x₂)是可行的预约，并且ϕ(x₂)={y₁}, |ϕ(x₂)|=1，同时，(y₁, x₁)满足式(1)意味着| ϕ(x₂)|+1≥|ϕ(x₁)|+1，否则(y₁, x₁)不会满足式(1)。于是| ϕ(x₂)|≥ |ϕ(x₁)|≥1，| ϕ(x₁)|=1。这就意味着(x₁, x₂)是拥挤集，与假定矛盾。所以，必然有δ(y₁)=1。因此，余下的可行预约集B_x1, _M－δ(y1)是一个有N－1个充电站和M－1辆电动汽车预约问题的可行预约集。

令Φ(x₁)=y₁。

接下来，重新把上述操作应用于余下的可行预约集B_{x1, M－1}；也就是说，在余下的可行预约集B_{x1, M－1}中，完成(y₁, x₁)配对之后，原有电动汽车集合S_M变为S_M－1，且S_M－1⊂S_M，且S_M－1中任何电动汽车的可行预约集均不会包含充电站y₁。根据定理条件，此时S_M－1依然不存在任何拥挤集，因此可以重复上一步操作过程。假设可以找到x₂ ≠x₁ ，y₂ ≠y₁ , (y₂ , x₂ )是可行的预约，令Φ(x₂)=y₂。

以此类推，每一步都将申请预约的电动汽车数量减少1辆，充电站也减少1个。因为M≤N都是有限的自然数，所以必然在第M步之后把所有的电动汽车都完成预约。即函数Φ在S_M中所有的元素x上都有了定义。也就是说，定义了函数Φ：Φ(x_i)∈S_N, x_i∈S_M, i=1, …, M。

根据上述算法，显然有Φ(x_i)≠Φ(x_j)⇔x_i≠x_j，i≠j, i, j=1, …, M，即函数Φ是一一对应的映射。

证毕。

应用这个定理提供的算法，来计算上面那个例子的最大化充电车辆的预约。

显然，x₁=1，y₁=B，x₂=2，y₂=A；或者x₁=2，y₁=A，x₂=1，y₂=B。这说明最优解可能不是唯一的。

研究提出的算法是一种递归算法，每一步都是把余下的可行预约集的元素最多的那个预约进行预约，所以可以称为“最大可行预约余集预约法”。

3 算例

下面给出1个算例，该算例要比上述例子复杂一些。

某个城市的物联网协调电动汽车的空间区域里面有6个充电站A, B, C, D, E, F。需要指出的是，本处所致的充电站，实质上是充电位，即在同一时段只能供1辆电动汽车充电之用，而且在之后的轮次当中可提供充电服务的充电站可能并不完全与本轮一致。同时，目前有5辆电动汽车申请尽快充电。假设第一轮充电时间(包括等待时间)平均为E=40 min，亦即假设本轮预约自开始到结束持续40 min。因此，每一个充电站将提供第一轮充电服务的时间由下面的表 2给出。根据表 2，6个充电站完成正在进行的充电所需的时间均小于E，因此该6个充电站全部属于本轮可接受预约的充电站的集合。下面的表 3给出每一辆电动汽车按照城市限速走最短路线并考虑路线一般拥堵时间的情形下，预计到达各个充电站将要花去的时间，而且当前剩余电量能够支撑其在预估时间内到达某一充电站，否则预估时间设定为∞。

由此可知，每个电动汽车的可行预约集为

$ \left. \begin{array}{l} \phi \left( 1 \right) = \left\{ {A,B,C,D,E,F} \right\}\\ \phi \left( 2 \right) = \left\{ {A,B,C,D,E,F} \right\}\\ \phi \left( 3 \right) = \left\{ {A,B,C,E,F} \right\}\\ \phi \left( 4 \right) = \left\{ {A,D,E,F} \right\}\\ \phi \left( 5 \right) = \left\{ {A,B,C,D,E,F} \right\} \end{array} \right\}, $

(7)

$ \left. \begin{array}{l} \left( {A,1} \right),\left( {B,1} \right),\left( {C,1} \right),\left( {D,1} \right),\left( {E,1} \right),\left( {F,1} \right)\\ \left( {A,2} \right),\left( {B,2} \right),\left( {C,2} \right),\left( {D,2} \right),\left( {E,2} \right),\left( {F,2} \right)\\ \left( {A,3} \right),\left( {B,3} \right),\left( {C,3} \right),\left( {E,3} \right),\left( {F,3} \right)\\ \left( {A,4} \right),\left( {D,4} \right),\left( {E,4} \right),\left( {F,4} \right)\\ \left( {A,5} \right),\left( {B,5} \right),\left( {C,5} \right),\left( {D,5} \right),\left( {E,5} \right),\left( {F,5} \right) \end{array} \right\}。$

(8)

按照定理给出的算法，如果预约匹配电动汽车1与充电站A，则余下的可行预约集中有17个预约；如果预约匹配电动汽车1与充电站B，则余下的可行预约集中有18个预约；如果预约匹配电动汽车1与充电站C，则余下的可行预约集中有18个预约；如果预约匹配电动汽车1与充电站D，则余下的可行预约集中有18个预约；如果预约匹配电动汽车1与充电站E，则余下的可行预约集中有17个预约；如果预约匹配电动汽车1与充电站F，则余下的可行预约集中有17个预约。

由于电动汽车2的可行预约集合与电动汽车2相同，所以类似的结果也成立。当然还有电动汽车5也一样。下面就看看电动汽车3和4。

如果预约电动汽车3与充电站A, 则余下的可行预约集中有17个预约；如果预约电动汽车3与充电站B, 则余下的可行预约集中有19个预约；如果预约电动汽车3与充电站C, 则余下的可行预约集中有19个预约；如果预约电动汽车3与充电站E, 则余下的可行预约集中有17个预约；如果预约电动汽车3与充电站F, 则余下的可行预约集中有18个预约。

如果预约电动汽车4与充电站A, 则余下的可行预约集中有19个预约；如果预约电动汽车4与充电站D, 则余下的可行预约集中有20个预约；如果预约电动汽车4与充电站E, 则余下的可行预约集中有19个预约；如果预约电动汽车4与充电站F, 则余下的可行预约集中有19个预约。

显然，有x₁=4；首先预约的是电动汽车4与充电站D.余下的可行预约集为

$ \left. \begin{array}{l} \left( {A,1} \right),\left( {B,1} \right),\left( {C,1} \right),\left( {E,1} \right),\left( {F,1} \right)\\ \left( {A,2} \right),\left( {B,2} \right),\left( {C,2} \right),\left( {E,2} \right),\left( {F,2} \right)\\ \left( {A,3} \right),\left( {B,3} \right),\left( {C,3} \right),\left( {E,3} \right),\left( {F,3} \right)\\ \left( {A,5} \right),\left( {B,5} \right),\left( {C,5} \right),\left( {E,5} \right),\left( {F,5} \right) \end{array} \right\}。$

(9)

电动汽车1与任何充电站预约后的可行余集元素数量都是12；电动汽车2与任何充电站预约后的可行余集元素数量都是12；电动汽车3与任何充电站预约后的可行余集元素数量都是12；电动汽车5与任何充电站预约后的可行余集元素数量都是12。

这时候可以任意令x₂=1，预约的是电动汽车1与充电站A，余下的可行预约集为

$ \left. \begin{array}{l} \left( {B,2} \right),\left( {C,2} \right),\left( {E,2} \right),\left( {F,2} \right)\\ \left( {B,3} \right),\left( {C,3} \right),\left( {E,3} \right),\left( {F,3} \right)\\ \left( {B,5} \right),\left( {C,5} \right),\left( {E,5} \right),\left( {F,5} \right) \end{array} \right\}。$

(10)

电动汽车2与任何充电站预约后的可行余集元素数量都是6；

电动汽车3与任何充电站预约后的可行余集元素数量都是6；

电动汽车5与任何充电站预约后的可行余集元素数量都是6。

这时候可以任意令x₃=2，预约的是电动汽车2与充电站B，余下的可行预约集为

$ \left. \begin{array}{l} \left( {C,3} \right),\left( {E,3} \right),\left( {F,3} \right)\\ \left( {C,5} \right),\left( {E,5} \right),\left( {F,5} \right) \end{array} \right\}。$

(11)

类似地，这时候可以任意令x₄=3，预约的是电动汽车2与充电站C，余下的可行预约集为

$ \left\{ {\left( {E,5} \right),\left( {F,5} \right)} \right\}。$

(12)

这时候可以任意令x₅=5，预约的是电动汽车2与充电站E。这样，就获得一个解。预约配对是

$ \left. \begin{array}{l} 1 \Leftrightarrow A\\ 2 \Leftrightarrow B\\ 3 \Leftrightarrow C\\ 4 \Leftrightarrow D\\ 5 \Leftrightarrow E \end{array} \right\}。$

(13)

提出的算法在电动汽车快速充电的有序调配中仅仅考虑充电车辆的数量最大化目标。如果进一步考虑快速充电对于电网的影响，包括谐波影响和负荷影响，算法还需要进一步的修改和发展推广。然而，即使是现在提出的这种算法，也可以直接用于考虑了这些影响之后的电动汽车快速充电有序调配。譬如，在每一轮的可行预约过程中，正如上面这个例子中看到的那样，总是有许多可行预约被预约后的余集的元素数量是相等的。这时候可以存在多种挑选可行预约进行预约的选择。借助于计算机的快速运算，可以把每一种挑选方法都用一次，这样就可以得到许多种不同的预约配对结果，而每一种结果都可以通过计算机计算出对于电网的总体影响程度。把每一种配对对应的电网影响评估计算出来后，可以选择最小负面影响的配对进行配对。这样就把影响减少到最低的程度。这也是一种优化的方案。另外，在多个选择的情况下，也可以依据最快到达并实现充电位依据进行优先选择等。借助于计算机的高速运算，其实这样的比较过程在瞬间就完成了。

研究提出的这种算法还可能用于其他的经济管理领域，譬如物流产业中的业务配对。如果一个物流公司接收到若干个在未来某一天的业务项目。公司每一个车队都可以完成某些不同的业务(譬如，跑同一方向的不同运输业务)，则可以用这种算法为公司车队与不同业务项目之间进行配对预约，可以承接最大化的业务数量。