针对自动存取系统(AS/RS)货物装卸顺序约束和轨道小车(RGV)潜在碰撞的问题，引入装卸顺序冲突和碰撞冲突的概念对问题进行描述，以最小化任务总完工时间为目标，建立了消除冲突的数学规划模型.针对小规模问题，应用CPLEX获取其最优解；对于中大规模问题，构建了改进型和声搜索算法.在算法设计中，通过拆分、合并和声记忆库加快搜索速度，并融入4种变邻域搜索策略和1种变异操作以克服基本和声搜索算法早熟收敛、易陷入局部最优等不足.仿真实验与其他算法的对比结果表明，所构建算法具有较高的求解质量和良好的收敛性能，能提高AS/RS的运行速度和实用性.
To deal with the problems of cargo loading/unloading sequence constraint and impending collision between rail guided vehicles (RGVs) in automated storage and retrieval system (AS/RS), the concepts of the conflicts of cargo loading/unloading sequence and collision are introduced. And a mathematical programming model considering the characteristics of eliminating the conflicts is established to minimize the total complete time. CPLEX is employed to optimally solve the small-scale problems, and a modified harmony search(MHS) algorithm is constructed for medium to large scale problems. In the algorithm design, the harmony memory is repeatedly divided and regrouped to accelerate the searching process, and four variable neighborhood search strategies and a mutation operation are integrated to overcome the deficiencies of the basic harmony search algorithm, such as limited search depth and tendencies to trap into local optimum. Simulation experiments of the MHS algorithm are compared with other evolution algorithms, and the simulation results show that the algorithm has high solution quality and good convergence performance, and can improve the running speed and the practicality of the AS/RS.
［1］ROODBERGEN K J, VIS I F A. A survey of literature on automated storage and retrieval systems［J］. European Journal of Operational Research, 2009, 194(2): 343-362.
［2］郑向东, 谢飞. 均料分配系统中环形同轨自动导引车的应用研究［J］. 物流技术, 2011, 30(7): 187-189.
ZHENG Xiangdong, XIE Fei. Application of circular co-rail guided vehicle in load-sharing systems［J］. Logistics Technology, 2011, 30(7): 187-189.
［3］LEE S G, DE SOUZA R, ONG E K. Simulation modelling of a narrow aisle automated storage and retrieval system (AS/RS) serviced by rail-guided vehicles［J］. Computers in Industry, 1996, 30(3): 241-253.
［4］LEE J. Dispatching rail-guided vehicles and scheduling jobs in a flexible manufacturing system［J］. International Journal of Production Research, 1999, 37(1): 111-123.
［5］CHEN F F, HUANG J, CENTENO M A. Intelligent scheduling and control of rail-guided vehicles and load/unload operations in a flexible manufacturing system［J］. Journal of Intelligent Manufacturing, 1999, 10(5): 405-421.
［6］DOTOLI M, FANTI M P. A coloured Petri net model for automated storage and retrieval systems serviced by rail-guided vehicles: A control perspective［J］. International Journal of Computer Integrated Manufacturing, 2005, 18(2/3): 122-136.
［7］LIU Y K, LI S S, LI J, et al. Operation policy research of double rail-guided vehicle based on simulation［C］//2010 International Conference on E-Product E-Service and E-Entertainment. Henan, China: IEEE, 2010.
［8］KUNG Y, KOBAYASHI Y, HIGASHI T, et al. Order scheduling of multiple stacker cranes on common rails in an automated storage/retrieval system［J］. International Journal of Production Research, 2014, 52(4): 1171-1187.
［9］GAO Q, LU X W. The complexity and on-line algorithm for automated storage and retrieval system with stacker cranes on one rail［J］. Journal of Systems Science and Complexity, 2016, 29(5): 1302-1319.
［10］HU W H, MAO J F, WEI K J. Energy-efficient rail guided vehicle routing for two-sided loading/unloading automated freight handling system［J］. European Journal of Operational Research, 2017, 258(3): 943-957.
［11］GEEM Z W, KIM J H, LOGANATHAN G V. A new heuristic optimization algorithm: Harmony search［J］. Simulation, 2001, 76(2): 60-68.
［12］周炳海, 徐佳惠, 彭涛.基于新型线边集成超市的周期性物料配送优化［J］. 吉林大学学报(工学版), 2018, 48(2): 588-595.
ZHOU Binghai, XU Jiahui, PENG Tao. Optimization of cyclic part feeding with novel line-integrated supermarket［J］. Journal of Jilin University (Engineering and Technology Edition), 2018, 48(2): 588-595.
［13］KARAOGLAN I, ALTIPARMAK F. A hybrid genetic algorithm for the location-routing problem with simultaneous pickup and delivery［J］. Industrial Engineering and Management Systems, 2011, 10(1): 24-33.
［14］AI T J, KACHITVICHYANUKUL V. A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery［J］. Computers & Operations Research, 2009, 36(5): 1693-1702.
