Project Elevator 简介

阅读时间 ~ 44 分钟

概述(Overview)

作为一个公司内专门设计和建造电梯系统的工程师,你最新的项目是为一个11层大楼的电梯设计一个高效的控制模块。电梯控制模块决定着电梯目前要去的层数和电梯目前的服务方向(即电梯要载去往上层还是下层的乘客)。

要求(Rules)

  1. 对于每一个已经乘坐电梯乘客,都必须将其送到目标楼层。
  2. 电梯不能向乘客目标楼层相反的方向移动。
  3. 电梯只有在空着或送最后一批乘客时(将要空时)才能改变服务方向。
  4. 有三部电梯。
  5. 只能从下表提供的几个电梯模型中选择。

    Model

  6. 三部电梯其中一个为货物电梯(载重>=14)。
  7. 所有的电梯必须服务于所有的楼层。
  8. 当任何一部电梯当前无法被使用的时候,乘客必须仍然可以使用剩下的两部电梯到达任一楼层。
  9. 控制模块不能有自己的内部时钟,但可以拥有一个计时器。
  10. 电梯没有传感器来得到货物的重量以及当前电梯内乘客的数量。
  11. 每层楼高为4米。

分析:

由规则1.2.可以知道,如果有乘客想去往某一楼层,则不能路过该楼层而不停下。

规则3.其实和1.2.是自恰的,如果电梯在仍有乘客时就改变了服务方向,必会违反1.或2.。

规则4.中所给出的电梯根据载客量可以分为货物电梯和正常电梯(参见规则6),而每一类中的每一部电梯都不处于完全劣势,因此无法直接排除选择任何一个。

规则7.废掉了那种「某部电梯只往返于OO楼和XX楼之间以优化平均时间」的想法。

规则8.是说不能有「所有电梯对乘客需求都置之不理来优化平均时间」的情况。

规则9.是说不能在规定的时刻用特定的算法,也就是不允许计对不同的scenario 设计程序。Timer 可以使用保证了不会有乘客被「饿死」的现象,即可以规定如果某人等待时长超过XX,则不顾一切先去接他。

规则10.是说无法预先得知楼层乘客的数量以及电梯内乘客的数量,从而不能根据这两个数据来判断是否在某一楼层停下。(比如电梯已经满员则不再接受任何乘客)

前期准备(Preparation)

电梯的模拟器已经写好,作为一个Project放出,你所要做的工作就是设计其中的控制模块。

电梯的其他重要模块以及接口简介:

一、GUI

GUI0

GUI1

GUI2

GUI3

二、布署

[java]
// (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)

[java]
// 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)

[java]
// 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

最简单的办法,对每一个电梯布署同样的控制模块,每次只上或下一层(现实中如果有这样的电梯一定会把人逼疯)。算法流程图如下。

BasicController

代码:

[java]
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 &lt; 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 &amp;&amp; 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的那些脑残特性。算法流程图如下。

BaselineController

代码:

[java]
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 &lt; E.length; i++) { // Elevator's velocity. speed == 0 =&gt; Stopped;
// speed &gt; 0 =&gt; Moving up; speed &lt; 0 =&gt; Moving down
double speed = E[i].getSpeed();

// Committed Direction
Direction CD = E[i].getDirection();

if (CD == UP &amp;&amp; speed &gt; 0)
handleCase1(i);
else
if (CD == UP &amp;&amp; speed == 0)
handleCase2(i);
else
if (CD == DOWN &amp;&amp; speed &lt; 0)
handleCase3(i);
else
if (CD == DOWN &amp;&amp; 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 &gt;= 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 &gt;= 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 &gt;= 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]

2019 回顾

![2019](https://blog.mforever78.com/images/2019-review.png)2019 在它听起来还像一个新鲜的年份的时候,过去了。在各大 App 都在尝试为我的 2019 做总结的时候,我突然对好久不更新的博客心生愧疚。2019 在...… 继续阅读

写给塔塔的

Published on January 04, 2017

春风十里

Published on March 19, 2016