Routing problems derived from silicon-interposer and etc. are often formulated as a set-pair routing problem where the combination of pin-pairs to be connected is flexible. In this routing problem, a length matching routing pattern is often required due to the requirement of the signal propagation delays be the same. We propose a fast length matching routing method for the set-pair routing problem. The existing algorithm generates a good length matching routing pattern in practical time. However, due to the limited searching range, there are length matching routing patterns that cannot find due to the limited searching range of the algorithm. Also, it needs heavy iterative steps to improve a solution, and the computation time is practical but not fast. In the set-pair routing, although pin-pairs to be connected is flexible, it is expected that combinations of pin-pairs which realize length matching are restricted. In our method, such a combination of pin-pairs is selected in advance, then routing is performed to realize the connection of the selected pin-pairs. Heavy iterative steps are not used for both the selection and the routing, then a routing pattern is generated in a short time. In the experiments, we confirm that the quality of routing patterns generated by our method is almost equivalent to the existing algorithm. Furthermore, our method finds length matching routing patterns that the existing algorithm cannot find. The computation time is about 360 times faster than the existing algorithm.

Vehicle routing is an important combinatorial optimization problem. In real transport networks,the travel speed and travel time of roads have large time-variability and randomness. The study of vehicle routing problem in time-dependent network has even more practical value than static network VRP problem. This paper combines the features of time-dependent networks and gives the mathematical models of the time-dependent vehicle routing problem. On this basis, the traditional ant colony optimization algorithm is improved. A new path transfer strategy of ants and new dynamic pheromone update strategy applicable to time-dependent network are proposed. Based on these strategies, the improved ant colony algorithm is given for solving the vehicle routing problem in time-dependent networks. The simulation results show that the algorithm can effectively solve the vehicle routing problem in time-dependent network and has better computational efficiency and convergence speed.

We consider the minimum cost edge installation problem (MCEI) in a graph G=(V,E) with edge weight w(e)≥ 0, e∈ E. We are given a vertex s∈ V designated as a sink, an edge capacity λ>0, and a source set S⊆ V with demand q(v)∈ [0,λ], v∈ S. For each edge e∈ E, we are allowed to install an integer number h(e) of copies of e. MCEI asks to send demand q(v) from each source v∈ S along a single path Pv to the sink s without splitting the demand of any source v∈ S. For each edge e∈ E, a set of such paths can pass through a single copy of e in G as long as the total demand along the paths does not exceed the edge capacity λ. The objective is to find a set P={Pv| v∈ S∈ of paths of G that minimizes the installing cost ∑e∈ E h(e)w(e). In this paper, we propose a (15/8+ρST)-approximation algorithm to MCEI, where ρST is any approximation ratio achievable for the Steiner tree problem.

We consider the capacitated multi-source multicast tree routing problem (CMMTR) in an undirected graph G=(V,E) with a vertex set V, an edge set E and an edge weight w(e) ≥ 0, e ∈ E. We are given a source set S ⊆ V with a weight g(e) ≥ 0, e ∈ S, a terminal set M ⊆ V-S with a demand function q : M → R+, and a real number κ > 0, where g(s) means the cost for opening a vertex s ∈ S as a source in a multicast tree. Then the CMMTR asks to find a subset S′⊆ S, a partition {Z1,Z2,...,Zl} of M, and a set of subtrees T1,T2,...,Tl of G such that, for each i, ∑t∈Ziq(t) ≤ κ and Ti spans Zi∪{s} for some s ∈ S′. The objective is to minimize the sum of the opening cost of S′and the constructing cost of {Ti}, i.e., ∑s∈S′g(s)+w(Ti), where w(Ti) denotes the sum of weights of all edges in Ti. In this paper, we propose a (2ρUFL+ρST)-approximation algorithm to the CMMTR, where ρUFL and ρST are any approximation ratios achievable for the uncapacitated facility location and the Steiner tree problems, respectively. When all terminals have unit demands, we give a ((3/2)ρUFL+(4/3)ρST)-approximation algorithm.

This paper compared the approaches concerning the pinball routing problem that occurs in the nested network in network mobility environment and developed the analytic framework to model. Each model was evaluated of transmission latency, memory usage, and BU's occurrence number at routing optimization process. The estimation result showed that the optimization mechanism achievement overhead existed in each model, and the full optimization of the specific model was not attained because of it. Therefore, the most appropriate approach for routing optimization in nested NEMO can be determined only after a careful evaluation, and the proposals must consider using it in combination with other approaches. The modeling framework presented in this paper is intended to quantity the relative merits and demerits of the various approaches.

A constraint resolution scheme in the Hopfield-type neural network named "Neuron Filter" is presented for efficiently solving combinatorial optimization problems. The neuron filter produces an output that satisfies the constraints of the problem as best as possible according to both neuron inputs and outputs. This paper defines the neuron filter and shows its introduction into existing neural networks for N-queens problems and FPGA board-level routing problems. The performance is evaluated through simulations where the results show that our neuron filter improves the searching capability of the neural network with the shorter computation time.

In this paper, we propose a new cooperative search algorithm based on pheromone communication for solving the Vehicle Routing Problems. In this algorithm, multi-agents can partition the problem cooperatively and search partial solutions independently using pheromone communication, which mimics the communication method of real ants. Through some computer experiments the cooperative search of multi-agents is confirmed.

Genetic algorithms have been shown to be very useful in a variety of search and optimization problems. In this paper, we propose a modified genetic channel router. We adopt the compatible crossover operator and newly designed compatible mutation operator in order to search solution space more effectively, where vertical constraints are integrated. By carefully selected fitness function forms and optimized genetic parameters, the current version speeds up benchmarks on average about 5.83 times faster than that of our previous version. Moreover the total convergence to optimal solutions for benchmarks can be always obtained.

Genetic algorithms have been shown to be very useful in a variety of search and optimization problems. In this paper, we describe the implementation of genetic algorithms for channel routing problems and identify the key points which are essential to making full use of the population of potential solutions, that is one of the characteristics of genetic algorithms. Three efficient crossover techniques which can be divided further into 13 kinds of crossover operators have been compared. We also extend our previous work with ability to deal with dogleg case by simply splitting multi-terminal nets into a series of 2-terminal subnets. It routes the Deutsch's difficult example with 21 tracks without any detours.

Evolution programs have been shown to be very useful in a variety of search and optimization problems, however, until now, there has been little attempt to apply evolution programs to channel routing problem. In this paper, we present an exolution program and identify the key points which are essential to successfully applying evolution programs to channel routing problem. We also indicate how integrating heuristic information related to the problem under consideration helps in convergence on final solutions and illustrate the validity of out approach by providing experimental results obtained for the benchmark tests. compared with the optimal solutions.

Suppose that there are terminals on two concentric circles Cin and Cout, with Cin inside of Cout. A set of two-terminal nets is given and the routing area is the annular region between the two circles. In this paper, we present an O(n2) time algorithm for testing whether the given net set is two-layer routable, where n is the number of nets. Applying this algorithm repeatedly, we can find, in O(n3) time, a maximal subset of nets which is two-layer routable.