Genetic Algorithm Based Combinatorial Auction Method for Multi-Robot Task Allocation

An improved genetic algorithm is proposed to solve the problem of bad real-time performance or inability to get a global optimal/better solution when applying single-item auction （SIA） method or combinatorial auction method to multi-robot task allocation. The genetic algorithm based combinatorial auction （GACA） method which combines the basic-genetic algorithm with a new concept of ringed chromosome is used to solve the winner determination problem （WDP） of combinatorial auction. The simulation experiments are conducted in OpenSim, a multi-robot simulator. The results show that GACA can get a satisfying solution in a reasonable shot time, and compared with SIA or parthenogenesis algorithm combinatorial auction （PGACA） method, it is the simplest and has higher search efficiency, also, GACA can get a global better/optimal solution and satisfy the high real-time requirement of multi-robot task allocation.

Negotiation Based Combinatorial Double Auction Mechanism in Cloud Computing

Cloud computing is a demanding business platform for services related to the field of IT.The goal of cloud customers is to access resources at a sustainable price,while the goal of cloud suppliers is to maximize their services utilization.Previously,the customers would bid for every single resource type,which was a limitation of cloud resources allocation.To solve these issues,researchers have focused on a combinatorial auction in which the resources are offered by the providers in bundles so that the user bids for their required bundle.Still,in this allocation mechanism,some drawbacks need to be tackled,such as due to the lower average bid price the users are dropped from the auction process.To solve this problem,we proposed a“Negotiation based Combinatorial Double Auction Mechanism for Resource Allocation(N-CDARA)in cloud computing”.The proposed method negotiates with dropped users.Lower average bid price users are asked by our proposed mechanism to increase their bids,as by the quoted bids they will be dropped by the auctioneer.Most of the users that are close to winning accept the proposal and increase their bid prices.The proposed mechanism is implemented in a CloudSim simulation toolkit.Results are compared with the latest model and performance study shows that in our proposed scheme more users win and get their requested services and the utilization of offered services is increased up to 18.4%than the existing schemes.

Privacy-Aware Service Subscription in People-Centric Sensing:A Combinatorial Auction Approach

With the emergence of ambient sensing technologies which combine mobile crowdsensing and Internet of Things,large amount of people-centric data can be obtained and utilized to build people-centric services.Note that the service quality is highly related to the privacy level of the data.In this paper,we investigate the problem of privacy-aware service subscription in people-centric sensing.An efficient resource allocation framework using a combinatorial auction(CA)model is provided.Specifically,the resource allocation problem that maximizes the social welfare in view of varying requirements of multiple users is formulated,and it is solved by a proposed computationally tractable solution algorithm.Furthermore,the prices of allocated resources that winners need to pay are figured out by a designed scheme.Numerical results demonstrate the effectiveness of the proposed scheme.

CRAB—CombinatoRial Auction Body Software System

Auctions are important market mechanisms for the allocation of goods and services. Combinatorial auctions are those auctions in which buyers can place bids on combinations of items. Combinatorial auctions have many applications. The paper presents the CRAB software system. CRAB is a non-commercial software system for generating, solving, and testing of combinatorial auction problems. The system solves problems by Balas’ method or by the primal-dual algo-rithm. CRAB is implemented in Ruby and it is distributed as the file crab.rb. The system is freely available on web pag-es for all interested

考虑绿色氢能证书和水电制氢的综合能源系统优化运行

利用清洁能源发电富余电力电解水制氢,绿色氢能实现了生产源头的二氧化碳零排放,在全球能源转型中扮演着重要角色。针对绿色氢能证书市场机制不健全等问题,该文提出一种考虑绿色氢能证书组合双向拍卖和水电制氢的综合能源系统优化运行方法。首先,为解决园区内绿色氢能证书价格和数量匹配不均衡的问题,提出绿色氢能证书组合双向拍卖(combinatorial double auction,CDA)交易机制竞价模型;其次,建立含水电制氢的综合能源系统优化模型,并将绿色氢能证书组合双向拍卖机制引入其中;最后,以某省含水电制氢的综合能源系统为例进行仿真分析,结果表明所提模型不仅能有效提高综合能源系统(integrated energy system,IES)的运行经济性,也能提升可再生能源的消纳量。

基于组合拍卖的广义共享储能运营机制设计

共享储能已经成为缓解可再生能源大规模并网带来的一系列问题的有效途径,但现有共享储能机制未充分考虑用户对于储能的互补性和替代性需求,严重影响用户购买意愿。此外,当前共享机制也未考虑储能的电量约束、充放电功率约束和荷电状态的影响,不利于运营商的投标策略设计,使其面临经济损失风险。因此,该文设计基于组合拍卖的广义共享储能运营机制。首先,考虑基站备用储能、空调、电动汽车充电站等资源具有储能特性而运行行为迥异的特性,利用广义储能模型对其进行统一聚合封装,降低多种需求侧资源的调度难度;其次,对储能使用权进行划分,设计广义储能功率使用权和容量使用权两种交易品种,并为卖方设计计及储能荷电状态的投标曲线,为买方设计不同时段、不同品种耦合需求的组合形式,以满足用户对储能的多种需求,提高用户满意度;然后,基于组合拍卖理论,设计包含投标、竞胜标决定、资源定价与资金结算等环节的共享储能运营机制,以实现广义共享储能资源的高效利用和社会福利的公平分配;最后,算例仿真结果表明,所述运营机制可满足用户灵活性需求,降低储能服务成本。

面向边缘计算资源分配的防假名拍卖机制

边缘计算激励机制可以激励用户参与到资源分配的过程中来.为防范不诚实用户对资源分配的操纵,现有激励机制致力于使参与者在投标时给出他们的真实估值,但未考虑对假名攻击的对抗策略.为解决现有机制缺乏对抗假名攻击的能力这一问题,首先,对假名攻击投标决策手段进行分析,设计了假名过滤算法和结合边缘服务器成本的最小临界值定价算法,假名过滤算法剔除可能的假名用户,定价算法则保证了假名用户无法通过操纵临界价格提高效用.然后,证明了该防假名拍卖机制满足真实性和个体理性,此外还证明了该机制对假名攻击具有抗操纵性.实验结果表明,该机制能够在满足真实性的同时,保证用户无法通过单方面发起假名攻击增加效用.

基于日前预测与日内运行储能动作偏差量的多园区分布式储能云服务交易机制设计

目前云储能的商业模式及市场机制尚不成熟,用户参与云储能服务的方式较为单一。同时,分布式储能多用于用户侧与可再生能源协同运行以平抑其出力的波动性,其不确定性导致的日前预测与日内运行(DAF-IDO)存在偏差。为此,提出了基于DAF-IDO储能动作偏差量的多园区分布式储能云服务交易机制,将运行与交易相结合,在解决DAF-IDO偏差的同时,为分布式储能用户参与云储能服务提供全新的市场途径。提出了DAF-IDO储能动作偏差量的确定方法,使得各园区运营商能够对园区储能供需量进行定量计算;制定了基于组合拍卖的园区间分布式储能云服务交易机制,并在云储能价格机制中加入谷时段补偿机制,在兼顾各方经济性的同时提升了用户参与云服务的积极性及自主性。通过算例仿真验证了所提机制的可行性和合理性。

基于区块链的电动汽车去中心化交易研究

随着分布式电源技术和新能源技术快速发展,参与电力交易的电动汽车和新能源发电用户数量不断增多。由于电动汽车和新能源具有随机性和不确定性,现有交易模式无法支撑交易需求。区块链具有去中心化、不可篡改等特点,可以有效解决车网互联系统(vehicle-to-grid,V2G)电力交易遇到的挑战。首先,基于区块链技术,提出基于组合拍卖和滚动撮合交易的交易规则,设计了滚动撮合交易模型。随后,基于组合拍卖和滚动撮合交易机制规则,设计了V2G的电力交易智能合约。最后,为验证所提方案的可行性,将智能合约发布到趣链区块链平台上,进行模拟实验。实验结果表明,本文所提方法能够有效提高交易成功率。

考虑多维参数耦合的共享储能匹配交易机制

共享储能在电力供应链的各个环节中已经呈现出极强的应用潜力和价值,被视为解决储能成本疏导困难的有效手段。然而,储能共享不仅会涉及多类型应用场景,且其本身的运行方式是功率、容量等多维参数耦合的,亟须探索高效的储能共享机制,以最大化挖掘系统灵活性潜力。为此,围绕考虑多维参数耦合的共享储能匹配交易机制展开研究。首先,构建考虑多维参数耦合的共享储能匹配交易框架,在此基础上,基于组合拍卖理论构建多维参数耦合的共享储能匹配交易模型。其次,针对传统方法求解组合拍卖计算复杂度较高的问题,提出投标密度的概念,以单位标的物的价值对投标信息进行价值评估并排序,以此实现共享储能组合拍卖问题的快速求解,进而提出基于投标密度的共享储能匹配交易结算机制。最后,通过算例证明所提方法的有效性。

Evolutionary Techniques for Reverse Auctions

Winner determination is one of the main challenges in combinatorial auctions. However, not much work has been done to solve this problem in the case of reverse auctions using evolutionary techniques. This has motivated us to propose an improvement of a genetic algorithm based method, we have previously proposed, to address two important issues in the context of combinatorial reverse auctions: determining the winner(s) in a reasonable processing time, and reducing the procurement cost. In order to evaluate the performance of our proposed method in practice, we conduct several experiments on combinatorial reverse auctions instances. The results we report in this paper clearly demonstrate the efficiency of our new method in terms of processing time and procurement cost.

具有激励相容和能源共享特性的混合储能组合拍卖

针对综合能源微网单独配置储能经济性较低的问题,建立了一个经济高效的电-热混合能源共享模型,多个综合能源微网共享一个电-热混合储能装置。在电-热混合储能容量共享的研究中,采用了一种基于多物品拍卖理论的混合储能组合拍卖方法:每个微网分别提交多组不同的电、热储能容量需求以及相应的投标价格,分别竞拍电化学储能容量和储热罐容量,利用这些储能容量达到节省购电费用的目的。储能运营商则以社会福利最大化为目标决定拍卖的结果,即储能容量如何分配给各微网可以最大化其效用。在最后的费用结算过程中采用维克瑞-克拉克-格罗夫(Vickrey-Clarke-Groves, VCG)机制计算各微网需要支付的费用。由于VCG机制具有激励相容性,各微网没有虚假报价的动机,都倾向于提交真实的投标价格,保证了组合拍卖结果具有最大的社会福利。算例结果表明,在社会福利方面,所提的混合储能组合拍卖模式相比于一般的共享储能模式更具优势。

基于多属性组合拍卖的多式联运服务采购改进机制

随着多式联运的发展,托运人的采购需求日益复杂。现有采购机制主要围绕组合拍卖和多属性拍卖展开,满足托运人采购多种线路和考虑价格、非价格因素的需求。为进一步增强机制适用性,本文兼顾托运人收益及资源利用率,基于VCG机制,设计了一种多属性组合拍卖改进机制即改进PA-VCG机制,在考虑质量与价格的前提下,改善线路的分配及支付价格。理论分析表明,改进PA-VCG机制不仅较VCG机制增加了托运人收益,还满足激励相容与个体理性。实验结果表明,改进PA-VCG机制给托运人带来的收益增量随线路需求量的增加而增加,同时,实现良好的资源利用率,社会福利和客户满意率。因此,本文机制满足了托运人的实际采购需求,且重视合作关系,有助于实现可靠、高效的多式联运服务采购。

基于随机游走算法的频谱组合拍卖机制

如何将频谱有效地分配给用户并提高提供商的收益是目前研究的热点。针对频谱组合拍卖中提供商收益低的问题,结合用户估值分布不对称的特点,设计了基于随机游走的频谱组合拍卖(RWSCA)机制,以最大化频谱提供商的收益。首先引入了虚拟估值的思想,用随机游走算法在参数空间搜索一组最优参数,并根据参数线性映射买家的估值;然后运行基于虚拟估值的VCG (Vickrey-Clarke-Groves)机制,从而确定赢得拍卖的用户并计算相应的支付金额。理论分析证明了所提机制具有激励相容和个体理性的性质。在频谱组合拍卖仿真实验中,相较于VCG机制,RWSCA机制至少提高16.84%以上提供商收益。

Combinatorial auction algorithm for project portfolio selection and scheduling to maximize the net present value

Scheduling projects at the activity level increases the complexity of decision making of project portfolio selection but also expands the search space to include better project portfolios. An integer programming model is formulated for the project portfolio selection and scheduling problem. An iterative multi-unit combinatorial auction algorithm is proposed to select and schedule project portfolios through a distributed bidding mechanism. Two price update schemes are designed to adopt either a standard or an adaptive Walrasian tatonnement process. Computational tests show that the proposed auction algorithm with the adaptive price update scheme selects and schedules project portfolios effectively and maximizes the total net present value. The price profile generated by the algorithm also provides managerial insights for project managers and helps to manage the scarce resources efficiently.

Meeting peak electricity demand through combinatorial reverse auctioning of renewable energy

The option of organizing E-auctions to purchase electricity required for anticipated peak load period is a new one for utility companies.To meet the extra demand load,we develop electricity combinatorial reverse auction(CRA)for the purpose of procuring power from diverse energy sources.In this new,smart electricity market,suppliers of different scales can participate,and homeowners may even take an active role.In our CRA,an item,which is subject to several trading constraints,denotes a time slot that has two conflicting attributes,electricity quantity and price.To secure electricity,we design our auction with two bidding rounds:round one is exclusively for variable energy,and round two allows storage and nonintermittent renewable energy to bid on the remaining items.Our electricity auction leads to a complex winner determination(WD)task that we represent as a resource procurement optimization problem.We solve this problem using multi-objective genetic algorithms in order to find the trade-off solution that best lowers the price and increases the quantity.This solution consists of multiple winning suppliers,their prices,quantities and schedules.We validate our WD approach based on large-scale simulated datasets.We first assess the time-efficiency of our WD method,and we then compare it to well-known heuristic and exact WD techniques.In order to gain an exact idea about the accuracy of WD,we implement two famous exact algorithms for our constrained combinatorial procurement problem.

Low Complexity Joint Spectrum Resource and Power Allocation for Ultra Dense Networks

In this paper,we propose a low complexity spectrum resource allocation scheme cross the access points(APs)for the ultra dense networks(UDNs),in which all the APs are divided into several AP groups(APGs)and the total bandwidth is divided into several narrow band spectrum resources and each spectrum resource is allocated to APGs independently to decrease the interference among the cells.Furthermore,we investigate the joint spectrum and power allocation problem in UDNs to maximize the overall throughput.The problem is formulated as a mixed-integer nonconvex optimization(MINCP)problem which is difficult to solve in general.The joint optimization problem is decomposed into two subproblems in terms of the spectrum allocation and power allocation respectively.For the spectrum allocation,we model it as a auction problem and a combinatorial auction approach is proposed to tackle it.In addition,the DC programming method is adopted to optimize the power allocation subproblem.To decrease the signaling and computational overhead,we propose a distributed algorithm based on the Lagrangian dual method.Simulation results illustrate that the proposed algorithm can effectively improve the system throughput.

Pricing in combinatorial double auction-based grid allocation model

This article proposes a novel grid resource allocation model, in which the users and the grid service providers participate in the combinatorial double auction for the resource allocation. To obtain the detailed resource allocation status and the price information, a novel pricing algorithm is designed for the allocation model. Simulation results demonstrate that the proposed algorithm completes the resource allocation and pricing efficiently, and exhibits incentive compatible characteristic. Moreover, users with the higher average price and providers with the lower average price get compensation during the pricing process.

Using a combinatorial auction-based approach for simulation of cooperative rescue operations in disaster relief

In practice,we experience low efficiency of search and rescue(SAR)frequently in disaster relief.Here,we will optimize the SAR through agent-based simulation.In the kind of cases described here,rescue teams are characterized by different capabilities,and the tasks often require different capabilities to complete.To this end,a combinatorial auction-based task allocation scheme is used to develop a cooperative rescue plan for the heterogeneous rescue teams.Then,we illustrate the proposed cooperative rescue plan in different scenarios with the case of landslide disaster relief.The simulation results indicate that the combinatorial auction-based cooperative rescue plan would increase victims’relative survival probability by 13.8–16.3%,increase the ratio of survivors getting rescued by 10.7–12.7%,and decrease the average elapsed time for one site getting rescued by 19.0–26.6%.The proposed rescue plan outperforms the rescue plan based on the F-Max-Sum a little bit.The robustness analysis shows that the proposed rescue plan is relatively reliable on condition that both the search radius and scope of cooperation are larger than thresholds.Furthermore,we have investigated how the number of rescue teams influences the rescue efficiency.

A Combinatorial Auction-Based Collaborative Cloud Services Platform

In this paper, we present a novel, dynamic collaboration cloud platform in which a Combinatorial Auction（CA）-based market model enables the platform to run effectively. The platform can facilitate expense reduction and improve the scalability of the cloud, which is divided into three layers： The user-layer receives requests from end-users, the auction-layer matches the requests with the cloud services provided by the Cloud Service Provider（CSP）, and the CSP-layer forms a coalition to improve serving ability to satisfy complex requirements of users.In fact, the aim of the coalition formation is to find suitable partners for a particular CSP. However, identifying a suitable combination of partners to form the coalition is an NP-hard problem. Hence, we propose approximation algorithms for the coalition formation. The Breadth Traversal Algorithm（BTA） and Revised Ant Colony Algorithm（RACA） are proposed to form a coalition when bidding for a single cloud service in the auction. The experimental results show that RACA outperforms the BTA in bid price. Other experiments were conducted to evaluate the impact of the communication cost on coalition formation and to assess the impact of iteration times for the optimal bidding price. In addition, the performance of the market model was compared to the existing CA-based model in terms of economic efficiency.