摘要
Ants of artificial colony are able to generate good solutions to the famous traveling salesman problem (TSP). We propose an artificial ants algorithm for solving the minimum ratio TSP, which is more general than the standard TSP in combinatorial optimization area. In the minimum ratio TSP, another criterion concerning each edge is added, that is, the traveling salesman can have a benefit if he travels from one city to another. The objective is to minimize the ratio between total costs or distances and total benefits. The idea of this type of optimization is in some sense quite similar to that of traditional cost-benefit analysis in management science. Computational results substantiate the solution quality and efficiency of the algorithm.
Ants of artificial colony are able to generate good solutions to the famous traveling salesman problem (TSP). We propose an artificial ants algorithm for solving the minimum ratio TSP, which is more general than the standard TSP in combinatorial optimization area. In the minimum ratio TSP, another criterion concerning each edge is added, that is, the traveling salesman can have a benefit if he travels from one city to another. The objective is to minimize the ratio between total costs or distances and total benefits. The idea of this type of optimization is in some sense quite similar to that of traditional cost-benefit analysis in management science. Computational results substantiate the solution quality and efficiency of the algorithm.
基金
This project was supported by the Shanghai Education Development Foundation (No.2000SG30).
