面向充電樁時間分配的在線雙邊拍賣機制設計

摘 要：隨著新能源汽車的快速發展，充電時間分配問題成為關注的焦點。現有研究主要集中在根據預先規劃的駕駛路線選擇充電樁，但對于車主的動態需求卻沒有提供即時解決方案。為解決該問題，文章首先根據車主的需求量、地理位置以及充電完成度等因素設計了一種需求者優先級函數，然后將充電樁的時間分配問題建模為密封競價在線雙邊拍賣，在此基礎上，提出了一種真實的交易機制。理論分析證明了該機制不僅滿足個體理性、預算平衡，還能夠引導供需雙方報告真實的到達離開時間以及物品估值。最后通過具體的實驗證明了該拍賣機制的實用性和有效性。所提出拍賣機制滿足雙邊市場中交易個體的屬性偏好和在線環境的交易特征，為當前的在線充電平臺提供了有益的參考。

關鍵詞：充電樁時間分配；在線雙邊拍賣；優先級函數；機制設計；激勵相容；個體理性

中圖分類號：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.