Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints

In this paper, we extend the multiple traveling repairman problem by considering a limitation on the total distance that a vehicle can travel; the resulting problem is called the multiple traveling repairmen problem with distance constraints (MTRPD). In the MTRPD, a fleet of identical vehicles is dispatched to serve a set of customers. Each vehicle that starts from and ends at the depot is not allowed to travel a distance longer than a predetermined limit and each customer must be visited exactly once. The objective is to minimize the total waiting time of all customers after the vehicles leave the depot. To optimally solve the MTRPD, we propose a new exact branch-and-price-and-cut algorithm, where the column generation pricing subproblem is a resource-constrained elementary shortest-path problem with cumulative costs. An ad hoc label-setting algorithm armed with bidirectional search strategy is developed to solve the pricing subproblem. Computational results show the effectiveness of the proposed method. The optimal solutions to 179 out of 180 test instances are reported in this paper. Our computational results serve as benchmarks for future researchers on the problem.     

Smooth and non-smooth traveling wave solutions of some generalized Camassa–Holm equations

In this paper we employ two recent analytical approaches to investigate the possible classes of traveling wave solutions of some members of a recently-derived integrable family of generalized Camassa–Holm (GCH) equations. A recent, novel application of phase-plane analysis is employed to analyze the singular traveling wave equations of three of the GCH NLPDEs, i.e. the possible non-smooth peakon and cuspon solutions. One of the considered GCH equations supports both solitary (peakon) and periodic (cuspon) cusp waves in different parameter regimes. The second equation does not support singular traveling waves and the last one supports four-segmented, non-smooth M-wave solutions.Moreover, smooth traveling waves of the three GCH equations are considered. Here, we use a recent technique to derive convergent multi-infinite series solutions for the homoclinic orbits of their traveling-wave equations, corresponding to pulse (kink or shock) solutions respectively of the original PDEs. We perform many numerical tests in different parameter regime to pinpoint real saddle equilibrium points of the corresponding GCH equations, as well as ensure simultaneous convergence and continuity of the multi-infinite series solutions for the homoclinic orbits anchored by these saddle points. Unlike the majority of unaccelerated convergent series, high accuracy is attained with relatively few terms. We also show the traveling wave nature of these pulse and front solutions to the GCH NLPDEs.     

Traveling wave solutions of nonlinear evolution equations via the enhanced (G′/G)-expansion method

In this article, an enhanced (G′/G)-expansion method is suggested to find the traveling wave solutions for the modified Korteweg de-Vries (mKDV) equation. Abundant traveling wave solutions are derived, which are expressed by the hyperbolic and trigonometric functions involving several parameters. The efficiency of this method for finding these exact solutions has been demonstrated. It is shown that the proposed method is effective and can be used for many other nonlinear evolution equations (NLEEs) in mathematical physics.     

Searching the k-change neighborhood for TSP is W[1]-hard

We show that searching the k-change neighborhood is W[1]-hard for metric TSP, which means that finding the best tour in the k-change neighborhood essentially requires complete search (modulo some complexity-theoretic assumptions).     

An application of traveling wave analysis in economic growth model

A temporal–spatial economic growth model is established in this paper. As a useful tool, traveling wave analysis is used to analyze technological growth and diffusion. Numerical simulation shows that this model has perfect performance.     

红外激光技术在运动物体位置跟踪系统中的应用

运动物体位置跟踪系统可用工作在红外波段的激光 ,测量“调制光波”往返于被测距离上相位差的方法来测定距离。利用 DSP鉴相技术 ,通过快速傅立叶变换软件可快速实时测量运动物体的距离及其运行速度。该系统能极其准确地显示运动物体的实际位置 ,实现对运动物体速度的数字化控制。     

On the graphical relaxation of the symmetric traveling salesman polytope

The Graphical Traveling Salesman Polyhedron (GTSP) has been proposed by Naddef and Rinaldi to be viewed as a relaxation of the Symmetric Traveling Salesman Polytope (STSP). It has also been employed by Applegate, Bixby, Chvátal, and Cook for solving the latter to optimality by the branch-and-cut method. There is a close natural connection between the two polyhedra. Until now, it was not known whether there are facets in TT-form of the GTSP polyhedron which are not facets of the STSP polytope as well. In this paper we give an affirmative answer to this question for n ≥ 9. We provide a general method for proving the existence of such facets, at the core of which lies the construction of a continuous curve on a polyhedron. This curve starts in a vertex, walks along edges, and ends in a vertex not adjacent to the starting vertex. Thus there must have been a third vertex on the way.      

Analysis of crossovers and selections in a coarse-grained parallel genetic algorithm

The parallel genetic algorithms (PGA) have been developed for combinatorial optimization problems, and its parallel efficiencies have been investigated on a specific problem. These investigations were concerned with how to design a topology and the determination of the optimum setting for parameters (for example, size of subpopulations, migration interval, and so on) rather than the effectiveness of genetic operators. This paper investigates a relation between the parallel efficiency of the coarse-grained PGA and genetic (crossover and selection) operators for the traveling salesman problem on an MIMD parallel computer. The following genetic operators are considered: improved edge recombination (IERX), distance preserving (DPX), and complete subtour exchange (CSEX) crossovers, and two selection operators, which have relatively high selection pressures. Computational results indicate that the parallel efficiency is significantly affected by the difference of crossovers rather than the selections, and the PGA with CSEX gives better properties.