System and method for group elevator scheduling based on submodular optimization

Patent metadata

Field	Value
Publication number	US-10118796-B2
Application number	US-201715448644-A
Country	US
Kind code	B2
Filing date	Mar 3, 2017
Priority date	Mar 3, 2017
Publication date	Nov 6, 2018
Grant date	Nov 6, 2018

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.

First claim

What is claimed is:

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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

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

10. The system of claim 1 , wherein the second set of coefficients of the two sets of coefficients includes w ij c , such that w ij c is a bilinear coefficient that is equal to the pairwise delay between hall calls from passengers h i and h j , 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.

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.

12. 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.

13. The method of claim 11 , wherein the cumulative waiting time is determined according to

Q
⁡

(
x
)

⁢
B
⁢

∑

i
=
1

N

⁢

∑

Assignees

• Mitsubishi Electric Res Laboratories Inc

Inventors

• Nikovski Daniel Nikolaev
• Raghunathan Arvind U
• Ramalingam Srikumar

Classifications

• B66B1/2458 Primary

  For elevator systems with multiple shafts and a single car per shaft · CPC title

• B66B2201/20

  Details of the evaluation method for the allocation of a call to an elevator car · CPC title

• B66B2201/34

  Operations & Transport · mapped topic

• B66B1/2433

  For elevator systems with a single shaft and multiple cars · CPC title

• B66B2201/211

  Waiting time, i.e. response time · CPC title