Real-time algorithms for the bilevel double-deck elevator dispatching problem

Double-deck elevators consist of two elevator cars attached together and, thus, save building core space. In the destination control system (DCS), passengers register their destination floors in the elevator lobbies. In return, the DCS immediately assigns an elevator to each transportation request and signals it to the passenger. Based on the additional information, the DCS is able to increase handling capacity under incoming traffic conditions. However, the double-deck DCS does not yet function optimally in mixed lunch traffic, which consists of incoming, outgoing and interfloor traffic. In this paper, the double-deck DCS is further developed by introducing delayed elevator and deck assignments. With the delayed assignments, the serving elevator or deck of each request can be reassigned to another elevator or deck until the last moment. Such a double-deck DCS can better adapt to emerging requests and, as a result, can improve passenger service quality in lunch traffic dramatically. To enable real-time optimization in an elevator group control system, this paper formulates the double-deck elevator dispatching problem as a bilevel optimization problem and solves the problem fast with a genetic algorithm. Numerical experiments show that the bilevel algorithm outperforms the earlier single-level algorithm in both solution quality and computation times.