IE Network Conference 2012
17-19 October 2012 Cha-am Phetchaburi
Solving Maximal Covering Location Problem by Using Dynamic Programming
Sunarin Chanta1*, Ornurai Sangsawang2
1,2Department of Industrial Management, Faculty of Industrial Technology and Management,
King Mongkut’s University of Technology North Bangkok
E-mail: 1*, 2
Abstract
The maximal covering location problem (MCLP) is the problem in which facilities are located at existing stations on the network so as to maximizing the number of demand that can be covered or can be responded within a standard time under limited number of facilities. As we have known that location/relocation problems are typically NP-complete problems. The solving time increases dramatically as the size of the solution space increases. Because of the complex combinatorial nature of the problem, there have been various attempts to find optimal solution via exact method or identify near-optimal solution through the use of meta-heuristics search. A meta-heuristics method tends to find a solution in short time, but the solution found may not guarantee optimal. In contrast, the exact method provides the optimal solution, but most of them require the longer solving time.In this paper, we proposed an optimization algorithm for solving MCLP. Dynamic programming is one of the exact methods that guarantee to provide optimal solution. By formulating the problem in recursive form helps we solve the problem efficiently. We compared the efficiency of our optimization algorithm using dynamic programming to optimization software using branch-and-bound method. The performances of these two methods are investigated by solving both small size and large size problems.
Keywords:maximal covering location problem, facility location, dynamic programming
IE Network Conference 2012
17-19 October 2012 Cha-am Phetchaburi
1. Introduction
The covering problem is the problem in which facilities are located at existing stations on the network so as to cover all the demand zones while minimizing the number of facilities. The basic coverage model was developed by Toregas et al., 1971, [1] with the objective of minimizing the number of vehicles needed to cover all demand nodes. Church and ReVelle, 1974, [2] extended the basic coverage model to deal with the situation in which the number of vehicles available is less than the number needed to cover all demand zones, called a maximal covering location problem (MCLP). MCLP has been widely applied in solving facility location problems such as locating ambulance dispatching stations, fire stations, police stations, gas stations, department stores, schools, hospitals, and relief centers, etc., where a decision maker determines a fixed number of facilities or a limited budget to cover the demands as much as possible. To see more details about the models, solutions, and applications of covering problems, see Schilling et al., 1993 [3] and Farahani et al., 2012 [4].
As we have known that location/relocation problems are typically NP-complete problems [5]. The size of the solution space of locating m response units in n zones is nm. The challenge here is how to solve the problem efficiently, especially when we dealing with large scale problems. Many researchers have been proposed various ways to find an optimal solution via exact methods such as branch-and-bound, dynamic programmingor identify a near-optimal solution through the use of meta-heuristics search methodssuch as tabu search (TS), simulated annealing (SA), and genetic algorithm (GA).The previous attempts are included in [6-8]. A meta-heuristics method tends to find a solution in short time, but the solution found may not guarantee optimal. In contrast, the exact method provides the optimal solution, but most of them require the longer solving time. In this paper, we want to compare twodifferent exact methods for solving MCLP which are dynamic programming, andbranch-and-bound via optimization software. Both small-size and large-size problems are tested used these two approaches by comparing the solving time and quality of solution.
2. MCLP Model
The MCLP formulations are shown as the following. The objective showed in Equation (1) is to maximize the number of requested calls in the demand zones that can be covered. The constraint in Equation (2) is the limitation of the number of facilities; summation of facility located at each station should not exceed the total number of facilities that we have. For constraint in Equation (3), a demand zone can receive service from a station that has at least one vehicle located there. Equations (4) and (5) represent non-negativity and integrality constraints.
Maximize (1)
Subject to:
(2)
i=1, …,n (3)
= {0, 1}for all j (4)
= {0, 1} for all i(5)
Where:yi= 1 if demand zonei is covered by
station j
0 otherwise
hi= the population in demands zone i
xj= the number of vehicles located at
stationj
dij = the distance from station j to demand
zonei
p= the total number of vehicles to be
located
Ji= = set of stations that can
covered demand zone i
D= the maximum distance that can be
reached within 9 minutes (4 miles)
N= the number of demand zones
m= the number of stations
3. Dynamic Programming Model
In dynamic programming, the problem is divided into sub problems whereas the solution that optimal to a sub problem is also optimal to the problem. Since the optimal function of DP can be written in a recursive form, it is computationally efficient to solve. Moreover, the optimal solution is also guarantee. However, the advantage of using a DP algorithm depends on how we design the DP algorithm and how we code it in computer language. In maximal covering location problem model, we want to maximize the demands that can be covered by stations. In this case, we can let the stage be the station and solve the problem from stage 1 which is station 1 through stage m or station m. At each stage, we want to maximize the number of demands or calls that can be covered, so we have to keep parameters that effect on the coverage as our state. The state can be the number of vehicles left to be located, and the available stations. The number of vehicles go from 1 to p while the available stations go from {1}, {2}, …, {m}, {12}, {13}, …, {(m-1)(m)}, {123}, …, {1,2,3,…m}. At each stage, we solve the problem by making a decision whether locate or not locate a vehicle based on the coverage that gains more when open a new station. The DP formulations are shown as the following.
Stages (i) = current station
= 1, 2, 3, …,m
States (x,{s}) = (number of available vehicles,
{set of available stations})
x= 1, 2, 3, …,p
{S}={1},{2},…{12},{13},…,
{123…m}
Actions (ai)= locate or not locate
= 1, 0
Optimality Equation
= maximum covered demand at
stagen with X vehicles and {S}
stations.
=
Where Di = demand cover at each stage, ai = action in stagei which is either 0 or 1.
Recursive relationship of optimality equation
i=m, m-1,…,1
Where D{i,{S}) = covered demand by locating
vehicle at station i when i=1
= covered demand by locating
vehicleat stations in set {S}-
covered demand by locating
vehicles at stations in the set
{S}\{i} when i>1.
Boundary Condition
for all x, {S}
5. Results
5.1 A small size problem
In the small size problem, we have 5 zones; n=5, and 4 candidate stations; m=4, and 2 vehicles available; p=2. The data is in the Table 1-2.
Table 1: Distances between demand zones and
stations (miles)
Demand Zone / Station1 / 2 / 3 / 4
1 / 0 / 11 / 12 / 4
2 / 11 / 0 / 23 / 9
3 / 12 / 23 / 0 / 14
4 / 4 / 9 / 14 / 0
5 / 4 / 15 / 8 / 6
Table 2: Input data for the small-size problem
Demand Zone / Requested Calls / Station Set be able to response within 9 min1 / 5 / {14}
2 / 10 / {2}
3 / 6 / {3}
4 / 2 / {14}
5 / 5 / {1}
With the small size problem, we can show how to calculate and solve the problem using DPformulations. Since DP model is formulated in recursive form, the value in the one stage effect the value in another stage. We have to solve itconsecutively, start with the boundary condition at stage 0. All solutions in this stage are equal to zero. Then continue to solve at stage 1, 2, 3, and so on. The example illustrated below is solved with parameters as the following. The number of stations=4, so stage goes from 1, 2, 3, 4; the number of vehicles=2, so state goes from 1, 2; and the possible station sets are {1}, {2}, {3}, {4}, {12}, {13}, {14}, {23}, {24}, {34}, {123}, {124}, {134}, {234}, {1234}. The problem is analyzed through the recursive equation. The objective function and action at each stage are shown in Table 3. Maximal coverage when the number of vehicles is 2 is 22, and the solution to optimal is {12} which are locating vehicles at station 1, 2.
Table 3: Results of solving MCLP using
thesmall size problem
stage / state / f / a / stage / State / f / ax / S / x / S
1 / 1 / {1} / 12 / 1 / 1 / 2 / {1} / 12 / 1
1 / 1 / {2} / 0 / 0 / 1 / 2 / {2} / 0 / 0
1 / 1 / {3} / 0 / 0 / 1 / 2 / {3} / 0 / 0
1 / 1 / {4} / 0 / 0 / 1 / 2 / {4} / 0 / 0
1 / 1 / {12} / 12 / 1 / 1 / 2 / {12} / 12 / 1
1 / 1 / {13} / 12 / 1 / 1 / 2 / {13} / 12 / 1
1 / 1 / {23} / 0 / 0 / 1 / 2 / {23} / 0 / 0
1 / 1 / {14} / 12 / 1 / 1 / 2 / {14} / 12 / 1
1 / 1 / {24} / 0 / 0 / 1 / 2 / {24} / 0 / 0
1 / 1 / {34} / 0 / 0 / 1 / 2 / {34} / 0 / 0
1 / 1 / {123} / 12 / 1 / 1 / 2 / {123} / 12 / 1
1 / 1 / {124} / 12 / 1 / 1 / 2 / {124} / 12 / 1
1 / 1 / {134} / 12 / 1 / 1 / 2 / {134} / 12 / 1
1 / 1 / {234} / 0 / 0 / 1 / 2 / {234} / 0 / 0
1 / 1 / {1234} / 12 / 1 / 1 / 2 / {1234} / 12 / 1
stage / state / f / a / stage / State / f / a
x / S / x / S
2 / 1 / {1} / 12 / 0 / 2 / 2 / {1} / 12 / 0
2 / 1 / {2} / 10 / 1 / 2 / 2 / {2} / 10 / 0
2 / 1 / {3} / 0 / 0 / 2 / 2 / {3} / 0 / 0
2 / 1 / {4} / 0 / 0 / 2 / 2 / {4} / 0 / 0
2 / 1 / {12} / 12 / 0 / 2 / 2 / {12} / 22 / 1
2 / 1 / {13} / 12 / 0 / 2 / 2 / {13} / 12 / 0
2 / 1 / {23} / 10 / 1 / 2 / 2 / {23} / 10 / 1
2 / 1 / {14} / 12 / 0 / 2 / 2 / {14} / 12 / 0
2 / 1 / {24} / 10 / 1 / 2 / 2 / {24} / 10 / 1
2 / 1 / {34} / 0 / 0 / 2 / 2 / {34} / 0 / 0
2 / 1 / {123} / 12 / 0 / 2 / 2 / {123} / 22 / 1
2 / 1 / {124} / 12 / 0 / 2 / 2 / {124} / 22 / 1
2 / 1 / {134} / 12 / 0 / 2 / 2 / {134} / 12 / 0
2 / 1 / {234} / 10 / 1 / 2 / 2 / {234} / 10 / 1
2 / 1 / {1234} / 12 / 0 / 2 / 2 / {1234} / 22 / 1
stage / state / f / a / stage / State / f / a
x / S / x / S
3 / 1 / {1} / 12 / 0 / 3 / 2 / {1} / 12 / 0
3 / 1 / {2} / 10 / 0 / 3 / 2 / {2} / 10 / 0
3 / 1 / {3} / 6 / 1 / 3 / 2 / {3} / 6 / 1
3 / 1 / {4} / 0 / 0 / 3 / 2 / {4} / 0 / 0
3 / 1 / {12} / 12 / 0 / 3 / 2 / {12} / 22 / 0
3 / 1 / {13} / 12 / 0 / 3 / 2 / {13} / 18 / 1
3 / 1 / {23} / 10 / 0 / 3 / 2 / {23} / 16 / 1
3 / 1 / {14} / 12 / 0 / 3 / 2 / {14} / 12 / 0
3 / 1 / {24} / 10 / 0 / 3 / 2 / {24} / 10 / 0
3 / 1 / {34} / 6 / 1 / 3 / 2 / {34} / 6 / 1
3 / 1 / {123} / 12 / 0 / 3 / 2 / {123} / 22 / 0
3 / 1 / {124} / 12 / 0 / 3 / 2 / {124} / 22 / 0
3 / 1 / {134} / 12 / 0 / 3 / 2 / {134} / 18 / 1
3 / 1 / {234} / 10 / 0 / 3 / 2 / {234} / 16 / 1
3 / 1 / {1234} / 12 / 0 / 3 / 2 / {1234} / 22 / 0
stage / state / f / a / stage / State / f / a
x / S / x / S
4 / 1 / {1} / 12 / 0 / 4 / 2 / {1} / 12 / 0
4 / 1 / {2} / 10 / 0 / 4 / 2 / {2} / 10 / 0
4 / 1 / {3} / 6 / 0 / 4 / 2 / {3} / 6 / 0
4 / 1 / {4} / 7 / 1 / 4 / 2 / {4} / 7 / 1
4 / 1 / {12} / 12 / 0 / 4 / 2 / {12} / 22 / 0
4 / 1 / {13} / 12 / 0 / 4 / 2 / {13} / 18 / 0
4 / 1 / {23} / 10 / 0 / 4 / 2 / {23} / 16 / 0
4 / 1 / {14} / 12 / 0 / 4 / 2 / {14} / 12 / 0
4 / 1 / {24} / 10 / 0 / 4 / 2 / {24} / 17 / 1
4 / 1 / {34} / 7 / 1 / 4 / 2 / {34} / 13 / 1
4 / 1 / {123} / 12 / 0 / 4 / 2 / {123} / 22 / 0
4 / 1 / {124} / 12 / 0 / 4 / 2 / {124} / 22 / 0
4 / 1 / {134} / 12 / 0 / 4 / 2 / {134} / 18 / 0
4 / 1 / {234} / 10 / 0 / 4 / 2 / {234} / 17 / 1
4 / 1 / {1234} / 12 / 0 / 4 / 2 / {1234} / 22 / 0
5.2 A large size problem
For this large size problem, the data are collected from the Fire/EMS department at Hanover Country, VA [9]. The responsibility area is divided to 122 demand zones and there are 16 existing station locations for locating EMS vehicles. The individual 911 emergency calls are collected during 2007 and aggregated in each demand zone. A demand zone is covered when there exists an EMS vehicle that is able to respond within 9 minutes. So we have 122 zones; n=122, and 16 existing stations; m=16, and 5 to 10 vehicles available; p=5 to 10. The input data is in the same pattern as a small size problem.
For a large size problem, we compare our DP algorithm to optimization software ILOG OPL 5.5.The DP algorithm was written in C language using the Visual Studio 2005. The experiments were run on a Dell Latitude D410 machine with Intel Pentium processor 1.73 GHz, 0.99 GB of RAM. The results are show in Table 4. We see that DP algorithm performs very well. It obtained optimal solutions 100% with less runtime compared with OPL.
Table 4: Results of solving MCLP using
the large size problem
p / Opened stations / Covered demand(calls) / Runtime(sec)
OPL / DP
5 / {1 4 6 14 15} / 1559 / 4.55 / .422
6 / {1 4 6 11 14 15} / 1640 / 4.76 / .859
7 / {1 4 5 6 11 14 15} / 1636 / 4.53 / 1.50
8 / {1 4 5 6 9 11 14 15} / 1657 / 5.00 / 2.15
9 / {1 2 4 5 6 8 9 11 14} / 1674 / 4.01 / 2.68
10 / {1 2 4 5 6 8 9 11 12 14} / 1688 / 5.26 / 3.14
Note that station 1 and station 16 are identical, so open station 1 or open station 16 results in the same coverage. In computational DP algorithm, it always picks station 16 rather than station 1, because it solves from stage 16 to 1.
6. Discussion
A maximal covering location problem is not easy to solve because of binary variables in the model, so even using optimization software it still has to perform searching on the solution space. That is the reason why when problem size is large, heuristics are more prefer. DP is also another good option; however, the efficiency of an algorithm depends on the design of recursive function and the computational coding. For small example with 4 stations; m=4, 2 vehicles; p=2, and 5 zones; n=5. There are combinations of station sets. So the total number of solutions that we have to evaluate is 4x2x15=120 which is a lot. However, by taking the advantage of the recursive function and computer programming, we can solve the problem more efficient. That is we can solve the problem forward starting with the stage 4 and then move on to stage 3, 2, 1, 0, respectively. At each stage, we only call recursive function two times to decide whether locate or not locate, results in evaluating 21+22+23+24=36 solutions which is acceptable.
7. Conclusion
This paper proposed a dynamic programming (DP) algorithm to solve a maximal covering location problem. The problem is formulated in the DP form, and solved both analytically and computationally. The optimal solution is obtained in second in small problem size and several seconds on large problem size which is effective comparing with the other optimization software (OPL).
References
[1] Toregas, C., Swain, R., ReVelle, C., and Bergman, L., 1971, “The location of emergency service facilities,” Operations Research, 19, 1363-1373.
[2] Church, R. L. and ReVelle, C., 1974, “The maximal covering location problem,” Papers of Regional Science Association, 32, 101-118.
[3] Schilling, D. A., Jayaraman, V., and Barkhi, R., 1993, “A review of covering problem in
facility location,” Location Science, 1(1), 25–55.
[4] Farahani, R. Z., Asgari, N., Heidari, N., Hosseininia, M., and Goh, M., 2012, “Covering problemsin facility location: Areview,” Computers & Industrial Engineering, 62(1),368-407.
[5] Saydam,C., Repede, J., and Burwell, T., 1994, “Accurate estimation of expected coverage: a comparative study, ” Socio-Economic Planning Sciences, 28(2), 113-120.
[6] Chiyoshi, F.Y., Galvão, R.D., and Morabito, R., 2003, “ A note on solutions to themaximalexpectedcoveringlocationproblem”
Computers & Operations Research, 30(1), 87-96.
[7] ReVelle, C., Scholssberg, M., and Williams, J., 2008, “ Solving themaximal coveringlocationproblemwith heuristic concentration”Computers& Operations Research, 35(2),427-435.
[8] Zarandi, M.H.F., Davari, S., and Sisakht, S.A.H., 2011, “The large scalemaximal coveringlocationproblem,” ScientiaIranica,18( 6),1564-1570.
[9] Chanta, S., Mayorga, M.E., and McLay, A.M., 2011, “Improving Rural Emergency Services without Sacrificing Coverage: A Bi-Objective Covering Location Model for EMS Systems,” Annals of Operations Research, DOI 10.1007/s10479-011-0972-6.