Total flowtime and makespan for a no-wait <Emphasis Type="Italic">m</Emphasis>-machine flowshop with set-up times separated

This paper addresses the m-machine no-wait flowshop problem where the set-up time of a job is separated from its processing time. The performance measures considered are the total flowtime and makespan. The scheduling problem for makespan reduces to the travelling salesman problem (TSP), and the scheduling problem for total flowtime reduces to the time-dependent travelling salesman problem (TDTSP). Non-polynomial time solution methods are presented, along with a polynomial heuristic.     

Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem

The generalized traveling salesman problem (GTSP) is a well-known combinatorial optimization problem with a host of applications. It is an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into so-called clusters, and the salesman has to visit every cluster exactly once.     

A cutting plane procedure for the travelling salesman problem on road networks

A cutting plane algorithm for the exact solution of the symmetric travelling salesman problem (TSP) is proposed. The real tours on a usually incomplete road network, which are in general non-Hamiltonian, are characterized directly by an integer linear programming model. The algorithm generates special cutting planes for this model. Computational results for real road networks with up to 292 visiting places are reported, as well as for classical problems of the literature with up to 120 cities. Some of the latter problems have been solved for the first time with a pure cutting plane approach.     

The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms

We identify new solvable cases of the travelling salesman problem (TSP) by an indirect analysis that has useful consequences. First, we develop new procedures for the TSP that require only linear time to execute and yield TSP tours that are better than an exponential number of alternative tours. We then identify special subgraphs, easily generated, so that our method yields these outcomes for every instance of these subgraphs. Finally, when the associated costs satisfy prescribed conditions, we show the solutions produced by these algorithms are optimal and thus we have new solvable cases of the TSP. Besides possible practical applications to problems that may exhibit these cost conditions, our algorithms may also be applied as subroutines within more complex metaheuristics. Our methods extend in a natural way to bottleneck TSP formulations, and their underlying results raise new theoretical questions about the analysis of heuristics for hard combinatorial problems.     

A note on the lifted Miller–Tucker–Zemlin subtour elimination constraints for routing problems with time windows

We propose lifted versions of the Miller–Tucker–Zemlin subtour elimination constraints for routing problems with time windows (TW). The constraints are valid for problems such as the travelling salesman problem with TW, the vehicle routing problem with TW, the generalized travelling salesman problem with TW, and the general vehicle routing problem with TW. They are corrected versions of the constraints proposed by Desrochers and Laporte (1991).     

NP完全问题多项式时间算法研究

本文从代数及组合两个方面论证了NP完全问题存在多项式时间算法 .以往利用线性规划 (LP)技术来分析NP完全问题中的TSP问题 ,因其存在子环游问题 ,从而使问题得不到有效解决 .文中发展一分层网络 ,在求解TSP问题时 ,存在另一类(不完全 )子环游问题 .但两模型允许解集的交集避免了两类子环游基本可行解 ,从而使TSP问题可利用LP技术多项式时间内得以解决 ,同时给出了求哈密尔顿回路的多项式标记证明方法 ,开创了NPC问题研究的新局面 .     

Maximizing the profit per unit of time for the TSP with convex resource-dependent travelling times

This paper introduces a new problem that is an extension of the travelling salesman problem (TSP) in which the travelling times are resource dependent and the objective is to maximize the profit per unit of time. We present an optimal solution approach comprised of three main steps: (1) calculating the optimal amount of total resource required (regardless of the selected tour); (2) constructing the tour; and (3) assigning the optimal resource to each connection between vertices using the equivalent load method. This solution approach finds the optimal solution with the same computational complexity for solving the classic TSP.     

Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions

Mukherjee and Basu proposed a new method for solving fuzzy assignment problems. In this paper, some fuzzy assignment problems and fuzzy travelling salesman problems are chosen which cannot be solved by using the fore-mentioned method. Two new methods are proposed for solving such type of fuzzy assignment problems and fuzzy travelling salesman problems. The fuzzy assignment problems and fuzzy travelling salesman problems which can be solved by using the existing method, can also be solved by using the proposed methods. But, there exist certain fuzzy assignment problems and fuzzy travelling salesman problems which can be solved only by using the proposed methods. To illustrate the proposed methods, a fuzzy assignment problem and a fuzzy travelling salesman problem is solved. The proposed methods are easy to understand and apply to find optimal solution of fuzzy assignment problems and fuzzy travelling salesman problems occurring in real life situations.     

Heuristic Approaches for a Scheduling Problem in the Plastic Molding Department of an Audio Company

A production scheduling problem for making plastic molds of hi-fi models is considered. The objective is to minimize the total machine makespan in the presence of due dates, variable lot size, multiple machine types, sequence dependent, machine dependent setup times, and inventory limits. Goal programming and load balancing are applied to select the set of machine types and assign mold types to machines, resulting in a set of single-machine scheduling problems. A mixed-integer program (MIP) is formulated for the general problem but could solve only small instances. A single-machine scheduling heuristic is designed to adopt a production sequence from a travelling salesman solution. The start time of every cycle is determined by a simplified MIP. Production cycles are defined to equalize the stockout times of mold types. A post-processing step reduces the number of setups in the last cycle. Results using real-life data are promising. Characteristics giving rise to high machine utilization are discussed.     

An improved upper bound for the TSP in cubic 3-edge-connected graphs

We consider the travelling salesman problem (TSP) problem on (the metric completion of) 3-edge-connected cubic graphs. These graphs are interesting because of the connection between their optimal solutions and the subtour elimination LP relaxation. Our main result is an approximation algorithm better than the 3/2-approximation algorithm for TSP in general.     

The Vehicle Routing-Allocation Problem: A unifying framework

Summary In this paper the Vehicle Routing-Allocation Problem (VRAP) is presented. In VRAP not all customers need be visited by the vehicles. However customers not visited either have to be allocated to some customer on one of the vehicle tours or left isolated. We concentrate our discussion on the Single Vehicle Routing-Allocation Problem (SVRAP). An integer linear programming formulation of SVRAP is presented and we show how SVRAP provides a unifying framework for understanding a number of the papers and problems presented in the literature. Specifically the covering tour problem, the covering salesman problem, the median tour problem, the maximal covering tour problem, the travelling salesman problem, the generalised travelling salesman problem, the selective travelling salesman problem, the prize collecting travelling salesman problem, the maximum covering/shortest path problem, the maximum population/shortest path problem, the shortest covering path problem, the median shortest path problem, the minimum covering/shortest path problem and the hierarchical network design problem are special cases/variants of SVRAP.     

An algorithm for finding hamilton paths and cycles in random graphs

This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the existence of such a cycle. If all graphs withn vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. The algorithm HAM is also used to solve the symmetric bottleneck travelling salesman problem with probability tending to 1, asn tends to ∞. Various modifications of HAM are shown to solve several Hamilton path problems. Supported by NSF Grant MCS 810 4854.     

Experimental analysis of heuristics for the bottleneck traveling salesman problem

In this paper we develop efficient heuristic algorithms to solve the bottleneck traveling salesman problem (BTSP). Results of extensive computational experiments are reported. Our heuristics produced optimal solutions for all the test problems considered from TSPLIB, JM-instances, National TSP instances, and VLSI TSP instances in very reasonable running time. We also conducted experiments with specially constructed ‘hard’ instances of the BTSP that produced optimal solutions for all but seven problems. Some fast construction heuristics are also discussed. Our algorithms could easily be modified to solve related problems such as the maximum scatter TSP and testing hamiltonicity of a graph.     

A tour construction heuristic for the travelling salesman problem

The tour construction heuristic that generates initial tours for the tour improvement heuristics plays an important role in solving the travelling salesman problem (TSP). With the help of an effective tour construction heuristic, the performance of a heuristic can be improved. In this study we present a new tour construction algorithm, the construction priority (CP). We incorporate the performance of the CP into metaheuristics such as tabu search, genetic algorithm, space smoothing, and noising methods. The performance of the CP is empirically compared with the nearest neighbour (NN) approach. Extensive computational comparison shows that the CP is considerably more effective compared to NN.     

Some Simple Applications of the Travelling Salesman Problem

The travelling salesman problem arises in many different contexts. In this paper we report on typical applications in computer wiring, vehicle routing, clustering and job-shop scheduling. The formulation as a travelling salesman problem is essentially the simplest way to solve these problems. Most applications originated from real world problems and thus seem to be of particular interest. Illustrated examples are provided with each application.     

Using a TSP heuristic for routing order pickers in warehouses

In this paper, we deal with the sequencing and routing problem of order pickers in conventional multi-parallel-aisle warehouse systems. For this NP-hard Steiner travelling salesman problem (TSP), exact algorithms only exist for warehouses with at most three cross aisles, while for other warehouse types literature provides a selection of dedicated construction heuristics. We evaluate to what extent reformulating and solving the problem as a classical TSP leads to performance improvements compared to existing dedicated heuristics. We report average savings in route distance of up to 47% when using the LKH (Lin–Kernighan–Helsgaun) TSP heuristic. Additionally, we examine if combining problem-specific solution concepts from dedicated heuristics with high-quality local search features could be useful. Lastly, we verify whether the sophistication of ‘state-of-the-art’ local search heuristics is necessary for routing order pickers in warehouses, or whether a subset of features suffices to generate high-quality solutions.     

Solvable Cases of the No-Wait Flow-Shop Scheduling Problem

The no-wait flow-shop scheduling problem (NWFSSP) with a makespan objective function is considered. As is well known, this problem is ????-hard for three or more machines. Therefore, it is interesting to consider special cases, i.e. special structured processing time matrices, that allow polynomial time solution algorithms. Furthermore, it is well known that the NWFSSP with a makespan objective function can be formulated as a travelling salesman problem (TSP). It is observed that special structured processing time matrices for the NWFSSP lead to special structured distance matrices for which the TSP is polynomially solvable. Using this observation, it is shown that some NWFSSPs with fixed processing times on all except two machines are well solvable while the others are conjectured to be ????-hard. Also, it is shown that NWFSSPs with a mean completion time objective function restricted to semi-ordered processing time matrices are easily solvable.     

A decomposition approach for optimal control problems with integer innerpoint state constraints

A large class of optimal control problems for hybrid dynamic systems can be formulated as mixed‐integer optimal control problems (MIOCPs). A decomposition approach is suggested to solve a special subclass of MIOCPs with mixed integer inner point state constraints. It is the intrinsic combinatorial complexity of the discrete variables in addition to the high nonlinearity of the continuous optimal control problem that forms the challenges in the theoretical and numerical solution of MIOCPs. During the solution procedure the problem is decomposed at the inner time points into a multiphase problem with mixed integer boundary constraints and phase transitions at unknown switching points. Due to a discretization of the state space at the switching points the problem can be decoupled into a family of continuous optimal control problems (OCPs) and a problem similar to the asymmetric group traveling salesman problem (AGTSP). The OCPs are transcribed by direct collocation to large‐scale nonlinear programming problems, which are solved efficiently by an advanced SQP method. The results are used as weights for the edges of the graph of the corresponding TSP‐like problem, which is solved by a Branch‐and‐Cut‐and‐Price (BCP) algorithm. The proposed approach is applied to a hybrid optimal control benchmark problem for a motorized traveling salesman. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Speeding up IP-based algorithms for constrained quadratic 0–1 optimization

In many practical applications, the task is to optimize a non-linear objective function over the vertices of a well-studied polytope as, e.g., the matching polytope or the travelling salesman polytope (TSP). Prominent examples are the quadratic assignment problem and the quadratic knapsack problem; further applications occur in various areas such as production planning or automatic graph drawing. In order to apply branch-and-cut methods for the exact solution of such problems, the objective function has to be linearized. However, the standard linearization usually leads to very weak relaxations. On the other hand, problem-specific polyhedral studies are often time-consuming. Our goal is the design of general separation routines that can replace detailed polyhedral studies of the resulting polytope and that can be used as a black box. As unconstrained binary quadratic optimization is equivalent to the maximum-cut problem, knowledge about cut polytopes can be used in our setting. Other separation routines are inspired by the local cuts that have been developed by Applegate, Bixby, Chvátal and Cook for faster solution of large-scale traveling salesman instances. Finally, we apply quadratic reformulations of the linear constraints as proposed by Helmberg, Rendl and Weismantel for the quadratic knapsack problem. By extensive experiments, we show that a suitable combination of these methods leads to a drastic speedup in the solution of constrained quadratic 0–1 problems. We also discuss possible generalizations of these methods to arbitrary non-linear objective functions.