Developing the Branch and Bound Method in the Problem of Searching for the Optimal Cyclic Route (Cyclic Rural Postman Pr
- PDF / 177,121 Bytes
- 10 Pages / 594 x 792 pts Page_size
- 95 Downloads / 178 Views
DEVELOPING THE BRANCH AND BOUND METHOD IN THE PROBLEM OF SEARCHING FOR THE OPTIMAL CYCLIC ROUTE (CYCLIC RURAL POSTMAN PROBLEM) A. O. Ovezgeldyyeva† and A. V. Morozova‡
UDC 519.161
Abstract. A mathematical model is constructed for the applied problem of the optimization of closed routes, i.e., the rural postman problem. A two-stage method of the branch-and-bound type is proposed, which finds the solution or establishes the unsolvability of the problem. The first stage of the method includes testing the sufficient unsolvability conditions and the vertex-edge transformation procedure. This reduces the solution time at the second stage by the proposed modification of the Little algorithm. This procedure uses (for the first time) the partition of the solution set into disjoint subsets with the help of three branching rules and computation of the corresponding lower-bound estimates of the optimal solution. The proposed method correctly searches for the optimal solution of the Hamiltonian rural postman problem and of the general and Hamiltonian traveling salesman problems. Keywords: branch and bound method, traveling salesman problem, postman problem. PROBLEM STATEMENT Numerous results accumulated in the analysis of the traveling salesman problem continuously develop and raise pressing questions of the development and perfection of combinatorial optimization methods and their application in practical and scientific activity. Solution algorithms applicable in real situations are developed by no means for any optimization problem on a transportation network. One of such problems is the rural postman problem (RPP); in the paper, we will consider its restricted version. Let there be given a connected weighted graph H = (V , U ) with the set of vertices V, |V | = n, and set of edges U. Each edge {i, j} ÎU is associated with a weight d ij Î Z 0+ , i ¹ j, i, j = 1, n; Z 0+ is the set of nonnegative integer numbers. The graph H is completely defined by the symmetric cost matrix [ d ij ] n , where d ij Î Z 0+ if {i, j} ÎU and d ij = ¥; otherwise, i ¹ j, i, j = 1, n, d ii = ¥, i = 1, n. A nonempty subset of edges R Ì U is specified on the set U. It is required to find a simple cycle in the graph H, which includes each edge from the set R and has the minimum sum of edge weights. In contrast to the RPP, the required cycle should be simple in the problem under study. We will call the problem the cyclic rural postman problem (CRPP). MAIN IDEA OF THE SOLUTION METHOD The CRPP is NP-complete, and only its restricted special cases are effectively solvable. From the NP-completeness of the CRPP it follows that it cannot be solved by efficient exact solution techniqies. Since the set of simple cycles of the graph, which include all the edges R, can appear empty, efficient approximate algorithms are inapplicable. Therefore, the only a
Zhytomir State Technological University, Zhytomir, Ukraine, †[email protected]; ‡[email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 5, September–October, 2013, pp. 112–123. Original
Data Loading...
