TR2017-079

Submodular Function Maximization for Group Elevator Scheduling


    •  Ramalingam, S., Raghunathan, A.U., Nikovski, D.N., "Submodular Function Maximization for Group Elevator Scheduling", International Conference on Automated Planning and Scheduling (ICAPS), June 2017.
      BibTeX TR2017-079 PDF
      • @inproceedings{Ramalingam2017jun,
      • author = {Ramalingam, Srikumar and Raghunathan, Arvind and Nikovski, Daniel N.},
      • title = {Submodular Function Maximization for Group Elevator Scheduling},
      • booktitle = {International Conference on Automated Planning and Scheduling (ICAPS)},
      • year = 2017,
      • month = jun,
      • url = {https://www.merl.com/publications/TR2017-079}
      • }
  • MERL Contacts:
  • Research Areas:

    Data Analytics, Optimization

Abstract:

We propose a novel approach for group elevator scheduling by formulating it as the maximization of submodular function under a matroid constraint. In particular, we propose to model the total waiting time of passengers using a quadratic Boolean function. The unary and pairwise terms in the function denote the waiting time for single and pairwise allocation of passengers to elevators, respectively. We show that this objective function is submodular. The matroid constraints ensure that every passenger is allocated to exactly one elevator. We use a greedy algorithm to maximize the submodular objective function, and derive provable guarantees on the optimality of the solution. We tested our algorithm using Elevate 8, a commercialgrade elevator simulator that allows simulation with a wide range of elevator settings. We achieve significant improvement over the existing algorithms.