云计算中TSP问题求解服务的定价机制

旅行商问题(TSP)是一个典型的路径优化问题，在城市交通规划、物流运输、通信网络设置等领域都存在类似的问题和应用。但是，TSP问题的求解是NP难的，当问题规模很大时，必须借助大规模并行计算环境，例如云计算平台，以较大的计算开销来获得可行解。以TSP问题为具体实例，研究云计算服务的定价机制。一般情况下，定价机制要满足公平、灵活、动态、自适应。从公平合理角度来看，影响计算服务定价的因素主要有两方面:一是求解问题的难度，包括计算时间复杂性、空间复杂性、输入输出数据规模等;二是求解服务质量，即服务契约，包括可以作为服务等级协定指标的求解精度、响应时间、资源要求等。由此，提出了一种新的云计算中的服务定价机制:CloudPricing。该机制给出了服务定价的一般和具体原则，并给出了相应的定价公式。针对TSP问题求解，进行了具体的定价实例分析，这对云计算中NP难问题求解服务的定价有参考意义。

Pricing Mechanism of TSP Solving Service in Cloud Computing

The traveling salesman problem(TSP) is a typical path optimization problem which has similar problems and applications in urban transportation planning, logistic transport and communication network settings. However, TSP is a NP hard problem When problem scale is very large, large scale parallel computing environment such as cloud computing platform is needed. In this paper, we illustrated cloud service pricing mechanism with TSP. Uenerally, pricing mechanism should be fair, flexible, dynamic and flexible. To be fair and reasonable, there arc two main aspects to be considered when pricing a service. One is the difficulty of solving the problem including time complexity, space complexity and quantity of data the application input and output. The other is the quality of service including precision of the result, response time and whether the service is provided in peak time or not which can be served for Service Level Agreement between service provider and customer. Next, we proposed principles of pricing the service and pricing formula. Finally,a case study aiming at pricing solving TSP service was given, which has a reference value for pricing NP hard problem in cloud computing environment.