! 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); ENDCALC
|