This paper analyzes a linear feature covering problem (LFCP) with distance constraints, and characterizes the problem by a fuzzy multi-objective (MO) optimization model. An integrated approach combining an Ant algorithm (LFCP-Ant) and a Geographic Information System (GIS) has been devised to solve the LFCP problem in large scale. The efficacy of the proposed approach is demonstrated using a case study of locating new fire stations in Singapore. A GIS has been used to transform the continuous problem into a discrete one, which is then solved using the LFCP-Ant. This algorithm employs a two-phase local search to improve both search efficiency and precision.
A typical linear feature covering problem (Fig. 1) with distance constraints consists of m polylines (m is 5 in Fig. 1) and n points (shown as dots in Fig. 1 and termed as potential location. n is 8 in Fig. 1) located at a Cartesian plane. In such problems, polylines are considered as lines composed of one or more linear line segments. Given a critical distance R, a desired balance distance D, and an integer number p (p is 4 in Fig. 1), the locations of p (out of n) points (for p new facilities) are to be selected so that the total length of those polylines lying within distance R of at least one point is maximized. Also, the distance between each new point and its nearest point must also maximally approach the desired balance distance D. The aforementioned problem is a bi-objective optimization problem, i.e. a MO (Multi-Objective) optimization problem with two objectives. The problem simultaneously considers linear feature coverage maximization (termed as objective A) and distance balancing (termed as objective B). To facilitate the understanding of objective A, we may take the points as supply side while regard polylines as demand side. Without losing generality, we may suppose that the demands are uniformly generated from the polylines, hence maximizing the coverage of polylines is equivalent to satisfying the demands maximally. Besides objectives A and B, other objectives might also be considered, e.g. minimizing the maximum distance from a point to a linear feature. Nevertheless, such objectives are supplementary, and this paper addresses primarily the optimization problem with the aforementioned two objectives.Problems of this kind occur in a variety of practical applications, especially in locating emergency and protection facilities. Locating new fire stations under plan is an archetypal representation of such a problem. Fire stations offer the personnel and equipment for protecting lives and belongings, and their location considerably influences their emergency response and fire protection abilities. While situating fire stations, the following two factors must be considered: (1) The stations should be capable of providing ‘timely aid’ when a road-accident or a mishap involving hazardous materials occurs; (2) There should be a reasonable distance between two fire stations [14], in order that any two fire stations may cooperate more easily and efficiently. Simply stated, all fire stations should be distributed “evenly” over the land, so as to be able to provide necessary protection to the largest possible area.
Location problems with distance constraints have been studied by researchers during the past several decades. Cooper and Drebes [4] presented a set covering approach involving a heuristic procedure to determine the minimum number of centers to cover all customers. However, this objective is significantly different from those dealt in our MO problem and hence the approach adopted in [4] is not relevant for the case discussed herein. Watson-Gandy [15] provided three heuristics and their variations to solve the m-partial cover problem (maximal covering problem) on a Cartesian plane. Their objective was to situate m centers so as to maximize the sum of the weights of those points lying within a critical distance (R) of at least one center. Even though this appears to be in line with objective A considered in this paper, Watson-Gandy [15] has not considered objective B (distance balancing) in their work. In some discrete location problems, distance constraints also do exist, e. g. the set covering problem and the maximal covering problem [5]. Such discrete problems are usually formulated as an Integer Linear Programming Problem (ILPP) and solved either by branch-and-bound approaches or Lagrangian relaxation heuristics. However, the demands in all these problems originate from nodes and hence the demand nodes can be easily recognized using a coordinate pair (x, y). It can be overtly judged if a demand node is covered by a supply facility (node). This is done by comparing the critical covering distance R with the Euclidean (network or user defined) distance between the two nodes. Nevertheless, in our case, we are dealing with polylines rather than points. The fire stations that are to be situated should serve accident locations uniformly distributed along particular routes and are not situated at points whose locations are known well in advance. This can hardly be expressed in a general mathematical equation and presents tremendous challenge in determining the percentage of polylines that have been covered. Simply put, it is hard to find a way to evaluate the objectives when the demand is originated from polylines. As will be discussed below, we solve this problem by discretizing the polylines into a series of connected cells. Although this makes it possible to model the whole problem in ILPP, the combinatorial complexity prohibits us to do so. This will be detailed later.
Badri et al. [1] stressed the need for a MO model in determining fire station locations. They employed a multiple criteria modeling approach via integer goal programming to evaluate potential sites in 31 sub-areas in the state of Dubai. Their model determines the location of fire stations and the areas the fire stations are supposed to serve. They considered 11 strategic objectives including travel times, travel distances and also other cost-related objectives. They also took into account several other technical and political criteria, or other factors satisfying certain system requirements. However, the integer goal programming used in [1] is not applicable for our problem since: (a) the objectives considered are different, and (b) if not discretized, the problem itself cannot be modeled into an integer goal programming problem; if discretized, it still would be a very large computational problem which cannot be solved using integer goal programming. Tzeng and Chen [14] used a fuzzy MO approach to determine the optimal number and sites of fire stations in Taipei's international airport. Their paper utilized a genetic algorithm (henceforth called TC-GA) and compared with the brute force enumeration method. From literature review, we find that TC-GA [14] is the most pertinent approach, in view of the nature of our problem. Even though the results showed that the GA is appropriate for solving similar location problems, its efficiency in large scale problems is yet to be verified.
This paper explores a fuzzy MO model to characterize a large scale Linear Feature Covering Problem (LFCP). The continuous problem is transformed into a discrete one using a Geographic Information System (GIS). In the discretized problem, the polylines are represented by a string of discrete coordinate pairs, thus facilitating easy determination of their coverage. As such, a continuous optimization location problem is converted to a discrete combinatorial optimization problem. This discrete optimization problem is then solved using the LFCP-Ant, a novel Ant algorithm, which, to the best of our knowledge, has not been attempted before. This algorithm takes advantage of a two-phase local search to enhance search efficiency as well as accuracy.
The remainder of this paper is organized as follows. At the outset, the fuzzy MO formulation of the problem is presented. Then, a brief prologue to GIS and its application in converting a continuous plane and road lines into grid cells is given. This is followed by a detailed discussion of the proposed Ant algorithm, LFCP-Ant. A case study of determining the locations of new fire stations in Singapore using our proposed approach is then presented. A computational study between the LFCP-Ant and TC-GA in [14] is also carried out to benchmark the efficiency of LFCP-Ant. Finally, the paper concludes with a summary and outlook.
This paper has presented a general fuzzy MO optimization model to describe the linear feature covering problem with distance constraints, and the solution through the use of a GIS-supported Ant algorithm. The Ant algorithm, i.e. LFCP-Ant, consists of a two-phase local search mechanism, which makes it a universal meta-heuristic suitable for solving large-scale location problems upon a grid system. Computational comparison in the case study shows that LFCP-Ant is much more efficient and robust than the GA, TC-GA.
In this paper, the distance is measured in the Euclidean form. In order to achieve more accurate results, the network distance could be employed within the transportation network. However, using network distance will increase the complexity of the problem. When evaluating objectives, one needs to calculate the network distance through the original vector map. To calculate the network distance in terms of travelling time is a non-trivial task since it involves randomness, i.e. the traffic condition on the road changes anytime. Nevertheless, this idea could lead to a challenging, yet interesting research topic.
The two objectives considered are equally weighted. In the event of the local authorities changing their views and deciding to place different emphasis on any of these two objectives, the fuzzy MO model can easily be modified by assigning appropriate weights to the objectives. Furthermore, if other objectives need to be considered, the fuzzy MO modelling approach can incorporate them in an efficient and trouble-free way without destroying the original model structure. Even though this study uses only the basic functions of GIS, it has been demonstrated that integrating GIS and heuristics in location is indeed an efficient technique. The data attained from the GIS environment are fed into the heuristic algorithm, and the heuristics provides the optimal solution, which can be evaluated on a GIS platform. This continuous process serves as a prototype for the development of a decision support system incorporating both GIS and heuristic algorithms, which helps in decision making for emergency facility locations and other real-life spatial location problems.
