物流配送优化问题及算法2006年12月17日 星期日 上午 10:351、旅行商问题(TravelingSalesmanProblem,TSP) 这个问题字面上的理解是:有一个推销员,要到n个城市推销商品,他要找出一个包含所有n个城市的具有最短路程的环路。TSP的历史很久,最早的描述是1759年欧拉研究的骑士周游问题,即对于国际象棋棋盘中的64个方格,走访64个方格一次且仅一次,并且最终返回到起始点。TSP由美国RAND公司于1948年引入,该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。2、中国邮递员问题(ChinesePostmanProblemCPP)同样的问题,在中国还有另一个描述方法:一个邮递员从邮局出发,到所辖街道投递邮件,最后返回邮局,如果他必须走遍所辖的每条街道至少一次,那么他应如何选择投递路线,使所走的路程最短?这个描述之所以称为中国邮递员问题,因为是我国学者管梅古谷教授于1962年提出的这个问题并且给出了一个解法。3、“一笔画”问题(Drawingbyoneline)