文档介绍：European Journal of Operational Research 167 (2005) 574–587
ate/dsw
. Applications
Dynamic optimization of the operation of single-car
elevator systems with destination hall call registration:
Part II. The solution algorithm
Shunji Tanaka *, Yukihiro Uraguchi, Mituhiko Araki 1
Graduate School of Electrical Engineering, Kyoto University, Kyotodaigaku-Katsura, Nishikyo-ku, Kyoto 615-8510, Japan
Received 29 November 2002; accepted 18 April 2004
Available online 19 July 2004
Abstract
In this study we consider the elevator operation problem of single-car elevator systems with destination hall call reg-
istration. In this part we construct a branch-and-bound algorithm to solve the dynamic operation optimization problem
formulated in the first part. To calculate lower bounds of the subproblems generated in the course of the branch-and-
bound algorithm, we first relax some of the constraints of the subproblems and pose the relaxed subproblems
into three parts. Then, we apply the Lagrangian relaxation method to the posed subproblems.
Ó 2004 Elsevier . All rights reserved.
Keywords: Transportation; Elevator operation; Destination hall call registration; Branch-and-bound algorithm; Lagrangian relaxation
1. Introduction
In this part of the study we propose a branch-and-bound algorithm to solve the dynamic optimization
problem of elevator operation with destination hall call registration formulated in the first part.
The problem size, , the number of passengers to be served, or the number of floors to be visited de-
pends on how heavy passenger traffic is. During heavy traffic, it is inevitable to solve dynamic optimization
problems in that the car is full and there are at least as many waiting passengers as on-board passengers; the
number of passengers is at least twice as large as the car capacity (P 30), or the number of floors to be
* Corresponding author. Tel.: +81 75 383 2204; fax: +81 75 383 2201.
E-mail addresses: ******@