Search results for "Travelling"
showing 10 items of 44 documents
A note on the separation of subtour elimination constraints in elementary shortest path problems
2013
Abstract This note proposes an alternative procedure for identifying violated subtour elimination constraints (SECs) in branch-and-cut algorithms for elementary shortest path problems. The procedure is also applicable to other routing problems, such as variants of travelling salesman or shortest Hamiltonian path problems, on directed graphs. The proposed procedure is based on computing the strong components of the support graph. The procedure possesses a better worst-case time complexity than the standard way of separating SECs, which uses maximum flow algorithms, and is easier to implement.
Separating capacity constraints in the CVRP using tabu search
1998
Abstract Branch and Cut methods have shown to be very successful in the resolution of some hard combinatorial optimization problems. The success has been remarkable for the Symmetric Traveling Salesman Problem (TSP). The crucial part in the method is the cutting plane algorithm: the algorithm that looks for valid inequalities that cut off the current nonfeasible linear program (LP) solution. In turn this part relies on a good knowledge of the corresponding polyhedron and our ability to design algorithms that can identify violated valid inequalities. This paper deals with the separation of the capacity constraints for the Capacitated Vehicle Routing Problem (CVRP). Three algorithms are prese…
Using a TSP heuristic for routing order pickers in warehouses
2010
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-sp…
Optimal Paths on Urban Networks Using Travelling Times Prevision
2012
We deal with an algorithm that, once origin and destination are fixed, individuates the route that permits to reach the destination in the shortest time, respecting an assigned maximal travel time, and with risks measure below a given threshold. A fluid dynamic model for road networks, according to initial car densities on roads and traffic coefficients at junctions, forecasts the future traffic evolution, giving dynamical weights to a constrained 𝐾 shortest path algorithm. Simulations are performed on a case study to test the efficiency of the proposed procedure.
The Rural Postman Problem on mixed graphs with turn penalties
2002
In this paper we deal with a problem which generalizes the Rural Postman Problem defined on a mixed graph (MRPP). The generalization consists of associating a non-negative penalty to every turn as well as considering the existence of forbidden turns. This new problem fits real-world situations more closely than other simpler problems. A solution tour must traverse all the requiring service arcs and edges of the graph while not making forbidden turns. Its total cost will be the sum of the costs of the traversed arcs and edges together with the penalties associated with the turns done. The Mixed Rural Postman Problem with Turn Penalties (MRPPTP) consists of finding such a tour with a total mi…
Development of new CdZnTe detectors for room-temperature high-flux radiation measurements
2017
Recently, CdZnTe (CZT) detectors have been widely proposed and developed for room-temperature X-ray spectroscopy even at high fluxes, and great efforts have been made on both the device and the crystal growth technologies. In this work, the performance of new travelling-heater-method (THM)-grown CZT detectors, recently developed at IMEM-CNR Parma, Italy, is presented. Thick planar detectors (3 mm thick) with gold electroless contacts were realised, with a planar cathode covering the detector surface (4.1 mm × 4.1 mm) and a central anode (2 mm × 2 mm) surrounded by a guard-ring electrode. The detectors, characterized by low leakage currents at room temperature (4.7 nA cm−2 at 1000 V cm−1), a…
A velocity–diffusion method for a Lotka–Volterra system with nonlinear cross and self-diffusion
2009
The aim of this paper is to introduce a deterministic particle method for the solution of two strongly coupled reaction-diffusion equations. In these equations the diffusion is nonlinear because we consider the cross and self-diffusion effects. The reaction terms on which we focus are of the Lotka-Volterra type. Our treatment of the diffusion terms is a generalization of the idea, introduced in [P. Degond, F.-J. Mustieles, A deterministic approximation of diffusion equations using particles, SIAM J. Sci. Stat. Comput. 11 (1990) 293-310] for the linear diffusion, of interpreting Fick's law in a deterministic way as a prescription on the particle velocity. Time discretization is based on the …
A theoretical approach of the propagation through geometrical constraints in cardiac tissue
2007
International audience; The behaviour of impulse propagation in the presence of non-excitable scars and boundaries is a complex phenomenon and induces pathological consequences in cardiac tissue. In this article, a geometrical con¯guration is considered so that cardiac waves propagate through a thin strand, which is connected to a large mass of cells. At this interface, waves can slow down or even be blocked depending on the width of the strand. We present an analytical approach leading to determine the blockade condition, by introducing planar travelling wavefront and circular stationary wave. Eventually, the in°uence of the tissue geometry is examined on the impulse propagation velocity.
Automating the Parameter Selection in VRP: An Off-line Parameter Tuning Tool Comparison
2014
Vehicle route optimization is an important application of combinatorial optimization. Therefore, a variety of methods has been proposed to solve different challenging vehicle routing problems. An important step in adopting these methods to solve real-life problems is to find appropriate parameters for the routing algorithms. In this chapter, we show how this task can be automated using parameter tuning by presenting a set of comparative experiments on seven state-of-the-art tuning methods. We analyze the suitability of these methods in configuring routing algorithms, and give the first critical comparison of automated parameter tuners in vehicle routing. Our experimental results show that t…
Generation of travelling sine-Gordon breathers in noisy long Josephson junctions
2022
The generation of travelling sine-Gordon breathers is achieved through the nonlinear supratransmission effect in a magnetically driven long Josephson junction, in the presence of losses, a current bias, and a thermal noise source. We demonstrate how to exclusively induce breather modes by means of controlled magnetic pulses. A nonmonotonic behavior of the breather-only generation probability is observed as a function of the noise intensity. An experimental protocol providing evidence of the Josephson breather's existence is proposed.