! Cell phone base station location model in LINGO, www.lindo.com ;
! Decide 1) Which locations should have a base transceiver station (BTS),
         2) the coverage radius, or range, for each BTS.
     The coverage radius of a BTS can be controlled by the broadcasting
  power used at that BTS.
  Each BTS cannot have more demand assigned than its capacity.
  If  DP j is within the range of BTS i, 
    then j must be assigned to i. Similarly,
  if DP j is assigned to BTS i, 
     then j must be within range of i.
 ;
! Key words: Cell phone, Mobile phone, Network design, Facility location, Covering;
SETS:
 BTS:    ! Candidate base transceiver stations;
    CB,  ! Cost of BTS i;
    R,   ! Radius of standard coverage for station;
    Y;   ! Y(i) = 1 if cell tower used at location i;
 DP:     ! Demand points;
   DEM,  ! Demand at point j, e.g., expected calls in progress;
    Z;   ! Z(j) = 1, if j not assigned;

 BXD( BTS, DP): 
   DIST, ! DIST(i,j) = distance from BTS i to DP j, e.g., in signal attenuation;
      X; ! X(i,j) = 1 if DP j assigned to BTS i. Could be assigned to more than 1;
ENDSETS

DATA:
  CAP = 125; ! Max demand that can be assigned to any cell, calls in progress;
  WNH = 10;  ! Weight or cost on demand not handled;
  BTS =  1  2  3  4  5; ! The base stations (BTS);
   CB =  8  5  7  9  6; ! Cost of each;
  DP = 1   2   3   4   5   6   7   8   9  10  11  12; !Demand points (DP);
  DEM= 15 34  28  32  12  27  19  29  12  41  37  23; !Demand at each, expected calls
                                                         in progress at any instant;
  DIST=  ! Distance from each BTS to each DP. E.g., power needed at i to
            give acceptable signal at j;
 0.781  0.781  1.616  2.571  0.640  0.640  1.552  2.532  1.487  1.487  2.052  2.865 
 1.456  1.523  2.126  2.953  0.566  0.721  1.649  2.631  0.721  0.849  1.709  2.668 
 1.942  1.253  1.170  1.780  1.603  0.608  0.412  1.404  1.836  1.082  0.985  1.664 
 2.550  1.581  0.707  0.707  2.550  1.581  0.707  0.707  2.915  2.121  1.581  1.581 
 2.953  2.126  1.523  1.456  2.631  1.649  0.721  0.566  2.668  1.709  0.849  0.721; 
 ! Above data set corresponds to demand points being at the grid points of a
   (1..4) by (1..3) grid, with the 5 candidate BTS sites at
   (1.5, 1.6), (1.4, 2.4), (2.6, 2.1), (3.5, 1.5), (3.6, 2.4);
ENDDATA

SUBMODEL CHUZ_CELLS:
! Decision variables:
    Y(i) = 1 if a BTS is established at site i, else 0,
    X(i,j) = 1 if DP j is within the coverage range of i, else 0,
    R(i) = range or coverage radius of BTS at i,
    Z(j) = 1 if DP j is not within range of any BTS;


 ! Minimize weighted cost of the BTS installed and demand not handled;
   MIN = COSTBTS + WNH*SUMDNH;
         COSTBTS = @SUM( BTS(i): CB(i)*Y(i)); ! Cost of stations;
         SUMDNH = @SUM(DP(j): DEM(j)*Z(j));   ! Unassigned demand;

 ! Z(j) = 1 if DP j not in range of any BTS;
  @FOR( DP(j):
    Z( j) >= 1-@SUM( BXD(i,j): X(i,j));
      );

  ! Cannot assign too much demand to any BTS i.
    Any DP j within range of a BTS uses up capacity;
  @FOR( BTS(i):
    @SUM( BXD(i,j): DEM(j)*X(i,j)) <= CAP*Y(i);
      );

  ! If BTS i not used, then radius must be 0;
  @FOR( BTS(i):
     R(i) <= RMAX*Y(i);
     @BIN( Y(i));
      );

  ! If DP j assigned to BTS i, then j must be
    within range of BTS i ;
  @FOR(BXD(i,j):
         R(i) >= DIST(i,j)*X(i,j);
       @BIN(X(i,j));
      );

 ! If DP j is within range BTS i,
    then j must be assigned to i;
  @FOR(BXD(i,j):
       R(i)- DIST(i,j) <= RMAX*X(i,j);
      );
 ENDSUBMODEL


 CALC:
  
! Max radius one might need;
   RMAX = @MAX(BXD(i,j):DIST(i,j));
   @SET('TERSEO', 2); ! Turn off default output;
   @SOLVE( CHUZ_CELLS);
   @WRITE(@NEWLINE(1),' Cell Network Design Report',@NEWLINE(1));
   @WRITE( @FORMAT(COSTBTS, '12.2f'), '= Cost of cells, BTS.',@NEWLINE(1));
   @WRITE( @FORMAT(WNH*SUMDNH, '12.2f'), '= Cost of demand points not covered.',@NEWLINE(1));
 
   @WRITE(@NEWLINE(1),'       Cell      Radius',@NEWLINE(1));
   @FOR( BTS(i) | Y(i) #GT# .5:
     @WRITE( @FORMAT(BTS(i),'10s'),'  ', @FORMAT(R(i),'10.3f'), @NEWLINE(1));
        );
   
   @WRITE(@NEWLINE(1),' Cell to Demand Point Coverage',@NEWLINE(1));
   @WRITE('       Cell      Demand point covered',@NEWLINE(1));
   @FOR( BXD(i,j) | X(i,j) #GT# .5:
     @WRITE( @FORMAT(BTS(i),'10s'),'  ', @FORMAT(DP(j),'10s'), @NEWLINE(1));
        );

 ENDCALC