An Explicit Lower Bound for TSP with Distances One and Two

Abstract. We show that, for any ɛ>0 , it is NP-hard to approximate the asymmetric traveling salesman problem with distances one and two within 2805/2804-ɛ . For the special case where the distance function is constrained to be symmetric, we show a lower bound of 5381/5380-ɛ , for any ɛ>0 . While it was previously known that there exists some constant, strictly greater than one, such that it is NP-hard to approximate the traveling salesman problem with distances one and two within that constant, this result is a first step towards the establishment of a good bound. In our proof we develop a new gadget construction to reduce from systems of linear equations mod 2 with two unknowns in each equation and at most three occurrences of each variable. Compared with earlier reductions to the traveling salesman problem with distances one and two, ours reduces the number of cities to less than a tenth of what was previously necessary.     

欧氏空间货郎担问题的一个多项式时间近似方案的改进与实现

货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离di,j,要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究的热点之一.在过去几十年中,这一经典问题成为许多重要算法思想的测试平台,并促使一些研究领域的出现,如多面体理论和复杂性理论.欧氏空间上的货郎担问题,结点限制在欧氏空间,距离定义为欧氏距离.即使是这样,欧氏空间上的货郎担问题仍然是NP难的.1996年,Arora提出欧氏空间上货郎担问题的第1个多项式时间近似方案.对其中货郎担问题的算法进行了改进：提出一种新的构造方法,使应用于该算法的“补丁引理”结论由常数6改进到常数3,从而使算法的时间复杂度大幅减少;同时,编程实现了该算法,并对实验结果进行了分析.     

球面旅行商问题常数及其实验分析

给出了球面随机旅行商问题最优值的一个上界以及最优值期望的一个下界.猜想球面旅行商问题常数存在且与平面旅行商问题常数相等.所做两组数值实验支持该猜想,且显示球面比平面正方形更适宜作为二维旅行商问题常数的测试床.     

Approximation algorithms for time-dependent orienteering

The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between two sites is in general dependent on the starting time.For any ε>0, we provide a (2+ε)-approximation algorithm for the time-dependent orienteering problem which runs in polynomial time if the ratio between the maximum and minimum traveling time between any two sites is constant. No prior upper approximation bounds were known for this time-dependent problem.     

求解TSP问题的多级归约算法

TSP(traveling salesman problem)问题是最经典的NP-hard组合优化问题之一.长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的计算时间内解决大规模问题.由于对较大规模的问题,目前的近似算法尚不能在较短的时间内给出高质量的解,因此提出了多重归约算法.该算法的基本原理是通过对TSP问题的局部最优解与全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解.利用这些部分解可以大大缩小原问题的搜索空间,同时也不会降低搜索的性能.这就是所谓的归约原理.再通过多次归约使问题的规模降到足够小,然后对这个较小规模的实例直接用已有的算法求解,最后通过相反的次序拼接部分解,最终得到一个合法的解.在TSPLIB(traveling salesman problem library)中,典型实例上的实验结果表明,此算法在求解质量和求解速度上与目前已知的算法相比有较大的改进.     

The symmetric travelling salesman problem II. New low bounds

The branch-and-bound method is adduced for the symmetric salesman problem where two lower bounds are proposed as bounds. The first bound is a solution to the problem of optimal 2-matching; the second one, to the problem of minimum spanning 1-tree. The last bound is enhanced by applying the problem of optimal 2-matching. Both these bounds considerably improve the symmetric traveling salesman problem as compared to the asymmetric problem.     

Lower tolerance-based Branch and Bound algorithms for the ATSP

In this paper, we develop a new tolerance-based Branch and Bound algorithm for solving NP-hard problems. In particular, we consider the asymmetric traveling salesman problem (ATSP), an NP-hard problem with large practical relevance. The main algorithmic contribution is our lower bounding strategy that uses the expected costs of including arcs in the solution to the assignment problem relaxation of the ATSP, the so-called lower tolerance values. The computation of the lower bound requires the calculation of a large set of lower tolerances. We apply and adapt a finding from [23] that makes it possible to compute all lower tolerance values efficiently. Computational results show that our Branch and Bound algorithm exhibits very good performance in comparison with state-of-the-art algorithms, in particular for difficult clustered ATSP instances.     

Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One

A cycle cover of a graph is a spanning subgraph, each node of which is part of exactly one simple cycle. A k-cycle cover is a cycle cover where each cycle has length at least k. Given a complete directed graph with edge weights zero and one, Max-k-DDC(0,1) is the problem of finding a k-cycle cover with maximum weight. We present a 2/3 approximation algorithm for Max-k-DDC(0,1) with running time O(n ^5/2). This algorithm yields a 4/3 approximation algorithm for Max-k-DDC(1,2) as well. Instances of the latter problem are complete directed graphs with edge weights one and two. The goal is to find a k-cycle cover with minimum weight. We particularly obtain a 2/3 approximation algorithm for the asymmetric maximum traveling salesman problem with distances zero and one and a 4/3 approximation algorithm for the asymmetric minimum traveling salesman problem with distances one and two. As a lower bound, we prove that Max-k-DDC(0,1) for k 3 and Max-k-UCC(0,1) (finding maximum weight cycle covers in undirected graphs) for k 7 are \APX-complete.     

On the relationship between the biconnectivity augmentation and travelling salesman problems

A strategy for solving the traveling salesman problem is adapted to the problem of finding a biconnected subgraph of a weighted graph whose cost function satisfies the triangle inequality. An approximation algorithm similar to Christofides' algorithm [5] for the traveling salesman problem is shown to possess the same worst-case bound of $\text{3}\text{2}$ when applied to the biconnectivity augmentation problem. A tight inequality is derived relating the cost of an optimal traveling salesman tour to the cost of an optimal biconnection.     

Two-Machine Stochastic Flow Shops With Blocking and the Traveling Salesman Problem

The paper deals with the problem of minimizing the expected makespan in a two-machine flow shop with blocking and random job processing times. It is well known that it reduces to an instance of the traveling salesman problem (TSP). Assuming that the job processing times can be stochastically ordered on both machines, we show that the problem under study is equivalent to TSP on a permuted Monge matrix. This allows us to prove that it is NP-hard for the independently and exponentially distributed job processing times, and identify a new class of efficiently solvable special cases.     

A comparison of algorithms for origin–destination matrix generation on real road networks and an approximation approach

This paper considers the generation of the origin–destination (OD) matrix, basic data in any vehicle routing or traveling salesman problem. An OD matrix must be generated by calculating the shortest paths between some nodes. Candidate methods for this are repetitive use of one-to-all shortest path algorithms such as Dijkstra’s algorithm, use of all-to-all shortest path algorithms such as the Floyd–Warshall algorithm, and use of specifically designed some-to-some shortest path algorithms. This paper compares the performance of several shortest path algorithms in computing OD matrices on real road networks. Dijkstra’s algorithm with approximate bucket data structure performed the best for most of the networks tested. This paper also proposes a grouping-based algorithm for OD matrix generation. Although it is an approximation approach, it has several good characteristics: it can find the exact shortest distances for most OD pairs; it guarantees that all the calculated shortest path distance values have corresponding paths; the deviation of any distance from the corresponding true shortest distance is small; and its computation time is short.     

A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem

We address in this paper the one-commodity pickup-and-delivery traveling salesman problem, which is characterized by a set of customers, each of them supplying (pickup customer) or demanding (delivery customer) a given amount of a single product. The objective is to design a minimum cost Hamiltonian route for a capacitated vehicle in order to transport the product from the pickup to the delivery customers. The vehicle starts the route from a depot, and its initial load also has to be determined. We propose a hybrid algorithm that combines the GRASP and VND metaheuristics. Our heuristic is compared with other approximate algorithms described in Hernández-Pérez and Salazar-González [Heuristics for the one-commodity pickup-and-delivery traveling salesman problem. Transportation Science 2004;38:245–55]. Computational experiments on benchmark instances reveal that our hybrid method yields better results than the previously proposed approaches.     

An Algorithm for the One Commodity Pickup and Delivery Traveling Salesman Problem with Restricted Depot

In this paper we study the one commodity pickup-and-delivery traveling salesman problem with restricted depot (1-PDTSP-RD), which is a generalization of the classical traveling salesman problem (TSP). We first introduce a polynomial size integer programming formulation for the problem and then study the feasibility issue which is shown to be \(\mathcal {NP}\)-complete by itself. In particular, we prove sufficient conditions for the feasibility of the problem and provide a polynomial algorithm to find a feasible solution. We also develop a bound on the cost of the 1-PDTSP-RD solution in terms of the cost of the TSP solution. Based on this bound, we provide a heuristic algorithm to solve the 1PDTSP-RD. Extensive numerical experiments are performed to evaluate the efficiency of both the exact and approximation algorithms.     

群体间竞争与协作的遗传算法解决旅行商问题

旅行商问题是经典的NP难组合优化问题之一,快速有效地解决旅行商问题具有重要的理论和实际意义。受自然界物种群体间相互联系的启发,提出了群体间竞争与协作的遗传算法来解决旅行商问题。该算法在迭代的过程中,每次只选择竞争力大的种群进行进化,同时为了维持各个种群间发展的平衡,对它们进行周期性的交流,能促使进化过程中中好的基因模式迅速地在各个种群中传播,提高了整体的进化速度。此算法不但能有效地维持群体的多样性,而且能提高收敛的速度。通过对旅行商问题的仿真实验,证明了该算法的可行性与有效性。     

Improving Combinatorial Optimization Algorithms through Record Keeping in Constructive Multistart Search

Constructive multistart search algorithms are commonly used to address combinatorial optimization problems; however, constructive multistart search algorithm performance is fundamentally affected by two factors: (i) The choice of construction algorithm utilized and (ii) the rate of state space search redundancy. Construction algorithms are typically specific to a particular combinatorial optimization problem; therefore, we first investigate construction algorithms for iterative hill climbing applied to the traveling salesman problem and experimentally determine the best performing algorithms. We then investigate the more general problem of utilizing record‐keeping mechanisms to mitigate state space search redundancy. Our research shows that a good choice of construction algorithm paired with effective record keeping significantly improves the quality of traveling salesmen problem solutions in a constant number of state explorations. Particularly, we show that Bloom filters considerably improve time performance and solution quality for iterative hill climbing approaches to the traveling salesman problem.     

Hybrid control systems and the dynamic traveling salesman problem

A new approximate algorithm for solving the dynamic traveling salesman problem (DTSP) is proposed; the traveling salesman starting from the base city visits megapoleis and cities inside megapoleis and comes back to the base city. A specific feature of this variant of DTSP is the movement of cities inside megapoleis in time. To solve this problem, a general solution theory for hybrid (complicated) systems with “combinatorial” and “continuous” path segments is developed. The general theory is based on the sufficient optimality conditions known in the theory of optimal control.     

混合最大最小蚁群算法在VRPTW中的应用

为解决有时间窗车辆路径问题,采用两个最大最小蚁群系统,一个蚁群最小化车辆数量,另一个蚁群最小化旅行距离。通过分析有时间窗车辆路径问题和旅行商问题的区别,改进了最大最小蚁群算法中状态转移策略,并增加与可用车辆相同数量的虚拟仓库,使这两个蚁群使用独立的信息素但通过分享全局最优解来协作,算法还结合了2-opt局部搜索,从而减少了算法的计算时间并避免过早收敛。仿真实验结果表明,该算法性能优良,能有效地求解有时间窗车辆路径问题。     

A novel discretization scheme for the close enough traveling salesman problem

This paper addresses a variant of the Euclidean traveling salesman problem in which the traveler visits a node if it passes through the neighborhood set of that node. The problem is known as the close-enough traveling salesman problem. We introduce a new effective discretization scheme that allows us to compute both a lower and an upper bound for the optimal solution. Moreover, we apply a graph reduction algorithm that significantly reduces the problem size and speeds up computation of the bounds. We evaluate the effectiveness and the performance of our approach on several benchmark instances. The computational results show that our algorithm is faster than the other algorithms available in the literature and that the bounds it provides are almost always more accurate.     

Discrete optimization by optimal control methods. III. The dynamic traveling salesman problem

For one of the basic variants of the dynamic minisum traveling salesman problem, a decomposition scheme is designed, which in general gives a new approximate solution algorithm. This algorithm is exact if certain conditions are imposed on the distance matrix. The problem is solved with the sufficient optimality conditions known in optimal control theory.     

Irreducible bin packing and normality in routing open shop

The open shop is a classical scheduling problem known since 1976, which can be described as follows. A number of jobs have to be processed by a given set of machines, each machine should perform an operation on every job, and the processing times of all the operations are given. One has to construct a schedule to perform all the operations to minimize finish time also known as the makespan. The open shop problem is known to be NP-hard for three and more machines, while is polynomially solvable in the case of two machines. We consider the routing open shop problem, being a generalization of both the open shop problem and the metric traveling salesman problem. In this setting, jobs are located at nodes of a transportation network and have to be processed by mobile machines, initially located at a predefined depot. Machines have to process all the jobs and return to the depot to minimize makespan. A feasible schedule is referred to as normal if its makespan coincides with the standard lower bound. We introduce the Irreducible Bin Packing decision problem, use it to describe new sufficient conditions of normality for the two machine problem, and discuss the possibility to extend these results on the problem with three and more machines. To that end, we present two new computer-aided optima localization results.