Some biological experiments show that the tubular structures of Physarum polycephalum are often analogous to those of Steiner trees. Therefore, the emerging Physarum-inspired Algorithms (PAs) have the potential of computing Steiner trees. In this paper, we propose two PAs to solve the Steiner Tree Problem in Graphs (STPG). We apply some widely-used artificial and real-world VLSI design instances to evaluate the performance of our PAs. The experimental results show that: 1) for instances with hundreds of vertices, our first PA can find feasible solutions with an average error of 0.19 , while the Genetic Algorithm (GA), the Discrete Particle Swarm Optimization (DPSO) algorithm and a widely-used Steiner tree approximation algorithm: the Shortest Path Heuristic (SPH) algorithm can only find feasible solutions with an average error above 4.96 ; and 2) for larger instances with up to tens of thousands of vertices, where our first PA, GA and DPSO are too slow to be used, our second PA can find feasible solutions with an average error of 3.69 , while SPH can only find feasible solutions with an average error of 6.42 . These experimental results indicate that PAs can compute Steiner trees, and it may be preferable to apply our PAs to solve STPG in some cases.
Besides the attempts to solve STPG, some PAs have already solved the shortest path problem @cite_26 . A well-known one of such PAs is the Physarum Solver @cite_6 , which is the basis of many PAs @cite_28 @cite_0 @cite_38 . We introduce it in this section.
@cite_38 @cite_26 @cite_28 @cite_6 @cite_0
2057742448 2142607374 1977133702 2059816321
This paper considers Stochastic Shortest Path (SSP) problems in probabilistic networks. A variety of approaches have already been proposed in the literature. However, unlike in the deterministic case, they are related to distinct models, interpretations and applications. We have chosen to look at the case where detours from the original path must be taken whenever the “first-choice” arc fails. The main results obtained include the proof of some counterintuitive facts (e.g., the SSP may contain a cycle), the proof of the validity of applying stochastic programming to this problem and the proof that the computational complexity of a particular SSP problem is polynomial. We consider the special case of the traveling salesman problem (TSP) in which the distance metric is the shortest-path metric of a planar unweighted graph. We present a polynomial-time approximation scheme (PTAS) for this problem. In this paper we review the exact algorithms proposed in the last three decades for the solution of the vehicle routing problem with time windows (VRPTW). The exact algorithms for the VRPTW are in many aspects inherited from work on the traveling salesman problem (TSP). In recognition of this fact this paper is structured relative to four seminal papers concerning the formulation and exact solution of the TSP, i.e. the arc formulation, the arc-node formulation, the spanning tree formulation, and the path formulation. We give a detailed analysis of the formulations of the VRPTW and a review of the literature related to the different formulations. There are two main lines of development in relation to the exact algorithms for the VRPTW. One is concerned with the general decomposition approach and the solution to certain dual problems associated with the VRPTW. Another more recent direction is concerned with the analysis of the polyhedral structure of the VRPTW. We conclude by examining possible future lines of research in the area of the VRPTW. The elementary shortest-path problem with resource constraints (ESPPRC) is a widely used modeling tool in formulating vehicle-routing and crew-scheduling applications. The ESPPRC often occurs as a subproblem of an enclosing problem, where it is used to generate implicitly the set of all feasible routes or schedules, as in the column-generation formulation of the vehicle-routing problem with time windows (VRPTW). As the ESPPRC problem is NP-hard in the strong sense, classical solution approaches are based on the corresponding nonelementary shortest-path problem with resource constraints (SPPRC), which can be solved using a pseudo-polynomial labeling algorithm. While solving the enclosing problem by branch and price, this subproblem relaxation leads to weak lower bounds and sometimes impractically large branch-and-bound trees. A compromise between solving ESPPRC and SPPRC is to forbid cycles of small length. In the SPPRC with k-cycle elimination (SPPRC-k-cyc), paths with cycles are allowed only if cycles have length at least k + 1. The case k = 2 forbids sequences of the form i - j - i and has been successfully used to reduce integrality gaps. We propose a new definition of the dominance rule among labels for dealing with arbitrary values of k ≥ 2. The numerical experiments on the linear relaxation of some hard VRPTW instances from Solomon's benchmark show that k-cycle elimination with k ≥ 3 can substantially improve the lower bounds of vehicle-routing problems with side constraints. The new algorithm has proven to be a key ingredient for getting exact integer solutions for well-known hard problems from the literature.