Abstract: 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.

Key words: Cloud computing, TSP problem, Solving service, Pricing mechanism, SLA