Energy-Efficient Elevating Transfer Vehicle Routing for Automated Multi-Level Material Handling Systems

摘要

We investigate an energy-efficient elevating transfer vehicle routing problem (ETVRP), in which an elevating transfer vehicle (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-hard 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 propose a new and more efficient exact formulation whose dimensionality does not constantly increase with the number of requests and is bounded by the size of the underlying grid network. To further enhance computational efficiency, 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. The performances of the proposed formulation and the approximation algorithms are further examined through numerical simulations. Note to Practitioners-Elevating transfer vehicles (ETVs) are widely utilized in automated multi-level material handling systems for transporting, storing, and retrieving units vertically and horizontally. We develop an efficient and effective method to reduce energy consumption of operating ETV, which is critical for improving both financial and environmental sustainability of these systems. The method can be adopted to realize online timely decision making for automatic vehicle routing when facing a huge number of pickup and delivery requests in multi-level material handling systems. A class of popular application scenarios, termed "Free-Permutation," is identified and mathematically characterized, in which the energy consumption can be exactly minimized in a theoretical sense within tractable computational times. For general application scenarios, an efficient and robust method is designed to guarantee to save the energy consumption to a level lower than 67% above the theoretical minimum level. Preliminary numerical experiments suggest the efficiency and effectiveness of this approach, but it has not yet been incorporated into nor tested in a practical system. In the future research, we will approach the application scenarios with two or more ETVs simultaneously operated in a multi-level material handling system.