Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Modeling uncertain passenger arrivals in the elevator dispatching problem with destination control

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

An Elevator Group Control System (EGCS) assigns an elevator of a group to each passenger transportation request by solving a snapshot optimization problem, the Elevator Dispatching Problem (EDP). In the destination control, passengers register their destination floors in the elevator lobbies, after which the EGCS completes the assignment at once and is not allowed to change it later. Therefore, the EDP is formulated as a stochastic optimal control problem, where uncertain future passenger arrivals are modeled by a Poisson and a geometric Poisson process. The EDP is considered as a certainty equivalent controller in which the uncertain quantities are replaced by their expected values, and as a robust controller in which they take multiple values according to risk scenarios. Numerical experiments show that the expectations do not accurately predict EDP variables. The modeling with the geometric Poisson process results in better forecasting accuracy than with the Poisson process and many scenarios that closely match the realizations of the variables. Hence, the scenarios can be used as a basis for a robust EDP which simultaneously minimizes a passenger service quality criterion and its variation due to uncertain demand.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Alexandris, N.: Statistical models in lift systems. Ph.D. thesis, The Victoria University of Manchester, Institute of Science and Technology (1977)

  2. Alizadeh, S., Marcotte, P., Savard, G.: Two-stage stochastic bilevel programming over a transportation network. Transp. Res. B Meth. 58(1), 92–105 (2013)

    Article  Google Scholar 

  3. Audestad, J.A., Gaivoronski, A., Werner, A.: Extending the stochastic programming framework for the modeling of several decision makers: pricing and competition in the telecommunication sector. Ann. Oper. Res. 142(1), 19–39 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  4. Barney, G.: Elevator Traffic Handbook. Spon Press, London (2003)

    Book  Google Scholar 

  5. Bertsekas, D.: Dynamic Programming and Optimal Control, vol. I, 3rd edn. Athena Scientific, Belmont, MA (2005)

    MATH  Google Scholar 

  6. Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52(1), 35–53 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  7. Closs, G.: The computer control of passenger traffic in large lift systems. Ph.D. thesis, The Victoria University of Manchester, Institute of Science and Technology (1970)

  8. Fernández, J., Cortés, P.: A survey of elevator group control systems for vertical transportation: a look at recent literature. IEEE Contr. Syst. Mag. 35(4), 38–55 (2015)

    Article  Google Scholar 

  9. Fisher, M., Jaikumar, R.: A generalized assignment heuristic for vehicle routing. Networks 11(2), 109–124 (1981)

    Article  MathSciNet  Google Scholar 

  10. Galliher, H., Morse, P., Simond, M.: Dynamics of two classes of continuous-review inventory systems. Oper. Res. 7(3), 362–384 (1959)

    Article  MathSciNet  Google Scholar 

  11. Gendreau, M., Laporte, G., Séguin, R.: Stochastic vehicle routing. Eur. J. Oper. Res. 88(1), 3–12 (1996)

    Article  MATH  Google Scholar 

  12. Hiller, B., Klug, T., Tuchscherer, A.: An exact reoptimization algorithm for the scheduling of elevator groups. Flex. Serv. Manuf. J. 26(4), 585–608 (2014)

    Article  Google Scholar 

  13. Inamoto, T., Tamaki, H., Murao, H., Kitamura, S.: An application of branch-and-bound method to deterministic optimization model of elevator operation problems. In: SICE 2002. Proceedings of the 41st SICE Annual Conference, vol. 2, pp. 987–992 (2002)

  14. Johnson, N., Kemp, A., Kotz, S.: Univariate Discrete Distributions, 3rd edn. John Wiley & Sons Inc, Hoboken, New Jersey (2005)

    Book  MATH  Google Scholar 

  15. Koehler, J., Ottiger, D.: An AI-based approach to destination control in elevators. AI Mag. 23(3), 59–78 (2002)

    Google Scholar 

  16. Kosuch, S., Le Bodic, P., Leung, J., Lisser, A.: On a stochastic bilevel programming problem. Networks 59(1), 107–116 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  17. Kuusinen, J-M., Sorsa, J., Siikonen, M-L.: The elevator trip origin-destination matrix estimation problem. Transp. Sci. 49(3), 559–576 (2015)

  18. Kuusinen, J-M., Sorsa, J., Siikonen, M-L., Ehtamo, H.: A study on the arrival process of lift passengers in a multi-storey office building. Build. Serv. Eng. Res. Technol. 33(4), 437–449 (2012)

  19. Luh, P., Chang, T., Ning, T.: Pricing problems with a continuum of customers as stochastic Stackelberg games. J. Optim. Theory Appl. 55(1), 119–131 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  20. Luh, P., Xiong, B., Chang, S.C.: Group elevator scheduling with advance information for normal and emergency modes. IEEE Trans. Autom. Sci. Eng. 5(2), 245–258 (2008)

    Article  Google Scholar 

  21. Ma, Y., Xu, J.: Vehicle routing problem with multiple decision-makers for construction material transportation in a fuzzy random environment. Int. J. Civ. Eng. 12(2), 331–345 (2014)

    Google Scholar 

  22. Marinakis, Y., Migdalas, A., Pardalos, P.: A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm. J. Glob. Optim. 38(4), 555–580 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  23. Mulvey, J., Vanderbei, R., Zenios, S.: Robust optimization of large-scale systems. Oper. Res. 43(2), 264–281 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  24. Nikovski, D., Brand, M.: Marginalizing out future passengers in group elevator control. In: Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence, pp. 443–450. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2003)

  25. Patriksson, M., Wynter, L.: Stochastic mathematical programs with equilibrium constraints. Oper. Res. Lett. 25(4), 159–167 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  26. Pepyne, D., Cassandras, C.: Optimal dispatching control for elevator systems during uppeak traffic. IEEE Trans. Contr. Syst. Technol. 5(6), 629–643 (1997)

    Article  Google Scholar 

  27. Ruokokoski, M., Ehtamo, H., Pardalos, P.: Elevator dispatching problem: a mixed integer linear programming formulation and polyhedral results. J. Comb. Optim. 29(4), 750–780 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  28. Ruokokoski, M., Sorsa, J., Siikonen, M-L., Ehtamo, H.: Assignment formulation for the Elevator Dispatching Problem with destination control and its performance analysis. Eur. J. Oper. Res. 252(2), 397–406 (2016)

  29. Schröder, J.: Advanced dispatching – destination hall calls + instant car-to-call assignment: “M-10”. Elev. World 38(3), 40–46 (1990)

    Google Scholar 

  30. Shimizu, K., Ishizuka, Y., Bard, J.: Nondifferentiable and Two-Level Mathematical Programming. Kluwer Academic Publishers, Boston, MA (1997)

    Book  MATH  Google Scholar 

  31. Siikonen, M-L.: Planning and control models for elevators in high-rise buildings. Ph.D. thesis, Helsinki University of Technology, Systems Analysis Laboratory (1997)

  32. Siikonen, M-L., Susi, T., Hakonen, H.: Passenger traffic flow simulation in tall buildings. Elev. World 49(8), 117–123 (2001)

  33. Sorsa, J., Siikonen, M-L.: Double-deck destination control system. Elevatori 37(5), 42–56 (2008)

  34. Sorsa, J., Siikonen, M-L., Ehtamo, H.: Optimal control of double-deck elevator group using genetic algorithm. Int. Trans. Oper. Res. 10(2), 103–114 (2003)

  35. Tyni, T., Ylinen, J.: Genetic algorithms in elevator car routing problem. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pp. 1413–1422. Morgan Kaufman Publishers, San Francisco, CA, USA (2001)

  36. Özaltin, O., Prokopyev, O., Schaefer, A.: The bilevel knapsack problem with stochastic right-hand sides. Oper. Res. Lett. 38(4), 328–333 (2010)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the anonymous reviewers for their valuable comments to improve the paper. The first author was partially supported by The Academy of Finland grant number 136040 and by the Education Fund of Finland grant number 88230.

Author information

Authors and Affiliations

  1. KONE Corporation, P.O. Box 7, 02151, Espoo, Finland

    Janne Sorsa, Juha-Matti Kuusinen, Mirko Ruokokoski & Marja-Liisa Siikonen

  2. Systems Analysis Laboratory, Aalto University School of Science, P.O. Box 11100, 00076, Aalto, Finland

    Harri Ehtamo

Authors
  1. Janne Sorsa
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Harri Ehtamo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Juha-Matti Kuusinen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mirko Ruokokoski
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Marja-Liisa Siikonen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Janne Sorsa.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sorsa, J., Ehtamo, H., Kuusinen, JM. et al. Modeling uncertain passenger arrivals in the elevator dispatching problem with destination control. Optim Lett 12, 171–185 (2018). https://doi.org/10.1007/s11590-017-1130-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-017-1130-0

Keywords

Search

Navigation