共享经济预约模式下资源分配的拍卖机制设计*

张 静，张骥先，李伟东，刘旭东，张学杰+

1.云南大学 信息学院，昆明 650500

2.云南大学 数学与统计学院，昆明 650500

1 引言

共享经济通过互联网平台将闲置的资源共享给他人，并从中获取一定的金钱回报；对于用户而言，无需购买资源，按需付费租赁即可，是一种新型的经济模式[1-2]。共享经济给人们生活方式带来巨大改变，目前已遍及交通、住宿、餐饮、教育、医疗等领域。其运营模式主要分为预约模式和实时模式。预约模式中，用户事先提出资源需求，待搜集所有用户需求后，由提供商进行资源的租赁分配，用户可在预约时间准时得到服务，如神州专车的预约用车服务。实时模式下用户实时提交需求，系统立即从当前空闲资源中选取最合适的分给用户，如滴滴打车。本文主要研究的是共享经济预约模式下的资源分配与用户定价问题。

在共享经济预约模式中，如何将资源分时租赁给用户使得提供商的收益最大化，是主要研究的问题。但目前的预约模式中，都是采用固定价格及先预约先服务的方式来分配资源，这种方式简洁高效，但随着市场的扩大，存在以下弊端。（1）固定的价格导致提供商收益低下。资源按使用时长收费，虽然会在高峰期调整倍数，但仍没考虑市场实时供需情况，造成资源紧缺时不能提高价格，空闲时没能降价使得资源闲置，收益较低。（2）资源分配不均导致资源利用率低。当用户申请类型与闲置资源类型不符时，导致某些型号资源供不应求，其余却大量闲置。（3）分配产生的碎片时间造成了资源浪费。先预约先服务的方式下，由于用户的使用时间不确定性，产生很多碎片化时间浪费了资源。

拍卖机制是指通过相应的规则和买者竞价来进行资源配置的一种市场机制[3]。将拍卖与共享经济预约服务相结合，通过竞价方式对资源进行全局规划，能实现资源的合理配置；另一方面，拍卖根据相应的规则和市场供需情况动态决定用户支付价格，保证公平性的同时吸引更多的用户参加。

综上，将拍卖应用于共享经济预约模式中，可以解决当前市场分配方式存在的不足。基于此，本文提出一种公平可信的拍卖机制，用于解决共享经济预约模式中资源的分配及用户支付定价问题。该机制适用于按时收费的共享资源在预约模式下做分配，如共享停车位、共享住宿等；也适用于其他按时收费的资源，如云资源分配、医疗诊治预约等。但共享经济市场中还有一些移动的共享资源，其收费与取还点相关，如共享充电宝，这种复杂的情况不在本文考虑范围内。本文贡献如下：

（1）共享经济预约模式的拍卖机制设计：基于共享经济预约模式的特征，抽取出资源表示元数据，构建限制条件下以收益最大化为目标的整数规划模型，同时在机制可信（strategy-proof）的基础上，设计相应的资源分配算法及价格支付算法。

（2）资源分配算法设计：针对共享资源按时间段租赁的特性，设计最优资源分配算法；但最优资源分配算法具有较高的计算复杂度，因此结合关键路径思想，设计单调的启发式资源分配算法，能够在接近最优解的前提下，提高计算效率。

（3）支付价格算法设计：最优机制中，设计基于VCG（Vickrey-Clark-Groves）理论的最优用户定价算法；该算法同样存在计算效率问题，近似机制中提出基于二分法的价格支付求解算法，能够保证在机制可信的必要条件下，提高计算效率。

（4）对提出的拍卖机制进行了严格的理论证明，证明提出的最优和近似机制都是可信的。

本文组织结构如下：第2章介绍相关工作；第3章对共享经济预约模式问题建模；第4章提出最优机制，包括资源的最优分配算法及基于VCG的支付算法；第5章提出启发式机制，用关键路径思想求资源分配，以及二分法求支付价格；第6章设计实验来对比分析各算法；第7章总结全文并提出未来研究方向。

2 相关工作

目前，拍卖机制和共享经济相关问题都已被广泛研究，但将拍卖与共享经济结合起来的研究还较少，相关工作主要分为以下三方面。

第一，共享经济。目前对共享经济的研究较少，大多从经济学理论分析其商业模式及本质等；另一部分是针对共享经济最重要的领域网约车的研究，包括乘客预测、订单匹配、车辆实时调度等，并没有涉及预约模式下资源配置问题。文献[4]利用乘客运动模式及车辆GPS轨迹等来进行乘客预测；文献[5]对用户历史数据建立贝叶斯框架，来预测用户目的地分布，解决出租车与订单更有效匹配的问题；文献[6]开发基于PCA-WNN（principal components analysis wavelet neural network）的适应性机制进行出租车实时调度，但不适用于预约模式。

云资源也是一种动态共享的资源，云提供商已引入拍卖机制用于对云资源进行分配[7-8]；张林等人提出了一个在真实频谱利用率及社会福利间取得权衡的可信拍卖机制，用于对频谱资源拍卖[9]。根据拍卖在其他领域的应用，尝试将拍卖与共享经济结合，通过拍卖提高资源利用率，增加收益。

第二，资源分配。资源分配是实现拍卖机制的必要条件[10]。文献[11]提出了PTAS（polynomial time approximation scheme）强近似机制，用于解决多资源的自主VM（virtual machine）配置问题。文献[12]将Saas提供问题模拟为Stackelberg博弈，转化为求解优化问题来求得分配策略。文献[13]为基于拍卖的动态VM配置问题设计了真实的最优和近似机制。有的工作以绿色云计算为出发点，尽量最小化能源消耗[14]。文献[15]的频谱分配将空间上无冲突的用户分组，对分组团体出价排序并分配资源。用户分组给予本文启发，与文献[15]不同的是，本文按照资源成本降序并对用户分组。文献[16]提出真实的双向频谱拍卖机制，提高频谱利用率。以往拍卖机制的目标大都为社会福利最大化，本文的研究中不同型号资源成本不同，目标为最大化供应商利润。

第三，支付价格。分配完成后，需要合适的价格支付算法保证机制可信。广义第二价格（generalized second pricing，GSP）思想简单，被广泛用于广告关键字拍卖[17]，但GSP不可信，买方会谎报出价来获益。部分研究中基于VCG理论求支付价格[13-14]，本文将VCG用于最优分配中保证可信。Mashayekhy等人提出的近似机制中用二分法求支付，能无限逼近最低获得分配的价格[11]。普通二分法判定条件为用户能否以新价格获得分配，但共享经济中新价格可能让用户分得低成本资源，不够支付已租到的高成本资源，需对二分法进行改进。

以往的研究已经在共享经济、拍卖机制、资源分配、支付价格方面取得了显著的成果，其拍卖应用中用户申请资源只会有分配和不分配两种结果，目标为社会福利最大化；但在共享经济中，用户有多种型号可选择，满足成本价的情况下可以选择高、中、低成本资源，对应的目标也需改为利润最大化；而支付算法需保证用户的支付价格大于所租资源型号的成本价。因此共享经济中资源的分配及用户定价问题与以往的拍卖应用大为不同，本文旨在设计针对共享资源的拍卖机制。

3 问题描述及模型定义

在共享经济的预约模式中，供应商有多种型号的资源，并对应不同的成本价；用户提交预约信息，包括使用时间段及竞价，型号则由系统根据该时段竞争情况及用户竞价决定，以最大化资源利用率。供应商收集所有用户的预约信息后，做出最合理的租赁分配方案以获取最大收益。通过分析共享经济预约模式的特征，对资源及用户预约信息作简一化处理，得到资源表示元数据，并根据共享经济预约模式需满足的约束条件，抽象出整数规划模型。

资源信息定义：假设供应商有m个资源，资源集合为C={1,2,…,m}，对于每一个资源i∈C，对应一个单位时间使用成本价格ei，资源按照成本ei降序排序。目前供应商的资源一般有多种型号（如高、中、低档次的汽车），每种型号有多个资源，每种型号的单价也不同。

用户预约信息定义：假设有n个用户的预约请求，用户按照开始使用时间升序排序，用户集合为U={1,2,…,n}，对于每个用户j∈U，用户的预约信息为qj=(sj,dj,bj)。其中sj为开始使用时间，dj为结束使用时间，bj为竞价。

整数规划模型：资源按照时间段租赁给各用户，分配方案用矩阵X[m][n]表示，其中任意一个元素xij表示的是第i个资源租给第j个用户的状态。当xij=1时，表示i资源分配给第j个用户，使用时间段(sj,dj)。当xij=0时，表示i资源不分给j用户。本文所有矩阵的下标从1开始编号。

目标函数：

约束函数：

以往研究中目标函数都是社会福利最大化，即胜出拍卖用户竞价之和最大。但在共享经济预约模式中，用户可选择满足成本的多种型号的资源，但不同型号下竞价是相同的，社会福利最大无法保证给用户分配到最合适的资源，且易选择使用时间长但利润少的用户。因此目标函数改为利润最大化，才能保证供应商获得最大的收益。最优租赁方案就在满足上述3个约束条件下，使得目标函数最大的分配矩阵X。各约束条件的含义如下：

约束条件（1a）：对于每个用户j，最多只会租到一个资源。约束条件（1b）：j用户的竞价必须大于i资源为其服务的成本，j才有可能租到i资源。约束条件（1c）：在求资源i的租赁分配时，对于任意用户对(j,k)，若j用户和k用户的使用时间段有交集，i最多只能租给一个用户，即xij+xik≤1。

定义1（可信Truthfulness）一个可信的机制必须满足：

即当诚实报价是所有用户的占优策略时，该机制可信[11]。

注：为了区别策略符号∧，标记j用户采取策略为∧1，其他用户集采取策略集合为∧2。

定义2（单调性monotonicity）当用户j∈U在提交竞价bj的情况下参与拍卖，租赁到i资源，若用户j提高竞价为bj′＞bj，则用户j能租赁到与i同成本或者更高成本的资源，则称该资源分配是单调的[11,13]。

定义3（临界值critical value）用户j∈U在提交竞价bj的情况下租到i资源，对于用户j存在一个临界值cvj，当用户改变竞价为bj″，若bj″＞cvj时，用户j才有可能租赁到与i同成本或更高成本的资源，反之一定不满足[11,13]。

引理1一个拍卖机制M={A,P}，当其分配算法A求出的是最优解，支付算法P使用VCG计算，则机制M被证明是可信的[19]。

引理2一个拍卖机制M={A,P}，当其分配算法A满足单调性，支付算法P是基于临界值求解的，则机制M是可信的[18,20]。

4 资源分配和用户定价最优机制

一个拍卖机制，包含资源分配算法完成对资源的优化配置，还要有支付算法计算拍卖胜出用户需要支付的价格。资源分配和用户定价最优拍卖机制包含以下两部分：

（1）最优资源分配算法：得到资源的最优分时租赁分配方案，使得供应商获得最大的利益。

（2）最优用户定价算法：在最优租赁分配方案下，计算每个租到资源的用户需支付的合理价格，以保证机制可信。

4.1 最优资源分配算法

最优资源分配算法，就是要求出资源的最优分时租赁分配方案，该方案下资源最大化利用，供应商利益最大化。根据整数规划模型，用CPLEX求解器编程建立各个约束条件及目标函数。求出资源的最优租赁分配方案，得到拍卖胜出的用户，以及给各用户分配的资源，将各资源按时间段租赁给用户，得到供应商的最大收益。

4.2 最优用户定价算法

在求得资源的最优租赁分配方案的前提下，每个租到资源的用户需支付给供应商相应的费用。VCG理论下，用户的支付价格与自己出价无关，而是由市场决定，激励用户真实报价，保证机制可信。VCG对应的目标函数是社会福利最大化，即胜利用户竞价之和最大化；但在共享经济资源配置中，不同型号资源的成本不同，竞价最大不能保证利润最大，因此目标为供应商利润最大化。而相应的价格算法也需对VCG基础算法进行改进。

没有胜出拍卖的用户支付价格为0，胜出的用户j需要支付的价格为pj，假设j用户租到i资源，又设用户j应该付给供应商的利润为fj，则：

式（2）表示用户j给供应商支付的价格pj为两部分相加，fj是j给供应商的支付利润，ei(dj-sj)是i资源为j提供服务的成本。

基于VCG理论求解支付价格，用户需要支付的费用为他参与拍卖给别的用户带来的损失之和，即用户不参与时的社会福利，减去用户参与时的福利剔除用户竞价[21]。但最优分配中，目标函数为供应商最大化的利润和，对等的，在求解用户j的支付利润fj时应用VCG算法。用户j的预约申请为qj，所有用户的预约请求集合为Q，除去j剩余用户的请求集为Q-j。对所有用户调用最优分配算法为A(Q)，对除去j的用户集调用最优分配算法为A(Q-j)。即支付利润fj计算公式如下：

式（3）严格按照VCG理论计算，每个胜出的用户需要支付的利润值fj为他参与拍卖给别的用户带来的利润损失之和。即fj为两部分相减，YA(Q-j)为j用户不参与拍卖下供应商的利润和；(YA(Q)-(bj-ei(dj-sj)))为用户j参与拍卖时供应商的利润和YA(Q)减去j用户租赁i资源所贡献的利润(bj-ei(dj-sj))。

将式（3）带入式（2）得：

化简式（4）得到：

即pj为两部分相减，YA(Q-j)是j不参与拍卖下的利润和，(YA(Q)-bj)是j参与拍卖下的利润和剔除j的竞价bj。

定理1最优拍卖机制是可信的。

证明最优拍卖机制的最优分配算法中，按照整数规划模型用CPLEX编程求解，遍历了所有分配方案的可能性，找出其中让利润最大的方案，即得到资源分配的最优解；最优用户定价算法是基于VCG计算的。基于引理1，求出最优资源分配方案，并基于VCG理论计算支付价格的拍卖机制是可信的[19]。因此最优拍卖机制是可信的。

5 资源分配和用户定价近似机制RAUPAM

虽然最优机制能求得最优的租赁分配方案，使得供应商的利益最大，但其时间复杂度很高，当用户数目增多时，求解时间呈指数级别增长。因此提出了一种共享经济预约模式下资源分配和用户定价的近似机制RAUPAM（resources allocation and user payment approximation mechanism）。

近似机制包括以下两部分：

（1）资源分配近似算法RAAM（resources allocation approximation mechanism）：根据共享资源分时租赁的数学模型，在满足各个约束条件下，设计单调的启发式资源分配算法，能够在接近最优解的前提下，提高计算效率。

（2）用户定价近似算法UPAM（user payment approximation mechanism）：在求得近似的租赁分配方案后，在保证机制可信的前提下，计算出每个租到资源的用户需要支付的价格。

5.1 资源分配近似算法RAAM

启发式的资源分配近似算法RAAM将资源分时租赁问题转化为资源的时间分配图，将每个资源可租赁的用户按照时间先后链接在图上，复杂的资源调度问题转化为图问题，进而用关键路径思想得到资源最大近似分配。设计算法并满足模型中的三个约束条件：用户只能租到一个资源、租赁需满足成本价、有时间交集的用户不能同时租到同一资源。RAAM的伪代码如算法1所示。

算法1RAAM求解资源分配方案

输入：资源总数m，各资源的单位时间成本ei；用户总数n，所有用户的预约集Q，其中qj=(sj,dj,bj)。

输出：资源租赁分配矩阵X[m][n]，供应商收益Y。

预处理：

1.ei降序排序，给对应资源编号，得到资源集合C={1,2,…,m}，成本集合E={e1,e2,…,em}。

2.Q按照qj中的sj升序排序，得到用户集U={1,2,…,n}与预约信息集Q={q1,q2,…,qn}。

3.X[m][n]初始化所有元素为0，供应商利益Y=0。

4.系统用户集初始U={1,2,…,n}，当前资源用户集U′。

程序：

1.for eachi∈Cdo

2.U′=U

3.for eachp∈U′do

4.Ifei(dp-sp)≥bpthen

5.U′p/*剔除竞价≤成本的用户*/

6.end if

7.end for

8.R[n+2][n+2]={0}/*初始化所有元素赋0*/

9.for eachj∈U′do

10.R[0][j]=bj-(dj-sj)ei

11.end for

12.for eachj∈U′do

13.for eachk＞jandk∈U′do

14.ifdj≤skthen /*j和k无时间交集*/

15.R[j][k]=bk-(dk-sk)ei=R[0][k]

16.end if

17.end for

18.end for

19.R[n+2][n+2]调用关键路径算法，求得0到(n+1)的关键路径长度赋值给yi

20.Y=Y+yi

21.for each 关键路径除0和(n+1)外涉及的节点jdo

22.xij=1

23.U j/*从系统可用用户中删除j*/

24.end for

25.end for

26.returnY,X[m][n]

RAAM算法将资源按成本降序排序，优先分配成本高的资源，其淘汰的用户还能继续租到低成本资源，最大化资源利用率；且给用户优先分配高成本型号，提高了用户满意度。U存放系统当前可用用户，更新筛选掉已租到资源的用户，满足一个用户只能租到一个资源。按顺序取一个资源i作为当前资源，其用户集U′=U，并删除竞价低于成本的用户，U′存放当前资源的可用用户，满足竞价高于成本才能租赁。资源i对U′调用构建路径-关键路径算法，求出i的租赁方案及收益。

构建资源i的关键路径时，根据其单价及可用用户的预约信息，构建矩阵R[n+2][n+2]，R中0代表源节点，(n+1)代表终节点，其余n个节点为n个用户。源节点0到U′中各用户节点j的路径等于资源i为j服务的利润；j到终节点的路径为0。因为U′中用户按照开始使用时间排序，对于U′中所有用户对(j,k)，当j的结束时间早于k的开始时间，j到k有路径相连，长度为i租给k获得的利润，满足没有时间交集的用户才有可能租到同一个资源的约束条件。通过上面步骤，将资源i能服务的用户按时间先后联通在一个图上。对R调用关键路径算法，求得0到(n+1)节点的关键路径长度，即i租给U′中用户所能获得的最大利益，所有资源的利益相加就是供应商获得的总利益。i的关键路径中除0和(n+1)外涉及的节点j，成功租到资源i，在分配矩阵中标注xij=1，并从U中删除，将不会租到别的资源。

完成i资源的构建路径-关键路径算法后，取下一个成本较低的资源继续前面的步骤。直到所有资源分配完后，得到供应商的资源分配方案X[m][n]及获得的总利润Y。

定理2RAAM求的分配方案是满足式（1）的一个可行解。

证明在RAAM分配算法中，对资源按照单价高低逐次分配，代码21～24行将当前资源服务用户从全局可用用户里删除，保证每个用户最多只会租到一个资源，满足约束条件（1a）。代码3～7行对资源的可用用户集筛选掉竞价不高于成本价的用户，满足式（1b）。由于用户按照开始使用时间排序，代码12～18行确保当资源的两个可用用户使用时间没有交集时，两用户之间才有路径相连，当有交集则没有路径，确保一个资源一定不可能同时租给两个有时间交集的用户，满足式（1c）。求解每个资源的分配方案时，在其可用用户集合中基于关键路径思想求解，最大化资源的利润，满足目标函数最大化。因此，RAAM求的分配方案是满足式（1）的一个可行解。

5.2 用户定价近似算法UPAM

RAAM求得资源分配方案后，每个租到资源的用户需给供应商支付相应的费用。最优机制中采用基于VCG的价格支付算法，该算法时间复杂度高，且需对应最优分配算法使用才能保证机制可信。用户定价近似算法UPAM采用二分法计算支付价格，其基于临界值的思想，能无限逼近最低获得分配的价格[22]，吸引更多的用户参与拍卖，也提高了计算效率[23]。但是基础二分法对于共享资源并不适用，其求解思想是，只要能分配到资源则更新降低竞价[24]，但无限降价可能导致用户租到了低成本的资源，不够支付原本租的高成本资源，需对基础二分法进行改进。设用户j付给供应商的价格为pj，UPAM的伪代码如算法2所示。

算法2UPAM求解用户需要支付的价格

输入：资源分配矩阵X，用户集U，预约信息集Q。

输出：各个用户支付价格集P={p1,p2,…,pn}。

程序：

1.for eachj∈Udo

2.pj=0,cp=0

3.for eachi∈Cdo

4.Ifxij=1then /*如果j租到了资源i*/

5.cp=ei,break/*记录j租到的资源的成本*/

6.end if

7.end for

8.Ifcp≠0then

9.h=bj,l=0 /*初始支付价格最大值h=bj，支付价格最小值l=0*/

10.while|h-l|＞εthen

11.bj=(h+l)/2

12.ifj以bj参与RAAM分配，能分配给成本单价≥cp的资源then

13.h=bj

14.elsel=bj

15.end if

16.end while

17.pj=h

18.end if

19.end for

20.returnP

UPAM算法记录每个用户所租资源的成本cp，不断更新竞价，判断新价格能否给用户分到不低于cp成本的资源。成功则降低最高竞价，否则升高最低竞价。不断重复该步骤，最高和最低竞价不断逼近，最终得到用户需要支付的临界价格。

5.3 RAUPAM机制可信证明

定理3RAAM分配算法满足单调性。

证明RAAM分配结束后，任意一个租到资源的用户j，记其分配资源为i，成本单价为ei。当用户提高自己的报价为bj′＞bj时，其他用户请求不变，再次执行RAAM分配。资源按照单价降序排序，优先分配高成本资源，可能会出现以下两种情况：（1）用户j租到编号为i′∈{1,2,…,i-1}中的一个资源；（2）当（1）情况不满足时，用户j必然会租到i资源。

（1）求解i′资源分配方案时，其中i′∈{1,2,…,i-1}，当新的bj′＞bj时，若bj′大于i′的运行成本，j成为i′可用用户，调用关键路径算法后，j有可能租到i′资源；或者j本来就是i′的可用用户，之前的关键路径没采用j，当提高竞价后，j有可能成为i′的关键路径上节点。当j租到i′资源时，用户分配到的是比之前单价成本更高或者同成本的资源型号。

（2）（1）中的情况可能出现，当（1）情况没发生时，在i资源分配求解中，关于j用户的路径都会增加，i的之前包含j的关键路径也会增加，则j用户必然会被选作关键路径上的节点，租到i资源。

因此，当用户j提高竞价bj′＞bj后，用户能分配到更高成本的资源，或者至少是同成本的资源，满足单调性。

定理4UPAM是基于临界值求支付价格的。

证明根据UPAM算法可知，代码1～7行对每个租到资源的用户j，记分配的资源成本单价为cp。初始其支付价格最大值h=bj，最小值l=0。代码10～16行表示，当|h-l|大于设定的阈值ε时，更新bj=(h+l)/2，用户j以新的bj参与RAAM分配，若j能租到成本单价≥cp的资源，则降低支付价格最大值h=bj，否则升高最小值l=bj。重复上述步骤，直到不满足|h-l|＞ε时，h与l不断逼近。最终求得用户能分到单价为cp资源的保底价格h，作为用户的支付价格pj。算法保证当竞价bj″＞pj=h时，用户一定能分到成本单价≥cp的资源；当用户竞价bj″＜l时，用户一定不能分到成本单价不低于cp的资源，满足临界值的定义3。

定理5RAUPAM机制是可信的。

证明根据引理2，一个拍卖机制，若资源分配算法满足单调性，且支付算法是基于临界值的，该机制可信。在RAUPAM拍卖机制中，由定理3可知RAAM分配算法满足单调性，由定理4可知UPAM基于临界值求支付价格，因此RAUPAM是可信的拍卖机制。

5.4 示例

交通出行是共享经济应用最突出的领域，本文以神州专车的预约用车为例，通过RAAM算法给各用户分派合适的车辆，通过UPAM计算出用户需要支付的费用。

设有两辆车，按单位时间成本降序排序，得到车辆集合为C={1,2}，成本集合E={10,8}。按照开始用车时间对用户排序，表1为用户预约信息。

Table1 User's reservation information table表1 用户预约信息表

（1）RAAM求车辆分配

首先对第一辆车求分配，成本单价e1=10，剔除成本≥竞价的用户4，第1辆车可用用户集U′={1,2,3,5}。构建时间分配矩阵R，初始化每个元素为0。然后对U′中任意用户j求r0j，如r01=b1-(d1-s1)∙e1=4。再对U′中任意用户j求元素rjk，其中k＞j,k∈U′，以r12为例，不满足d1≤s2，不作操作；又如r13，满足d1≤s3，r13=r03=b3-(d3-s3)∙e1=7。以此类推，得到第1辆车的时间分配矩阵R，用图表示如图1所示。

Fig.1 Time distribution diagram of vehicle 1图1 车辆1时间分配转化图

对R调用关键路径算法求得0到6节点的关键路径为0-1-3-5-6，关键路径长度为y1=16。将第1辆车分给用户1、3和5，从可用用户集合U中删除这3个用户，U={2,4}。继续按照上述方法对第2辆车进行分配，求得第2辆车的关键路径为0-2-4-6，长度为y2=14，将第2辆车分给用户2和4。最后车辆供应商收益Y=y1+y2=30，车辆分配矩阵X如表2所示。

Table2 Vehicle allocation matrixX表2 车辆分配矩阵X

（2）UPAM计算支付价格

需要为每个分到车的用户计算支付价格。本示例中设置阈值ε=1，所有计算结果向下取整。以求解1用户支付价格为例。用户1租到第1辆车，成本参数cp=e1=10，初始h=b1=24，l=0。|h-l|=24＞ε，更新竞价b1=(h+l)/2=12，重新运行RAAM，此时用户1不能分到成本不低于cp=10的车，因此令l=b1=12。由于h=24,l=12，|h-l|=12＞ε，更新b1=(h+l)/2=18，重新进行RAAM。重复运行RAAM，若用户1能分到成本不低于cp=10的车，则h=b1；若不能则l=b1，不断更新b1=(h+l)/2，直到 |h-l|≤ε，计算结束。最终取新的h作为用户的支付价格，最后求得用户1需支付p1=h=22。

6 实验

6.1 实验设置

本文采用真实的出租车数据模拟预约用车数据，反映用户的真实用车需求，以此来测试本文提出的算法对于共享经济预约模式下资源的分配结果。实验数据包含每辆车在不同时间点的经纬度、速度、载客状态等信息。根据车辆编号，对每辆车按照时间从早到晚排序，选取了2007-01-31日12：00—24：00半天的数据，并剔除了冗余的数据。实验设置如下。

（1）得到的信息中没有价格及车型等信息，实验采用神州专车预约平台的车型数据，共有三种车型，每分钟单价平均为8、6、4元，三种车型各占1/3。用户的竞价=用车时间×（5到10之间的随机数），即用户竞价与用车时长相关。

（2）不失一般性，实验分为小、中、大三种规模。

（3）实验设置不同密度，分别模拟不同的竞争情况，以分析各种情况下算法的执行效果。

（4）设置不同分配周期，并分析周期对分配的影响。

（5）实验环境：实验搭建在 Intel®i7-6700 CPU 3.40 GHz,8 GB内存平台。

实验采用三种主流算法与本文算法进行对比。（1）CPLEX求解器的最优算法。通过编写规划模型，在求解器CPLEX上求出最优解。但CPLEX十分消耗内存，几百个用户的约束条件就会导致内存耗尽，基本只能解决小规模下的分配。（2）先预约先服务算法（first-come-first-serve，FCFS），按照预约顺序给用户安排车辆，算法实现简单，这是目前专车预约平台采用的分配方式。（3）最高出价优先算法（MAXBID）。利用贪婪法的思想，总是选取当前竞价最高的用户，使得局部收益最大化，但局部最优并不能实现全局最优。

6.2 结果分析

实验将对CPLEX求解的最优算法、提出的RAUPAM算法、FCFS、MAXBID算法进行以下三方面的评估。第一，多维度分析算法效果。实验首先选取了三个有代表性的密度0.8、2.0、4.0，来分别模拟低峰期、正常时期、高峰期的情况，以分析各种情况下算法的执行效果。然后实验分三种不同的周期T4、T6、T12对车辆进行分配，并将各周期结果分别加和以分析长短周期对分配产生的影响。第二，评估指标。在同种密度和周期下，本文从平台利润、服务用户率、车辆时间利用率对算法进行评估。第三，不失一般性。为了降低数据对结果的影响，实验分为小规模（10辆车）、中规模（100辆车）、大规模（1 000辆车）三种情况，从不同的规模对本文算法进行评估。

6.2.1 密度对算法执行效果的影响

在不同的时期，资源竞争情况也不同。如对于车辆的预约来说，在上下班高峰期，车辆资源稀缺；在白天其他时间段，车辆基本可以满足所有用户的请求；在晚上，车辆又大量闲置。对于共享经济中的其他资源，也同样存在使用高峰期和低峰期。实验选用T6第一个周期的数据，设置了三种密度，0.8、2.0、4.0，并分析不同密度下算法的执行效果。

图2通过展示三种密度下服务用户率的差别，这三个密度可分别用来代表不同的资源竞争情况。在0.8密度下，平均将8辆车的用户分配给10辆车，车辆富余，几乎所有算法的服务用户率都是1.0，可以用来模拟低峰期的情况。2.0密度下，平均将20辆车的用户分给10辆车，虽存在竞争，但车辆基本能满足用户的需求，所有算法的服务率都能达到90%以上，用来模拟正常时期。4.0密度下，平均将40辆车的用户分配给10辆车，车辆供不应求，服务用户率只能达到50%左右，可用来模拟高峰期。

图3在三种密度下，对比了各算法得到的利润。任何一种规模下，密度越大，利润越大，证明高峰期能为供应商带来更多的利润。在小规模时，CPLEX的利润是最高的，但随着密度增大，CPLEX的增长速率逐渐缓慢；而RAUPAM的利润一直匀速增长，随着密度的增大，与CPLEX的差距逐渐缩少，体现了RAUPAM算法在高峰期时表现优异。

Fig.2 Comparison of service user rates of different algorithms under different densities图2 不同算法在不同密度下的服务用户率比较

Fig.3 Profits of different algorithms under different densities图3 不同算法在不同密度下的利润比较

接下来比较RAUPAM、FCFS、MAXBID三种算法受密度的影响程度。在任意一种规模下，0.8密度时，车辆资源充足，三种算法都能使得几乎所有用户得到服务，利润几乎相等。到了2.0密度时，三种算法差别不大，按照利润大小排序为RAUPAM>MAXBID>FCFS。到了4.0密度时，三种算法差距增大，RAUPAM是利润最大的，比FCFS平均高出75%，比MAXBID算法平均高出30%。因此在任意密度下，即高峰期和低峰期时，RAUPAM都是三种算法中利润最大的，尤其在高峰期优势更明显。

任意规模下，RAUPAM算法的利润都随着密度的提高而匀速增长，而FCFS和MAXBID算法的利润增长速率随密度增长逐渐变小，其中FCFS算法减小得更多。证明在不同密度下，即是高峰期和低峰期，RAUPAM算法都表现稳定，不受密度影响；而FCFS和MAXBID算法在高峰期执行效果变差。因此RAUPAM为共享经济供应商在高峰期和低峰期都能提供更优的资源配置方案。

6.2.2 周期对算法执行效果的影响

本文提出的机制用于共享经济预约模式下做资源配置，预约模式下用户在使用时间之前提出预约请求，机制按周期对资源进行分配，用户需在周期开始前提交预约请求。但是具体周期时长应如何确定，是一个复杂的问题。因为共享经济中的资源使用时间特点不同，周期应不同。如对于共享住宿，周期以天为单位；而预约挂号，应以分钟为单位。周期应能包含多数用户的使用周期，避免周期过短而淘汰大量跨周期用户。但周期过长，虽然能包含大量用户的请求，又需要用户更早做预定。

本文设置了三种不同的周期，分析周期对于RAUPAM、FCFS、MAXBID这三种算法的影响。实验采用的是2007-01-31日12：00—24：00半天的数据，密度采用4.0，设置了三种不同的周期：短周期，4 h周期（T4），共有3个周期；中周期，6 h周期（T6），两个周期；长周期，12 h周期（T12），1个周期。实验将T4的3个周期的利润加和，T6的两个周期利润加和，与T12周期的利润进行比较。

如图4所示，在同种规模的不同周期下，各种算法的周期利润总和差别不大，因此周期对算法的利润影响不大。对于RAUPAM算法来说，相同规模下，周期越长，得到的利润总和越大，即T12>T6>T4，因此在条件允许的情况下，尽量提醒用户提前预约。这是因为RAUPAM算法对车辆进行时间资源规划，周期越长，每辆车的可选用户增多，就能规划出更优的配置方案。FCFS和MAXBID算法受周期影响利润值有所波动，如小规模下，FCFS算法在T6的利润和最大，但在中规模时，又是T12利润和最高。RAUPAM随周期增长收益在小幅增加，表现稳定；而FCFS和MAXBID随周期变化收益波动，易受周期影响。

Fig.4 Comparison of profits of different algorithms under different cycles图4 不同算法在不同周期下的周期利润和比较

在同种规模下，无论RAUPAM的周期选T4、T6、T12，RAUPAM的周期利润和都远高于FCFS和MAXBID的三种周期中的最高值，即无论选取任何一种周期做分配，RAUPAM算法都比FCFS和MAXBID有明显的优势。虽然共享经济中资源的使用周期不尽相同，以天、小时、分钟为单位，但RAUPAM算法不受周期影响，在长短周期都表现优异，适合为不同分配周期的共享资源做优化配置。

6.2.3 四种算法详细比对

实验对四种算法从平台利润、服务用户率、车辆时间利用率这三个指标进行详细对比分析。选取T6第一个周期的数据，密度采用4.0。

（1）平台利润

社会福利是常用来衡量机制的重要指标，但是社会福利是各个胜出拍卖用户的竞价之和，社会福利最大不代表利润最大（选取多数使用时间长的用户），而利润才是供应商最关心的指标。本文所有算法的目标为平台利润最大化，并对四种算法从利润方面进行对比。表3详细展示各种规模下的车辆数目与4.0密度下对应的用户数目，列出四种算法在三种规模下得到的利润值，并将FCFS和MAXBID算法的收益值与RAUPAM算法进行比对，得到RAUPAM对这两种算法在利润方面的提升率。

Table3 Experimental result表3 实验结果表

如表3所示，在小规模下，RAUPAM的利润与CPLEX最优算法的利润值最接近，达到CPLEX最优解的75%左右，而另外两种算法只能达到50%左右。当车辆数目在10以上，用户数目超过500时，约束条件数目过大，CPLEX求解内存空间不够导致无法求解，而其他三种算法在大规模时仍然能快速求解。在中、大规模下，RAUPAM算法得到的利润是最大的，从最后一列可以看出，RAUPAM算法对于FCFS和MAXBID算法有显著的提高。

四种算法中，FCFS的利润最差，这是因为用户预约请求时间的不确定性，先预约的用户可能占用时间长且利润低，导致后预约的用户虽然能带来更大利润却预约不成功。随着规模的扩大，RAUPAM算法的优势比FCFS更明显，如从小到大规模时，RAUPAM在利润方面比FCFS的提高率从55%到77%，再上升到93%，几乎是其两倍。

MAXBID采用贪婪的思想，选取当前竞价最高的用户，因为不知道能分配到何种车型，成本不固定，所以没有采用利润最大优先算法。这种局部选取最大竞价的思想，却并未实现全局竞价最优。表3中社会福利即等于竞价之和，MAXBID在每种规模下的竞价之和并没有RAUPAM的高。MAXBID对于规模不太敏感，一直表现较稳定，但是随着规模增大，RAUPAM比MAXBID算法在利润方面的优势在小幅提高。RAUPAM的利润比MAXBID算法平均高30%左右。

RAUPAM算法从全局考虑资源的分配，优先让高成本车辆选取出价高的用户，其淘汰的用户能继续租到低成本车辆，最大化资源的利用。在计算每个车辆的分配方案时，对该车可用用户调用关键路径算法，求得对用户集的最优分配方案，最大化该车的利润，因此RAUPAM的利润比FCFS和MAXBID有显著提高。小规模时，CPLEX的竞价之和不是最大，利润却是最高，其成本是四种算法中最低的，因为其优先给每个用户分配低成本的车型以获得更大的利润。但RAUPAM算法优先为用户分配满足成本的高档车辆，出价高的用户优先分到好的车型，满足公平性且提升了用户的满意度。

（2）服务用户率

当车辆资源紧缺时，算法应该在符合利润最大化的前提下满足更多用户的预约请求，服务用户率等同于用户预约订单成功率，直接影响用户的体验度，是共享经济租赁平台关注的另一重要指标。

Fig.5 Comparison of service user rates of different algorithms图5 不同算法的服务用户率比较

图5 从服务用户率的维度对四种算法进行对比分析。在小规模时，CPLEX算法的服务用户率是最高的，达到59%，RAUPAM算法其次，达到56%。在所有规模下，RAUPAM、FCFS、MAXBID这三种算法中，RAUPAM算法的服务率都是最高的，FCFS其次，RAUPAM的用户服务率平均比FCFS提高了7%左右；MAXBID的服务率最低，RAUPAM的服务用户率比其平均提高了20%～30%。当前密度为4，车辆资源稀缺，RAUPAM的服务用户率维持在60%左右，使得尽可能多的用户请求得到了满足。MAXBID服务用户率最低，平均只有43%左右，因为其遵循出价最大选择用户，选取大量使用时长的用户占据了资源，使得车辆能服务的用户数减少。

（3）车辆时间利用率

4.0密度下，车辆对于用户供不应求，每辆车都会被用到，计算车辆利用率没有意义。而车辆时间利用率是根据每种算法服务用户的时间加和，并除以所有车辆的可用时间之和，更能反映车辆资源的使用情况。图6从车辆时间利用率方面对四种算法进行了对比。

Fig.6 Comparison of utilization rates of vehicle time of different algorithms图6 不同算法的车辆时间利用率比较

如图6所示，在任意规模下，RAUPAM算法的车辆时间利用率都是最高的，在小规模时都高于CPLEX算法。随着规模的扩大，各算法的车辆时间利用率增加。RAUPAM算法的平均车辆时间利用率高达88%，因为算法对每辆车做规划，减少碎片时间，提高了车辆资源的利用率。FCFS的车辆时间利用率是所有算法中最低的，平均只有79%。FCFS按照用户预约申请顺序来进行车辆的分配，先预约的用户占住了时间，产生大量碎片时间，导致车辆时间利用率低。

实验结论：通过比较密度对于算法的影响，发现在高峰期和低峰期，RAUPAM的利润都大于FCFS和MAXBID，且表现稳定不受密度影响；而FCFS和MAXBID算法在高峰期表现较差，因此RAUPAM为共享经济供应商在高峰期和低峰期都能提供更优的资源配置方案。通过分析周期对算法的执行影响，发现在同种规模下，无论RAUPAM的周期选T4、T6、T12中的任意一种，RAUPAM得到的周期利润和都远高于FCFS和MAXBID的三种周期中的最高值。因此RAUPAM算法不受周期影响，在长短周期都表现优异，适合为不同周期的共享资源做优化配置。同周期同密度下，对四种算法进行了更详细的比对。无论何种规模下，RAUPAM算法的利润都显著大于FCFS和MAXBID，比FCFS至少提高55%，比MAXBID算法平均提高30%。在服务用户率方面，RAUPAM算法的服务用户率平均达到60%，比FCFS平均提高7%，比MAXBID平均提高了20%～30%，保证大多数用户能得到服务。任何规模下，RAUPAM算法的车辆时间利用率都是最高的，平均高达88%，达到了较高的资源利用率。

7 结束语

针对目前共享经济预约模式采用固定价格及先预约先服务分配资源的方式，存在的供应商收益低下、资源利用率不高等问题，本文设计可信的拍卖机制用于解决共享经济预约模式中资源的分配及用户定价问题。

本文对共享经济预约服务中资源的分时租赁问题建模，并设计可信的最优拍卖机制，用CPLEX求解最优资源分配方案，基于VCG理论计算用户的支付价格。但最优机制无法在多项式时间求解，提出可信的启发式机制RAUPAM解决大规模的资源租赁分配及用户定价问题，用关键路径的思想求解近似最优分配方案，再用二分法求用户的支付价格。测试结果表明，RAUPAM比传统算法FCFS和MAXBID取得了更好的结果。

本文提出的拍卖机制，适用于任何按时收费的共享资源在预约模式下做分配，如共享停车位、共享住宿、共享厨房等；也适用于其他按时使用收费的资源，如云平台中资源的分配、医疗诊治预约等。但在实际共享经济市场中，还有一些可移动的共享资源，用户可在不同的地点分别领取和归还资源，其收费与取还点相关，如共享充电宝、共享服装等。在未来的研究工作中，将设计适用于这些可移动资源预约的拍卖机制，将取还点纳入参考因素，从全局决策这些资源预约模式下的租赁分配方案。