广义旅行商问题与旅行商问题的转化

摘要

广义旅行商问题(Generalized Traveling Salesman Problem,简称GTSP)是比旅行商问题(Traveling Salesman Problem,简称TSP)更为复杂的一类组合优化问题,TSP可视为GTSP的特例.GTSP的应用领域更广,但相对于TSP的研究而言,GTSP的研究成果很少.本文介绍了GTSP问题的定义与背景,研完了GTSP与TSP的转化,提出了转化的优缺点和研究方向.