! 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;
 LXLXTS( LXL, TIME): ND; ! Use sparse set,
                         assuming demand is sparse;
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); ENDCALC