TR2003-61

Decision-Theoretic Group Elevator Scheduling


Abstract:

We present an efficient algorithm for exact calculation and minimization of expected waiting times of all passengers using a bank of elevators. The dynamics of the system are represented by a discrete-state Markov chain embedded in the continuous phase-space diagram of a moving elevator car. The chain is evaluated efficiently using dynamic programming to compute measures of future system performance such as expected waiting time, properly averaged over all possible future scenarios. An elevator group scheduler based on this method significantly outperforms a conventional algorithm based on minimization of proxy criteria such as the time needed for all cars to complete their assigned deliveries. For a wide variety of buildings, ranging from 8 to 30 floors, and with 2 to 8 shafts, our algorithm reduces waiting times up to 70% in heavy traffic, and exhibits an average waiting-time speed-up of 20% in a test set of 20,000 building types and traffic patterns. While the algorithm has greater computational costs than most conventional algorithms, it is linear in the size of the building and number of shafts, and quadratic in the number of passengers, and is completely within the computational capabilities of currently existing elevator bank control systems.

 

  • Related News & Events

    •  NEWS    ICAPS 2003: 2 publications by Matthew Brand and Daniel Nikovski
      Date: June 9, 2003
      Where: International Conference on Automated Planning and Scheduling (ICAPS)
      MERL Contacts: Matthew Brand; Daniel N. Nikovski
      Brief
      • The papers "Decision-Theoretic Group Elevator Scheduling" by Nikovski, D. and Brand, M. and "Non-Linear Stochastic Control in Continuous State Spaces by Exact Integration in Bellman\'s Equations" by Nikovski, D. and Brand, M. were presented at the International Conference on Automated Planning and Scheduling (ICAPS).
    •