# US 10,118,796 B2 · System and method for group elevator scheduling based on submodular optimization

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,118,796 B2
- Document ID: US10118796B2
- Status: Granted
- Kind: B2
- Application number: 15/448,644
- Filed: 2017-03-03
- Published: 2018-09-06
- Granted: 2018-11-06
- Earliest claimed: 2017-03-03
- Assignees: Mitsubishi Electric Research Laboratories, Inc.
- Applicants: Mitsubishi Electric Research Laboratories, Inc.
- Inventors: Daniel Nikolaev Nikovski; Arvind U Raghunathan; Srikumar Ramalingam
- Web page: https://patentgrep.com/patent/US10118796B2

## CPC

- B66B 1/2458: {For elevator systems with multiple shafts and a single car per shaft}
- B66B 1/2433: {For elevator systems with a single shaft and multiple cars}
- B66B 2201/00: Aspects of control systems of elevators
- B66B 2201/20: Details of the evaluation method for the allocation of a call to an elevator car
- B66B 2201/211: Waiting time, i.e. response time
- B66B: ELEVATORS; ESCALATORS OR MOVING WALKWAYS ({apparatus for raising or lowering persons on theatrical stages or the like A63J5/12} ; funicular railbound systems with rigid ground-supported tracks and cable traction, e.g. cliff railways, B61B9/00; arrangements of ammunition handlers in vessels B63G3/00; hoists, lifts, or conveyors for loading or unloading in general B65G; braking or detent devices controlling normal movements of winding drums or barrels B66D; ship-lifting devices E02C; garages for many vehicles with mechanical means for lifting vehicles E04H6/12; hoists for feeding ammunition or projectiles to launching apparatus or to loading mechanisms F41A9/00)

## Abstract

Systems and Methods for controlling a movement of cars of an elevator system. A processor determines for each car an individual waiting time of each hall call. Determines for each pair of hall calls assigned for each car, a pairwise delay over the individual waiting time of each hall call in the pair caused by a joint assignment of the car to the pair of the hall calls. Approximate a cumulative waiting time of an assignment of the cars to the hall calls as a sum of individual waiting times for each hall call with the assigned car and a sum of all pairwise delays determined between all pairs of hall calls assigned to the same car. Determine the assignment of the cars using a greedy optimization algorithm that greedily assigns hall calls to the cars to minimize the approximated cumulative waiting time, and control the movement of the cars.

## Claims

### Claim 1

A system for controlling a movement of a plurality of elevator cars of an elevator system, comprising:
at least one input interface for accepting a plurality of hall calls requesting service of the plurality of elevator cars to different floors of a building;
a processor in communication with the input interface is configured to
determine, for each elevator car, an individual waiting time of accommodating each hall call, if the hall call is the only hall call assigned to the elevator car;
determine, for each pair of hall calls assigned to each elevator car, a pairwise delay over the individual waiting time of each hall call in the pair caused by a joint assignment of the elevator car to accommodate the pair of the hall calls;
approximate a cumulative waiting time of an assignment of the plurality of elevator cars to accommodate the plurality of hall calls as a sum of individual waiting times for accommodating each hall call with the assigned elevator car, and a sum of all pairwise delays determined between all pairs of hall calls assigned to the same elevator car; and
determine the assignment of the plurality of elevator cars using a greedy optimization algorithm that greedily assigns the plurality of hall calls to the plurality of elevator cars to minimize the approximated cumulative waiting time; and
a controller for controlling the movement of the plurality of elevator cars according to the assignment.

### Claim 2 (depends on 1)

The system of claim 1, wherein the greedy optimization algorithm is an algorithmic paradigm that determines at an initial step, an assignment of an unassigned first hall call, based on a locally optimal choice determined at a time of the initial step, then proceeds to the next step or the next successive unassigned hall call.

### Claim 3 (depends on 2)

The system of claim 2, wherein the locally optimal choice identifies at each step, a combination of an unassigned hall call from all the remaining unassigned hall calls and an elevator car from the plurality of elevator cars, that results in a least increase in a waiting time for all assigned hall calls including the first hall call, while considering all previous assigned hall calls, then the combination is accepted and the hall call is assigned without further consideration and removed from all the remaining unassigned hall calls.

### Claim 4 (depends on 1)

The system of claim 1, wherein the greedy optimization algorithm starts with an empty set of assignments of hall calls needing to be assigned, such that at every step including an initial step which starts with a first hall call, is added to the set of assignments of hall calls needing to be assigned, so as to result in a total of N steps, until all unassigned hall calls are assigned.

### Claim 5 (depends on 4)

The system of claim 4, wherein each step in the total of N steps includes a hall call for every passenger to be moved between floors of the building, such that during each step, an unassigned hall call from a passenger is considered sequentially in time, and is initially added to an elevator car of the plurality of elevator cars successively.

### Claim 6 (depends on 5)

The system of claim 5, wherein for every combination of the hall call and the elevator car, the greedy optimization algorithm computes a cumulative waiting time of all hall calls assigned at that moment in time, plus the first hall call assigned at the initial step.

### Claim 7 (depends on 6)

The system of claim 6, wherein the hall call and the elevator car combination having a least increase in the cumulative waiting time for all assigned hall calls including the first hall call of the initial step, the combination is accepted, and the hall call is assigned and removed from all the remaining unassigned hall calls, then continues to the next step or the next successive unassigned hall call.

### Claim 8 (depends on 1)

The system of claim 1, wherein the greedy optimization algorithm is based on optimizing the approximated cumulative waiting time in N steps, where N is a number of unassigned hall calls from passengers waiting to be assigned at a time at each step, such that two sets of coefficients are computed to construct a quadratic Boolean approximation of the cumulative waiting time of all the plurality of hall calls from passengers currently waiting to be assigned at the time of that step.

### Claim 9 (depends on 8)

The system of claim 8, wherein the first set of coefficients of the two sets of coefficients includes wic, such that wic is a linear coefficient that is an expected waiting time of a hall call from a passenger hi, if the hall call is picked by an elevator car c, and no other hall call is picked up by that elevator car.

### Claim 10 (depends on 1)

The system of claim 1, wherein the second set of coefficients of the two sets of coefficients includes wijc, such that wijc is a bilinear coefficient that is equal to the pairwise delay between hall calls from passengers hi and hj, based on a specific pick-up order of the two hall calls by the elevator car c, such that only one of the two hall calls is causing a delay to the other hall call, and the hall call that is picked-up first causes a delay for the hall call that is picked-up second.

### Claim 11

A method for scheduling elevator cars of an elevator system, comprising:
using at least one input interface for accepting a plurality of hall calls requesting the plurality of elevator cars to different floors of a building;
determining independently, using a processor in communication with the input interface, for each elevator car, an independent waiting time of accommodating each hall call, if the hall call is the only hall call assigned to the elevator car;
determining, for each pair of hall calls assigned for each elevator car, a pairwise delay over the individual waiting time of each hall call in the pair caused by a joint assignment of the elevator car to accommodate the pair of the hall calls;
approximating a cumulative waiting time of an assignment of the plurality of elevator cars to accommodate the plurality of hall calls as a sum of individual waiting times for accommodating each hall call with the assigned elevator car and a sum of all pairwise delays determined for the assigned elevator car between all pairs of hall calls assigned to the same elevator car;
determining the assignment of the plurality of elevator cars using a greedy optimization algorithm that greedily assigns the plurality of hall calls to the plurality of elevator cars to minimize the approximated cumulative waiting time; and
using a controller for controlling the movement of the plurality of elevator cars according to the assignment.

### Claim 12 (depends on 11)

The method of claim 11, wherein the greedy optimization algorithm is an algorithmic paradigm that determines at an initial step, an assignment of an unassigned first hall call, based on a locally optimal choice determined at a time of the initial step, then proceeds to the next step or the next successive unassigned hall call.

### Claim 13 (depends on 11)

The method of claim 11, wherein the cumulative waiting time is determined according to
Q
⁡
(
x
)
⁢
B
⁢
∑
i
=
1
N
⁢
∑
c
=
1
C
⁢
w
i
c
⁢
x
i
c
+
∑
i
=
1
N
⁢
∑
j
=
i
+
1
N
⁢
∑
c
=
1
C
⁢
w
ij
c
⁢
x
i
c
⁢
x
j
c
,
where is an indicator variable which takes on a value of 1 when the hall call from the passenger i is assigned to the elevator car c, and 0 otherwise, and that all N·C indicator variables are collected in a decision vector x=[x11, x21, . . . , xN1, x12, x22, . . . , xN2, . . . , x1C, x2C, . . . , xNC].

### Claim 14 (depends on 11)

The method of claim 11, wherein the greedy optimization algorithm has complexity O(CN2) , that is, linear in a number of elevator cars C and quadratic in a number of hall calls by passengers N, and leverages a property of submodularity of an objective function.

### Claim 15 (depends on 14)

The method of claim 14, wherein for each step, all remaining unassigned hall calls by passengers are considered sequentially in time, and are initially added to each elevator car successively, and for every combination of a hall call and an elevator car, the SPD of all hall calls assigned, plus the new hall call assigned at the initial step are then calculated, and any combination of the hall call initially added with the elevator car that increases the SPD least, then the hall call is assigned to that elevator car, and removed all the remaining unassigned hall calls, and then continues to the next step.

### Claim 16

A non-transitory computer readable storage medium embodied thereon a program executable by a computer for performing a method, the method for scheduling elevator cars of an elevator system, the elevator system including a plurality of elevator cars, and a plurality of hall calls, comprising:
using at least one input interface for accepting a plurality of hall calls requesting the plurality of elevator cars to different floors of a building;
determining independently, using a process in communication with the input interface, for each elevator car, an independent waiting time of accommodating each hall call, if the hall call is the only hall call assigned to the elevator car;
determining, for each pair of hall calls assigned for each elevator car, a pairwise delay over the individual waiting time of each hall call in the pair caused by a joint assignment of the elevator car to accommodate the pair of the hall calls;
approximating a cumulative waiting time of an assignment of the plurality of elevator cars to accommodate the plurality of hall calls as a sum of individual waiting times for accommodating each hall call with the assigned elevator car and a sum of all pairwise delays determined for the assigned elevator car between all pairs of hall calls assigned to the same elevator car;
determining the assignment of the plurality of elevator cars using a greedy optimization algorithm that greedily assigns the plurality of hall calls to the plurality of elevator cars to minimize the approximated cumulative waiting time; and
using a controller for controlling the movement of the plurality of elevator cars according to the assignment.

### Claim 17 (depends on 16)

The method of claim 16, wherein the greedy optimization algorithm starts with an empty set of assignments of hall calls needing to be assigned, such that at every step including an initial step which starts with a first hall call, is added to the set of assignments of hall calls needing to be assigned, so as to result in a total of N steps, until all unassigned hall calls are assigned.

### Claim 18 (depends on 17)

The method of claim 17, wherein each step in the total of N steps includes a hall call for every passenger to be moved between floors of the building, such that during each step, an unassigned hall call from a passenger is considered sequentially in time, and is initially added to an elevator car of the plurality of elevator cars successively.

### Claim 19 (depends on 18)

The method of claim 18, wherein for every combination of the hall call and the elevator car, the greedy optimization algorithm computes a cumulative waiting time of all hall calls assigned at that moment in time, plus the first hall call assigned at the initial step.

### Claim 20 (depends on 19)

The method of claim 19, wherein the hall call and the elevator car combination having a least increase in the cumulative waiting time for all assigned hall calls including the first hall call of the initial step, the combination is accepted, and the hall call is assigned and removed from all the remaining unassigned hall calls, then continues to the next step or the next successive unassigned hall call.