The Clustered Traveling Salesman Problem with a Prespecified Order on the Clusters, a variant of the well-known traveling salesman problem is studied in literature. In this problem, delivery locations are divided into clusters with different urgency levels and more urgent locations must be visited before less urgent ones. However, this could lead to an inefficient route in terms of traveling cost. This priority-oriented constraint can be relaxed by a rule called d-relaxed priority that provides a trade-off between transportation cost and emergency level. Our research proposes two approaches to solve the problem with d-relaxed priority rule. We improve the mathematical formulation proposed in the literature to construct an exact solution method. A meta-heuristic method based on the framework of Iterated Local Search with problem-tailored operators is also introduced to find approximate solutions. Experimental results show the effectiveness of our methods.
翻译:集中旅行销售商问题,包括预先规定的集群销售商问题,在文献中研究了众所周知的旅行销售商问题的一种变式,在此问题上,交货地点被分为不同紧迫程度的集群,在不那么紧迫的情况下,必须先对更紧急的地点进行视察,但是,这可能导致旅行费用方面的一条效率低下的路线,而这种注重优先的制约可以通过一项称为 " 低度优先 " 的规则来放松,该规则规定了运输成本与紧急程度之间的权衡。我们的研究提出了两种办法,用低度优先规则来解决问题。我们改进了文献中建议的数学公式,以构建一个精确的解决方案。还采用了基于与问题特制操作商的 " 本地循环搜索 " 框架的超常方法,以寻找近似的解决办法。实验结果显示了我们方法的有效性。