System and method for group elevator scheduling based on submodular optimization

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.

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.