System and method for scheduling elevator cars using branch-and-bound
View Patent ↗A method schedules cars of an elevator system. Each possible assignment of a set of hall calls to a set of cars is represented by a solution vector maintained as a node in a search tree. Each solution vector is evaluated using an ESA-DP process according to an immediate policy to determine initially a best solution. A branch-and-bound process is applied to each solution vector using the initial best solution and the search tree to determine a globally optimal solution for scheduling the cars according to a reassignment policy.
1. A method for scheduling cars of an elevator system, comprising the steps of:
representing each possible assignment of a set of hall calls to a set of cars by a solution vector maintained as a node in a search tree;
evaluating each solution vector using an ESA-DP process according to an immediate policy to determine initially a best solution; and
applying a branch-and-bound process to each solution vector using the initial best solution and the search tree to determine a globally optimal solution for scheduling the cars according to an reassignment policy.
2. The method of claim 1 , in which the search tree includes a top level root node representing all possible assignments, intermediate parent and child nodes representing partial assignments, and bottom level leaf nodes representing complete assignments.
3. The method of claim 1 , in which each solution vector is (c 1 , c 2 , . . . , c n ), where c i a particular one of m cars and n is the number hall calls, and further comprising:
assigning, to the particular car c i , a value in a range 1≦c i ≦m for assigned hall calls, and −1 for unassigned hall calls.
4. The method of claim 2 , further comprising:
partitioning the set of hall calls into m distinct subsets {H 1 , H 2 , . . . , H m }, such that H i ∩H j =Ø, for i≠j, and for ∪ i=1 m H i =H, wherein m is the number of cars c;
determining an expectation of an average waiting time by minimizing an objective function F
F
(
{
H
1
,
H
2
,
…
,
H
m
}
)
:=
∑
c
=
1
m
∑
h
∈
H
W
c
(
h
|
H
i
)
,
when the solution vector is represented by a leaf node to determine a current solution; and
replacing the best solution with the current solution.
5. The method of claim 4 , further comprising:
determining a lower bound for the current solution;
discarding the leaf node if the lower bound exceeds the best solution; and otherwise
generating m child nodes from leaf node.
6. The method of claim 1 , further comprising:
sorting the assignments of the hall calls to the cars in a first-to-last order according to distances to floors originating the hall calls.
7. The method of claim 1 , in which an intrinsic order in which the set of hall calls are assigned to a particular car depends on a direction of travel of the particular car.
8. The method of claim 4 , in which the nodes of the search tree are processed in a top-to-bottom order, and the expectation of the average waiting time is determined incrementally while descending the search tree.
9. The method of claim 1 , further comprising:
pruning substantial portions of the search tree using a tight bound which is substantially close to the globally optimal solution.