5
$\begingroup$

Could you OR whizkids please help me out with this one:

https://stackoverflow.com/questions/61854621/a-good-memoryless-elevator-strategy

Surely somebody has solved this before. How do you classify this problem? A 1D transportation problem? A routing problem? What methods do you recommend for solving it?

Notice that the task isn't given at the outset: People keep arriving all the time pushing buttons saying "come here, I want to go there". Notice also that there is only one elevator.

The object is of course to bring people to their destinations as quickly as possible. The individual shouldn't be trampled down: Each customer must be served within a reasonable time, even if he or she travels in an unusual way.

There are simple evident strategies in common use in old elevators, but they cannot be optimal. I wonder how much room there is for improvement.

First of all I'm looking for a memoryless strategy: The decision should only depend on the current list of orders. The next step will be to explore if you can improve on this by learning from experience.

Improve this question
$\endgroup$
3
  • $\begingroup$ There's an extremely common strategy that uses one bit of memory. Surely you can use that one? $\endgroup$
    – John Dvorak
    May 24, 2020 at 8:16
  • $\begingroup$ I do not know how the elevators work. That being said, maybe you could try to solve it as a model based on a parallel machine scheduling problem, trying to minimize the maximum lateness. Each push on the button would be a new variable, a new Job, and its processing, the transporting of the people that are going to its floor or the entering of the person on the elevator (this one maybe having a higher priority, or not, I don't know). $\endgroup$
    – Josa Ferreira
    Feb 12, 2021 at 14:30
  • $\begingroup$ Are you asking this as a purely hypothetical mathematical exercise, or as something to be applied in the real world? ¶ Consider how someone taking an elevator up to the 10th floor would react when it stops, goes back down a few floors to pick up someone else, and then resumes going up? Anywhere that installed such an algorithm would almost certainly uninstall it the same day. ¶ "The object is of course to bring people to their destinations as quickly as possible." isn't a real-world goal. Minimizing the dissatisfaction of the users (or more specifically, the number of complaints) is. $\endgroup$
    – Ray Butterworth
    Jun 19 at 14:36

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.