IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v29y2015i4d10.1007_s10878-013-9620-1.html
   My bibliography  Save this article

Elevator dispatching problem: a mixed integer linear programming formulation and polyhedral results

Author

Listed:
  • Mirko Ruokokoski

    (School of Science, Aalto University)

  • Harri Ehtamo

    (School of Science, Aalto University)

  • Panos M. Pardalos

    (University of Florida)

Abstract

In the static elevator dispatching problem the aim is to design a route for each capacitated elevator to satisfy a set of transportation requests such that a cost function is minimized while satisfying a number of constraints. This problem is a crucial part in the control of an elevator group. So far, the problem has been formulated in various algorithmic-dependent forms, where part of the constraints have been given only verbally. In this paper we present a mixed-integer linear programming formulation of the problem where all constraints are given in explicit mathematical form. This allows, e.g., polyhedral analysis of the problem. We also present some new valid inequalities to strengthen the formulation. Furthermore, we study the polyhedral structure of the problem in a generic case arising in the down-peak traffic pattern. In particular, we show which equalities define a minimal equality system for the polytope of the problem, which is defined as the convex hull of the feasible solutions. In addition, we provide the dimension of the polytope and analyze which valid inequalities derived are facet inducing.

Suggested Citation

  • Mirko Ruokokoski & Harri Ehtamo & Panos M. Pardalos, 2015. "Elevator dispatching problem: a mixed integer linear programming formulation and polyhedral results," Journal of Combinatorial Optimization, Springer, vol. 29(4), pages 750-780, May.
    • Handle: RePEc:spr:jcomop:v:29:y:2015:i:4:d:10.1007_s10878-013-9620-1
    DOI: 10.1007/s10878-013-9620-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-013-9620-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-013-9620-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Benjamin Hiller & Andreas Tuchscherer, 2008. "Real-Time Destination-Call Elevator Group Control on Embedded Microcontrollers," Operations Research Proceedings, in: Jörg Kalcsics & Stefan Nickel (ed.), Operations Research Proceedings 2007, pages 357-362, Springer.
    2. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    3. Archetti, Claudia & Savelsbergh, Martin W.P. & Grazia Speranza, M., 2008. "To split or not to split: That is the question," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 44(1), pages 114-123, January.
    4. Stefan Ropke & Jean-François Cordeau, 2009. "Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 43(3), pages 267-286, August.
    5. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Janne Sorsa, 2019. "Real-time algorithms for the bilevel double-deck elevator dispatching problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(1), pages 79-122, March.
    2. Ruokokoski, Mirko & Sorsa, Janne & Siikonen, Marja-Liisa & Ehtamo, Harri, 2016. "Assignment formulation for the Elevator Dispatching Problem with destination control and its performance analysis," European Journal of Operational Research, Elsevier, vol. 252(2), pages 397-406.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    2. Pedro Munari & Martin Savelsbergh, 2020. "A Column Generation-Based Heuristic for the Split Delivery Vehicle Routing Problem with Time Windows," SN Operations Research Forum, Springer, vol. 1(4), pages 1-24, December.
    3. Jeffrey W. Ohlmann & Michael J. Fry & Barrett W. Thomas, 2008. "Route Design for Lean Production Systems," Transportation Science, INFORMS, vol. 42(3), pages 352-370, August.
    4. Qin, Hu & Moriakin, Anton & Xu, Gangyan & Li, Jiliu, 2024. "The generator distribution problem for base stations during emergency power outage: A branch-and-price-and-cut approach," European Journal of Operational Research, Elsevier, vol. 318(3), pages 752-767.
    5. Timo Gschwind & Stefan Irnich, 2012. "Effective Handling of Dynamic Time Windows and Synchronization with Precedences for Exact Vehicle Routing," Working Papers 1211, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    6. Albert H. Schrotenboer & Evrim Ursavas & Iris F. A. Vis, 2019. "A Branch-and-Price-and-Cut Algorithm for Resource-Constrained Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 53(4), pages 1001-1022, July.
    7. Capelle, Thomas & Cortés, Cristián E. & Gendreau, Michel & Rey, Pablo A. & Rousseau, Louis-Martin, 2019. "A column generation approach for location-routing problems with pickup and delivery," European Journal of Operational Research, Elsevier, vol. 272(1), pages 121-131.
    8. Roberto Baldacci & Enrico Bartolini & Aristide Mingozzi, 2011. "An Exact Algorithm for the Pickup and Delivery Problem with Time Windows," Operations Research, INFORMS, vol. 59(2), pages 414-426, April.
    9. Schulz, Arne & Pfeiffer, Christian, 2024. "Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems," European Journal of Operational Research, Elsevier, vol. 312(2), pages 456-472.
    10. Sophie N. Parragh & Jorge Pinho de Sousa & Bernardo Almada-Lobo, 2015. "The Dial-a-Ride Problem with Split Requests and Profits," Transportation Science, INFORMS, vol. 49(2), pages 311-334, May.
    11. Andrew Allman & Qi Zhang, 2021. "Branch-and-price for a class of nonconvex mixed-integer nonlinear programs," Journal of Global Optimization, Springer, vol. 81(4), pages 861-880, December.
    12. Sun, Yanshuo & Chen, Zhi-Long & Zhang, Lei, 2020. "Nonprofit peer-to-peer ridesharing optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    13. Hoogendoorn, Y.N. & Dalmeijer, K., 2021. "Resource-robust valid inequalities for set covering and set partitioning models," Econometric Institute Research Papers EI 2020-08, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    14. Yuan, Yuan & Cattaruzza, Diego & Ogier, Maxime & Semet, Frédéric & Vigo, Daniele, 2021. "A column generation based heuristic for the generalized vehicle routing problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    15. Luo, Zhixing & Qin, Hu & Lim, Andrew, 2014. "Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints," European Journal of Operational Research, Elsevier, vol. 234(1), pages 49-60.
    16. Veaceslav Ghilas & Jean-François Cordeau & Emrah Demir & Tom Van Woensel, 2018. "Branch-and-Price for the Pickup and Delivery Problem with Time Windows and Scheduled Lines," Transportation Science, INFORMS, vol. 52(5), pages 1191-1210, October.
    17. Du, Jianhui & Zhang, Zhiqin & Wang, Xu & Lau, Hoong Chuin, 2023. "A hierarchical optimization approach for dynamic pickup and delivery problem with LIFO constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    18. Wang, Mengtong & Zhang, Canrong & Bell, Michael G.H. & Miao, Lixin, 2022. "A branch-and-price algorithm for location-routing problems with pick-up stations in the last-mile distribution system," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1258-1276.
    19. Roberto Baldacci & Enrico Bartolini & Aristide Mingozzi & Roberto Roberti, 2010. "An exact solution framework for a broad class of vehicle routing problems," Computational Management Science, Springer, vol. 7(3), pages 229-268, July.
    20. Gschwind, Timo, 2015. "A comparison of column-generation approaches to the Synchronized Pickup and Delivery Problem," European Journal of Operational Research, Elsevier, vol. 247(1), pages 60-71.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:29:y:2015:i:4:d:10.1007_s10878-013-9620-1. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.