A Cut-and-Branch Algorithm for the Multicommodity Traveling Salesman Problem

摘要：

This paper presents a Cut-and-Branch algorithm for the Multicommodity Traveling Salesman Problem (MTSP),a useful variant of the Traveling Salesman Problem (TSP).The MTSP presents a more general cost structure,allowing for solutions that consider the quality of service to the customers,delivery priorities and delivery risk,among other possible objectives.In the MTSP the salesman pays the traditional TSP fixed cost for each arc visited,plus a variable cost for each of the commodities being transported across the network.We present a strong mathematical formulation for this relevant problem.We implement a Cut-and-Branch algorithm for the MTSP which is able to find optimal solutions faster than stand-alone CPLEX codes.

关键词： Multicommodity Traveling Salesman Problem Minimum Latency Problem Cut-and-Branch Algorithm Benders Decomposition

作者: Joao Sarubbi Gilberto Miranda Henrique Pacca Luna Geraldo Mateus

作者单位: CEFET-MG Divin′opolis-MG-Brazil UFMG Belo Horizonte,Brazil UFAL Macei′o,AL,Brazil UFMG Belo Horizonte,MG,Brazil

会议类型: 国际会议

会议名称: 2008 IEEE International Conference on Service Operations and Logistics, and Informatics(IEEE/SOLI’2008)(IEEE服务运作、物流与信息年会)

会议地点: 北京

会议语种:英文

在线出版日期: 2008-10-12（万方平台首次上网日期，不代表论文的发表时间）