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.

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.

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.

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)的运行经济性,也能提升可再生能源的消纳量。

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

随着分布式电源技术和新能源技术快速发展,参与电力交易的电动汽车和新能源发电用户数量不断增多。由于电动汽车和新能源具有随机性和不确定性,现有交易模式无法支撑交易需求。区块链具有去中心化、不可篡改等特点,可以有效解决车网互联系统(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.

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.

Pricing in combinatorial double auction-based grid allocation model

这篇文章建议一个新奇格子资源分配模型，用户和格子服务供应商为资源分配在参予组合双拍卖。获得详细资源分配地位和价格信息，一个新奇定价算法为分配模型被设计。模拟结果证明建议算法高效地完成资源分配和定价，并且展出刺激兼容机特征。而且，有更高平均的价格的用户和有更低的平均价格的供应商在定价过程期间得到赔偿。

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.

基于组合双向拍卖的网格资源分配

针对网格环境中资源分配的特点,提出新的基于组合双向拍卖的网格资源分配模型,通过网格用户和业务提供者的组合双向拍卖来实现资源的分配,并提出了网格资源定价算法,用以解决资源分配基础之上的计费问题.仿真结果表明,所提出的方案可以高效的完成资源的分配及定价,并且可以对平均报价较高的竞买方以及平均报价较低的竞卖方给予价格补偿.

多因素采购组合拍卖动态机制设计研究

在允许"价格-质量"投标的多因素投标环境下,设计了一种多因素采购组合拍卖的动态机制(规则),提出了竞争均衡打分的概念。构建了多因素采购组合拍卖动态机制的优化模型,讨论了拍卖规则和优化模型实现互补松弛条件之间的必然联系。基本结论是:在本拍卖机制中,投标者采用最佳近视反应投标策略,将使拍卖的分配结果趋向最优,最终在拍卖结束时实现系统效用最大化。

组合采购拍卖的多因素投标机制设计研究

采购组合拍卖指的是通过组合拍卖的方式进行多物品采购。在进行采购组合拍卖时,拍卖的机制设计不仅要考虑供应商——投标者的利益,同时还要考虑采购商——拍卖者的利益,也即拍卖的分配效率问题。然而,由于产品的成本函数往往是投标者的私有信息,投标者并不愿意暴露该信息,该私有信息的存在影响着机制实现分配效率。考虑到该问题,本文设计了一种让投标者直接对物品组合进行"价格-质量"投标的多因素采购组合拍卖机制(MA-VCG-PQ),该机制具有分配有效、激励相容、个体理性和预算平衡的良好性质,同时避免了供应商成本函数信息的曝露。

基于加权平均的网格资源分配与定价

针对网格资源分配中现有组合双向拍卖模型以资源包平均价格定价的不足,提出以各类资源的单价定价的算法.根据组合双向拍卖和网格信任理论,提出基于加权平均算法的网格资源分配与定价策略,以信任度阈值的加权平均鉴别恶意节点,以归一化报价和信任度的加权平均衡量正常节点的价格及信任综合竞争力.仿真结果表明,该算法交易率较高,可防范恶意节点,交易效用可激励正常节点以提高其综合竞争力.