Energy-efficient elevating transfer vehicle routing for automated multi-level material handling systems

摘要

Elevating Transfer Vehicles (ETV) are widely utilized in automated multi-level material handling systems for transporting, storing and retrieving units vertically and horizontally. Reducing energy consumption of operating ETV is critical for improving both financial and environmental sustain-ability of these systems. We investigate an energy-efficient ETV routing problem (ETVRP), in which an ETV serves a multi-level freight handling system to transport cargo containers between airside and landside in an air cargo terminal. The problem can be regarded as a special case of Stacker Crane Problem defined on a regular grid graph constructed by uniform rectangular tiles. Even with the special grid network structure, the ETVRP is still NP-Complete in general. We manage to identify a subset of the ETVRP instances that are polynomially solvable based on the condition of free-permutation. For general ETVRPs, we develop two approximation algorithms, one of which is asymptotically optimal and has the time-complexity that grows linearly with the number of requests; the other has a bounded time-complexity and works better for instances with smaller arc lengths. Combining these two algorithms can guarantee an approximation ratio of 5/3.