ABSTRACT:
Three heuristics for scheduling of a modern elevator system are evaluated and compared to one another. Modern elevators are described as an elevator system with multiple cabins per elevator shaft with the capability of travelling horizontally as well as vertically in a unidirectional system.
SNIPPETS:
Modern Elevator:
The MES described in this report is capable of operating both horizontally and vertically, with multiple cabins per shaft. The system have different lanes as directions in the shaft to prevent collisions. As the cabins can operate horizontally the building structures can become more complex and still allow for travelling with an elevator throughout the entire building.
The Complex Building Used, Plotted as a Graph.
Nearest Cabin Heuristic:
A basic heuristic is the nearest cabin (NC) control algorithm. The NC algorithm assigns the closest elevator travelling in the correct direction to the floor call. This means that if the elevator is travelling in a direction and passes a passenger that also wants to travel in that direction, the elevator will stop and pick up that passenger. The heuristic calculates a figure of suitability (F S) which is described by Barney (2004).
If the cabin is travelling in the same direction as the passengers request, then
F S= (N+ 2)−d
if the cabin is travelling toward the call but in the wrong direction relative the passengers
request then
F S= (N+ 1)−d
and if the elevator is travelling away from the call then
F S= 1
Search Based Heuristic:
The search based heuristic creates a search problem to evaluate every possible assignments of a call to a cabin. Any parameter can be used in the search heuristic depending on what the systems aims to minimize as explained by Tobita et al. (1991).
There are greedy search algorithms and non-greedy search algorithms according to Crites et al. (1998). The greedy algorithm evaluates a result at the time it is added and does not re evaluate the assignment. The non-greedy algorithm can re-evaluate the assignment to optimize it given new information.
Zone Based Heuristic:
Zone Based heuristic is a way of dividing the floors and exits in a building into zones and assigning cabins to them. The cabins should be evenly distributed within the building in order to minimize waiting time according to Strakosch and Caporale (2010), which is what the zone based heuristic does. The different zones allow the cabins to respond more quickly to calls than if they were clustered around a specific exit.
METHOD
Heuristics:
In our MES the shaft is unidirectional as opposed to a RES where each elevator can travel in two directions in its shaft. Several cabins also share a shaft in the MES which creates the possibility of collisions between cabins. This changes the conditions for the heuristics described in the background and they have to be adapted to the MES since they are developed for a RES. Below follows the specifics on how we adjusted the heuristics described in the background to work with our MES.
Simulation:
To compare the three different heuristics we wanted to gather data on waiting, and travel times in different buildings. In order to get this data, a simulation was written to simulate three different environments and buildings in which the modern elevators operate. A small building, a larger skyscraper-like building and a complex larger building.
RESULTS
The results presented in graphs 5.2, 5.3, and 5.4 represent the three different buildings that our simulation includes. In each of the graphs, the columns represent each heuristic with the number of cabins in the MES specified below. The graphs present the added average times that the passengers spent waiting for the cabin and travelling with the cabin, in other words the total time spent by the passenger to get to their destination.
Frequency of Travel Within the Building.
CONCLUSION
In the simple building the nearest cabin and search based performed similarly with higher average for the zone based. The zone based also had the highest average times in the complex building but the lowest average in the skyscraper, the nearest cabin and search based heuristic performed similarly in both with a slight advantage to search.
The zone based did however in a majority of the cases yield lower maximum values which means that it is better at ensuring service for the users and is less likely to fail and leave someone waiting for unreasonable amounts of time. Based on the amount of simulated data low maximum values for the zone heuristic is promising and it seems to be the best
heuristic for our MES.
Source: KTH
Authors: Viktor Björkholm | Jesper Bränn