メインページ
A I I E Transactions Fast Algorithms for the Round Trip Location Problem
Fast Algorithms for the Round Trip Location Problem
Drezner, Zviこの本はいかがでしたか？
ファイルの質はいかがですか？
質を評価するには、本をダウンロードしてください。
ダウンロードしたファイルの質はいかがでしたか？
巻:
14
言語:
english
ジャーナル:
A I I E Transactions
DOI:
10.1080/05695558208975236
Date:
December, 1982
ファイル:
PDF, 382 KB
あなたのタグ:
1～5分以内にこのファイルをあなたの電子メールにお届けします。
1～5分以内にこのファイルをあなたのKindleにお届けします。
注意！Kindleへ送信するすべての本は、メールによる確認が求められています。Amazon Kindle Supportからメールが送信されますので、メールをご確認ください。
注意！Kindleへ送信するすべての本は、メールによる確認が求められています。Amazon Kindle Supportからメールが送信されますので、メールをご確認ください。
関連ブックリスト
0 comments
書評を書いて、体験を共有しましょう。他の読者さんは、あなたがお読みになった本のご感想に興味があります。お読みになった本はお気に入ったかどうか別として、それについて詳細にかつ正直にご感想を述べていただけたら、他の皆さんも自分にとってぴったりの本が探しやすくなります。
2


This article was downloaded by: [130.132.123.28] On: 24 December 2014, At: 09:03 Publisher: Taylor & Francis Informa Ltd Registered in England and Wales Registered Number: 1072954 Registered office: Mortimer House, 3741 Mortimer Street, London W1T 3JH, UK A I I E Transactions Publication details, including instructions for authors and subscription information: http://www.tandfonline.com/loi/uiie19 Fast Algorithms for the Round Trip Location Problem Zvi Drezner a a School of Management, The University of MichiganDearborn , Dearborn, Michigan, 48128 Published online: 09 Jul 2007. To cite this article: Zvi Drezner (1982) Fast Algorithms for the Round Trip Location Problem, A I I E Transactions, 14:4, 243248, DOI: 10.1080/05695558208975236 To link to this article: http://dx.doi.org/10.1080/05695558208975236 PLEASE SCROLL DOWN FOR ARTICLE Taylor & Francis makes every effort to ensure the accuracy of all the information (the “Content”) contained in the publications on our platform. However, Taylor & Francis, our agents, and our licensors make no representations or warranties whatsoever as to the accuracy, completeness, or suitability for any purpose of the Content. Any opinions and views expressed in this publication are the opinions and views of the authors, and are not the views of or endorsed by Taylor & Francis. The accuracy of the Content should not be relied upon and should be independently verified with primary sources of information. Taylor and Francis shall not be liable for any losses, actions, claims, proceedings, demands, costs, expenses, damages, and other liabilities whatsoever or howsoever caused arising directly or indirectly in connection with, in relation to or arising out of the use of the Content. This article may be used for research, teaching, and private study purposes. Any substantial or systematic reproduction, redistribution, reselling, loan, sublicensing, systematic supply, or distribution in any form to anyone is expressly forbidden. Terms & Conditions of; access and use can be found at http:// www.tandfonline.com/page/termsandconditions Fast Algorithms for the Round Trip Location Problem 1 ZVI DREZNER Downloaded by [] at 09:03 24 December 2014 School of Management The University of MichiganDearborn Dearborn, Michigan 481 28 Abstract: This paper presents several fast algorithms for the round trip location problem. I show how to simplify the method given in an article by Chan and Hearn in which only the rectilinear case is addressed and get an algorithm with improved complexity for a given accuracy. An exact solution algorithm (the complexity of which is unknown) that solved test data problems even faster is presented and generalized for Euclidean and lip distances. Computational results are also presented. The round trip location problem for rectilinear distances has been introduced by Chan and Hearn [I]. The problem has been generalized to Qp distances by Drezner and Wesolowsky [5] . A solution method based on a solution of a set of ordinary differential equations is presented there. In this paper I present faster algorithms for these problems giving the practitioner the tools for solving much bigger problems. Geometric Properties of F(X) The first observation on the structure of F(X) is that wiri(X) 2 fi , where fi = wi(l ai  ci I + I bi  di I +gi), and that wiri(X)=fi in the rectangular region: The Rectilinear Problem Min{a, ci ) < x < Max {ai, ci ) , The rectilinear distance round trip location problem as defined in [I] is: For N given pairs of points Pi, Qi where Pi= (ai, bi)and Qi = (c,, d i ) for i = 1, . . . ,N, and given nonnegative constants gi, let X = (x, y ) and let Min {bi, di ) <y < Max (4) {b,, di ). It follows that &Y)>~axCfi)=F. 19iGN ri(X)= I x  a i l + l y  b i l + I x  c i l + I ' y  d i I+gi. (1) We have to minimize F(X) = Max {wiri(X)) for 1 < i <N , (2) (5) Let us find the region for whch wiri(X)<f, for a given value offo. Let ei be Cf,  fi)/wi. If ei < 0,this region is empty. For ei > 0 we get the octagon described in Fig. 1. The definition of such an octagon is: where wi for i = 1, . . . ,N are nonnegative weights. Min { a , ci ) ei <x Received May 1981; revised May 1982. Paper was handled by the Facilities Design/Location Analysis Department. December 1982, IIE TRANSACTIONS < Max {ai, ci ) + ei (6a) Min {bi, di ) ei <y <Max {bi, di ) + ei (6b) 0569554/82/12000243/$2.00/0 01982 IIE 243 Now we have the tools to present the first algorithm. First construct a routine that results in the feasible region for the equation F(X) < f o or find that the feasible region is empty. Simply, find the intersection of the N octagons defined by wiri(X)< f,; either this is the desired region or it is empty. This procedure is of complexity O(N). The First Algorithm First find by Equation (5) the value of F. Apply the above described routine to find if there is a feasible solution to F(X) <p. If the intersection is not empty, we solved the problem. If the intersection is empty, however, we suggest the following. Fig. 1 . The Octagon. Let E* be the optimal value of the objective function. We construct sequences FLS1,FL1 , . . . and H f l , e l , . . . such that for every k > 0: Flkl< F* < and FLk = (FLol F P ] ) / ~ ~This . is done by the ordinary bisection method. We choose F ~ O ] = F . [Equation (5)] and FLol = F(X) for some arbitrary X. Suppose we have found FF] and F[;] , and let us define FLk= (FLk + FfP1) 1 2. Find by the above routine if there is a feasible solutionto F(X) < F l k 1 . If the intersection is empty then set F ~ ~ " ' = F[' and F & ~ " = ] F t k l If the octagon exists, then U ' set FLk+" = FLkl a n d F h k + l l = H k 1 . The stopping criterion can be defined either by a tolerance on F(X)  F * or by a tolerance on the distance between the solution point and the optimal point. This is because, for any F & ~ ] , the optimal solution point must be included in the Anal .octagon. For a given degree of accuracy this is an algorithm of complexity O(N), because the number of iterations is independent of N. Downloaded by [] at 09:03 24 December 2014 FF] Min {ai, c i )  Max {b,, di) ei < x  y < Max {ai, c i ) (6d)  Min {bi, di ) + ei Note that when ei = 0, Equations (6c) and (6d) are redundant, and the octagon reduces to the rectangle given by Equation (4). It is geometrically evident that the intersection of the areas of two octagons is either empty or an octagon. The proof for this theorem is obvious and thus omitted. Theorem 1. Consider two octagons given by FPI The Second Algorithm Their intersection is an octagon defined by Max {v,, u,) <Xy <Min{v,, u s ) . Note that the solution to set (7) may be empty. In order to determine if this is true, apply the onepass procedure method presented in [ l , pp. 1161171. The octagon is equivalent to R 2 n R 3 there. This algorithm is similar to the algorithm suggested in [4] for the solution of the single facility minimax location problem. First, note that a maximum of three pairs of points defines the optimal solution. This is shown lmphcitly in 111 and is also a special case of a more general theorem proven in [2]. In [ I ] it is shown that the solution is determined as a maximum of five values H , , . . . , H 5 defined there. These values are determined by one, two, or three pairs of points. Therefore, the solution point based on these pairs only must be the same. The following theorem is proven in [2] . Given N convex functions in a kdimensional space, we need to find a point that minimizes the maximal values among these functions. There exists a subgroup of functions with cardinality less than or equal to k + 1 such that the problem based on this reduced set (the reduced problem) has the same optimal value as the original problem. Furthermore, at least one of the solution points to the reduced problem is also a solution point to the original problem. IIE TRANSACTIONS, Volume 14, No. 4 The approach is quite simple. Find an initial point xCo1 . decrease. This is the desired solution. Let X* be an optimal We suggest the starting point given in (5): solution. This solution must be categorized into one of the following three cases: Downloaded by [] at 09:03 24 December 2014 Case I: X* is the intersection point of the three ellipses. is the greatest. Find the three pairs for which Let us call this set of pairs the "core" group. Find a solution for these three pairs by the method in [ I ] . Let this solution be x[' . Suppose xrk with value of objective function F[' has been found for k 2 1. Find Max {wjrj(xrkI)) for 1 <j < N . Let this maximal value be f l k 1 achieved for pair m. 1 f f k 1 = p k l , then Xlkl is optimal. Otherwise add pair m to the core group. Solve the problem of the new core group by the method in[l] .Let the solution point bexrk+l1 with a value of the objective function of P k + ' ] . Since the optimal point is not necessarily unique, we must take further precautions on top of the approach in [4]. If F [ ~ + ' ]> p k l , choose the new core group as tnose points, out of the core, for which wiri(xCk+' ) = flk+'. But if F [ ~ + '=] F [ ~ ] ,retain all points in the core. Note that the number of members in the core group increases if flk+' = P k 1 , but it does down to three members or less otherwise. Repeat the process until fCk = Pk for some k. This algorithm is finite. It can be easily verified that no core group is calculated twice and there is a finite number of possible core groups. The Euclidean Problem Case 11: Two ellipses are tangent to each other at X*, and X* is inside the third ellipse. Case 111: X* is on the line connecting the two foci of one ellipse (when the ellipse shrinks to the segment connecting the foci), and X* is inside the other two ellipses. Necessary but not sufficient conditions for these three cases can be characterized by the number of ellipses for which Fi(X*) = F(X*). We find three ellipses in Case I, two ellipses in Case 11, and only one ellipse in Case 111. For sufficiency we must make sure that the following hold. In the first case the intersection of the three ellipses must consist of only one point. Let "center" be the intersection point between the normal at a point on the ellipse and the segment between the two foci (see Fig. 2). A circle through that point on the ellipse, centered at the center, is tangent to the ellipse. Therefore the areas of the three ellipses have only one common point if and only if the areas of the three above described circles have only one common point. Let us redefine the distance as Euclidean distance, replacing Equation (1) by r(x)=[(~ai)2+O)bi) 2 ]1/2 + [ ( x  ~ ~ ) ' + O )  d ~ ) ' ] ' ~ + g ~ . (9) The octagon (6) is now an ellipse with foci at the two points Piand Qi. A more general theorem [Z] shows that at most three pairs of points define the optimal solution. We can therefore construct an algorithm similar to the second algorithm in the previous section. Let us first present a solution procedure for a problem with three pairs of points. The ThreePairs Problem Let us define Fi(X) := wiri(X) and F(X) = Max \(Fi(X) for 1 < i 9 3. The method in [5] can be applied for three pairs of points. However, we believe that the following is simpler and faster. In order to present the method we need the following "descriptive" process. The feasible region for Fi(X) 9 F, for some Fo is either empty or an ellipse. When F, decreases, the ellipse shrinks. Let us start with a "big3'F0 and examine the intersection of the three ellipses. If F, is big enough, then the intersection is not empty. If Fo decreases, the intersection of the three ellipses shrinks until the intersection vanishes by a further December 1982, IIE TRANSACTIONS p Fig. 2. The Ellipse. In the second case the ellipses must be tangent to each other at the solution point. Two ellipses must be tangent to each other if they have a common tangent line at the intersection point. Therefore the condition is that the solution point must be on the line connecting the two centers. In the third case we must check if the solution point is on the line connecting the foci of the ellipse for which Fi(X*) is maximal. 24.5 The above discussion leads to the following procedure. Choose any starting point xCo1 ;for instance, Equation (8). Say that xLk1 has already been found. Find the centers for the ellipses of the three pairs. Let d l k 1 for i = 1 , 2, 3 be the distances between xCk1 and the centers. See Fig. 2, in which one ellipse is depicted and the index i is omitted. Let Step 5: If k > k, stop. Declare nonconvergence. Step 6: 1f ( Z  X ' ~ + ] )G ~  Y [ * ]>)c ~ 2 , go to Step 2. Step 7: Stop with xCk+'as the solution. We shall prove that if the iterative procedure converges to a point X*, then X* is optimal for the round trip location problem with three pairs. The following properties are easy to prove. where Property 1 : w I k ] d f k ]< 1. Property 2 : Downloaded by [] at 09:03 24 December 2014 ~ f F ~ ( ~ [ ~ ] ) = ~ ( ~ ~ ~ ~ ) , t=h1. enwi[~~di[ Solve the single facility minimax Euclidean distance problem with weights wCk and demand points at the centers. An explicit formula for the solution of this problem is given in [4].Let the solution point b e x set ~ [ ~ + ' ] = f l +h)xCk1 (l for a given h < 1. Repeat the process until either the distance between XI'] and X is less than a prespecified tolerance, or the number of iterations exceeds a prespecified limit. In the latter case apply the guaranteed solution method of [ 5 ] . We have found that a good strategy for utilizing h is to start with h = 1. If convergence has not been accomplished in 50 iterations, change h to 9 for 50 more iterations then use A = 0' for 50 more iterations and so on. In our computations we used 19 = 0.75. The algorithmic formulation is given in the next section. Property 3 : (dil + di2  ~ ~ ) / d <i [2~. ] Property 4: (dil +di2  ~ ~ ) / d =i [(dil ~ +di2) X { ( d i ~+diz sill [ d i di2(di1 ~ + di2 + si)] )' . Property 5: I f s i = 0 , then w f k l = ~ W , / [ F ( X [~wIi g) i ] . Algorithm for the ThreePairs Problem Step 1 : Choose XI'] by Equation (8). Set k = 0, A = 1 . Step 2: Calculate d i l , diz for i = 1 , 2 , 3 , by Equation (10). Find the three centers. It can be shown that they are given by xic = (dilci + dizai)/(dil + d i 2 ) y i c = ( d i l d i+di2bi)/(dil+ d i 2 ) . Theorem 2. If the limit to xLkl exists for a fixed h as k goes to infinity, then the limit is the optimal solution to the threepairs problem. Then di[kl = In [ 3 ] a similar iterative procedure is presented for the single facility minimax problem with a setup of gi. By Property 5 , our iterative procedure turns to the iterative procedure in [3] when the pair of points is located at the same site. The procedure of [ 3 ] is proven to converge to the optimal location. We could not prove convergence here (we know of cases of nonconvergence for h = l ) , but we prove that if the algorithm converges, it is to the optimal solution.  X f ) 2+ ( y [ k l  Y f ) 2)'I2 for i = 1,2,3. Proof. Let the limit to xCkbe X.If wirk goes to infinity for some i, then by Property 3  wi(si + gi) = 0 . Therefore, X is optimal (Case 111). If the wfkl are bounded, then since wFk are continuous as a function of X [ I, the limits We have for wFk and,dik] exist. Let them be and ~(3 Calculate wlk for i = 1,2,3 by Equation (10). Step 3 : Solve the single facility minimax problem with demand points at (xf, y f ) and weights w l k l for i = 1, 2 , 3. ~+ Step 4: Let the optimal solution be y. Set xLk+ll = ( 1  A ) J ? ~ and k = k + 1. If 50 divides k, then set h=hO. wi z. By Properties 1 and 2, Maxi {wizi ) =l . By the theorems proved in [5] about the solution point for the single facility minimax location problem, there are two possibiliVolume 14, No. 4 IIE TRANSACTIONS, ties for the optimal solution. The first possibility is that all are equal to one, and the three weighted distances three discs centered at the centers have only one common point. By Equation (1 1) we get F(R = wi(di, + di2 + gi) for i = 1, 2, 3. Therefore is optimal for the threepairs problem (Case I). The second possibility is that the wiZi are equal to one for two points and are less than one for the third. Also, 2 is on the line connecting two centers. By Equation (1 I), wi( dil + di2 +gi) = F ( B for two pairs and wi(di, + di2 + gi) < F ( B for the third pair. Also, since X is on the line connecting the two centers, the ellipses are tangent at X.Therefore Xis optimal (Case 11). wizi x Downloaded by [] at 09:03 24 December 2014 The Euclidean Algorithm This algorithm is simliar to the second algorithm for the rectilinear case. The algorithm is simpler if the objective function must increase every iteration. The objective function must increase if there is a unique solution point to each threepairs problem. The threepairs algorithm indicates that only Case I11 may yield a nonunique solution. Steps 1 and 2 in the following algorithm assure that Case I11 cannot occur, since F [ ~will ] always be greater than any possible Case I11 solution. Step 7: ~fFrn(xCkI ) = FCkl,stop; xCkl is optimal. Step 8: Otherwise add pair m as the new member of the core; set k = k + 1 and go to Step 4. The Q,Distance Problem The second algorithm for the rectilinear case is also applicable to general Qp distances. By the general theorem in [2] , the optimal solution is also determined by at most three pairs. Therefore, to complete the second algorithm for this case we only need a solution procedure for a threepairs problem. This can be easily done by the method in [5], and thus we have a faster algorithm for this case too. The geometry involved in the general Qp distance does not seem to be neat like the octagon for rectilinear distance or the ellipse for the Euclidean case. Also, the II,distance single facility minimax problem is solved in an iterative procedure [4). Therefore it seems that an iterative procedure (for which each step is an iterative procedure) similar to the Euclidean algorithm for the solution of the threepairs problem is inefficient, and we use rather the method in [5] as suggested above. Computational Results Algorithm for the Euclidean Distance Problem Step 1: Find F, = ~ax{wi([(a, ci)' + (bi  di)' ] I n +gi)} for 1 < i <N, and let j be the index for which tne maximum is obtained.. Step 2: Find FCol ,the minimum value of F(X) on the segment connecting Pj and Q j , by Fibonacci search. Let X, be the minimal point of the segment. If F I O 1 = F,, then X, is optimal. We present a comparison between the two algorithms for the rectilinear round trip problem, some experiments performed on the threepairs Euclidean problem, and results for the Euclidean distance problem. All run times are in seconds by a FORTRAN IVH code on the Amdahl470/V8 computer at the University of Michigan. A tolerance of E = lo5 was used where applicable. All parameters ai, bi, ci, di, wi, and gi for the test problems were randomly generated by a uniform distribution on (0, 1). The Rectilinear Problem Step 3: Find the two pairs for which Fi(Xm) is the greatest. Define these two pairs plus pair j as the core. S e t k = 1. Step 4: Solve the core problem. If there are four pairs in the core solve three threepairs problems for all sets of three pairs out of four that include the new member in the core. The solution is the greatest value of the objective function among all these problems. Let the solution point be xLkwith the . value of objective function FCkl The performance of the two procedures is compared in Tables 1 and 2. Ten problems were generated for each N. Procedure 2 seems to be empirically faster. An average run time of 0.1 sec for the solution of a 5,000pairs problem speaks for itself. Chan and Hearn [I] reported for N = 50, run times of 0.1 sec and 11.2 sec for the O ( P ) and O(N3) cases, respectively. Since our problem is 100 times bigger, solving by [I] would require about 0.1 X 10,000 sec or 15 min in the faster case, and about 11.2 X 1,000,000 sec or 129 days in the worse case. Step 5: Define as old members of the core those pairs of the threepairs problem that yielded the solution ) < FLkfor it. in Step 4. Omit a pair if Fi(xCk The ThreePairs Euclidean Problem Step 6 : Go over all N pairs and frnd the maximal Fi(xLk I). Let it bepairm. We have randomly generated 1,000 problems of three pairs each. We applied the formula of Property 4 in order to avoid a possible calculation error when the ratio of December 1982, IIE TRANSACTIONS Table 1: Rectilinear problems (first procedure). No. of Pairs Iterations Table 3: Euclidean problems. Time (sec) Max vMa x Min Min 100 1 18 13.7 0.002 0.019 0.014 500 1 18 12.3 0.007 0.083 0.057 1000 1 17 10.2 0.013 0.154 0.095 2000 1 18 10.5 0.025 0.319 0.191 5000 1 17 10.1 0.061 0.755 No. of Av 0.455  Property 4 is close to a 010. Total run time for all 1,000 problems was 1.91 1 sec. The algorithm converged in all cases. The average number of iterations was 9.3, the median number of iterations was 3, and between 1 and 297 iterations were required for each problem. Downloaded by [] at 09:03 24 December 2014 100 Min Iterations Max Av Min Time (sec) Max 3.0 0.003 0.009 0.006 500 1 5 3.3 0.007 0.018 0.013 1000 2 7 4.3 0.018 0.042 0.028 2000 1 5 3.4 0.024 0.060 0.045 5000 1 8 3.3 0.055 0.196 0.101 Av 0 4 1.9 0.063 0.112 0.084 0 3 1.6 0.1 10 0.166 0.141 500 1 4 1.8 0.288 0.384 0.343 1000 0. 4 1.8 0.508 0.848 0.694 2000 1 3 1.7 1.027 1.575 1.244 5000 0 3 1.9 2.858 3.403 3.083 References [2] 5 Time (sec) Max 100 Av 1 Min 200 [I] Table 2: Rectilinear problems (second procedure). No. of Pairs Iterations Max Av Pairs [3] [4] [5] Chan, A. W. and Hearn, D. W., "A Rectilinear Distance RoundTrip Location Problem," Transportation Science 11, 107123 (1977). Drezner, Z., "On Minimax Optimization Problems," Mathematical Programming 22,227230 (1982). Drezner, Z., "Location of Several New Facilities Minimizing the Maximal Sum of Distances," unpublished manuscript. Drezner, Z. and Wesolowsky, G. O., "Single Facility QpDistance Minimax Location," SIAM Journal of Algebraic andDiscrete Methods 1,315321 (1980). Drezner, Z. and Wesolowsky, G. O., "A Trajectory Method for the Round Trip Location Problem," Transportation Science 16,5666 (1982). The Euclidean Problem In Table 3 we present results for the Euclidean round trip location problem. Ten different problems were randomly generated for each N. Note that most of the run time is spent in Step 2 of the algorithm. Zero number of iterations indicate that F['' was equal to F,,, in Step 2. Run times for the Euclidean case are much faster than those reported in [5]. Assuming linear run time for the method in [5], about 6 rnin on the CDC 6400 are required for the solution of a 5,000pairs problem. . 248 Zvi Drezner is an Associate Professor of Business Administration at the School of Management, University of Michigan, Dearborn. He received both his BSc and DSc degrees from the Technion, Israel Institute of Technology, Haifa, Israel. His interests are in location theory, mathematical programming, and systems analysis. He has recently published in ZIE TRANSACTIONS, OPERATIONS RESEARCH, MANAGEMENT SCIENCE, N A VAL RESEARCH LOGISTICS QUARTERLY, and other journals. Volume 14, No. 4 IIE TRANSACTIONS,