我有一栋只有一部电梯的大楼，我需要为这部电梯找到一个算法。我们得到一个这样形式的对象列表:{i->j}，其中i是住户想要乘电梯的楼层，j 是他想要趴下的地板。
无限多个人可以同时使用电梯，与人在电梯里停留的时间长短无关。电梯从一楼开始。
我在网上查了一下，找到了“电梯算法”，但它并没有真正帮助我。它说我应该一直向上然后一直向下。但是考虑一下当一位居民想要从 1 层到 100 层而另一位居民想要从 50 层到 49 层时。使用上述算法，将需要 151 层的距离。如果我改用这条路径:1->50->49->100，它只需要 102 层，这样更好。
我应该使用什么算法？
最佳答案
这是将此问题表述为基于时间的整数程序的一种方法。 (生成所有约束似乎有点矫枉过正，但可以保证生成最优解)
假设电梯从楼层 F 出发需要 1 个单位的时间至 F+1或 F-1 .
The Insight:我们使用的事实是在任何时候t , 只能做出一个决定。是向上还是向下。这是我们问题的决策变量。 DIR_t = +1 如果电梯在时间 t 向上移动，否则 -1。
我们希望尽量缩短所有乘客到达目的地的时间。
这张表更清楚
Time FLOOR_t Dir_t
1 1 1
2 2 1
3 3 1
4 4 1
... ... ...
49 49 1
50 50 -1
51 49 1
52 50 1
...
100 99 1
101 100 NA
现在，让我们引入乘客。有 P 位乘客，每个人都想从
SF至 EF (他们的起点楼层到终点楼层，他们的目的地。)
所以我们得到了(SF_p, EF_p)每位乘客p .
约束
我们知道电梯在时间t所在的楼层是
F_t = F_t-1 + DIR_t-1
(F0 = 0，DIR_0 = 1，F1 = 1 只是为了开始。)
现在，让ST_p是乘客 p 开始他们的电梯旅程的时刻。让ET_p是乘客结束电梯旅程的时刻。
注意 SF和 EF是给我们的输入参数，但是ST和 ET是 IP 将在求解时设置的变量。也就是地板给我们，我们要与时俱进。
ST_p = t if F_t = SF_p # whenever the elevator comes to a passenger's starting floor, their journey starts.
ET_p = t if F_t = EF_p AND ST_p > 0 (a passenger cannot end their journey before it commenced.)
This can be enforced by introducing new 0/1 indicator variables.
ETp > STp # you can only get off after you got on
最后介绍一个号码T这是完成整组行程的时间。它是每个 p 的所有 ET 的最大值。这是需要最小化的。
T > ET_p for all p # we want to find the time when the last passenger gets off.
配方
综合起来:
Min T
T > ET_p for all p
F_t = F_t-1 + DIR_t-1
ETp > STp # you can only get off after you got on
ST_p = t if F_t = SF_p # whenever the elevator some to a passenger's starting floor, their journey starts.
ET_p = t if F_t = EF_p AND ST_p > 0
ET_p >= 1 #everyone should end their journey. Otherwise model will give 0 as the obj function value.
DIR_t = (+1, -1) # can be enforced with 2 binary variables if needed.
现在解决这个 IP 问题后，可以使用每个 DIR_t 的值来追踪确切的行程。对于每个 t .
关于algorithm - 最小距离的电梯算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22458201/