面向充电桩时间分配的在线双边拍卖机制设计

摘 要：随着新能源汽车的快速发展，充电时间分配问题成为关注的焦点。现有研究主要集中在根据预先规划的驾驶路线选择充电桩，但对于车主的动态需求却没有提供即时解决方案。为解决该问题，文章首先根据车主的需求量、地理位置以及充电完成度等因素设计了一种需求者优先级函数，然后将充电桩的时间分配问题建模为密封竞价在线双边拍卖，在此基础上，提出了一种真实的交易机制。理论分析证明了该机制不仅满足个体理性、预算平衡，还能够引导供需双方报告真实的到达离开时间以及物品估值。最后通过具体的实验证明了该拍卖机制的实用性和有效性。所提出拍卖机制满足双边市场中交易个体的属性偏好和在线环境的交易特征，为当前的在线充电平台提供了有益的参考。

关键词：充电桩时间分配；在线双边拍卖；优先级函数；机制设计；激励相容；个体理性

中图分类号：F503；U491.1 文献标志码：A DOI：10.13714/j.cnki.1002-3100.2024.18.011

Abstract： With the rapid development of new energy vehicles， the problem of charging time allocation has become the focus of attention. Existing studies mainly focus on charging pile selection based on pre-planned driving routes， but do not provide an immediate solution to the dynamic needs of car owners. In order to solve this problem， this paper first designs a demander priority function based on factors such as the owner's demand， geographical location， and charging completion degree， and then models the charging pile time allocation problem as an online bilateral auction with sealed bidding. On this basis， a real transaction mechanism is proposed. Theoretical analysis proves that this mechanism not only satisfies individual rationality and budget balance， but also guides the supply and demand sides to report the real arrival and departure time and item valuation. Finally， the practicability and effectiveness of the auction mechanism are proved by specific experiments. The proposed auction mechanism satisfies the attribute preferences of transaction individuals in the two-sided market and the transaction characteristics of the online environment， and provides a useful reference for the current online charging platform.

Key words： charging pile time allocation; online bilateral auction; priority function; mechanism design; incentive compatibility; individual rationality

0 引 言

在共享经济和绿色发展理念的大环境下，电动汽车逐步流行起来，我国电动汽车充电桩建设规模呈快速增长趋势。根据中国电动汽车百人会发布的最新数据，至2020年底，全国公共充电桩数量已超过136万个，覆盖了主要城市及沿海省份。截至2022年6月底，我国新能源汽车充电基础设施累计建设量已达到707.5万台，其中充电桩数量占绝大多数。2023年3月份我国公共充电桩继续呈现增长趋势，同比增加了8.9万台，增长了59%。可见，我国充电桩的建设数量和分布不断扩大，建设规模在不断完善和优化，公共充电桩建设正处于高速发展期[1]。及至现在，充电桩的建设数量已经相当可观，关注焦点已逐渐转移到如何优化现有的充电桩与电动车用户的匹配问题。充电桩时间分配是多个充电桩运营商和多个电动车车主参与的双边市场[2]。其中，充电桩运营商拥有充电桩设备，希望将其利用率最大化，以获取收入。电动车车主希望能够获得可靠、高效和方便的充电服务。因此，需设计一个双边拍卖机制合理地分配充电桩的使用时间，以确保每个车主都能在其需求的时间内获得充电服务。

现有充电桩的研究大多是基于规划、预测模型、排队论等方法来进行路径优化问题。如杨玉林等提出将目标优化问题采用加权的方式转化成单目标优化问题[3]，以及梁士栋等[4]提出了一种充电桩选择与电动汽车充电优化的组合模型。然而数学规划法无法解决不同的市场环境和需求变化下的资源配置问题。目前，很多学者设计了各种双边拍卖，并被运用到物流服务交易领域，例如Sun等研究了具有交易成本的多式运输LST问题，并为“一带一路”倡议设置了三种双边拍卖机制[5]。Liang等将数量折扣和合作采购整合到了LST双边拍卖市场当中，显著提高了交易量和社会福利[6]。但上述文献都没有将非价格属性和价格结合起来考虑，故在此基础上Yu等提出了一种B2B真实的多属性多单位双边拍卖电子商务物流服务交易[7]，其采用了交易减少机制来实现公平分配。以及Huang等[8]提出了电子市场的物流采购拍卖，Cheng等[9]提出了易腐供应链的多属性双边拍卖。在上述文章的基础上，Xiao等 [10]针对共享停车位的时间分配问题，提出了两种双边拍卖机制，实现了静态环境下停车位的分配。然而上述拍卖文献中，没有考虑到用户的即时需求，因此我们给充电桩拍卖机制设计者引入了在线拍卖，以降低使用成本，提高效率，促进充电桩时间拍卖市场的信息化水平，增强市场的协调性和规范性。

在线拍卖是一种以市场机制为基础的交易方式，允许竞标人在任意时间通过拍卖平台进行投标，并可以随时离开。在运输服务领域内，王先甲等考虑买卖双方交易单位可在用物品的情形，设计了一种在线双边拍卖机制[11]。Miyashita等设计了针对易腐物品的在线双边拍卖机制，该机制通过减少未知投标人产生的交易失误来提高盈利能力[12]。Gerding为解决汽车司机如何选择停车位问题，设计了两种不同的在线定价机制，并分别验证了两种机制的效率[13]。在经济学领域内， Li等人针对现有拍卖机制的局限性，提出了一种Iaas云在线拍卖机制[14]。王雅娟等针对单边、双边问题，一对多、多对多等问题的不同背景下设计了不同的在线拍卖机制，这些拍卖机制都能及时确定中标人，而投标者可以在任意时间离开和进入拍卖，不受时间的约束[15-16]。Chen等提出了一种弱激励相容的逢低买入在线拍卖机制[17]。Blum针对动态环境下买卖双方仅交易单位物品的双边拍卖市场，提出了满足激励相容的在线出清算法[18]。Bredin基于特性约束，对买卖双方仅交易单位物品的在线双边拍卖问题提出了一般性的框架[19]。在信息科学技术领域内，杜辉等在移动群智感知中提出了基于在线逆向拍卖的在线激励机制，该激励机制能够让用户报告他们的真实到达时间和离开时间以及感知成本[20]。

基于此，本文以充电桩市场充电时间分配为背景，提出了一种在线双边拍卖机制。首先，考虑到电车用户对充电时间需求的突发性和急迫性，设计了一种在动态环境下的投标语言。其次，设计了一款需求者优先级函数，该优先级函数考虑了车主的需求量、充电完成度以及地位位置因素，旨满足车主的需求。然后针对高效率和资源分配目标构建社会福利最大化模型，在该模型的基础上分别设计了分配和支付规则。其中，在分配规则上先计算优先级函数，然后结合建立的数学模型进行具体规则实施；在支付规则中运用VCG支付，从而能够吸引需求者和供应商双方自愿参与，激励他们真实报告。进一步证明了该机制的预算平衡、激励相容经济特性。最后通过实验研究了该机制的实用性和有效性。

1 问题描述与说明

2 在线双边机制设计模型

在充电桩分配中，需求者的优先级确定对于公平高效地满足用户需求至关重要。考虑到充电时间、完成度和距离因素，本文定义了下述需求者优先级函数，以综合确定每个需求者的优先级顺序。

其中充电时间优先级：充电需求越短，优先级越高，以尽快满足充电用户的需求；

完成度优先级：尽量满足即将完成充电任务的用户需求；定义：为时间τ-1之前需求者已经赢得的时间段，代表了其时间利用率；

距离优先级：越靠近停车场的用户优先级越高，以减少需求者的等待时间；。

为权重系数。可以通过数据收集和分析、根据数据的分析和车主的反馈等合理设定权重系数，从而有效地进行充电桩资源分配。

本文具体的数学模型将基于在线双边拍卖机制和优先级函数，旨在确保优先级更高的用户能够获得充电时间的分配。此外，该机制还着重考虑了社会福利的最大化，以满足管理方面的需求。该模型的设计目标是使整个社会的福利最大化，其中社会福利不仅包括供需双方的效益，还包含了拍卖组织者所获得的拍卖盈余。因此，当参与者真实报告其类型时，具体的数学模型如下。

其中式（1）目标函数主要是为了社会福利最大化；式（2）主要是为了让充电桩时间平衡约束，式（3）和式（4）主要是为了限制充电时间所有权交易数量不能超过自身的需求量或者供给量，式（5）是为了满足个体理性约束，式（7）是为了满足机制的预算平衡约束，式（8）是为了满足个体理性约束。

为了防止参与人说谎话，我们需要设计一种满足激励相容性的机制，即当供需双方参与拍卖时，无论他们如何投标，他们必须报告真实类型以获得最大效用。

Guo等[21]指出，不存在同时满足激励相容、个体理性和预算平衡的在线双边拍卖机制，因此本文引用了渐进有效概念，即在参与人足够多的情况下，损失的社会福利是一个有界函数。

3 在线双边拍卖机制

4 在线双边拍卖机制特性

4.1 激励相容性

激励相容说明参与人真实投标自己的估值是弱占优策略，因为参与人都是自私的。此时需求方的门槛价格由该时期内最高投标价格和VCG价格决定，如果谎报低价会遭到淘汰，谎报高价会损失自身的利益。

当供需双方谎报价格，首先考虑供应商情形。

当谎报时，供给者j失败，无法出租自己的充电桩。

当谎报时，供给者j赢得拍卖；此时供给者的效用为，此时的效用为正。

当谎报时，供给者j赢得拍卖，此时供给者的效用为0。

因此对于供给者来说，当他参与拍卖并不知道自己的实际支付价格，只能推断出几种以上可能出现的情形，所以对于供给者来说真实上报自己的投标是弱占优策略。

需求者方面：当谎报时，需求者赢得拍卖，可以获得充电时间；此时需求者的效用为：

当谎报时，需求者失败，无法赢得充电时间。

当谎报时，需求者赢得拍卖，此时需求者的效用为0。

所以对于需求者来说，当他参与拍卖时同样不知道自己的支付价格，因此真实上报投标类型是弱占优策略。

当需求者谎报进入和离开时间，根据支付的定义。

因为，根据支付规则，可以得出。

因此谎报到达和离开时间只会令需求者利益减少。同理，供应商谎报时间也会令自己的利益受损。同时由于，需求者i还会损失在该时间段上的交易机会。因此谎报到达和离开时间带来的效用并大于真实投标带来的效用，所以说该机制是满足时间激励相容的。

因此，供需双方谎报任何类型所获得的效用不大于真实报告类型获得的效用。

综上，不论供需双方真实报告类型是赢标还是失标均不会后悔，真实报告类型是其事后均衡策略，满足事后激励相容性。

4.2 个体理性

个体理性要求参与人参加拍卖的利益非负。在我们的机制中，对于任意需求者来说当他已经在最优分配结果中时，此时＞，此外，所以，需求者的效用非负。对于供给者j来说，当他处于最优分配结果中，此外，所以，供给者的效用非负。并且该机制激励相容，每个参与人都会真实投标自己的估值，因此每个参与人都能获得非负的利益。个体理性的机制可以吸引更多的参与人参加平台举行的拍卖，来获取自身所需要的充电时间。

4.3 预算平衡

所谓预算平衡就是满足；也就是说拍卖平台的收益非负。即考虑需求者的下限价格和供给者的上限价格，若两者之差非负，则平台的收益非负。此时需求者的支付为，供给者的支付为，因为双方的最终成交价格是由价格和门槛价格决定的，VCG机制本身就已经满足了预算平衡，所以我们比较双方门槛价格的大小，进入拍卖的参与双方经过分配机制可得，即。根据激励相容特性得，此外，因此。所以可以得出结论需求者的总支付大于等于供应商的总收入。因此我们可以说我们的机制是事后预算平衡的。

5 数值实验

作为第三方平台的盐城某区域国家电网公司欲使用在线双边拍卖机制最大化利用区域内的充电桩。由于现有在线双边拍卖机制还未应用于充电桩时间拍卖，部分数据来源于随机数据。

车主需在该区域内购买有限个时间单位，根据电网公司数据，其需求范围在[1，24]上选取，地理位置坐标在[1，10]上随机生成，具体投标价格范围在[10，20]上选取。

充电桩在该区域内提供充电时间，根据电网公司数据，其供应范围在[1，24]上选取，地理位置坐标在[1，10]上随机生成。根据国际物流服务平台、中国公路物流运价指数网整车运价，投标价格在[5，15]上随机生成。

采用MATLAB语言实现本文机制，首先针对不同参数取值对需求者效用、供给者效用、平台效用以及社会福利四个方面的影响，然后与现有MTR机制进行对比，比较两者所带来的需求者效用、供给者效用、平台效用以及成功交易量情况。

5.1 比较分析

根据电网数据随机抽取盐城某区内30个车主和20个充电桩，我们利用MATLAB随机生成投标序列。根据市场调查采取三种不同权重下的场景，a.。b.。c.。分别在MATLAB中运行以上三种场景下的拍卖机制。

表2是MATLAB的运行结果，在需求者优先级函数中设置充电完成度的权重较高，将使各方的利益达到最优化。下面进行对ab场景中各方收益的分析。在b场景中，优先级函数的设置主要考虑了距离与需求权重，导致供需双方的收益相对平衡，但整体社会福利较低。接下来，对ac场景进行比较。在c场景中，优先级函数更加重视距离因素，尽管这带来了供需双方利益的微小差异，但平台的利益相对较少。因此，在参数取值时，增大充电完成度权重将为机制带来更多的效用，并且这个结论具有一定的可靠性。

为了研究机制的渐进有效性，笔者计算收益损失率，即未进入拍卖的参与人的收益占总社会福利的比值。我们将场景a中的投标人规模扩大：1）I=500，J=450；2）I=600，J=500；3）I=800，J=700；4）I =1 000，J=900，在以上4种不同规模下运行机制比较收益损失。

根据图1的变化趋势，可以观察到随着参与人规模逐渐增加，社会福利的增加幅度逐渐加大，同时效益损失的比例逐渐减小。基于这些观察结果，可以得出结论，如果市场规模足够大，线上平台可以选择采用本文所提出的机制。

5.2 不同机制的对比

在本节中，我们对两种机制的绩效进行了研究，包括参与者和平台的效用以及交易量。我们进一步比较了上述人数不同的市场规模下，我们的机制与MTR机制性能差异。

图2表明本文机制带来了更高的社会福利。这意味着通过采用本文提出的机制，需求者的利益得到了增加，从而对整个社会福利产生了积极的影响。这样的结果进一步支持了采用本文机制的线上平台在促进社会福利增加方面的有效性。通过合理设置优先级函数进行资源分配，本文机制能够更好地满足需求者的需求，并确保资源的合理分配，从而提高整体的社会福利水平。这种针对优先级和需求的灵活性，使得机制能够更加智能地适应不同用户和不同情境，从而实现了资源的高效利用和社会福利的最大化。

图3表明随着参与人数的增加，两种机制都能够增加需求者的效益。同时，本文机制通过引入需求者优先级函数，能够为需求者带来更多的效用。这是因为本文机制在分配资源时引入需求者优先级函数，更加注重满足需求者的需求，以确保需求者能够获得更多的收益。

图4表明本文机制在面对较大规模市场时，能够更好地促进交易的发生，增加交易量线上平台采用本文机制，能够更有效地协调参与者之间的交易，减少交易摩擦，从而促进更多的交易发生。

图5表明本文机制在支付过程中，供给者的支付金额将限制在其自身的VCG支付以下。这意味着，供给者不需要支付高于其自身评估价值的费用，从而降低了供给者参与的门槛，提高了他们参与拍卖的积极性。这种设置能够在一定程度上激发供给者的主动参与，增加市场竞争，促进资源的合理配置。线上平台采用本文机制，能够吸引更多的供给者参与市场，并使他们从中获得更多的效用。

图6表明在平台收益方面，本文机制更加注重平台收益，在不同人数规模下能够带来比现有机制更多的平台效用。

研究结果表明：与MTR机制相比，我们的机制能够产生更大的社会福利和更多的交易量，从而提高充电桩的使用率和效率，有助于推动电动车产业的发展，促进相关产业链的壮大，从而带动经济增长。另外还吸引更多的托运人和承运人参与在线平台交易；我们的机制倾向于将更多的利润分配给第三方拍卖平台，以保障第三方的利益不受损害；最后，当市场规模足够大时，我们的机制表现出渐进有效性。

6 结 论

现有关于充电桩的问题主要集中在路径优化方面，然而由于现有方法的限制，充电桩问题的解决方案往往无法实时适应车主的即时需求以及现有方法通常将车主视为均质化的群体，忽略了个体之间的差异和个性化需求。为了解决这一问题，本文在特定的假设下提出了一种在线双边拍卖机制，以为车主分配合适的充电桩和使用时间段。该机制具有以下特性。

第一，针对现实环境的用户需求，考虑了车主的需求量、完成度、位置因素，设计了优先级函数，旨在让充电时间完成度优先级更高的车主优先分配，从而实现更高效、更公平的充电桩分配，满足车主的需求，提高整体服务质量。

第二，允许供需双方在任意时间进入和离开拍卖平台，缓解了时间对参与拍卖的限制，节省了双边拍卖的组织成本，从而实现了平台的全天候、全时段的服务。

第三，可以吸引更多的需求者和供应商参加交易，并激励他们披露真实投标，为拍卖平台的发展提供动力。

第四，通过数值实验进一步说明了该机制的渐进有效性以及能够带来的社会福利和各方效用，表明了该机制在充电桩时间分配上是富有效率的。

本研究提出了一种易于实施和高效的在线充电时间拍卖机制，为当前的在线充电平台提供了有益的参考。

参考文献：

[1] SHOUP D C．Cruising for parking[J]．Transport Policy，2006，13（6）：479-486.

[2] VAN OMMEREN J，WENTINK D，DEKKERS J．The real price of parking policy[J]．Journal of Urban Economics，2011，70（1）：25-31.

[3] 杨玉林，肖磊，杨丽，等．电动自行车充电桩安装优化分配方法研究[J]．轻工标准与质量，2022（5）：90-92.

[4] 梁士栋，赵勍，何建佳，等．共享充电桩下负荷时间分布均衡的小区电动汽车充电方案优化[J]．计算机应用研究，2022，39（12）：3688-3693.

[5] SUN Jiasen，LI Guo，XU Suxiu，et al．Intermodal transportation service procurement with transaction costs under belt and roadinitiative[J]．Transportation Research Part E：Logistics and Transportation Review，2019，127：31-48.

[6] LIANG Renchao，WANG Junwei，HUANG Ming，et al．Truthful auctions for e-market logistics services procurement withquantity discounts[J]．Transportation Research Part B：Methodological，2020，133，165-180.

[7] YU Hao，HUANG Min，CHAO Xiuli，et al．Truthful multi-attribute multi-unit double auctions for B2B e-commercelogistics service transactions[J/OL]．Transportation Research Part E：Logistics and Transportation Review，2022，164：102814.[2023-12-11].https：//doi.org/10.1016/j.tre.2022.102814.

[8] HUANG G Q，XU Suxiu.Truthful multi-unit transportation procurement aud2d41f9a15016ed1f2356bef5ee76cc6ctions for logistics e-marketplaces[J].Transportation Research Part B：Methodological，2013，47：127-148.

[9] CHENG Meng，XU Suxiu，HUANG G Q．Truthful multi-unit multi-attribute double auctions for perishable supply chaintrading[J]. Transportation Research Part E：Logistics and Transportation Review，2016，93：21-37.

[10] XIAO Haohan，XU Meng，YANG Hai．Pricing strategies for shared parking management with double auction approach：Differential pricevs.uniform price[J/OL]．Transportation Research Part E：Logistics and Transportation Review，2020，136：101899.[2023-12-12]．https：//doi.org/10.1016/j.tre.2020.101899.

[11] 王先甲，殷红．一种激励相容的电力市场双边拍卖机制[J]．电力系统自动化，2004，28（18）：9.

[12] MIYASHITA K．Online double auction mechanism for perishable goods[J]．Electronic Commerce Research and Applications，2014，13（5）：355-367.

[13] GERDING E H，STEIN S，ROBU V，et al．Two-sided online markets for electric vehicle charging[C]//Proceedings of the 2013international conference on Autonomous agents and multi-agent systems．International Foundation for Autonomous Agents and MultiagentSystems，2013：989-996.

[14] LI Juan，ZHU Yanmin，YU Jiadi，et al．Online auction for IaaS clouds：Towards elastic user demands and weighted heterogeneousVMs[J].IEEE Transactions on Parallel and Distributed Systems，2018，29（9）：2075-2089.

[15] 王雅娟，王先甲．多单位组合拍卖在排污权初始分配中的应用[J]．中国农村水利水电，2015（9）：194-197.

[16] 王雅娟，王先甲．一种激励相容的多单位在线双边拍卖机制[J]．管理科学学报，2015，18（8）：1-11.

[17] CHEN Hsiu-lang，PENNACCHI G G．Does prior performance affect a mutual fund's choice of risk？ Theory and furtherempirical evidence[J]． Journal of Financial and Quantitative Analysis，2009，44（4）：745-775.

[18] BLUM A，SANDHOLM T，ZINKEVICH M．Online algorithms for market clearing[J]．Journal of the ACM（JACM），2006，53（5）：845-879.

[19] BREDIN J L，DUONG Q，PARKES D C．Chain：A dynamic double auction framework for matching patient agents[J]．Journalof Artificial Intelligence Research，2007，30：133-179.

[20] 杜辉，李卓，陈昕．基于在线双边拍卖的分层联邦学习激励机制[J]．计算机科学，2022，49（3）：23-30.

[21] GUO Jiantao，ZHANG Juliang，CHENG T C E，et al．Truthful double auction mechanisms for online freight platforms withtransaction costs[J]．Transportation Research Part B：Methodological，2022，158：164-186.