Trip-Based Integer Linear Programming Model for Static Multi-Car Elevator Operation Problems

Tsutomu INAMOTO; Yoshinobu HIGAMI; Shin-ya KOBAYASHI

doi:10.1587/transfun.E100.A.385

Trip-Based Integer Linear Programming Model for Static Multi-Car Elevator Operation Problems

Tsutomu INAMOTO, Yoshinobu HIGAMI, Shin-ya KOBAYASHI

Full Text Views

0

Share
Cite this

Summary :

In this paper, the authors propose an integer linear programming (ILP) model for static multi-car elevator operation problems. Here, “static” means that all information which make the behavior of the elevator system indeterministic is known before scheduling. The proposed model is based on the trip-based ILP model for static single-car elevator operation problems. A trip of an elevator is a one-directional movement of that elevator, which is labaled upward or downward. In the trip-based ILP model, an elevator trajectory is scheduled according to decision variables which determine allocations of trips to users of an elevator system. That model has such an advantage that the difficulty in solving ILP formulations resulted by that model does not depend on the length of the planning horizon nor the height of the considered building, thus is effective when elevator trajectories are simple. Moreover, that model has many variables relevant to elevators' positions. The proposed model is resulted by adding 3 constraints which are basically based on those variables and make it possible to prevent elevators in a same shaft from interfering. The first constraint simply imposes the first and last floors of an upper trip to be above those of its lower trip. The second constraint imagines the crossing point between upper and lower trips and imposes it ahead of or behind the lower trip according to their directions. The last constraint estimates future positions of elevators and imposes the upper trip to be above floors of passengers on the lower trip. The basic validity of the proposed model is displayed by solving 90 problem instances and examining elevator trajectories generated from them, then comparing objective function values of elevator trajectories on a multi-car elevator system with those on single-car elevator systems.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.2 pp.385-394

Publication Date: 2017/02/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E100.A.385

Type of Manuscript: Special Section PAPER (Special Section on Mathematical Systems Science and its Applications)

Category

Authors

Tsutomu INAMOTO
  Ehime University
Yoshinobu HIGAMI
  Ehime University
Shin-ya KOBAYASHI
  Ehime University

Keyword

elevator operation problem, multi-car elevator system, integer linear programming, interference prevention

Cite this

Copy

Tsutomu INAMOTO, Yoshinobu HIGAMI, Shin-ya KOBAYASHI, "Trip-Based Integer Linear Programming Model for Static Multi-Car Elevator Operation Problems" in IEICE TRANSACTIONS on Fundamentals, vol. E100-A, no. 2, pp. 385-394, February 2017, doi: 10.1587/transfun.E100.A.385.
Abstract: In this paper, the authors propose an integer linear programming (ILP) model for static multi-car elevator operation problems. Here, “static” means that all information which make the behavior of the elevator system indeterministic is known before scheduling. The proposed model is based on the trip-based ILP model for static single-car elevator operation problems. A trip of an elevator is a one-directional movement of that elevator, which is labaled upward or downward. In the trip-based ILP model, an elevator trajectory is scheduled according to decision variables which determine allocations of trips to users of an elevator system. That model has such an advantage that the difficulty in solving ILP formulations resulted by that model does not depend on the length of the planning horizon nor the height of the considered building, thus is effective when elevator trajectories are simple. Moreover, that model has many variables relevant to elevators' positions. The proposed model is resulted by adding 3 constraints which are basically based on those variables and make it possible to prevent elevators in a same shaft from interfering. The first constraint simply imposes the first and last floors of an upper trip to be above those of its lower trip. The second constraint imagines the crossing point between upper and lower trips and imposes it ahead of or behind the lower trip according to their directions. The last constraint estimates future positions of elevators and imposes the upper trip to be above floors of passengers on the lower trip. The basic validity of the proposed model is displayed by solving 90 problem instances and examining elevator trajectories generated from them, then comparing objective function values of elevator trajectories on a multi-car elevator system with those on single-car elevator systems.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.385/_p

Copy

@ARTICLE{e100-a_2_385,
author={Tsutomu INAMOTO, Yoshinobu HIGAMI, Shin-ya KOBAYASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Trip-Based Integer Linear Programming Model for Static Multi-Car Elevator Operation Problems},
year={2017},
volume={E100-A},
number={2},
pages={385-394},
abstract={In this paper, the authors propose an integer linear programming (ILP) model for static multi-car elevator operation problems. Here, “static” means that all information which make the behavior of the elevator system indeterministic is known before scheduling. The proposed model is based on the trip-based ILP model for static single-car elevator operation problems. A trip of an elevator is a one-directional movement of that elevator, which is labaled upward or downward. In the trip-based ILP model, an elevator trajectory is scheduled according to decision variables which determine allocations of trips to users of an elevator system. That model has such an advantage that the difficulty in solving ILP formulations resulted by that model does not depend on the length of the planning horizon nor the height of the considered building, thus is effective when elevator trajectories are simple. Moreover, that model has many variables relevant to elevators' positions. The proposed model is resulted by adding 3 constraints which are basically based on those variables and make it possible to prevent elevators in a same shaft from interfering. The first constraint simply imposes the first and last floors of an upper trip to be above those of its lower trip. The second constraint imagines the crossing point between upper and lower trips and imposes it ahead of or behind the lower trip according to their directions. The last constraint estimates future positions of elevators and imposes the upper trip to be above floors of passengers on the lower trip. The basic validity of the proposed model is displayed by solving 90 problem instances and examining elevator trajectories generated from them, then comparing objective function values of elevator trajectories on a multi-car elevator system with those on single-car elevator systems.},
keywords={},
doi={10.1587/transfun.E100.A.385},
ISSN={1745-1337},
month={February},}

Copy

TY - JOUR
TI - Trip-Based Integer Linear Programming Model for Static Multi-Car Elevator Operation Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 385
EP - 394
AU - Tsutomu INAMOTO
AU - Yoshinobu HIGAMI
AU - Shin-ya KOBAYASHI
PY - 2017
DO - 10.1587/transfun.E100.A.385
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2017
AB - In this paper, the authors propose an integer linear programming (ILP) model for static multi-car elevator operation problems. Here, “static” means that all information which make the behavior of the elevator system indeterministic is known before scheduling. The proposed model is based on the trip-based ILP model for static single-car elevator operation problems. A trip of an elevator is a one-directional movement of that elevator, which is labaled upward or downward. In the trip-based ILP model, an elevator trajectory is scheduled according to decision variables which determine allocations of trips to users of an elevator system. That model has such an advantage that the difficulty in solving ILP formulations resulted by that model does not depend on the length of the planning horizon nor the height of the considered building, thus is effective when elevator trajectories are simple. Moreover, that model has many variables relevant to elevators' positions. The proposed model is resulted by adding 3 constraints which are basically based on those variables and make it possible to prevent elevators in a same shaft from interfering. The first constraint simply imposes the first and last floors of an upper trip to be above those of its lower trip. The second constraint imagines the crossing point between upper and lower trips and imposes it ahead of or behind the lower trip according to their directions. The last constraint estimates future positions of elevators and imposes the upper trip to be above floors of passengers on the lower trip. The basic validity of the proposed model is displayed by solving 90 problem instances and examining elevator trajectories generated from them, then comparing objective function values of elevator trajectories on a multi-car elevator system with those on single-car elevator systems.
ER -