Energy-efficient automated material handling systems - Fang, Zhou (2016)
The cost for operating equipment in Automated Material Handling Systems (AMHS), like manufacturing facilities and distribution centers, is an ongoing cost that requires a substantial commitment in electrical power. Many facilities are extremely large, depending on the complexity of the facilities conveyor system, it could account for as much as 50% of a facility's electrical load [1]. Increased fuel costs have pressured manufacturers to develop initiatives to find more efficient management of energy usage. In addition, emerging environmental regulations have forced companies to develop ways to reduce emissions without compromising the quality of their products. This motivates us to look into energy issues in AMHSs. However, the majority studies on the vehicle routing and dispatching problems only focused on the completion time or traveling distance issues, few of them paid energy issues any attention. In this thesis, we investigate a minimum-energy consumption routing problem of a stacker crane vehicle, which serves a multi-story storage and retrieval system (AS/RS) inside an air cargo terminal. We name this problem Energy-efficient Stacker Crane Problem (EESCP). This problem can be formulated as a Stacker Crane Problem on a two-dimensional (2D) grid network with a cost function in L1 norm. First, we prove this more specific problem to be NP-Complete. Still, due to the cost function in Manhattan norm, we are able to identify a special subset of 2D instances with certain arc patterns, to be polynomial-time solvable with an algorithm developed for one-dimensional problem, a.k.a Stacker Crane Problem on paths. For problem instances with more general arc patterns, we have proposed a new exact formulation the scale of which is fi xed by the underlying grid network. We have also developed two polynomial-time approximation algorithms with the grid network taken into account. One is asymptotically optimal and has the time-complexity that grows linearly with the number of requests given by the problem instance; the other has a bounded time-complexity and performs better for instances with smaller arc lengths. These two algorithms together provide an improved 5/3 theoretical worst-case bound than the 9/5 in the work of Frederickson, Hecht et al. [2]. Furthermore, we have adapted our static algorithm to the dynamic environment using a rolling-horizon approach. The dynamic algorithm has two parameters, look-ahead horizon and decision point. The algorithm performance under various combinations of these two parameters is tested via simulations. Finally, we propose an exact formulation for energy-effi cient multi-capacity problem and three heuristics. The exact formulation is bilinear and we have reformulated it into the linear form. The performances of the heuristics are compared against the exact solutions.