Note: Descriptions are shown in the official language in which they were submitted.
~IPR 26 '94 13:55 FROI~I OTIS INT PROP DEPT TO GOWLING C~N~bh Pr~GE.003~033
'- 21X~ 9
Elevator Di~pa~-ching with ~lt~pl~
Ter~ Objecti~ ~uncti~n and ~nst~ntaneous
~levator a~aignment
Technical Field
~he present inventlon r~lates tu assi.gnment of
elevator6 to hall calls.
Backqroun~ of the Inven~ion
An el~vator di~pat~her causes a particul~r
ele~ator in ~ ba~ of elevator cars to ~e ~ent to a
floor in ~esponse to a ~se~ pres~ing a hall b~tton at
that floor. ~raditionally, a hall lantern will
ill~minate 3ust p~ior to ~he opening of the ca~ doors in
order to infurm the us~r a~ to ~hich car will ~ervice
his hall call.
The disp~tcher as~gn6 a car to a hall ~all
according to a varic~y ~f el~ator syst~m p~ra~eter~.
It i~ poe~lble ~or valuee o~ t~Q6a sy~tem uaram~t~r~ to
change between the ~ime the hall call i~ r~gi~ter~d and
~he tlme t~e hall call ~s 6er~i~ed. There~ore, the
dispatcher ~ay reassign the ha~l c~ o oth~r cars ma~y
timos be~ore the hall call ~s serviced. The u~er do~s
not notice the Xeassi$~ment because t~o hall lantern iS
lit only after thefi~ ~ultipla reassig~nt~ have
~curre~ an~ just before t~e ~a~ axrives at the ~loor.
2S Ac~ordi~g tv a di6patching schem~t called
instantaneous car assignment (ICA), ~nce a car has been
assigne~ ~o a hall cctll, the a~ignment may not be
chang~d. ~like traditional el~tvator as~ign~ent
techniguet~ IC~ in~r~5 the u~¢r at t~e instant o~ ~irst
a~sign~t~nt (or sh~r~ly ~h~er~af~er) as to Which car Will
servi~e hisJher hall call. ~h~t benef~t is that the user
cctn be walkin~ to~ard that partic~lar car, o~ the bank
cyDl~t.~air~t~# _E~a?~7~44
~ C~it _ ~y~5-l~s3~ ~ _
0~--138~ c~ , t;~ t~ ';s ~ .r;~ n6itlYt
___S~lt
',',.' '. ' ~ ' '
,',' , ~ , ~,' ~ . ' .
i;. ' . ' . ,~,, :
' ~ 'i ' ' ' : '
hPR 26 '94 1(3:55 FliOI~I OT15 INT PROP DEPT TO GO~JLlN~i ChNhl:l~ PhGE.0~34/033
2122~6~
of cars, which ls going to serve hi~ and be positl~ned
and rea~y ~o enter that car when it ar~ives. A know-
and-qo time i5 tha time f~o~ ~hen a passeng~r knows
which car i5 respon~iny to his hall call to ~he tl~e i~
S takes him t~ qo over to the c~r. Therefore, giving ~he
user the opport~nity to be in fr~nt of the car when it
arrives re~ir~ that numerous rea~si~nments o~ a hall
call to di~ersnt cars can~ot take pl~ce. ~o t~e extent
a dispatcher ls spending ~me reassigning, the know-and-
go time is ~sed up.
~he reason ~r allowin~ m~ltiple reassi~nments in
the past was to obtain the ~est assignm~n~; concerD o~er
an initial optim~m assignm~nt was mini~iz~d in the past
b~oause there ~ould always be reassignments possible and
the~for~ the opportunity to correct for an initial
assign~nt th~t had beqome less tban optimum in llght of
subsequent even~s ~u¢h as new h~ll call~ and ~ar c~lls~
Und~r ICA, howe~er, P~ause there i6 llttl~ or no ~ime
for r~assi~nment~, ~he importanc~ Qf a go~d initial
~0 as~ignment i~ increased.
The ~ir6t use~ of ~CA were not as sen6iti~e to
this issue a~ they might have ~een. RelatiVe Sy~te~
~sponse (RSR), taught in n.s. Patent ~o. 4,363,38}
nR~lative System Respo~e Eleva~or Call Assignments", i~
one scheme typically used with the exp~ctation ~h~t
multip~ reassign~nts would be allowed. ICA wa~ us~d
in Gon~ mction ~dith JISR~ 'rhi6 RSR~ICA sc:~e~e,
th~efore, fixed the ~i~s~ cRr to hall call assignment
u~ing RSR - a s~heme ~or whi~h the initial assi~n~nt
did not account ~or f~ture events ~new hall ca~l6 and
car calls) which would serve ~o degrade the quali~y of
an initial assi~nme~t. ThQ need for ~ better initi~l
assig~ent re~ain#d a~ter RSR/ICA.
s .. .. :- . . , , . , :. : : . :
RFR 26 '94 ~0:5~ F1~011 OrlS INT PROP ~EPT TO GOIIJLING ChNh~ P~lGE.0135/033
.
21~2~.'3
The average registr~ion is the time from when th~
hall call b~tton is p~es~ed to the ti~e that the hall
call is canaelled. Thi~ latter point i~ time varies
with diff~rent elevator syste~ ~ for some, th~ hall
call i8 c~ncelled ~hen th~ car arriv~ at the ~loor and
is leveling wh~le fo~ othe~ the hall call is cancelled
at a s~op control point typically located where
deceleration of the elevator begins a~ it ne~rs th~
floo~ ~egins and a hall lantern is lit. ~o~e that
0 r~gistration time i~ no~ equal to waiting time because
not all pass~ngers wait ~e ~a~e ti~e and therefore we
cannot easily measure the waiting time of all
p~ssengers A
The av~rage r~gis~ration ti~e of an elevator
syst4~ i~ a ~o~mo~ me~ric for the p~rfo~mance of that
system. ~wever, a good avera~e regi~tration time can
be deceptive, hiding an occa~ional, extremely long
regi~tration time amonq numsrou~, ve~y ~hort
r~gistration ~i~e~. Engineer~ have di~co~r~d that
there will u~ually b~ on~ hall call fluring a heavy ~wO-
~ay tra~ic ~c~na~o which ~aits a very long tim~ ~or
exampl~, 135 ~coond~ hase long waits oc~ur rather
~ quently (for ~xa~ple, once o~ twice in one thousand
hall ~alls~. It has heen observed th~t the Associated
hall calls ha~e ~f~en ~een bypa6s~d by at least one
l~sually sa~eral) car. ~hese b~passe~ h~ppen beca~s~
the Pypassing car wa~ not th~ ~ne assig~ed to the h~ll
call a~ the tim~ of the b~pn~ f the bypassing car
had stopped ~or the hall call, then the Yery long
r~gis~r~tion time could h~ been re~uced~
~ustom~rs ~a~e pointed ~ut ~h~ need t~ red~ce
the~e ~ary long reg~tration times. ~y reduaing the
nu~ber o~ hall call ~ypasses, a dlspatcher may r~duce
the longest reqistration ~ime. At the s~me time,
- 3 -
'''. '- .`' , ' ' :
;'. '' ' ~ ' 1' ~ '
- . . . .
` ", ' .. . . ,.' ' ~ ;
`',"~ ' , ,' ~'I" "`' `
.:, ~, .
hPR 2b '~4 1E~:56 FR~rl OrlS INT PROP DEF; TO GOWLI~G C~NflDfl 5RGE.006~033
2~22~6~
however, the average o~ all regi~t~ation tim~s ~ay
increa~e because special treatment to a long-w~itin~
call is g~ven at the ~xpense o~ several other hall
~alls. In somQ ~arket~, it is understood t~t ~he
m~rket place will accept a higher ~v~ra~e r.egistration
~ime in favor of a lo~er maxim~m regis~r~t~Lon time.
Yigur~ 1 ;llustrat~s thi~ maXi~um regi~tra~ion
t~me dilemma a~d the ~ailure of the prior ar~ to addre~
i~. Aceordlng to the prior artI car B is a6signed a
hall call at ~loor 7 while car B is ~ading ln the down
direction when a new h~ll call ~t ~loor 9 i~ registered,
which hall oall i~ as y~ not a~signed. Car A is ~lso
~eading in ~he down direction but i~ ~arther from the
hall cal} regi3tered ~t ~loor 9 than car B. According
to the prior art RSR schemQ~ aar B Will more than likely
be a~s~gne~ to th~ hall call at ~loor 9 beca~se car B is
closer ~han aar A ~o ~loor 9. Thi~ is op~imUm for the
p~rson who ~istexed the hall call at ~loor 9, b~t tbe
p~rson who rQgisterea the hall call at ~laor 7, to Which
2~ car ~ is already c~mmitted, haa ~een waiting ~or ~i~t~
~econd~ ~or a car ~lready wheD t~e hall call at floor 9
was regi~tered~ T~e pe~son at floor 9 has a ve~y short
wait, but th~ person at ~loor 7 who ba6 already waited a
lon~ timer noW waits even ~ong~r.
Disclo6ure of the In~e~tion
Objectives of the present i~ention incl~de
reducing the ~aX~m~m re~istration ti~e, while ma~imizing
the know-~nd-g~ time and 6till ac~ie~ing a good i~itial .
el~vator assignment.
A~cording to the pre~ent inyentton~ a~signment of
cars to Pall ca~ls i~ performed dir~tly as a function
of syste~ perform~n~e paramet~rs, rel~ted to pas~nger
w~i~ing ~ime including 1) remaini~g response ~i~e ~R~
^ 4 -
,: . " ' '' . ''. ' '
RPR C6 '94 113:56 FRC111 OTIS I~T PROP l)EPT TO GOWLING CPNflD~ GE.E~07~33
21~2~
and one or more o~: 2) predicted r~gistr~tion ~im~
(PRT), 3) maximum pr~dic~ed re~istration time (maxPR~)
and ~ a relati~e system response ~RSR) qu~n~ty. In
still f~r~her accordance with the p~e~nt inven~ion, thQ
~ssignmen~ of elev~tor~ to hall call~ is perfo~ed
according to the ~yst~m param~ter~ and reassignQent i3
discouraged ~a in~orporate an instantaneous elevator
a~si~n~nt f~ature.
~n advantage is ~hat the ~aiting ti~e of long-
~aiting calls is ~educ~d~
Brl~f Description of the Drawin~s
Figure 1 is a prior art ~hart of floors m~pped
against the location of car~ in a ba~lk o~ ele~ators and
registered hall calls.
Fig~re 2 maps ~loors agains~ the location o~ a car
B ~nd car call-q and hall calls ~or assignment to car ~.
Figure 3 Ls a mappi~g of floors ~gain~t the
location of car~ ~, C and elevator calls associated with
t~o~e ~lQ~ators and a hall call a~60ciat~d with car B.
~0 Fig~re 4 i~ a map o~ ~loo~s again~t re~i~terQd
hall calls, ~nd the locat~on of car B, C.
Figure 5 i~ a ~ster ~low chart fo~ ~llu~trating
th~ ~othod of the present in~ention.
Figure 6 is a flo~ chart ~ a ~a}1 call a~sign~ent
algori~hm.
Figure 7 i~ a ~low chart for determinin~ an
o~iective function.
Figure 8 ie a graphical repre6entation of an
ob3~ctive func~ion ~ith a single i~d~pendent ~ariib}e,
showing the e~istence of a ~inim~m ~alue for ~4e
o~jecti~e function.
- 5 -
, . -- -- . . .
~ ~ : : :: :. ::-- .
.. , . : . . .
, .
,: . : .,:
:,: . :.~
-.: : ,,
,. . .
-: . .~ .
QPR 26 '94 11~:56 FRO~`1 OTIS l~r PROP DEPT TO GOWLING Cf~ DR P~J5E.00~3~0'3
21~2~6~
Be~t ~ode ~or carrying out the Inv~t.ion
The dispa~ching method of the present inv~ntion
consiStS o~ t~o parts~ First~ for a n~w ~all call, a
c~r i6 as~igned to the call by choo~ing th~ car which
provi~es the ~ni~um ~aluc o~ the objQctiYe (~ean~ng
goal) function:
OBJ ~iaar) = A-RRT ~ B-¦PRT - 20l
~ t C~maxPR~ - ~o~ ~ D~RSR.
E~ch t~rm is discussed in detail b~low.
~jectlve functions used in el~v~tor dispa~ching
are not new, see U.S. Patent 4,947,965 ~uzun~ki et ~1,
~Group Control Method and ApparatUs for an ~levator
System with Plural ~ages". ~he R5~ ~lgorithm uses an
objectivo ~unction. ~he RSR ~lgorithm and vario~
modifications of it can ~e 6aid to include ~ariou~
terms, dependin~ on the RSR algorithm employed. ~
basic co~ponent of the RSR ~l~ntity is an esti~ate of
th~ number of second~ a eleva~or would re~uire to reach
a hall call.
~ow~ve~, th~ ~ce of ~he ~ar~i~ular objectlve
function, the sel~¢tion of the elQ~Rn~s of the ob~ct
funation, thQ u~e of an objective ~unction in
combination with ICA ~nd the assignment o~ car~ ta hall
calls dlrec~ly Ag a ~unotion of elevator sy~tem
performance ~etrics are, a~ong o~har ~hing~ pre~nt~d
here, ne~.
~he second part of the inven~ion i~ th~
lnst~ntaneou~ car assign~ent tIC~) feature in
combina~ion with the ob~ective ~un~io~ For a hall
c~ll tha~ t~as been ~aiting for so~e ti~e wi*;h a c~r
alrea~y assignea, ~wi~ching th~ aB~ign:ment to anot~r
car iR unlikely according to ~he p~e~ent i~ntion.
Under no ciraums~nces will more than one reas~igD~ent
~e allowed. ~ switc~, that is a rea signment, i6
-- 6
: ~ . , , .:: ,.......... ~ : -
: : -
~PR ~b '~4 lE3:C7 FRQM OTIS INT PROP DEPr TO GOWLI~G CQN~ PfGE.13~19/0~3
2 ~
pQrmi~sible under t~o Qxceptional circumstancc~
ther~ is a car other than the a6aigned one that can
reach the call ~ignifica~tly faster (for ~a~ple, ~y at
least ~0 ~e~and6~ a~d ~) the ~sslgned c~ :Ls traveling
away ~rom the call ~for exampl~, ~he car a~5~gned to an
up ~11 call i5 traveling upwardly a~ove ~he call~. In
the case wher~ a ~witch is p~rmissi~l~, the assignment
iS made based on the ob~ective ~'~nction. The values o~
the coefficients ~, ~, C, and ~ can be v~rie~ to r~lect
the preference of the buildin~ owner. It is al~o clear
tha~ ~y etting all but one coef~icient to z~ro,
dispa~ching assignments c~n ~e made based on a single
metric.
The ter~ remaining respons~ ti~e is fully
desori~ed in U.S. Paten~ 5,146,053 entitled ~Ele~ator
Di~pat~h~ng Based on Remaining Respon~ Time", i~sued to
t~e ~a~e i~entor~ a~ t~e pr~s~nt inve~ti~n. It 15 an
e~timate of the n~mber of seco~ds an clevator would
reguire to rea~h the h~ll call unde-r con~deration given
its cu~r~t ~et ~f a~signed car ~alls and hall ~al1~.
t is sometimes ref~rred to in ~he eleva~o~ indus~ry as
esti~ated time o~ arri~l t~A)~
F~gur~ 2 illustrates ~ car a ~oving in the down
2~ direc~ion ~nd positioned a~ floor 12 on its ~ay ~o
service a car call at floor 9. At this poin~, a n,ew
~all call is regis~er~d at floar S. The remain~ng
re~on~e tlm2 for t~e new h~ll call fo~ ~ar ~ i~ an
exempl~ry lS seconds. A ~BW ~econds lat~r, a~other hall
3~ call i~ assigned when the car ~, still moving downwardly
i~ the dirac~ion o~ its car c~ll at ~loor 9 ~n~ a~signed
hall ~all ~dt floor 6, when another hall ca}l i6 asgig~ed
to it ~t fioor 10. The additional hall call a~ floor 10
- 7 -
~:,: , , :~
.. . : ~
~:. ~ :. : -:
. :: - . . - , .
.-
f~PR 26 '94 10:5~ FROM OTIS INT PROP DEPT TO GOIIJLING Cl~hDh P~GE.010/033
2~22~9
increas~s t~Q remainlng response time of t~e call at
~loor 6 to 25 seconds ~ro~ 15 s~conds.
Flgure 3 maps ~lo~rs in a ~uildlng against car
calls ~or cars B and C and a hall call assigned to car
B. Figure 3 ~llustrates the rem~ining response time
comcept af~er ~ h~ll call has alrea~y been waiting an
exemplary time o~ 20 ~econds. In Figu~e 3 a car B i~
tra~eling in the do~nward direction ~o 6er~ice two c~r
call~ be~re servicing a hall call as6igned to car B
lo wh~re ~he pasS~nger h~s a~ready ~Qen wai~ing or ~o
seco~ds. Meanwbile, a car C is mo~lng in the up~ard
direc~ion to serv~Ge a car cal~ at a floor abo~e th0
loca~ioP of the ~all call. The question arises as to
whether the hall call should r~ain assigned to car s or
b~ re~ssig~ad to car C.
~here thQ ~signme~t of ~ars to hall ca~ls is
based purely on re~Ainin~ response ~i~e, t~ re~aining
r~ponse ti~e ~or a~ nment to aar B i~ co~par~d to the
re~a~n;ng res~on~e ti~ Por car C to e~aluat~ th~ merit
o~ ~h~ curren~ asslgnment aT-d d~termln~ wh~her ~
~witch, ~at i6 a r~a~;s~gn~entr ~om car B to c~r C
would be a good id~a.
Al~o~ if the trip to raach a hall call in the
opposite direction includes an assi~ned hall call in the
~irecti~h o$ tra~el, thQn fo~ the purposes of remaining
re~pons~ ~i~B computation the car 1~ as~umed to go to
~he ~erminal ~loor. (For example, consid~r ~ car
t~aveli~g u~ a~ floor five wit~ a c~r call at 7 and an
assigned ~all call at floor 9. Now, a ~own c~l} is
3~ registered at floor ln. To e~ti~ate ~he remaini~g
respo~se ~i~e o~ the car, the car is a~aum~d to bQ s~nt
to the ~op terminal to f~lfill th4 car aall resultin~
~rom the hall call at floor 9 be~ore it can r~a~h ~loor
lQ in the down direction). Upon reflection, it can ~e
- 8 -
:.: : : ~ ~ . . : : , . : .
flFR 26 '94 lE~:57 FROI~I OTIS INT PROP DEPT TO GOl~lLlNG Ci:NhrlR PhGE.011/033
2122~69
seen th~t ~is assumptio~ that the cars go to the
terminal floor is ~o~ necessarily the ~ors~ case.
We assume that only one c~r ~all results fro~ the
up hall cail at ~loor g, and that is to the terminal
floor (the top). A ~uch wor~e situation w~uld be if
several people wero waitin~ behin~ t~e hall call at
floor 9, and each pressed a di~erent car call button.
For this worse case, the RRT would obvio~sly be muoh
longer, due to addi~ional s~ops.
~
~hi~ metric i~ the sum of ~he a~oun~ of th~ time
that the call ~as already been w~iting (the wait ti~e-
~o-far) a~ the RR~. For a new hall call, PXT ~
~i~ure 4 illustrates why assignment of hall calls based
solel~ on re~aining re~pon~ time is not su~icient for
.good hall call a~sigPment~ and why predicted
regis~ration ti~e ~s importa~t. Car B i~ presently at
floor 11, car B is moving downwardly to service a ha~1
c~ll as~igned to it ~t ~loor 6 where the passenger'~
~ait tim~-~o-far is ~a very lon~ 50 s~cond~ whe~ ~ new
hall call i~ regist~red At Cloor g. Anoth~r car C a~
~loor 14 i~ al80 ~o~ing downwa~d~y. Th~ re~ainlng
re~ponse ti~e o~ car B ~or th~ new hall c~ll a~ floor 9
is six seeonds. ~he remaining re~pon~e ti~e o~ the car
Z5 C ~ respect to the new hall call a~ 100r ~ is 15
seconds, becauce the car C i~ ~art~er a~ay from the ne~
hall than car B. It would soem at this point that the
logical ~el~ct~on for ~he as6igpment ~or th~ hall call
is car B. Under certain ~ircumstances, this assign~nt
3a ~ould not be approp~te, however, bec~use of t~e e~e~t
of that assign~en-t on other cal~. The pre~iated
re~i~tration time ~or tha call at ~loor six if car B i~
a~igned to the h~ll call ~t floor 9 is increase~ to 65
se~o~ds. ~e predi~ted rogi.stration ti~e ~or t~e ~all
_ g _
,. ... ,, , .,;:: . . .. ::. , .,.: ,., .. , . .. : . ~ :
,. . : . ; .: , .: .
: , . :: :::,
.. : .: :
::: : . . - :
: : . .
,~,:: : .. ~
., : ~., : :
hPR 2~ 'q4 10:58 FRO~ OTIS INT PROP IIEPT TO GC~ LIN5 C~ D~ PflGE.al2/033
~12~6~
dt floor ~ i~ car B i~ as~igned to the hall call a~
floor ~ is 55 second~. ~hus, assignin~ the car B to the
new hall call at floor ~ based on ~he ~horte5t r~maining
response time co~pari~on ~or the two cars res~lts in a
very long predict~d regis~r~tion tim~ ~or ~he passenger
a~ ~loor 6. Ihe p~ed~cted r~gistration tine resu~ts
wher~ an assignment is ~ade purely as a f~otion ~P ~be
remaining response ti~e ~tric is poign~nt where ~s ~n
ext.ra 10 secon~s of waitin~ for the passe~ger at floor 6
is the di~fer~nce between ~n anxious passen~er and a
fu~io~s passenger, as a conse~uence of ~he nonlinearlty
of passenger fru~tration as a fun~tion o~ waiting ti~e.
~ce, the wisdom of including the predicted
regi~t~ation ti~e in the o~jective function.
l T~e predicted re~istration time metric is incl~ded
ln the objeotive func~ion as the ah~olute value o~ the
dlfferenc~ be~ween the pr~dicted r~gistration tim~ An~
the term, T1, 0~ 20 ~cond3. I~ the predicted
registration tim~ lther v~ry short or ~er~ long~
then t~e ten~, T1, punaliz~s a car. ~his rQ~lects the
philosophy in fiome mark~s t~at a passen~er i5 willing
to wai~ approximately 20 secon~s without a~y level of
discom~ort. 0~ cour~o, thi~ penalty ter~ is variahle
and need ~ot be ~0 ~econds. Therefore~ a car t~at could
2S r~ach the hall call in a very s~ort time ( or example,
five seconds) might be~ t~r proc~ed to answer other.~ore
urgent elev~to~ ~ystem demands.
Waiting times in eXc~;s of ~0 seconds are
considered very long wbil~ their ~requency i~ low (onc~
or twlce in a two hour heaY~ two-way traffic). Their
effect is a ~ajor irritant to passengers. It is
i~porta~t to reduce th~ ~agnitude and freguency of these
long-waiting calls. The present invention p~opo~es to
~ 10 --
;'~' , ' ' ' ~
,:. ~ , ,:
RPR 26 '94 10:5S FROt~l OTI5 INT PROP DEPT 'O GOWLING CRNRDR K~GE.01:~/033
2122~
address thesu lan~ aall6 by penalizi~q ~h~ car for an
a~ign~nt only when that a~sign~ent Will cau~Q the
longe~t waiting call (o~ all hall calls presently
waiting) to ~ait long~r than a term, T2~ 6~ second~. It
i5 thought that a call ~ha~ has alre~dy wait2d 60
seconds has a poten~ial to cros~ ~he 90 seconds
thre~hold and therefo~e should be given sl?ecial
conside.ration. ~e p~alty terL i~ variable ~nd neQd
no~ be 60 seaonds. ~he ~erm i~ ~q~ared i;n the o~jective
~unction to reflect ~he passengers gro~ing irrita~ion
whioh i~ ~lt to be nonlin~ar and inc~easing as the
waiting time inoreases beyond 60 secon~s. Obviou~y,
the term ~axP~T, like PR~, need not be sguared ~ut could
~e the a~gument for any o~her function to ~odel
pass~ng~r irritation~ ~he Dirac ~el~a operator ensures
th~t the third term is zero ~here ~axPRT i not longer
than 60 s~conds.
T~is ~etric is used cur~tly in the objQctive
~nction in or~er tc allow the ~ilding awn~r to re~rt
~o ~he prior a~t RSR di~p~tchi~ methodology.
The v~lue of the RBR ~erm ~lected depend3 upon
whieh ~or~ of RSR is de~ired, as it ha~ many
modi~ica~ions. ~he b~ia compon~nt of tho RSR ~uantity
i5 the e~ti~ated a~ount o~ ti~e ~or a c~r to reach ~he
hal~ call whose assign~ent i5 bQi~g qeter~ined. The
valuo select~d, ho~ever, for the ~SR value may be ~ny o~
those shown in U~S. Pate~t 5,146,053 issued to Powell et
al entitl~d Elevator ~ispat~hing Based on Remainin~
Response ~im~; ~.S. Patent 4,3~3,381 issued to Bi~tar,
entitled Relative System Response Elevator Call
Assign~ænt~; U.S. Patent ~,~85,5~3 ~o Bi~tar en~itled
Weighted Relative System Rlevato~ Car Assignment System
with Varia~le Bonu~es and Penal~ies; U.5. Patent
~F'R 26 '94 10:5~ FRClr~ OTIS I~T PROP DEPT TO GOI~.ILING Chl`l~Df~ PRGE.~114/033
- 21%~69
4,7~2,g21 ~o MacDonald ~t al. entitled ~oin~ident Call
Optimization in an Elevator ~i~pa~ching Syste~5 ~.S.
Patent ~,202,540 is~ued to A~er antitled Two-way Ring
communicatio~ sy~tem ~or Ele~ator ~roup Control; U.S.
Patent 5,168,136 i6sued to Thangavelu ~t al en~itled
Lear~ing ~ethodology fo~ Improving ~ra~fic Prediction
Accuracy Or Elevator System ~sin~ Artificial
Intelligence; U.S. Paten~ ~,o~5,302 i~sue.d to
Thangavelu entitled Art~icia} lntelligence based
L~arni~g System Predicting Peak-Period Time4 ~or
Elevator Dispatching; U.S. Pa~nt 5,024,295 i~sued to
Thangavelu entitled Relative Sy~tem ~espon~e Elevator
Di~patc~er S~stem Using Artificial Intelligenc~ to ~ary
~onuses and Penal~ies; U.s. Patent 5,0~2,4g7 issued to
Thang~velu entitled Artificial Intclli~ence s~e~ C~owd
Sensing System for Elevdt~r Car Assignmenti and ~S.
Patent 4, 83R, 384 issued to ~hangavelu en~itled Q~ue
Based Elev~tor Di~patchinq System Using Pe.ak Period
Traffic Prediction, inc.orpora~ed by reference. Th~
~0 bonuses und penalt~es m~king up the RSR te~ c~n be
~aried or fixed.
Figu~ 5 i6 a ma~ter -flow cbart for lmplemQntin~
the method of the pr~sent invention. After a start, a
hall c~l1 at a floor N in a given direction is
2~ regi~ere~. Then, an el~ator dispatcher determines if
the hall call was pre~ou~ly ~ss~gned to a car and
records the car o~ the a~signment. ~ext, the remaining
respon~e time i5 calculated ~or each c~r in the bank and
the lowest remaining response t~me ~nd the car
associated with it is deter~ined.
A series of tests i~ now ex~c~ted to determin~ if
a hall call assign~ent algorith~ (Pig. ~) for
reassigning th~ call should be executed~ ~h~ rou~ines
of ~igures 5, 6 and 7 ~nGorpora~e the basic concsp~ of
- 12 -
.'.,' ~' ': ' ' " ''
;-' -: , :~ , ,
', ~ '':, ~,
.~: ~ ' '' . '' '~'':
.,:''` ' ' . :,'
".;. . : .,
~F:R 26 '44 1E) J8 FROI1 OrlS INT PROP DEPT TO GOWLII`IG Cfd`~FlDi~ P~GE.015/033
~22~S~
instantaneous car assignment in th~t the call is not
7-eassign~d unle6s there are s~rong incentiVa~ ~or doing
so; eve~ then, no more ~han one rea~ign~ent is allow~d,
The ~irst t~st ask~ "Is thi~ a new hall c~ll?n. If ~o,
co~pletion of the routine o~ Figure 5 ~ait~ for
exec~tion O~ the h~ll ca}l ~ssignment algorith~
illustrated in Figure 6. If not~ the ~ext three teqts
may ~e executed ~or determining w~ether ~he ~r~viously
as~i~ne~ call should be rea6si~ned. In te~t two, if the
remaining respon6e time of the assigned e]Le~ator is
greater than the lowest ra~aining response ti~e plus
seconds, execution of ~he routine-at Fi~ure 5 wait~
un~il execution of the hal~ ~all as6ign~ent algorith~
(Fig~ 6) for possible rea~ignment o~ the hall call to
another car. Thi~ test indicates that reassignment ~s
strong~y discouraged but i~ ~he re~aining respon~e tlm~
o~ the ~resent car is extremely poor with respec~ to the
lowest re~aining re~ponse timR then reassi~n~snt should
be Go~sidered~ Extrem~ly poor i~ d~fined by a ~ariable
pr~d1Gted re~i~tration time differe~ce, here 40. Th~
third and fourth test~ ~tall execution o~ the rou~in~ o~
Figuro 5 until the h~ll call a~signment algorithm ~
executed i~ th~ assigned ca~ ~s traveling awa~ ~rom the
as~igned call. None of these te~ts ~eing met in the
af~irmative, th~re is no re~sslgnmen~. .
~ig~re 6 lllustra~es th~ hall call as~ignment
algorithm. First, ~hQ rem~ini~g re~ponse ti~e ~lready
computed ~or the current ~et of a~;signmer~t:6 of ha~ 1
calls to cars i~ ~ead and used for computing th~
3n predicted registra~io~ ~ime (PRT) for all hall calls, by
adding th~ w~it time-so-far ~or e~c~ call to the
as~ociated remaining respon~e ti~. ~ext, a c~r index
~car i~ set to zero. The index is incremented by one
~or each c~r i~ the ~anX, and a m~lti-terc ob~eative
- 13 -
s~i
.:
~PR 26 '94 10:59 FROM OTIS INT PROP ~EPT TO GO~LING Cf~`lRDR P~GE.016~033
function is ~omputed for that car~ u~til ~11 cars ha~
be~n ~onsidered. Next, the car with the lowest
objective ~un~tion is d~termined and gi~en a label ~AR~
A series of tests is then exec~ted for dete~mlning
Whether there should be a r~a~ignment. ~hese thre~
tests are si~ilar to the ~our ~es~s o~ Figure 5 insofar
a~ their ~xecution infre~ently res~lts in reassign~ent
of a call out of deference tn insta~taneous c~r
a~ignmant. In the first te t, i~ the ha~l call is a
new one, then t~e hall call is assi~ned. If ~h~ hall
Gall is not a new call (test two~ ~nd ~he call has
alrea~y been switched once from t~e car of first
assign~n~, then ~he hall call i5 no~ reassi~ned. If
t~e call is not a ~aw one, then the predic~ed
registration time (PRT) of the a~sign~d car is comp~red
with the predicted re~ ration time ~PRT~ o~ the car,
~aR", wi~h th~ lowes~ object~ve function. If the
predlated registra~ion ti~e (PRT) o~' ~he ~6signed c~r is
~r greate~ t~an the predi~ed regist~ation ~imo o~ the
el~vator with the lowest objective ~unotiQrl, then t~e
hall call i~ r~n~lgned ~o the el~ator c~ ~RaR) Wi~h
the lowest objective ~unction, but otherwi~e~ no
reassignment occurs.
Figur~ 7 illustrates ca}culation of the multi-term
~5 objeati~e function. First, the ~it time-So-~ar ~or
e~ch hall call is ~tored a~d ~appe~ a~ainst th~
direction of that hall call. Next, the car ~or which
the ob~ecti~ function is being calculated is ass~m~d to
b~ igned to ~he call ~ein~ considered ~or
reassignment in t~e ~ater flow ch~rt routine, Thi~d,
~h~ remain~ng respo~se time (RRT)~ predi~ted
~gistration time (PR~, maximum predict~d registration
tim~ ~maxPRT), and the RSR value are c~lculat~d. The
valu~s for the four ter~ of ~he m~ erm obj~ativ¢
- 14 -
',:: . :
:.. , ' ' ~ ' . . ~
: ~,: . ., . ' . ,
hPR 26 '94 1~3:59 FRO~I OTIS INT PROP DEPT TO GOWLING Cf~ DFl Pf~GE.017/033
~ ' 2~C~2~)9
function ~re now calculated ~nd summ~d for producing the
~ult~-ter~ objecti~e function for use in the assign~nt
algorithm hall c~
Fi~ure ~ is a gra~ of the oPjectiYe function af
the ~rs i~ a bank; the car wi~h the mlni~l~m value o~
the obj~ctiYe ~unction (c~r B) is assigned ~o a hall
c~
Various chan~es may be made ~ithout departing ~ro~
the ~piri~ and soope of the inve~tion.
- 15 ~
, .
