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

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.

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

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

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

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

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

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

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

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

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

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

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.

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

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

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.

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

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

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

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

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

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

云环境下基于神经网络和群搜索优化的资源分配机制

在云环境下,各种闲置资源可以通过池化形成资源池,进而利用虚拟化技术将资源池中的不同资源组合以服务的形式提供给用户使用,因此需要合理而有效的机制来分配资源.针对云环境下资源的特点,将经济学和智能方法相结合,提出了一种基于双向组合拍卖的智能资源分配机制.在该机制中,提出了基于体验质量(quality of experience,简称QoE)的威望系统,引入威望衰减系数和用户信誉度,降低拍卖中恶意行为造成的影响,为资源交易提供QoE支持.对拍卖中的竞价决策,综合考虑多种因素,提出了基于BP神经网络的竞标价格决策机制,不仅可以合理确定竞标价,而且使价格可以动态适应市场变化.最后,由于组合拍卖胜标确定问题是NP完全的,因此引入群搜索优化算法,以市场盈余和总体威望为优化目标,得到资源分配方案.仿真研究结果表明,该机制是可行和有效的.