Home  About us  Contact
 

Salesman Problem (salesman + problem)

Distribution by Scientific Domains
Engineering26%

Kinds of Salesman Problem

  • traveling salesman problem
    		•

    Selected Abstracts

    Surgical correction of scoliosis: Numerical analysis and optimization of the procedure

    INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN BIOMEDICAL ENGINEERING, Issue 9 2010
    J. F. Aguilar Madeira
    Abstract A previously developed model is used to numerically simulate real clinical cases of the surgical correction of scoliosis. This model consists of one-dimensional finite elements with spatial deformation in which (i) the column is represented by its axis; (ii) the vertebrae are assumed to be rigid; and (iii) the deformability of the column is concentrated in springs that connect the successive rigid elements. The metallic rods used for the surgical correction are modeled by beam elements with linear elastic behavior. To obtain the forces at the connections between the metallic rods and the vertebrae geometrically, non-linear finite element analyses are performed. The tightening sequence determines the magnitude of the forces applied to the patient column, and it is desirable to keep those forces as small as possible. In this study, a Genetic Algorithm optimization is applied to this model in order to determine the sequence that minimizes the corrective forces applied during the surgery. This amounts to find the optimal permutation of integers 1, ,, n, n being the number of vertebrae involved. As such, we are faced with a combinatorial optimization problem isomorph to the Traveling Salesman Problem. The fitness evaluation requires one computing intensive Finite Element Analysis per candidate solution and, thus, a parallel implementation of the Genetic Algorithm is developed. Copyright © 2010 John Wiley & Sons, Ltd. [source]

    A travelling salesman problem with allocation, time window and precedence constraints , an application to ship scheduling

    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 3 2000
    K. Fagerholt
    Abstract A Travelling Salesman Problem with Allocation, Time Window and Precedence Constraints (TSP-ATWPC) is considered. The TSP-ATWPC occurs as a subproblem of optimally sequencing a given set of port visits in a real bulk ship scheduling problem, which is a combined multi-ship pickup and delivery problem with time windows and multi-allocation problem. Each ship in the fleet is equipped with a flexible cargo hold that can be partitioned into several smaller holds in a given number of ways, thus allowing multiple products to be carried simultaneously by the same ship. The allocation constraints of the TSP-ATWPC ensure that the partition of the ship's flexible cargo hold and the allocation of cargoes to the smaller holds are feasible throughout the visiting sequence. The TSP-ATWPC is solved as a shortest path problem on a graph whose nodes are the states representing the set of nodes in the path, the last visited node and the accumulated cargo allocation. The arcs of the graph represent transitions from one state to another. The algorithm is a forward dynamic programming algorithm. A number of domination and elimination tests are introduced to reduce the state space. The computational results show that the proposed algorithm for the TSP-ATWPC works, and optimal solutions are obtained to the real ship scheduling problem. [source]

    The one-commodity pickup-and-delivery traveling salesman problem: Inequalities and algorithms

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2007
    Hipólito Hernández-Pérez
    Abstract This article concerns the "One-commodity Pickup-and-Delivery Traveling Salesman Problem" (1-PDTSP), in which a single vehicle of fixed capacity must either pick up or deliver known amounts of a single commodity to a given list of customers. It is assumed that the product collected from the pickup customers can be supplied to the delivery customers, and that the initial load of the vehicle leaving the depot can be any quantity. The problem is to find a minimum-cost sequence of the customers in such a way that the vehicle's capacity is never exceeded. This article points out a close connection between the 1-PDTSP and the classical "Capacitated Vehicle Routing Problem" (CVRP), and it presents new inequalities for the 1-PDTSP adapted from recent inequalities for the CVRP. These inequalities have been implemented in a branch-and-cut framework to solve to optimality the 1-PDTSP that outperforms a previous algorithm (Hernández-Pérez and Salazar-González, Discrete Appl Math 145 (2004), 126,139). Larger instances (with up to 100 customers) are now solved to optimality. The classical "Traveling Salesman Problem with Pickups and Deliveries" (TSPPD) is a particular case of the 1-PDTSP, and this observation gives an additional motivation for this article. The here-proposed algorithm for the 1-PDTSP was able to solve to optimality TSPPD instances with up to 260 customers. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 258,272 2007 [source]

    An exact algorithm for the Traveling Salesman Problem with Deliveries and Collections

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2003
    R. Baldacci
    Abstract In this paper, we describe a new integer programming formulation for the Traveling Salesman Problem with mixed Deliveries and Collections (TSPDC) based on a two-commodity network flow approach. We present new lower bounds that are derived from the linear relaxation of the new formulation by adding valid inequalities, in a cutting-plane fashion. The resulting lower bounds are embedded in a branch-and-cut algorithm for the optimal solution of the TSPDC. Computational results on different classes of test problems taken from the literature indicate the effectiveness of the proposed method. © 2003 Wiley Periodicals, Inc. [source]

    A hybrid swarm intelligence algorithm for the travelling salesman problem

    EXPERT SYSTEMS, Issue 3 2010
    I-Hong Kuo
    Abstract: We present a hybrid model named HRKPG that combines the random-key search method and an individual enhancement scheme to thoroughly exploit the global search ability of particle swarm optimization. With a genetic algorithm, we can expand the area of exploration of individuals in the solution space. With the individual enhancement scheme, we can enhance the particle swarm optimization and the genetic algorithm for the travelling salesman problem. The objective of the travelling salesman problem is to find the shortest route that starts from a city, visits every city once, and finally comes back to the start city. With the random-key search method, we can search the ability of the particle and chromosome. On the basis of the proposed hybrid scheme of HRKPG, we can improve solution quality quite a lot. Our experimental results show that the HRKPG model outperforms the particle swarm optimization and genetic algorithm in solution quality. [source]

    A travelling salesman problem with allocation, time window and precedence constraints , an application to ship scheduling

    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 3 2000
    K. Fagerholt
    Abstract A Travelling Salesman Problem with Allocation, Time Window and Precedence Constraints (TSP-ATWPC) is considered. The TSP-ATWPC occurs as a subproblem of optimally sequencing a given set of port visits in a real bulk ship scheduling problem, which is a combined multi-ship pickup and delivery problem with time windows and multi-allocation problem. Each ship in the fleet is equipped with a flexible cargo hold that can be partitioned into several smaller holds in a given number of ways, thus allowing multiple products to be carried simultaneously by the same ship. The allocation constraints of the TSP-ATWPC ensure that the partition of the ship's flexible cargo hold and the allocation of cargoes to the smaller holds are feasible throughout the visiting sequence. The TSP-ATWPC is solved as a shortest path problem on a graph whose nodes are the states representing the set of nodes in the path, the last visited node and the accumulated cargo allocation. The arcs of the graph represent transitions from one state to another. The algorithm is a forward dynamic programming algorithm. A number of domination and elimination tests are introduced to reduce the state space. The computational results show that the proposed algorithm for the TSP-ATWPC works, and optimal solutions are obtained to the real ship scheduling problem. [source]

    Approximation algorithms for combinatorial multicriteria optimization problems

    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 1 2000
    M. Ehrgott
    Abstract The computational complexity of combinatorial multiple objective programming problems is investigated. NP-completeness and #P -completeness results are presented. Using two definitions of approximability, general results are presented, which outline limits for approximation algorithms. The performance of the well-known tree and Christofides' heuristics for the traveling salesman problem is investigated in the multicriteria case with respect to the two definitions of approximability. [source]

    Dynamic optimization of N -joint robotic limb deployments

    JOURNAL OF FIELD ROBOTICS (FORMERLY JOURNAL OF ROBOTIC SYSTEMS), Issue 3 2010
    Wolfgang Fink
    We describe an approach using a stochastic optimization framework (SOF) for operating complex mobile systems with several degrees of freedom (DOFs), such as robotic limbs with N joints, in environments that can contain obstacles. As part of the SOF, we have employed an efficient simulated annealing algorithm normally used in computationally highly expensive optimization and search problems such as the traveling salesman problem and protein design. This algorithm is particularly suited to run onboard industrial robots, robots in telemedicine, remote spacecraft, planetary landers, and rovers, i.e., robotic platforms with limited computational capabilities. The robotic limb deployment optimization approach presented here offers an alternative to time-intensive robotic arm deployment path planning algorithms in general and in particular for robotic limb systems in which closed-form solutions do not exist. Application examples for a (N = 4)-DOF arm on a planetary exploration rover are presented. © 2009 Wiley Periodicals, Inc. [source]

    Path inequalities for the vehicle routing problem with time windows

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2007
    Brian Kallehauge
    Abstract In this paper we introduce a new formulation of the vehicle routing problem with time windows (VRPTW) involving only binary variables. The new formulation is based on the formulation of the asymmetric traveling salesman problem with time windows by Ascheuer et al. (Networks 36 (2000) 69,79) and has the advantage of avoiding additional variables and linking constraints. In the new formulation, time windows are modeled using path inequalities that eliminate time and capacity infeasible paths. We present a new class of strengthened path inequalities based on the polyhedral results obtained by Mak (Ph.D. Thesis, 2001) for a variant of the TSP. We study the VRPTW polytope and determine its dimension. We show that the lifted path inequalities are facet defining under certain assumptions. We also introduce precedence constraints in the context of the VRPTW. Computational experiments are performed with a branch and cut algorithm on the Solomon test problems with wide time windows. Based on results on 25-node problems, the outcome is promising compared to leading algorithms in the literature. In particular, we report a solution to a previously unsolved 50-node Solomon test problem R208. The conclusion is therefore that a polyhedral approach to the VRPTW is a viable alternative to the path formulation of Desrochers et al. (Oper Res 40 (1992), 342,354). © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 273,293 2007 [source]

    The one-commodity pickup and delivery travelling salesman problem on a path or a tree

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2006
    Fan Wang
    Abstract Optimization algorithms for both path and tree topology classes of the one-commodity pickup and delivery travelling salesman problem (1-PDTSP) are proposed in this article, which focus on minimizing the route distance to transport products among pickup and delivery customers by a single vehicle with a limited capacity of k. Each pickup customer provides one unit volume of the product while each delivery customer requires one unit volume of the product. For the path case, we propose an O(n2/ min (k,n)) algorithm for any arbitrary k, and two O(n) algorithms for k = 1 and k = ,. For the tree case, O(n2) and O(n) algorithms are proposed for k = 1 and k = ,, respectively. Moreover, when k is arbitrary, the problem becomes NP-hard in the strong sense. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 24,35 2006 [source]

    Solving the asymmetric traveling salesman problem with periodic constraints

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2004
    Giuseppe Paletta
    Abstract In this article we describe a heuristic algorithm to solve the asymmetrical traveling salesman problem with periodic constraints over a given m -day planning horizon. Each city i must be visited ri times within this time horizon, and these visit days are assigned to i by selecting one of the feasible combinations of ri visit days with the objective of minimizing the total distance traveled by the salesman. The proposed algorithm is a heuristic that starts by designing feasible tours, one for each day of the m -day planning horizon, and then employs an improvement procedure that modifies the assigned combination to each of the cities, to improve the objective function. Our heuristic has been tested on a set of test problems purposely generated by slightly modifying known test problems taken from the literature. Computational comparisons on special instances indicate encouraging results. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(1), 31,37 2004 [source]