Gradually resolving procedures by a trip-based integer programming to optimize elevator operations

In this paper, we propose an integer programming formalization to optimize elevator operations under such an ideal condition that all information on passengers who arrive during the planning period is known in advance. The basic idea which inspired the formalization is the concept of trip, which represents a uni-directional (upward or downward) movement of an elevator and forms a trajectory of an elevator with other trips. In the formalization, all elevators are alloted to equal number of trips, and a passenger is assigned to one of trips of the same direction to that passenger. The number of necessary trips is unknown without an optimal schedule, whereas an optimal schedule can not be obtained without that number. This complication is straightforwardly solved by the incrementally resolving procedure by which the number of available trips starts with two and is incremented by two until an increment does not yield a more effective schedule. A supposition on the working of that procedure leads to the gradually resolving procedure, which restricts possible trips of passengers within neighborhoods of trips which are optimal under a fewer number of available trips. In computer illustrations, some problems which differ in numbers of elevators, passengers, and traffic patterns are considered. A certain number of embodied problem instances are generated for each problem, and an optimal schedule is obtained for each problem instance. Computational results display that the number of available trips seems to primarily affect computational costs, and a problem with multiple elevators can be easier as expected since such a problem does not require so many trips in usual. Additionally, the effectiveness of the gradually resolving procedure is shown as it yields schedules optimal in most cases within radically shorter computational times.