Lindo Systems

! Bus route design problem.
   Given a set of locations and periods,
 a number of people or commodities arrive at each
 location each period, desiring to be tranported
 to other locations. It takes a specified amount
 of time for a bus to travel from location i to location j,
 and people do not want to wait a long time, and each bus
 has a finite capacity, how should we route the buses,
 so that people get transported to their desired locations
 without having to wait very long?
   This is a discrete time model. The period length should
 be just short enough to accurately approximate travel times
 and wait times. E.g., if the average tolerable wait time
 is 6 minutes and the trip times is are multiples of 9 minutes,
 then a period length of 3 minutes should give an accurate
 approximation. The longer the period length, the fewer the
 number of periods needed to model a given interval of time,
 and thus more manageable is a problem with lots of locations;
! Keywords: Routing, Origin-desitination, Bus routing;
SETS:
 LOCN: INIV;
 LXL(LOCN, LOCN): TRVT;
 TIME;
 LXLXT( LOCN, LOCN, TIME): TRIP;
 LXLXTS( LXL, TIME): ND; ! Use sparse set,
                         assuming demand is sparse;
 LXLXTXT( LXLXTS, TIME) | &3 #LE# &4: XD;
ENDSETS
DATA:
  WMAX = 5; ! Maximum wait allowed in periods;
  DWGT = .01; ! Weight applied to wait/delay;
  VCAP = 5;   ! Vehicle capacity;
  LOCN = A B C;  ! The locations;
  TRVT = 1 2 3 ! Travel time, i to j, in periods;
         2 1 4
         3 4 1;
  TIME = 1..6; ! Number of periods;
  ! Demands by
   (origin, destination, period, number people);
  LXLXTS, ND =
   A B 1  3
   A C 1  2
   A B 3  4
   B A 2  1
   B C 3  2
   C A 1  3
   C A 2  2
   C B 2  2;
ENDDATA

! Variables:
    INIV(i) = initial number of vehicles/buses at location i,
    TRIP(i,j,t) = number of vehicles departing i for j
                  in period t,
    XD(i,j,s,t) = units of demand arriving at i at time s,
                  that depart for j on a vehicle departing
                  at time t, note, s <= t;

SUBMODEL BROUTE:
! Minimize weighted combination of number of vehicles needed
  + total delay of people;
  MIN = NVEH + DWGT*DELAY;
  NVEH = @SUM( LOCN(j): INIV(j));
  DELAY = @SUM( LXLXTXT(i,j,s,t): (t-s)*XD(i,j,s,t));

! Conservation of flow: incoming vehicles =
  outgoing vehicles at location k, time t;
  @FOR( LOCN(k):
    [FLO1] INIV(k) = @SUM( LOCN(j): TRIP(k,j,1)); ! Time period 1;
    @FOR( TIME( t) | t #GT# 1:   ! Later time periods;
     [FLO] @SUM( LOCN(i):@SUM( TIME(s)| s+TRVT(i,k) #EQ# t: TRIP(i,k,s)))
      = @SUM( LOCN(j): TRIP(k,j,t));
        );
       );

  ! There must be enough vehicle capacity to handle
    load departing from i to j in t;
  @FOR( LXLXT(i,j,t):
    [CAP] @SUM( LXLXTXT( i,j,s,t) | t-WMAX #LE# s #AND# s #LE# t: XD(i,j,s,t))
      <= VCAP*TRIP(i,j,t);
      );

  ! All Demand must be handled in timely fashion;
   @FOR( LXLXTS(i,j,s):
     [DEM] @SUM( LXLXT( i,j,t) | t-WMAX #LE# s #AND# s #LE# t: XD(i,j,s,t))
         = ND(i,j,s);
       ); 

  ! No fractional vehicles allowed;
   @FOR( LXLXT(i,j,t): @GIN( TRIP(i,j,t)));
ENDSUBMODEL

CALC:
  @SET('TERSEO', 2); ! Turn off default output;
  @SOLVE(BROUTE);
  @WRITE('  Bus Route Optimization', @NEWLINE(1));
  @WRITE(' Weight applied to passenger wait time= ', DWGT ,@NEWLINE(1));
  @WRITE(' Total Passenger delay in periods= ', DELAY,@NEWLINE(1));
  @WRITE(' Number vehicles used= ', NVEH, @NEWLINE(1));
  @WRITE('  Locn  Initial vehicles', @NEWLINE(1));
  @FOR( LOCN(i) | INIV(i) #GT# 0.5:
    @WRITE( '   ', LOCN(i),'     ', INIV(i), @NEWLINE(1));
      );
  @WRITE(@NEWLINE(1),' Vehicle Movements', @NEWLINE(1));
  @WRITE(' Time  Origin  Destn  Arrives_in  #vehicles',@NEWLINE(1));
  @FOR( TIME(s):
   @FOR(LXLXT(i,j,t) | i #NE# j #AND# t #EQ# s #AND# TRIP(i,j,t) #GT# 0.5:
    @WRITE( '   ',t,'     ',LOCN(i),'       ',LOCN(j),'      ', t+TRVT(i,j),
        '           ', TRIP(i,j,t),@NEWLINE(1));
       );
      );
 ! @GEN(BROUTE); ! Look at the formulation;
ENDCALC