概述(Overview)
作为一个公司内专门设计和建造电梯系统的工程师,你最新的项目是为一个11层大楼的电梯设计一个高效的控制模块。电梯控制模块决定着电梯目前要去的层数和电梯目前的服务方向(即电梯要载去往上层还是下层的乘客)。
要求(Rules)
- 对于每一个已经乘坐电梯乘客,都必须将其送到目标楼层。
- 电梯不能向乘客目标楼层相反的方向移动。
- 电梯只有在空着或送最后一批乘客时(将要空时)才能改变服务方向。
- 有三部电梯。
- 只能从下表提供的几个电梯模型中选择。
 
- 三部电梯其中一个为货物电梯(载重>=14)。
- 所有的电梯必须服务于所有的楼层。
- 当任何一部电梯当前无法被使用的时候,乘客必须仍然可以使用剩下的两部电梯到达任一楼层。
- 控制模块不能有自己的内部时钟,但可以拥有一个计时器。
- 电梯没有传感器来得到货物的重量以及当前电梯内乘客的数量。
- 每层楼高为4米。
分析:
由规则1.2.可以知道,如果有乘客想去往某一楼层,则不能路过该楼层而不停下。
规则3.其实和1.2.是自恰的,如果电梯在仍有乘客时就改变了服务方向,必会违反1.或2.。
规则4.中所给出的电梯根据载客量可以分为货物电梯和正常电梯(参见规则6),而每一类中的每一部电梯都不处于完全劣势,因此无法直接排除选择任何一个。
规则7.废掉了那种「某部电梯只往返于OO楼和XX楼之间以优化平均时间」的想法。
规则8.是说不能有「所有电梯对乘客需求都置之不理来优化平均时间」的情况。
规则9.是说不能在规定的时刻用特定的算法,也就是不允许计对不同的scenario 设计程序。Timer 可以使用保证了不会有乘客被「饿死」的现象,即可以规定如果某人等待时长超过XX,则不顾一切先去接他。
规则10.是说无法预先得知楼层乘客的数量以及电梯内乘客的数量,从而不能根据这两个数据来判断是否在某一楼层停下。(比如电梯已经满员则不再接受任何乘客)
前期准备(Preparation)
电梯的模拟器已经写好,作为一个Project放出,你所要做的工作就是设计其中的控制模块。
电梯的其他重要模块以及接口简介:
一、GUI




二、布署
// (1) Setup two elevators
Elevator elevators[] = {
new Elevator(12, 6, 3.0), new Elevator(12, 6, 3.0)
};</p>
// (2) Setup a building
Building building = new Building(10, 4.0);
// (3) Setup a simulation stage
SampleStage stage = new SampleStage(3000, 0);
// (4) Create an elevator controller
BasicController controller = new BasicController();
// (5) Run a simulation with or without GUI
Simulator.run(stage, building, elevators, controller, true);
[/java]
三、建立电梯(Elevator)
// First, create an array of N elevators
// (N = # elevators in the building)
Elevator elevators[] = new Elevator [N];</p>
// Then, assign each array element an Elevator object
elevators[0] = new Elevator(12, 6.0, 3.0);
[/java]
参数的意义:
- 参数 #1:容量
- 即该部电梯的载客量。
 
- 参数 #2:最大速度(单位 m/s)
- 参数 #3:加速度(单位 m/s^2)
- 即电梯速度的变化率。
- 电梯在保证能在目标楼层停下的情况下会自动加速至最大速度。
 
四、建立建筑物(Building)
// Create a building object
// (10 floors, and each floor is 4m in height)
Building building = new Building(10, 4.0);
[/java]
参数的意义
- 参数 #1:总层数
- 包括第0层。
 
- 参数 #2:层高(单位 m)
- 所有楼层高度相同。
 
五、情景模型(Scenario Stage)
一个情景模型控制着:
- 模拟器持续的时长
- 以时钟周期(clock tick)计算;1 clock tick = 0.1s
 
- 乘客流动模型
- 控制乘客从X层至Y层请求的频率。
- 多位乘客可以在同一时刻发出去任一楼层的请求。
 
六、电梯控制模块(Elevator Controller)
电梯控制模块决定着电梯目前要去的层数和电梯目前的服务方向(即电梯要载去往上层还是下层的乘客)
算法描述(Algorithm)
一、Basic Algorithm
最简单的办法,对每一个电梯布署同样的控制模块,每次只上或下一层(现实中如果有这样的电梯一定会把人逼疯)。算法流程图如下。

代码:
import org.segonds.elevators.model.*;</p>
public class BasicController implements Controller {
    protected ControlledBuilding building;
    protected ControlledElevator elevators[];
    private int buildingFloors, topFloor;
    public final Direction UP = Direction.UP;
    public final Direction DOWN = Direction.DOWN;
    public final Direction UNCOMMITTED = Direction.UNCOMMITTED;
    @Override
    public void setup(ControlledBuilding building) {
        this.building = building;
        elevators = building.getElevators();
        buildingFloors = building.getNbFloors();
        topFloor = buildingFloors - 1;
    }
    @Override
    public void reset() {
        // nothing to do
    }
    @Override
    public String getName() {
        return "Basic Sweep Controller";
    }
    @Override
    public void tick(Clock clock) {
      // For each elevator
      for (int i = 0; i < elevators.length; i++) {
        ControlledElevator elevator = elevators[i];
        double speed = elevator.getSpeed();
        int currentFloor = elevator.getFloor();
        // If the elevator is currently stopped at a floor and if its
        // doors are opening.
        if (speed == 0.0 && elevator.isOpening()) {
          // If the elevator was moving up
          if (elevator.getDirection() == UP) {
             // If the elevator is at the top floor, reverse its direction
             if (currentFloor == topFloor) {
               elevator.setDirection(DOWN);
               elevator.setTarget(topFloor-1);
             }
             else  // Otherwise, continue to move up to the next floor
               elevator.setTarget(currentFloor+1);
          }
          else
          if (elevator.getDirection() == DOWN) {
             // If the elevator is at the ground floor, reverse its direction
             if (currentFloor == 0) {
               elevator.setDirection(UP);
               elevator.setTarget(1);
             } // Otherwise, continue to move down to the next floor.
             else
               elevator.setTarget(currentFloor-1);
          }
        }
        if (elevator.getDirection() == UNCOMMITTED) {
          // If the elevator is idle. (initially)
          elevator.setDirection(UP);
          elevator.setTarget(0);
        }
      } // end for each elevator
    }
}
[/java]
二、Baseline Algorithm
上面的那个控制模块的优点是……好吧还真没什么优点。为了改进它,提出第二个控制模块,这也是现今大部分商场等电梯常用的控制程序,并没有什么特殊的优化,只是处理掉了Basic Algo的那些脑残特性。算法流程图如下。

代码:
import org.segonds.elevators.model.*;</p>
// Reference implementation of the Baseline Controller (as described in the
// lecture note)
public class RefBaselineController implements Controller {
    /* Declaration of instance variables */
    // The building object
    ControlledBuilding building;
    // An array of all elevator objects
    ControlledElevator E[];
    // Number of floors
    int nbFloors;
    // Floor number of the top floor
    int topFloor;
    // Set up shorter aliases
    final Direction UP = Direction.UP;
    final Direction DOWN = Direction.DOWN;
    final Direction UNCOMMITTED = Direction.UNCOMMITTED;
    public void setup(ControlledBuilding b) {
        // Save a reference to the building object for later use
        building = b;
        // Obtain a reference to the array of elevators
        E = building.getElevators();
       // Save these constants for easier access later
        nbFloors = building.getNbFloors();
        topFloor = nbFloors - 1;
    }
    // Nothing to reset
    public void reset() {}
    public String getName() {
        return "Baseline Controller";
    }
    public void tick(Clock clock) {
        // For each elevator
        for (int i = 0; i < E.length; i++) {             // Elevator's velocity. speed == 0 => Stopped;
            // speed > 0 => Moving up; speed < 0 => Moving down
            double speed = E[i].getSpeed();
            // Committed Direction
            Direction CD = E[i].getDirection();
            if (CD == UP && speed > 0)
                handleCase1(i);
            else
            if (CD == UP && speed == 0)
                handleCase2(i);
            else
            if (CD == DOWN && speed < 0)
                handleCase3(i);
            else
            if (CD == DOWN && speed == 0)
                handleCase4(i);
            else
            if (CD == UNCOMMITTED)
                handleCase5(i);
        }
    }
    public void handleCase1(int i) {
        int nextFloor = E[i].nextStoppableFloor();
        // If floor x is a candidate, candidates[x] will be set to true
        // Note: All elements are initialized to false by default.
        boolean candidates[] = new boolean [nbFloors];
        // Locate candidates
        for (int f = nextFloor; f = 0; f--)
            if (building.isFloorRequested(f, DOWN) || E[i].isFloorRequested(f))
                candidates[f] = true;
        // Initially use -1 to indicate "target not found"
        int target = -1;
        // Find the highest candidate floor as the target
        for (int f = topFloor; f >= 0; f--)
            if (candidates[f] == true) {
                target = f;
                break;
              }
        // If we can find a target
        if (target != -1)
            E[i].setTarget(target);
        // Otherwise, treat the case as an idle case
        else
            handleCase5(i);
    }
    public void handleCase4(int i) {
        int currentFloor = E[i].getFloor();
        if (currentFloor == 0) {
            handleCase5(i);
            return;
        }
        // Nothing to do if the elevator doors are NOT in closed or
        // closing states
        if (! E[i].isClosing() )
             return;
int nextFloor = currentFloor - 1;
boolean candidates[] = new boolean [nbFloors];
        for (int f = nextFloor; f >= 0; f--)
            if (building.isFloorRequested(f, DOWN) || E[i].isFloorRequested(f))
                candidates[f] = true;
int target = -1;
        // Find the highest candidate floor as the target
        for (int f = topFloor; f >= 0; f--)
            if (candidates[f] == true) {
                target = f;
                break;
            }
        // If we can find a target
        if (target != -1)
            E[i].setTarget(target);
        // Otherwise, treat the case as an idle case
        else
            handleCase5(i);
    }
    // Handle uncomitted case
    void handleCase5(int i) {
boolean candidates[] = new boolean [nbFloors];
        for (int f = 0; f = 0; f--)
            if (candidates[f] == true) {
                target = f;
                break;
            }
        if (target != -1) {
            E[i].setTarget(target);
            E[i].setDirection(DOWN);
            return;
        }
        // Otherwise stays idle
        E[i].setDirection(UNCOMMITTED);
    }
}
[/java]