Routing optimization in a multi-deck elevator

Abstract

A method for a passenger-allocation in a multi-deck elevator group where the decks of the elevator cars are stacked above each other and being mounted in a car frame to be moved synchronously in an elevator shaft utilizes an improved allocation strategy. The method is performed by a control unit to dispatch the elevator cars for serving any passenger call which can be entered as a landing call or a car call, wherein a call creates plural allocation proposals calculated by an optimization algorithm carried out by the control unit for dispatching an elevator to a passenger call. The allocation proposals are then processed in a routing algorithm defining one serving deck to be taken for the allocation of a specific call, which routing algorithm is restarted for any further incoming call independent of whether a further incoming call is creating new elevator allocation proposal(s) or when a reallocation timeout has passed. A computer program carrying out the method is further disclosed.

Claims

1. A method for passenger-allocation in a multi-deck elevator group, the decks of each elevator defining elevator cars, respectively, and being stacked above each other and mounted in a car frame to move synchronously in an elevator shaft, the method being performed by a control unit to dispatch the elevator cars for serving a passenger call, the method comprising: creating plural allocation proposals calculated by means of an optimization algorithm carried out by the control unit for dispatching an elevator to a passenger call, processing the allocation proposals in a routing algorithm defining a serving deck to be allocated to a specific passenger call; and rerunning the routing algorithm for any further incoming call or when a reallocation timeout has passed.

2. The method according to claim 1, wherein the routing algorithm is restarted for any further incoming call until a defined distance from the call floor is reached.

3. The method according to claim 2, wherein said defined distance is defined as the point when the elevator begins to decelerate for serving a call.

4. The method according to one of claims 1 to 3, wherein the routing algorithm decides the serving deck to be allocated to a call according to at least one of the following rules: minimizing a number of elevator stops, minimizing a load difference between the decks of the elevator, selecting the deck of the elevator with smaller load, arbitrarily choosing either leading or trailing deck of the elevator.

5. A method for passenger-allocation in a multi-deck elevator group, the decks of each elevator defining elevator cars, respectively, and being stacked above each other and mounted in a car frame to move synchronously in an elevator shaft, the method being performed by a control unit to dispatch the elevator cars for serving a passenger call, the method comprising: creating plural allocation proposals calculated by means of an optimization algorithm carried out by the control unit for dispatching an elevator to a passenger call, processing the allocation proposals in a routing algorithm defining a serving deck to be allocated to a specific passenger call; and rerunning the routing algorithm for any further incoming call or when a reallocation timeout has passed; wherein the routing algorithm decides the serving deck to be allocated to a call according to at least one of the following rules: minimizing a number of elevator stops, minimizing a load difference between the decks of the elevator, selecting the deck of the elevator with smaller load, arbitrarily choosing either leading or trailing deck of the elevator; and wherein the rules are hierarchically ordered in the sequence of first minimizing number of stops, then minimizing load difference between the decks.

6. The method according to claim 1, wherein the optimization algorithm is an integer optimization algorithm, especially a genetic algorithm.

7. The method according to claim 1, wherein the routing algorithm is an integer optimization algorithm, especially a genetic algorithm.

8. The method according to claim 1, wherein the method considers passenger transfers on the call floors and loads of the decks after each stop to minimize the number of stops and balance the load between the decks for one elevator trip at a time.

9. In a method for passenger-allocation in a multi-deck elevator group, the decks of each elevator defining elevator cars, respectively, and being stacked above each other and mounted in a car frame to move synchronously in an elevator shaft, the method being performed by a control unit to dispatch the elevator cars for serving a passenger call, a computer readable medium fixed in a tangible medium, the computer readable medium when executed on a computer performing: creating plural allocation proposals calculated by means of an optimization algorithm carried out by the control unit for dispatching an elevator to a passenger call, processing the allocation proposals in a routing algorithm defining a serving deck to be allocated to a specific passenger call; and rerunning the routing algorithm for any further incoming call or when a reallocation timeout has passed.

10. The method according to claim 2, wherein the optimization algorithm is an integer optimization algorithm, especially a genetic algorithm.

11. The method according to claim 3, wherein the optimization algorithm is an integer optimization algorithm, especially a genetic algorithm.

12. The method according to claim 4, wherein the optimization algorithm is an integer optimization algorithm, especially a genetic algorithm.

13. The method according to claim 5, wherein the optimization algorithm is an integer optimization algorithm, especially a genetic algorithm.

14. The method according to claim 2, wherein the routing algorithm is an integer optimization algorithm, especially a genetic algorithm.

15. The method according to claim 3, wherein the routing algorithm is an integer optimization algorithm, especially a genetic algorithm.

16. The method of claim 1 wherein the step of creating allocation proposals occurs once at the time of each elevator call; the processing of said allocation proposals being performed after said creating and being rerun in said rerunning step as a result of further incoming calls.

17. The computer readable medium of claim 9 wherein the step of creating allocation proposals occurs once at the time of each elevator call; the processing of said allocation proposals being performed after said creating and being rerun in said rerunning step as a result of further incoming calls.

Description

(1) In the following the invention is described by the aid of a double-deck-elevator example, which is displayed schematically in FIG. 1.

(2) The concept of the double-deck elevator dispatching problem for conventional control is demonstrated by a numerical example to clarify the differences between the formulations of the deck-assignment problem of prior art and the inventive one of an elevator assignment problem. In FIG. 1, a simplified example is given, meaning a group of one double-deck elevator 10 having first and second decks 10a, 10b which will have to serve two passengers. Another double-deck elevator 11 is further illustrated.

(3) FIG. 1 shows that initially, there is one passenger travelling in deck 1 (=lower deck) having registered a car call to floor 5 (circle) and one passenger waiting behind an up call at floor 5 (triangle upwards). The two possible routes to serve the passengers and the resulting stopping floors of deck 1 are shown titled with Route 1 and Route 2 depicting two possible ways to serve the up call. In the case of Route 1, the elevator first stops its upper deck to serve the up call at floor 5 (F5UP) and only after that the lower deck to serve the car call at floor 5 (F5CC). In the case of Route 2, only the lower deck is stopped at floor 5 to serve both the up and the car call at the same time. The arrows in the FIGURE depict movements of the elevator. Run times between the calls, including a 10-second stop time at floor 5, are shown beside the arrows. The table shows details of the calls including the artificial ones, elevator initial position (INI) and reversal floor (REV).

(4) TABLE-US-00001 TABLE Direction Passengers Serving deck Call Floor .sub.i .sub.i .sub.i y.sub.i INI 1 1 1 1 F5UP 5 1 1 1 or 2 F5CC 5 1 1 1 REV 7 or 8 1 1 1 or 2

(5) After the routes of the elevators have been created for the given assignment combination by the elevator selection algorithm 16, the quality of the assignment can be evaluated by an objective function such as passenger waiting- and journey-time. Since an elevator group is a service system, the global objective needs to be passenger-based (or call-based). However, it is possible to consider also other objectives, especially in the case of double-deck elevators, which evaluate the quality of the elevator routes locally. Such local objectives are, for example: 1) elevator travel time or distance, 2) number of stops, 3) number of coincident stops where more than one call is served, and 4) number of stops with only the other deck serving, i.e. there are passengers inside the deck but it does not serve any calls during a stop.

(6) The table below shows the values of each of the above-mentioned objectives for Route 1 and 2 of the example.

(7) TABLE-US-00002 Objective Route 1 Route 2 Passenger Waiting Time (s) 8 9 Passenger Journey Time (s) 62 34 Elevator Travel Time (s) 39 25 Number of Stops 3 2 Number of Coincident Stops 0 1 Stops with Other Deck Serving 2 0

(8) Consider first the global objectives, passenger waiting- and journey-time: Route 1 minimizes waiting time but Route 2 minimizes journey time with a marginal increase in waiting time. When looking at the local objectives, Route 2 is better than Route 1 in every measure. Which of the routes should be preferred? By experience, it is known that minimization of journey times results in significantly longer waiting times, which is not visible in this simple example. Naturally, prolonged waiting times are not desirable but Route 1 is clearly inefficient and therefore not desirable.

(9) Consider again the example of FIG. 1 but now as the elevator-assignment-problem formulation. For the assignment, there is nothing to decide when the person in the lobby is the first entering a call, since there is only one convenient elevator-car in the group. Since the car call in the lobby already has a fixed serving deck, the car is selected and will not be changed later on.

(10) If however the person in the fifth floor first enters his call, the elevator and the deck are assigned. The deck assignment can be deck 1 or deck 2. If it is the upper deck 2 being assigned, this deck will be re-assigned in case the person in the lobby enters his call for reaching the 5.sup.th floor. If however it is deck 1 which had been allocated to the person in the 5.sup.th floor, a reconsideration of the assigned deck will lead to no change and it is still deck 1 serving both.

(11) In the following an algorithm is proposed as an example for the routing algorithm 17, i.e. for allocating and reconsidering the serving deck after having allocated the elevator:

(12) TABLE-US-00003 Data: calls i V.sub.e of elevator e Result: elevator route R.sub.e and serving deck y.sub.e for i V.sub.c if W.sub.k is not empty then |set W.sub.k.sup.main := arg min.sub.iW.sub.k {|.sub.n.sub.k .sub.i|}; |set W.sub.k.sup.main fixed := {i W.sub.k.sup.min |y.sub.i cannot be changed }; |if W.sub.k.sup.main fixed is not empty then ||set n.sub.k+1 := argmax.sub.iWk.sup.main fixed {.sub.cy.sub.i}; |else ||set n.sub.k+1 := any i W.sub.k.sup.min; ||if n.sub.k+1 is coincident with n.sub.k then |||set y.sub.n.sub.k+1 := y.sub.n.sub.k + .sub.n.sub.k+1 .sub.n.sub.k; ||else if .sub.i V.sub.c.sup.fixed ahead of and coincident with n.sub.k+1 then |||set y.sub.n.sub.k+1 := y.sub.i+ .sub.n.sub.k+1 .sub.i; ||else if .sub.i V.sub.c ahead of n.sub.k+1 and .sub.n.sub.k+1 = .sub.i then |||set y.sub.n.sub.k+1 := |min.sub.d{i,2}.sub.n.sub.k+1 d|; ||else if .sub.i V.sub.e ahead of and coincident with n.sub.k+i then |||set y.sub.n.sub.k+1 := |.sub.n.sub.k+1 .sub.i| |min.sub.d(1,2) .sub.n.sub.k+1 d|; ||else if q.sub.e1n.sub.k q.sub.e2n.sub.k then |||set y.sub.n.sub.k+1 := argmin.sub.d(1,2) q.sub.edn.sub.k; ||else |||set y.sub.n.sub.k+1 := |max.sub.d(1,2) .sub.n.sub.k+1 d|; ||end |end