survey for the quadratic assignment problem

国际自动化与计算杂志.英文版.1.Improved Exponential Stability Criteria for Uncertain Neutral System with Nonlinear Parameter PerturbationsFang Qiu，Ban-Tong Cui2.Robust Active Suspension Design Subject to Vehicle Inertial Parameter VariationsHai-Ping Du，Nong Zhang3.Delay-dependent Non-fragile H∞ Filtering for Uncertain Fuzzy Systems Based on Switching Fuzzy Model and Piecewise Lyapunov FunctionZhi-Le Xia，Jun-Min Li，Jiang-Rong Li4.Observer-based Adaptive Iterative Learning Control for Nonlinear Systems with Time-varying DelaysWei-Sheng Chen，Rui-Hong Li，Jing Li5.H∞ Output Feedback Control for Stochastic Systems with Mode-dependent Time-varying Delays and Markovian Jump ParametersXu-Dong Zhao，Qing-Shuang Zeng6.Delay and Its Time-derivative Dependent Robust Stability of Uncertain Neutral Systems with Saturating ActuatorsFatima El Haoussi，El Houssaine Tissir7.Parallel Fuzzy P+Fuzzy I+Fuzzy D Controller:Design and Performance EvaluationVineet Kumar，A.P.Mittal8.Observers for Descriptor Systems with Slope-restricted NonlinearitiesLin-Na Zhou，Chun-Yu Yang，Qing-Ling Zhang9.Parameterized Solution to a Class of Sylvester MatrixEquationsYu-Peng Qiao，Hong-Sheng Qi，Dai-Zhan Cheng10.Indirect Adaptive Fuzzy and Impulsive Control of Nonlinear SystemsHai-Bo Jiang11.Robust Fuzzy Tracking Control for Nonlinear Networked Control Systems with Integral Quadratic ConstraintsZhi-Sheng Chen，Yong He，Min Wu12.A Power-and Coverage-aware Clustering Scheme for Wireless Sensor NetworksLiang Xue，Xin-Ping Guan，Zhi-Xin Liu，Qing-Chao Zheng13.Guaranteed Cost Active Fault-tolerant Control of Networked Control System with Packet Dropout and Transmission DelayXiao-Yuan Luo，Mei-Jie Shang，Cai-Lian Chen，Xin-Ping Guanparison of Two Novel MRAS Based Strategies for Identifying Parameters in Permanent Magnet Synchronous MotorsKan Liu，Qiao Zhang，Zi-Qiang Zhu，Jing Zhang，An-Wen Shen，Paul Stewart15.Modeling and Analysis of Scheduling for Distributed Real-time Embedded SystemsHai-Tao Zhang，Gui-Fang Wu16.Passive Steganalysis Based on Higher Order Image Statistics of Curvelet TransformS.Geetha，Siva S.Sivatha Sindhu，N.Kamaraj17.Movement Invariants-based Algorithm for Medical Image Tilt CorrectionMei-Sen Pan，Jing-Tian Tang，Xiao-Li Yang18.Target Tracking and Obstacle Avoidance for Multi-agent SystemsJing Yan，Xin-Ping Guan，Fu-Xiao Tan19.Automatic Generation of Optimally Rigid Formations Using Decentralized MethodsRui Ren，Yu-Yan Zhang，Xiao-Yuan Luo，Shao-Bao Li20.Semi-blind Adaptive Beamforming for High-throughput Quadrature Amplitude Modulation SystemsSheng Chen，Wang Yao，Lajos Hanzo21.Throughput Analysis of IEEE 802.11 Multirate WLANs with Collision Aware Rate Adaptation AlgorithmDhanasekaran Senthilkumar，A. Krishnan22.Innovative Product Design Based on Customer Requirement Weight Calculation ModelChen-Guang Guo，Yong-Xian Liu，Shou-Ming Hou，Wei Wang23.A Service Composition Approach Based on Sequence Mining for Migrating E-learning Legacy System to SOAZhuo Zhang，Dong-Dai Zhou，Hong-Ji Yang，Shao-Chun Zhong24.Modeling of Agile Intelligent Manufacturing-oriented Production Scheduling SystemZhong-Qi Sheng，Chang-Ping Tang，Ci-Xing Lv25.Estimation of Reliability and Cost Relationship for Architecture-based SoftwareHui Guan，Wei-Ru Chen，Ning Huang，Hong-Ji Yang1.A Computer-aided Design System for Framed-mould in Autoclave ProcessingTian-Guo Jin，Feng-Yang Bi2.Wear State Recognition of Drills Based on K-means Cluster and Radial Basis Function Neural NetworkXu Yang3.The Knee Joint Design and Control of Above-knee Intelligent Bionic Leg Based on Magneto-rheological DamperHua-Long Xie，Ze-Zhong Liang，Fei Li，Li-Xin Guo4.Modeling of Pneumatic Muscle with Shape Memory Alloy and Braided SleeveBin-Rui Wang，Ying-Lian Jin，Dong Wei5.Extended Object Model for Product Configuration DesignZhi-Wei Xu，Ze-Zhong Liang，Zhong-Qi Sheng6.Analysis of Sheet Metal Extrusion Process Using Finite Element MethodXin-Cun Zhuang，Hua Xiang，Zhen Zhao7.Implementation of Enterprises' Interoperation Based on OntologyXiao-Feng Di，Yu-Shun Fan8.Path Planning Approach in Unknown EnvironmentTing-Kai Wang，Quan Dang，Pei-Yuan Pan9.Sliding Mode Variable Structure Control for Visual Servoing SystemFei Li，Hua-Long Xie10.Correlation of Direct Piezoelectric Effect on EAPap under Ambient FactorsLi-Jie Zhao，Chang-Ping Tang，Peng Gong11.XML-based Data Processing in Network Supported Collaborative DesignQi Wang，Zhong-Wei Ren，Zhong-Feng Guo12.Production Management Modelling Based on MASLi He，Zheng-Hao Wang，Ke-Long Zhang13.Experimental Tests of Autonomous Ground Vehicles with PreviewCunjia Liu，Wen-Hua Chen，John Andrews14.Modelling and Remote Control of an ExcavatorYang Liu，Mohammad Shahidul Hasan，Hong-Nian Yu15.TOPSIS with Belief Structure for Group Belief Multiple Criteria Decision MakingJiang Jiang，Ying-Wu Chen，Da-Wei Tang，Yu-Wang Chen16.Video Analysis Based on Volumetric Event DetectionJing Wang，Zhi-Jie Xu17.Improving Decision Tree Performance by Exception HandlingAppavu Alias Balamurugan Subramanian，S.Pramala，B.Rajalakshmi，Ramasamy Rajaram18.Robustness Analysis of Discrete-time Indirect Model Reference Adaptive Control with Normalized Adaptive LawsQing-Zheng Gao，Xue-Jun Xie19.A Novel Lifecycle Model for Web-based Application Development in Small and Medium EnterprisesWei Huang，Ru Li，Carsten Maple，Hong-Ji Yang，David Foskett，Vince Cleaver20.Design of a Two-dimensional Recursive Filter Using the Bees AlgorithmD. T. Pham，Ebubekir Ko(c)21.Designing Genetic Regulatory Networks Using Fuzzy Petri Nets ApproachRaed I. Hamed，Syed I. Ahson，Rafat Parveen1.State of the Art and Emerging Trends in Operations and Maintenance of Offshore Oil and Gas Production Facilities: Some Experiences and ObservationsJayantha P.Liyanage2.Statistical Safety Analysis of Maintenance Management Process of Excavator UnitsLjubisa Papic，Milorad Pantelic，Joseph Aronov，Ajit Kumar Verma3.Improving Energy and Power Efficiency Using NComputing and Approaches for Predicting Reliability of Complex Computing SystemsHoang Pham，Hoang Pham Jr.4.Running Temperature and Mechanical Stability of Grease as Maintenance Parameters of Railway BearingsJan Lundberg，Aditya Parida，Peter S(o)derholm5.Subsea Maintenance Service Delivery: Mapping Factors Influencing Scheduled Service DurationEfosa Emmanuel Uyiomendo，Tore Markeset6.A Systemic Approach to Integrated E-maintenance of Large Engineering PlantsAjit Kumar Verma，A.Srividya，P.G.Ramesh7.Authentication and Access Control in RFID Based Logistics-customs Clearance Service PlatformHui-Fang Deng，Wen Deng，Han Li，Hong-Ji Yang8.Evolutionary Trajectory Planning for an Industrial RobotR.Saravanan，S.Ramabalan，C.Balamurugan，A.Subash9.Improved Exponential Stability Criteria for Recurrent Neural Networks with Time-varying Discrete and Distributed DelaysYuan-Yuan Wu，Tao Li，Yu-Qiang Wu10.An Improved Approach to Delay-dependent Robust Stabilization for Uncertain Singular Time-delay SystemsXin Sun，Qing-Ling Zhang，Chun-Yu Yang，Zhan Su，Yong-Yun Shao11.Robust Stability of Nonlinear Plants with a Non-symmetric Prandtl-Ishlinskii Hysteresis ModelChang-An Jiang，Ming-Cong Deng，Akira Inoue12.Stability Analysis of Discrete-time Systems with Additive Time-varying DelaysXian-Ming Tang，Jin-Shou Yu13.Delay-dependent Stability Analysis for Markovian Jump Systems with Interval Time-varying-delaysXu-Dong Zhao，Qing-Shuang Zeng14.H∞ Synchronization of Chaotic Systems via Delayed Feedback ControlLi Sheng，Hui-Zhong Yang15.Adaptive Fuzzy Observer Backstepping Control for a Class of Uncertain Nonlinear Systems with Unknown Time-delayShao-Cheng Tong，Ning Sheng16.Simulation-based Optimal Design of α-β-γ-δ FilterChun-Mu Wu，Paul P.Lin，Zhen-Yu Han，Shu-Rong Li17.Independent Cycle Time Assignment for Min-max SystemsWen-De Chen，Yue-Gang Tao，Hong-Nian Yu1.An Assessment Tool for Land Reuse with Artificial Intelligence MethodDieter D. Genske，Dongbin Huang，Ariane Ruff2.Interpolation of Images Using Discrete Wavelet Transform to Simulate Image Resizing as in Human VisionRohini S. Asamwar，Kishor M. Bhurchandi，Abhay S. Gandhi3.Watermarking of Digital Images in Frequency DomainSami E. I. Baba，Lala Z. Krikor，Thawar Arif，Zyad Shaaban4.An Effective Image Retrieval Mechanism Using Family-based Spatial Consistency Filtration with Object RegionJing Sun，Ying-Jie Xing5.Robust Object Tracking under Appearance Change ConditionsQi-Cong Wang，Yuan-Hao Gong，Chen-Hui Yang，Cui-Hua Li6.A Visual Attention Model for Robot Object TrackingJin-Kui Chu，Rong-Hua Li，Qing-Ying Li，Hong-Qing Wang7.SVM-based Identification and Un-calibrated Visual Servoing for Micro-manipulationXin-Han Huang，Xiang-Jin Zeng，Min Wang8.Action Control of Soccer Robots Based on Simulated Human IntelligenceTie-Jun Li，Gui-Qiang Chen，Gui-Fang Shao9.Emotional Gait Generation for a Humanoid RobotLun Xie，Zhi-Liang Wang，Wei Wang，Guo-Chen Yu10.Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault DetectionZhong-Liang Pan，Ling Chen，Guang-Zhao Zhang11.A Novel Fuzzy Direct Torque Control System for Three-level Inverter-fed Induction MachineShu-Xi Liu，Ming-Yu Wang，Yu-Guang Chen，Shan Li12.Statistic Learning-based Defect Detection for Twill FabricsLi-Wei Han，De Xu13.Nonsaturation Throughput Enhancement of IEEE 802.11b Distributed Coordination Function for Heterogeneous Traffic under Noisy EnvironmentDhanasekaran Senthilkumar，A. Krishnan14.Structure and Dynamics of Artificial Regulatory Networks Evolved by Segmental Duplication and Divergence ModelXiang-Hong Lin，Tian-Wen Zhang15.Random Fuzzy Chance-constrained Programming Based on Adaptive Chaos Quantum Honey Bee Algorithm and Robustness AnalysisHan Xue，Xun Li，Hong-Xu Ma16.A Bit-level Text Compression Scheme Based on the ACW AlgorithmHussein A1-Bahadili，Shakir M. Hussain17.A Note on an Economic Lot-sizing Problem with Perishable Inventory and Economies of Scale Costs:Approximation Solutions and Worst Case AnalysisQing-Guo Bai，Yu-Zhong Zhang，Guang-Long Dong1.Virtual Reality: A State-of-the-Art SurveyNing-Ning Zhou，Yu-Long Deng2.Real-time Virtual Environment Signal Extraction and DenoisingUsing Programmable Graphics HardwareYang Su，Zhi-Jie Xu，Xiang-Qian Jiang3.Effective Virtual Reality Based Building Navigation Using Dynamic Loading and Path OptimizationQing-Jin Peng，Xiu-Mei Kang，Ting-Ting Zhao4.The Skin Deformation of a 3D Virtual HumanXiao-Jing Zhou，Zheng-Xu Zhao5.Technology for Simulating Crowd Evacuation BehaviorsWen-Hu Qin，Guo-Hui Su，Xiao-Na Li6.Research on Modelling Digital Paper-cut PreservationXiao-Fen Wang，Ying-Rui Liu，Wen-Sheng Zhang7.On Problems of Multicomponent System Maintenance ModellingTomasz Nowakowski，Sylwia Werbinka8.Soft Sensing Modelling Based on Optimal Selection of Secondary Variables and Its ApplicationQi Li，Cheng Shao9.Adaptive Fuzzy Dynamic Surface Control for Uncertain Nonlinear SystemsXiao-Yuan Luo，Zhi-Hao Zhu，Xin-Ping Guan10.Output Feedback for Stochastic Nonlinear Systems with Unmeasurable Inverse DynamicsXin Yu，Na Duan11.Kalman Filtering with Partial Markovian Packet LossesBao-Feng Wang，Ge Guo12.A Modified Projection Method for Linear FeasibilityProblemsYi-Ju Wang，Hong-Yu Zhang13.A Neuro-genetic Based Short-term Forecasting Framework for Network Intrusion Prediction SystemSiva S. Sivatha Sindhu，S. Geetha，M. Marikannan，A. Kannan14.New Delay-dependent Global Asymptotic Stability Condition for Hopfield Neural Networks with Time-varying DelaysGuang-Deng Zong，Jia Liu hHTTp://15.Crosscumulants Based Approaches for the Structure Identification of Volterra ModelsHouda Mathlouthi，Kamel Abederrahim，Faouzi Msahli，Gerard Favier1.Coalition Formation in Weighted Simple-majority Games under Proportional Payoff Allocation RulesZhi-Gang Cao，Xiao-Guang Yang2.Stability Analysis for Recurrent Neural Networks with Time-varying DelayYuan-Yuan Wu，Yu-Qiang Wu3.A New Type of Solution Method for the Generalized Linear Complementarity Problem over a Polyhedral ConeHong-Chun Sun，Yan-Liang Dong4.An Improved Control Algorithm for High-order Nonlinear Systems with Unmodelled DynamicsNa Duan，Fu-Nian Hu，Xin Yu5.Controller Design of High Order Nonholonomic System with Nonlinear DriftsXiu-Yun Zheng，Yu-Qiang Wu6.Directional Filter for SAR Images Based on NonsubsampledContourlet Transform and Immune Clonal SelectionXiao-Hui Yang，Li-Cheng Jiao，Deng-Feng Li7.Text Extraction and Enhancement of Binary Images Using Cellular AutomataG. Sahoo，Tapas Kumar，B.L. Rains，C.M. Bhatia8.GH2 Control for Uncertain Discrete-time-delay Fuzzy Systems Based on a Switching Fuzzy Model and Piecewise Lyapunov FunctionZhi-Le Xia，Jun-Min Li9.A New Energy Optimal Control Scheme for a Separately Excited DC Motor Based Incremental Motion DriveMilan A.Sheta，Vivek Agarwal，Paluri S.V.Nataraj10.Nonlinear Backstepping Ship Course ControllerAnna Witkowska，Roman Smierzchalski11.A New Method of Embedded Fourth Order with Four Stages to Study Raster CNN SimulationR. Ponalagusamy，S. Senthilkumar12.A Minimum-energy Path-preserving Topology Control Algorithm for Wireless Sensor NetworksJin-Zhao Lin，Xian Zhou，Yun Li13.Synchronization and Exponential Estimates of Complex Networks with Mixed Time-varying Coupling DelaysYang Dai，YunZe Cai，Xiao-Ming Xu14.Step-coordination Algorithm of Traffic Control Based on Multi-agent SystemHai-Tao Zhang，Fang Yu，Wen Li15.A Research of the Employment Problem on Common Job-seekersand GraduatesBai-Da Qu。

2008年6月系统工程理论与实践第6期　文章编号:100026788(2008)0620081213开放式车辆路径问题的蚁群优化算法李相勇,田　澎(上海交通大学安泰经济与管理学院,上海200052)摘要:　研究了开放式车辆路径问题,该问题中车辆在服务完最后一个顾客点后不需要回到车场,若要求回到车场,则必须沿原路返回.提出了一种混合蚁群优化算法,该算法主体是一个在超立方框架下执行的M AX2MI N蚂蚁系统,算法混合了禁忌搜索算法作为局部优化算法,同时算法集成了一个后优化过程来进一步优化最优解.基于标准测试问题,最后给出了算法同文献中其它算法的性能比较结果,计算结果表明本文提出的算法是一个有效的求解开放式车辆路径问题的方法.关键词:　开放式车辆路径问题;蚁群优化算法;禁忌搜索算法;现代启发式算法;后优化过程中图分类号:　O221 文献标志码:　A Research on ant colony optimization alg orithm for theopen vehicle routing problemLI X iang2y ong,TI AN Peng(Antai C ollege of Economics&Management,Shanghai Jiaotong University,Shanghai200030,China)Abstract:　This paper studies the open vehicle routing problem,in which the vehicles do not return to the startingdepot after serving the last customers or,if they do,they must make the same trip in the reverse order.We propose anAnt C olony Optimization metaheuristic hybridized with tabu search alg orithm for the open vehicle routing problems.Theproposed alg orithm is a M AX2MI N Ant System hybridized with tabu search,which is im plemented in the hyper2cubeframew ork.Additionally,a post-optimization procedure is incorporated in the proposed alg orithm to further im provethe best-found s olutions.The com putational results of the proposed alg orithm com pared to those of other alg orithmsare reported.The com putation results experimentally indicate that the proposed alg orithm is an efficient method fors olving the open vehicle routing problems.K ey w ords:　open vehicle routing problem;ant colony optimization;tabu search;metaheuristic;post2optimizationprocedure1　引言开放式车辆路径问题(Open Vehicle R outing Problem,OVRP)是经典车辆路径问题(Vehicle R outing Problem,VRP)的拓展问题.OVRP和VRP最显著的区别在于:VRP中车辆路线是一个哈密尔顿巡回(Hamiltonian tour),而OVRP中,则是一个哈密尔顿路径(Hamiltonian path).这主要是由于在OVRP中,车辆在服务完最后一个顾客点后,不要求其回到出发车场,若需要回到车场,则必须沿原路返回.OVRP是配送管理中广泛存在的问题,它可以用来对很多实际应用问题来进行建模.比如一个没有自有车队的配送公司,为了完成对顾客的配送任务而将其业务分包给其它雇佣的车辆,上述问题即为一个OVRP,该问题中配送公司并不关心车辆是否回到车场(配送公司),其也不支付车辆从最后一个服务顾客点到配送公司之间的旅行费用.OVRP在现实中有很多应用,特别是在具有外包业务特点的经济活动中具有重要的应用价值,比如报纸配送、牛奶配送、校园班车问题等,在这类问题中,企业没有自己的自有车辆,而是将其配送业务外包给其它的车辆或车队,这些企业并不需要车辆在服务完顾客后回到车场点,因此如何合理的安排车收稿日期:2007201217作者简介:李相勇(1978-),男,江苏建湖人,上海交通大学安泰经济与管理学院博士研究生,研究方向:应用运筹学、智能优化算法分析与设计.28系统工程理论与实践2008年6月辆路线对于企业提高运营效率、改善顾客服务质量具有重要的价值.尽管文献中对于经典VRP进行了大量富有成效的研究工作,但是关于OVRP算法研究较少.对于OVRP,最早的文献要追溯到1981年Schrage的文章[1].从1981年开始的20多年,OVRP很少引起学者们的注意,也没有关于OVRP求解算法的论文发表.从2000年起部分学者开始研究OVRP的求解算法,并提出了如下一些算法.Sariklis和P owell[2]提出了一个求解OVRP的两阶段启发式算法,即先分组后安排路线.第一阶段分组阶段又分为两个步骤:在考虑车辆装载能力约束,顾客点首先被进行分组,然后在已经形成的分组间重新分配顾客,从而优化分组,即优化车辆路径距离.算法的第二阶段,通过求解一个最小生成树问题来将分组转化为OVRP的车辆路线.～o[3]提出了一个求解OVRP的禁忌搜索算法(T abu Search,TS).作者通过两种方法来产生初始解: Branda一个是用最近邻居法产生;一个是用K度方法(K表示车辆数的下界).在开始禁忌搜索算法之前,作者首先用两种方法来优化车辆路线距离:最近邻居法(Nearest Neighbor method)和改进的US过程(The unstringing and stringing procedure)[4].TS算法中使用了两种邻域结构:插入算子(Insert)和交换算子(S wap)来产生邻居解.在Fu等[5]、符卓[6]提出的求解OVRP的禁忌算法中,作者用两种方法来产生初始解,随机的方法和最远者优先启发式算法FFH(farthest first heuristic).FFH的基本思想是:一条新线路从离车场最远且尚未指派给任何线路的顾客点i开始.沿着从点i到车场的最短路,依次将客户分配给这条新线路(这辆车),直到车辆足够满为止;若车辆未达到足够满,则舍弃这条线路而转为尝试其次短路.重复这个过程直到一条线路被接受.算法定义了四种邻域结构:顶点重新指派、顶点交换、22opt以及“尾巴”交换.所谓顶点重新指派是指将所挑选的第一个顶点从线路上当前的位置中取出,并将其插入到所挑选的第二个顶点的位置之前.顶点交换将所挑选的两个顶点的位置互换.若所挑选的两个顶点在同一线路内,则象在TSP中标准的22 Opt一样,将所挑选的两个顶点间的所有顶点的排列顺序逆转.“尾巴”交换.若所挑选的两个顶点位于不同的线路上,则将所挑选的两个顶点后面的“尾巴”(从被选顶点至线路终点,两个顶点都必须是客户点)互换.T arantilis等[7]提出了一个求解OVRP的决策支持系统,该系统集成了地理信息系统和一个启发式算法BoneR oute[8].BoneR oute算法是一个类似于自适应记忆的算法,算法从一个解集中提取节点序列(文章中将其称为Bone),然后利用自适应记忆的方法来构造车辆路线.算法分为两个阶段:第一个阶段:P ool产生阶段(pool generation phase).该阶段首先利用加权节约算法(the weighted savings)[9]来产生一系列的初始解,然后用标准的禁忌搜索算法来改进这些解.算法第二个阶段:P ool利用阶段(P ool exploitation phase).算法从自适应记忆中选择好的节点序列来构造车辆路线,然后同样利用一个标准的禁忌搜索算法来改进这些解,最后用好的解来更新自适应记忆.作为BoneR oute局部优化算法的禁忌算法,其使用的邻域结构为:22Opt、121交换、120交换.121交换是指交换路线中的两个顾客点,这两个顾客点可以同属于一个路线或者两个不同的路线.120是指将一个顾客重新定位到另一个合适的位置(所在路线的其它位置、或者其它路线),具体内容请读者参阅文献[7].文献[10,11]提出了基于阈值接收算法(threshold accepting,T A)的启发式算法.T A算法是模拟退火算法的确定性变型算法,它同标准的模拟退火算法的不同在于:模拟退火算法以一定的概率来接受较差的解,而T A中则是通过设定一个阈值T(表示目标函数允许的增加值的上界),通过阈值来决定是否接受一个解.文献[11]提出的基于列表的T A算法(alist based threshold accepting,LBT A)则使用了一个阈值的列表,算法迭代每次则从阈值表中选择最大的元素作为阈值,算法迭代过程阈值列表不断更新.同文献[7]一样,算法也使用了局部搜索算子22Opt、121交换、120交换.OVRP的子问题是:为分配给车辆的每一组顾客点寻找最佳的哈密尔顿路径,其已经被证明为NP2hard 问题[12].因为OVRP可以转化为等价的哈密尔顿循环,所以整个OVRP也为一个NP2hard问题[3].鉴于OVRP固有的计算复杂性,在中等计算时间(m oderate com putation cost)内寻找问题的最优解变得不现实,一个比较合理的选择是采用启发式算法或者现代启发式算法来较快地产生好的解(尽管不是最优解).作为一个成功的现代启发式算法,蚁群优化算法(Ant C olony Optimization ,AC O )最早是由D orig o 等提出,AC O 是目前许多广泛应用的蚂蚁算法(Ant Alg orithm )及其变形算法的一般框架[13].自提出以来,AC O 以其作为求解组合优化问题的替代算法的巨大潜力,引起了广泛的关注,其已经被成功地用来求解了许多经典的组合优化问题的算法,比如旅行商问题、序列排序问题(sequential ordering problem )、二次指派问题(quadratic assignment problem )、Job 2shop 问题等,更详细的关于AC O 应用方面的综述,读者可以参考D orgio 和St ützle 出版的专著《Ant C olony Optimization 》[13].本文应用AC O 算法来求解OVRP ,并提出了一个集成了AC O 、禁忌搜索算法以及一个后优化过程(post optimization )的混合算法.本文的组织结构如下:第二部分详细给出了本文所提出的混合蚁群优化算法.第三部分给出算法的计算结果,同时比较了算法和文献中其它9种算法的求解质量.第四部分总结了全文并给出了一些将来的研究方向.2　求解OVRP 的蚁群优化算法211　问题定义OVRP 是经典VRP 的一个重要的松弛问题,从图论的角度,OVRP 可以表示为一个完全的赋权图,G =(V ,E ),这里V ={0,1,2,…,n }为节点集,E ={(i ,j )|i ,j ∈V ,i ≠j }为边集.0表示车场点,C ={1,2,…,n }表示顾客点集,n 为车辆服务的顾客点数目.每一条边赋有一个旅行距离d ij 或旅行费用c ij .每一个顾客点i ,有一个固定需求q i 和服务时间δi .所有车辆具有相同的最大装载能力Q 和最大允许旅行距离L (L 包括了车辆旅行距离以及对应的服务顾客点的服务时间).OVRP 问题中,每个车辆从车场出发对一组顾客点进行服务,其车辆路线开始于车场点终止于最后一个服务的顾客点,OVRP 的目标是确定一组具有最小车辆数以及最小旅行距离的哈密尔顿路径,这些车辆路线满足以下约束条件:1)车辆路线始于车场点,车辆服务完最后一个顾客点后无需回到车场点,若需要,则须沿原路返回;2)顾客点需求必须且只能由一辆车来服务完成;3)每一条车辆路线上客户点的需求量之和不超过车辆装载能力Q ;4)每一条车辆路线总的旅行距离与对应的顾客点的服务时间之和不超过车辆最大允许旅行距离L .文献中,学者们通常考虑一个层次目标函数(hierachical objectives ),即最小化车辆数作为首要优化目标,然后对应于给定的最小车辆数,最小化其车辆旅行距离,也就是说一个具有最小车辆数和较大车辆旅行距离的OVRP 解比一个具有较小车辆旅行距离和较大车辆数的OVRP 解好.在本文接下来的部分中,对于每一个蚂蚁发现的最优解通过下式最小化函数来进行适应度评价:f =M ・v +D ,f 为解所对应的总的旅行费用;v 为每个解所对应的车辆数;D 为车辆的旅行距离;M 为一个充分大的数,比如100000.通过引入参数M ,算法AC O 2OVRP 可以保证车辆数作为第一优化目标函数,在本文考虑的测试问题中,顾客点之间的旅行时间等于顾客点之间的旅行距离,顾客点服务时间和顾客点间的距离具有相同的量纲.212　蚁群优化算法概述蚁群优化算法AC O 是由D orig o 和其同事提出的受自然启发的(nature 2inspired )和基于群体(population 2bsed )的现代启发式算法[13].AC O 算法是一种受蚂蚁觅食行为启发而产生的计算范型(coputation paradigm ).自然界中,蚂蚁初始随机地搜索洞穴周围来寻找食物.当蚂蚁发现了食物回到洞穴时,会在路径上释放化学物质———信息素(pherom one ),信息素的数量依赖于所发现食物的数量和质量.在蚂蚁觅食过程中,蚂蚁在路径上释放的信息素作为蚂蚁通信和协调的媒介引导其它蚂蚁来寻找食物,那些具有较大信息浓度的路径将以较大的概率被蚂蚁在后续觅食过程中所选择.基于信息素的间接通信使蚂蚁能够发现洞穴和食物间的最短路径.生物蚁群基于信息素的简单的信息通信和正反馈,导致了复杂的群体智能(发现洞穴到食物间的最短路径)的涌现,是蚁群优化算法求解复杂组合优化问题的基础.AC O 算法的主要部分是一个由信息素迹(pherom one trail )所标定的参数概率模型,信息素模型(pherom one m odel ).在AC O 现代启发式算法中,人工蚂蚁基于信息素模型,随机地将解的组分(比如TSP 和OVRP 中为边(i ,j ))随机地添加到局部解(partial s olution )中,迭代构造求解问题的解.每个解的组分被赋有一个信息素值(pherom one value ),在算法迭代中,38第6期开放式车辆路径问题的蚁群优化算法利用蚂蚁所发现的较高质量的解来更新信息素,信息素更新的目的是使算法搜索集中于搜索空间中包含有较高质量解的区域[13].作为各种蚂蚁算法(ant alg orithm)的一般框架,AC O算法包括许多蚂蚁算法及其变形算法,比如蚂蚁系统(Ant System,AS)算法、精英蚂蚁系统(E litist Ant System,E AS)算法、等级蚂蚁系统(Rand2based Ant System,RAS)算法、蚁群系统(Ant C olony System,ACS)算法以及MAX2MI N蚂蚁系统(MAX2 MI N Ant System,M MAS)算法等.这些蚂蚁算法之间的主要区别在于:信息素的更新规则,对于详细的蚂蚁算法特征描述,感兴趣的读者可以参阅文献[13].213　求解OVRP的蚁群优化算法本文所提出的求解OVRP的AC O现代启发式算法,是一个集成了禁忌搜索算法和后优化过程的M MAS算法,且在超立方框架中执行M MAS.下文中我们简记所提出的算法为AC O2OVRP.作为对基本蚂蚁系统算法AS的改进,M MAS算法是由Stützle于1999年提出的[14],其与AS相比,通过对信息素值设置上界τmax和下界τmin来防止AS算法较早的陷入局部最优解.超立方框架(Hyper2CubeFramew ork,HCF)则是由Christian Blum提出的AC O算法的执行框架[15,16].HCF通过引入新的信息素更新规则(具体见下文)将信息素的值限制在区间[0,1]中,如文献[15]所指出的那样,在HCF中,执行AC O算法具有理论和实践价值. HCF中,对OVRP目标函数的自动标定(automatic scaling)能够降低问题维度和规模对算法参数选择和性能的影响,从而大大地提高了算法AC O2OVRP的鲁棒性.图1给出了算法AC O2OVRP的策略框架,图中使用的符号有:t:算法迭代计数器;E litist-num:使用局部搜索算法的蚂蚁数;num-iter:用来控制使用局部搜索算法的蚂蚁数目的参数;s i:蚂蚁i构造的解;s ib:算法AC O2OVRP当前代所有蚂蚁中发现的最好解;s rb:算法AC O2OVRP自重启以来所发现的最好解;s bs:算法AC O2OVRP自启动以来所发现的最好解;NU LL:表示解为空;f:OVRP的目标函数;m od:取模函数.Π3S tep1.初始化3Π初始化信息素矩阵参数设置S tep2.当算法满足终止条件时,转到Step3.否则重复执行下列过程:Π3S tep2.1确定使用局部搜索算子的蚂蚁数3Π 若m od(t,num-iter)=0且num-iter<10,则,Elitist-num=Elitist-num+1Π3S tep2.2解构造过程3Π for i=1to m 根据式(1)和(2)蚂蚁i构造解s iΠ3S tep2.3局部搜索过程3Π 确定算法当前代E litist-num个精英蚂蚁 for i=1to Elitist-num 对Elitist-num个精英蚂蚁发现的最优解使用禁忌搜索算法,进一步优化解Π3S tep2.4更新参数s ib,s rb和s b s的值3Π s ib=arg min(f(s1),f(s2),…,f(s m)) 若s rb=NU LL或f(s rb)>f(s ib),则,s rb=s ib 若s b s=NU LL或f(s b s)>f(s ib),则,s bs=s ibΠ3S tep2.5信息素更新过程3Π 根据式(3)～(6)更新信息素矩阵Π3S tep2.6收敛因子计算过程3Π 根据式(7)计算收敛因子c f的值Π3S tep2.7信息素重新初始化过程3Π 若c f≥0199,则 重置信息素值为015 s rb=NU LLΠ3S tep3.后优化过程3Π执行后优化过程进一步改进最优解S tep4.输出结果图1　算法AC O2OVRP的策略框架48系统工程理论与实践2008年6月算法AC O 2OVRP 工作流程如下.算法每一代,人工蚁群首先利用给定的信息素模型概率地构造OVRP 解,然后算法利用局部搜索算法改进部分精英蚂蚁发现的最优解解.当所有蚂蚁构造完解后,算法选择较好的解来更新信息素矩阵.算法主循环结束后,启动一个后优化过程来进一步优化算法发现的最优解.最后算法输出计算结果.下面我们详细给出算法AC O 2OVRP 的主要部分.21311　信息素初始化AC O 2OVRP 需要一个初始化的信息素矩阵来开始迭代搜索,即τ={τij },i ,j =1,2,…,n .τij 为边(i ,j )上的信息素,它表示蚂蚁在访问完顾客点i 后直接访问j 的愿望(desirability ).在M MAS 算法的原始文献中[14],为了增强算法在开始阶段的多样化探索(exploration )的能力,St ützle 将信息素值初始化为τmax .同文献[15,16]中一样,算法AC O 2OVP 的信息素都初始化为015.21312　OVRP 解的构造算法AC O 2OVRP 中,最重要的部分是其概率地构造OVRP 解的机理.在解的构造阶段,蚂蚁从节点0(车场)出发,概率地选择节点(OVRP 解的组分)添加到局部解中,直到所有的节点都包含在解中.当蚂蚁k 在顾客点i ,利用下述伪随机概率模型来选择下一个访问的顾客点j [13]:j =arg max l ∈Nki {τil },若q ≤q 0J ,否则(1)J 为基于下式概率分布利用轮盘赌方法选择的顾客点:p ij =τij ∑l ∈Nk iτil ,若j ∈N ki 0,否则(2)式中,N ki 表示所有未访问的可行顾客点j 的集合(可行顾客点插入到局部解中产生的解必须满足车辆能力Q 约束和车辆最大旅行距离L 约束).若N ki 为空集,则蚂蚁k 重新从车场点出发构造车辆路线,直到所有的顾客点都被访问完.q 为区间[0,1]上均匀分布随机数.q 0(0≤q 0≤1)为算法参数,其控制算法在集中搜索(exploitation )(exploration )之间取得平衡.由式(1)和(2)可知,蚂蚁以概率q 0从N ki 中选择具有最大信息值的顾客点j 作为下一个访问的顾客点,相反以概率1-q 0选择式(2)确定的顾客点作为下一个访问的顾客点.换句话说,算法以概率q 0利用信息素标定的学习经验来进行集中搜索,而以概率1-q 0在解空间中进行多样化搜索.21313　局部搜索大量的文献表明:在AC O 算法中,集成局部搜索算法可以提高AC O 算法的性能,获得较高质量的解[13].本节我们也考虑在算法AC O 2OVRP 中引入局部搜索算法来改进解.对于VRP 和OVRP ,禁忌搜索算法TS 已经被证明为高效的局部搜索算法,并且发现了较好的解[17],因此在图1中算法AC O 2OVRP 局部搜索阶段,我们考虑使用禁忌搜索算法.TS 是由G lover 提出的一种迭代局部搜索启发式算法[18],它利用短期或长期记忆使得算法跳出局部最优解.AC O 2OVRP 中,我们使用具有短期记忆的禁忌搜索算法.禁忌搜索算法使用的是一种典型的“侵略性”局部搜索,在算法每一代,算法探索整个搜索空间,寻求当前解x 到其邻域N (x )中最好解x ′的最好的可能移动(即使产生的邻居解x ′可能使目标函数值增加).为了避免算法迂回搜索,算法将刚刚访问的局部最优解的某些属性状态标记为禁忌,其禁忌的周期长度称为禁忌表长度,算法只接受处于非禁忌状态的移动.作为算法AC O 2OVRP 局部搜索算法的禁忌搜索算法包括以下几个重要组成部分:1)初始解:为了开始序列搜索,TS 需要产生一个初始解,初始解的产生方法有:随机产生、最近邻居法、利用其它启发式算法产生等几种方法.本文TS 作为局部搜索算法嵌入在算法AC O 2OVRP 中,因此如图1所示,算法选择的每一个使用局部搜索算法的蚂蚁所发现的最优解作为TS 算法的初始解.2)解的评价:为了增强算法AC O 2OVRP 搜索的多样性和促进在解空间的探索,算法接受任何移动(即使移动产生的解为非可行解).每一个产生的邻居解的评价基于一个新的考虑了两种惩罚项的目标函数.58第6期开放式车辆路径问题的蚁群优化算法这两个惩罚项分别度量产生的邻居解对两种约束的违背程度,即车辆装载能力和车辆最大允许旅行距离限制.算法AC O2OVRP使用了和文献[17]类似的目标函数,并且约束违背的惩罚参数动态调整.3)邻域结构:算法AC O2OVRP中执行禁忌搜索算法时,对当前解随机地使用不同的算子来产生邻居解:类22Opt和22Opt3算子[19]、交换算子(S wap operator)以及重置算子(Relocate operator).这里说的类22Opt 和22Opt3算子是指将原来针对VRP的22Opt和22Opt3算子修改为适应OVRP解特点的算子.交换算子是指交换同一条路线或两条不同路线不同位置的顾客点以寻求对解的改进.重置算子是指某一个顾客从当前位置移出,然后重新插入到解的不同位置(同一条路线的不同位置或者不同路线的不同位置).在TS执行的每一步迭代中,算法随机的选择一个算子作用于当前解以产生邻域解,为了减少算法计算时间,算法采用首次接受(First2accectp,FA)标准,即在发现第一个改进的邻居解后邻域算子停止搜索.4)禁忌对象和禁忌表:为了避免算法迂回搜索,刚刚被选择的解被禁止,置入禁忌表中.通常,对于产生一个邻居解的“改进”(m odification),将其“逆改进”设置为禁忌,并存储在禁忌表中.对于类22Opt3算子、交换算子和重置算子,“改进”定义为产生邻域解而从当前解中删除的边.而“逆改进”则定义为添加的边.对于类22Opt算子,我们定义禁忌对象为节点对,比如(i,j).对于四个不同的邻居算子,算法定义四个不同的禁忌表,相应的存储不同的禁忌对象.同文献[17]一样,这里我们也使用随机禁忌表长度,对于每一个禁忌对象其禁忌长度设置为取值于区间[θ,θ],比如[5,10]的随机整数.5)特赦标准(Aspiration criterion):在禁忌搜索算法中,可能会出现全部候选邻居解均被禁忌,或者存在一个比算法到目前为止发现的最好解更好的禁忌候选解,为了促进算法在解空间的探索,AC O2OVRP采用如下特赦准则将禁忌解解禁:若某个禁忌解优于算法到当前代为止发现的最优可行解,则解禁此候选解并选择其为算法新的当前解.在算法AC O2OVRP中,选择禁忌搜索算法作为局部搜索算法,我们需要考虑如何在解的质量和算法计算时间之间获得较好的平衡.如果在AC O2OVRP每一步迭代后,对所有蚂蚁发现的最优解都使用局部搜索算法,则计算时间将非常大.这里我们采用一种逐步增加使用局部搜索算法的蚂蚁数目的方法[14]:AC O2 OVRP首先只允许当前代最好的蚂蚁使用局部搜索算法,然后算法每隔num-iter次迭代,将使用局部搜索算法的蚂蚁数E litist-num增加1,但是其上限为10.21314　信息素更新在算法每一次迭代中,当所有蚂蚁构造完解,并且使用了局部搜索算法后,算法更新信息素矩阵.那些好解所包含的边上的信息素将得到加强,其基本的思想是:好的解所包含的信息通过信息素的量来标定,以此使得好解所包含的边将会在后续的算法迭代中受到其它蚂蚁的偏爱,即以较大的概率被蚂蚁所选择.这里,我们考虑利用三种不同的解所包含的信息来更新信息素:・s ib:算法当前迭代中所有蚂蚁中发现的最好解;・s rb:算法自重启起来所发现的最好解;・s bs:算法自启动以来所发现的全局最好解.算法AC O2OVRP首先确定边(i,j)上额外释放的信息素量.蚂蚁释放的信息素的量由下式来计算:Δτij=γ1δ(s ib,(i,j))+γ2δ(s rb,(i,j))+γ3δ(s bs,(i,j))(3)式中,γ1,γ2和γ3为三个权重参数,它标定三个不同的解在信息素更新中的相对重要性,三个权重参数满足以下条件:γi≥0(i=1,2,3)且γ1+γ2+γ3=1.函数δ(x,(i,j))定义如下:δ(x,(i,j))=1,若边(i,j)包含在解x中0,否则(4) 算法AC O2OVRP中信息素的更新规则为:τij=G mmas((1-ρ)・τij+ρ・Δτij)(5)G mmas(x)=τmin,if x<τminx,ifτmin≤x≤τmaxτmax,if x>τmax(6)68系统工程理论与实践2008年6月式中,0<ρ≤1为信息素蒸发率.1-ρ则表示边(i ,j )信息素的持久度.在式(5)和(6)所示的更新规则中,每条边(i ,j )上的信息素首先以固定的蒸发率ρ进行蒸发,然后在上述三种解对应包含的边上释放一定量的附加信息素.考虑到OVRP 中车辆路线是一个哈密尔顿路径的特点,每条路线上连接最后一个顾客点和车场点的边上面的信息素不更新,即边(i ,0),i ∈C .式(6)中,函数G m max 使得信息素的取值位于区间[τmin ,τmax ].所有边上信息素的值大于τmax ,其值被强制设为τmax ,所有边上信息素的值小于τmin ,其值被强制设为τmin .在关于M MAS 的原始文献[14]中,信息素值的上界设置为其最大值的渐进估计,即τmax =1(1-ρ)・1f (s opt ),这里f (s opt )表示最优解s opt 的目标函数值.信息素值的下界τmin 则根据上界值τmax 来设置,其值为τmax 的函数,比如τmin =12τmax.由于本文提出的算法AC O 2OVRP 是一个在超立方框架中执行的M MAS 现代启发式算法,因此信息素值的上下界分别为0和1.同文献[15]一样,在实验中我们将其值分别设置为τmax =01999和τmin =01001.如前文所述,我们考虑利用三种不同的解所提供的信息来更新信息素矩阵.s ib,s rb和s bs三者的相对重要性由式(3)中的参数γ1,γ2和γ3来标定,不同的γ1,γ2和γ3组合确定了不同的附加信息素释放值.这里我们考虑一种混合策略来动态确定s ib,s rb和s bs三者的相对重要性程度,如表1所示.表1　γ1,γ2和γ3的设置策略c f <0150150≤c f <01700170≤c f <01850185≤c f <01950195≤c f <01999γ110.70.40.10γ200.30.50.80γ30.00.10.11表1中,根据算法搜索过程中停滞的程度(extent of stagnation ),动态的调整三种不同解的相对重要性程度.这里我们定义指标收敛因子cf 来测度算法AC O 2OVRP 的收敛行为,cf 计算如式(7)所示:cf =2・∑ni =0∑nj =0max (τmax-τij ,τij -τmin )|τ|(τmax -τmin )-1(7)式中,|τ|表示信息素矩阵的大小.cf 表示收敛因子,其取值范围为cf ∈[0,1],其给出了算法搜索停滞状态的一种刻画和度量.当cf 取值接近于1时,算法陷入局部最优.当信息素值初始化为015时,cf =0,算法具有最大的多样化搜索能力.通过一些初步的实验,我们选择表1所示的设置策略.根据收敛因子的不同取值,算法动态的调整三个不同的解对信息更新的贡献程度.在迭代的早期阶段,算法当前代发现的最优解s ib 控制着信息素的更新.相反在算法的后期(接近于收敛),则s gb具有最大的贡献值.当cf ≥0199时,搜索过程的的多样性急剧下降,算法收敛于局部最优解,此时算法AC O 2OVRP 启动信息素重置过程,重新初始化信息素的值.21315　信息素重新初始化为了增强算法搜索的多样性、促进算法在搜索空间的探索,信息素不定期的被重新初始化.如图1所示当算法AC O 2OVRP 接近收敛时,比如cf ≥01999,所有边上的信息素被重新初始化为015,以增强算法在搜索空间多样化探索的能力.21316　后优化过程为了进一步优化算法发现的最优解,在我们提出的算法AC O 2OVRP 集成了一个后优化过程.如图1所示,当算法的主循环终止条件满足时,算法考虑使用一个后优化过程进一步改进算法主循环发现的最优解.这里考虑的后优化过程也是一个禁忌搜索过程,其执行过程同21313节“局部搜索”中给出的描述,我们将在下一节通过实验观察后优化过程的效应.当然我们也可以选择其它复杂的算法作为算法AC O 2OVRP 的后优化过程,比如GE NI US 算法等[17].78第6期开放式车辆路径问题的蚁群优化算法。

Optimal allocation of index positions on tool magazines using an ant colony algorithmAbstract Generation of optimal index positions of cutting tools is an important task to reduce the non-machining time of CNC machines and for achievement of optimal process plans. The present work proposes an application of an ant colony algorithm, as a global search technique, for a quick identification of optimal or near optimal index positions of cutting tools to be used on the tool magazines of CNC machines for executing a certain set of manufacturing operations. Minimisation of total indexing time is taken as the objective function.Keywords Indexing time . Automatic tool change .CNC machine . Optimization . Ant colony algorithm1 IntroductionIn today’s manufacturing environment, several industries are adapting flexible manufacturing systems (FMS) to meet the ever-changing competitive market requirements. CNC machines are widely used in FMS due to their high flexibility in processing a wide range of operations of various parts and compatibility to be operated under a computer controlled system. The overall efficiency of the system increases when CNC machines are utilized to their maximum extent. So to improve the utilization, there is a need to allocate the positions of cutting tools optimally on the tool magazines.The cutting tools on CNC machines can be changed or positioned automatically when the cutting tools are called within the part program. To do this turrets are used in CNC lathe machines and automatic tool changers (ATC) in CNC milling machines. The present model can be used either for the ATC magazines or turrets on CNC machines.The indexing time is defined as the time elapsed in which a turret magazine/ATC moves between the two neighbouring tool stations or pockets. Bi-directional indexing of the tool magazine is always preferred over uni-directional indexing to reduce the non-machining time of the machine. In this the magazine rotates in both directions to select automatically the nearer path between the current station and target station. The present work considers bi-directional movement of the magazine. In bidirectional indexing, the difference between the index numbers of current station and target station is calculated in such a way that its value is smaller than or equal to half of the magazine capacity.Dereli et al. [1] formulated the present problem as a “traveling salesman problem” (TSP), which is NP complete. They applied genetic algorithms (GA) to solve the problem. Dorigo et al. [2, 3] introduced the ant colony algorithm (ACA) for solving the NP-complete problems. ACA can find the superior solution to other methods such as genetic algorithms, simulated annealing and evolutionary programming for large-sized NP-complete problems with minimum computational time. So, ACA hasbeen extended to solve the present problem.2 MethodologyDetermination of the optimal sequence of manufacturing operations is a prerequisite for the present problem. This sequence is usually determined based on minimum total set-up cost. The authors [4] suggested an application of ACA to find the optimal sequence of operations. Once the sequence of operations is determined, the following approach can be used to get the optimal arrangement of the tools on the magazine.Step 1 Initially a set of cutting tools required to execute the fixed (optimal) sequence of the manufacturing operations is assigned. Each operation is assigned a single cutting tool. Each tool is characterized by a certain number. For example, let the sequence of manufacturing operations{M1-M4-M3-M2-M6-M8-M9-M5-M7-M10} be assigned to the set of cutting tools {T8-T1-T6-T4-T3-T7-T8-T2-T6-T5}. The set of tools can be decoded as {8-1-6-4-3-7-8-2-6-5}. Here the manufacturing operation M1 requires cutting tool 8, M4 requires 1 and so on. In total there are eight different tools and thus eight factorial ways of tool sequences possible on the tool magazine.Step 2 ACA is applied as the optimization tool to find the best tool sequence that corresponds to the minimum total indexing time. For every sequence that is generated by the algorithm the same sequence of indexpositions (numbers) is assigned. For example, let the sequence of tools {4-6-7-8-2-5-3-1} be generated and hence assigned to the indexing positions {1-2-3-4-5-6-7-8} in the sequential order, i.e. tool 4 is assigned to the 1st position, tool 6 to the 2nd position and so on.Step 3 The differences between the index numbers of subsequent cutting tools are calculated and then totaled to determine the total number of unit rotations for each sequence of cutting tools. Absolute differences are to be taken while calculating the number of unit rotations required from current tool to target tool. This following section describes an example in detail.The first two operations M1 and M4 in the pre-assumed fixed sequence of operations require the cutting tools 8 and 1, respectively. The tool sequence generated by the algorithm is {4-6-7-8-2-5-3-1}. In this sequence tools 8 and 1 are placed in the 4th and 8th indexing positions of the turret/ ATC. Hence the total number of unit rotations required to reach from current tool 8 to target tool 1 is | 4-8 |= 4. Similarly the total number of unit rotations required for the entire sequence is | 4-8 |+| 8-2 |+| 2-1 |+| 1-7 |+| 7-3 |+| 3-4 |+|4-5 |+| 5-2 |+| 2-6 |=30.Step 4 Minimization of total indexing time is taken as the objective function. The value of the objective function is calculated by multiplying the total number of unit rotations with the catalogue value of turret/ATC index time. If an index time of 4 s is assumed then the total index timerequired for the tool sequence becomes 120 s.Step 5 As the number of iterations increases ACA converges to the optimal solution.3 Allocation policyThe following are the three cases where the total number of available positions can be related with the total number of cutting tools employed.Case 1 The number of index positions is equal to the number of cutting toolsCase 2 The number of index positions is greater than the number of cutting tools (a) without duplication of tools, (b) with duplication tools Case 3 The number of index positions is smaller than the number of cutting toolsIf the problem falls into case 1, duplication of cutting tools in the tooling set is not required as the second set-up always increases the non-machining time of the machine.Table 1 List of features and their abbreviationsIn case 2, the effect of duplication of cutting tools should be tested carefully. Most of the times the duplication of tooling is too expensive. Case 3 leads to finding the cutting tools to be used in the second set-up. However, other subphases are possible in cases 2(b) and 3. The duplicated tools may be used in such a way that no unloaded index is left on ATC or some indexing positions are left unloaded.Table 2 Operations assigned to the features4 Ant colony algorithmThe ant colony algorithm (ACA) is a population-based optimization approach that has been applied successfully to solve different combinatorial problems like traveling salesman problems [2, 3], quadratic assignment problems [5, 6], and job shop scheduling problems [7]. This algorithm is inspired by the foraging behaviour of real life ant colonies in which individual ants deposit a substance called pheromone on the path while moving from one point to another. The paths with higher pheromone would be more likely to be selected by the other ants resultingin further amplification of current pheromone trails. Because of this nature, after some time ants will select the shortest path. The algorithm as applicable to the present problem is described in the following section.It is assumed that there is ‘k’ number of ants and each ant corresponds to a particular node. The number of ants is taken as equal to the number of nodes required to execute the fixed set of manufacturing operations. The task of eachant is to generate a feasible solution by adding a new cutting\ tool at a time to the current one, till all operations are completed. An ant ‘k’ situated in state ‘r’ moves to state ‘s’ using the following state transition rule:Table 3 Cutting tools assigned to optimal sequence of operationsWhere τ (r, s) is called a pheromone level. τ (r, s)’s are changed at run time and are intended to indicate how useful it is to make move ‘s’ when in state ‘r’. η(r, s) is a heuristic function, which evaluates the utility of move ‘s’ when at ‘r’. In the present work, it is the inverse of the number of unit rotations required to move from ‘r’ to ‘s’.Parameter ‘β’ weighs the relative importance of the heuristic function. ‘q’ is a value chosen randomly with uniform probability in [0,1], and ‘q0’ e0 q0 1T is a parameter. The smaller the ‘q0’, the higher the probability to make a random choice. In short ‘q0’ determines the relative importance of exploitation versus exploration in Eq. 1.Jk(r) represents the number of states still to be visited by the ‘k’ antwhen at ‘r’.S is a random variable selected according to the distribution given by Eq. 2, which gives the probability with which an ant in operation ‘r’ chooses ‘s’ to move to.This state transition rule will favour transitions towards nodes connected by short edges with high amount of trail.4.1 Local updating ruleWhile building a solution, ants change their trails by applying the following local updating rule:Where τ0 represents the initial pheromone value.4.2 Global updating ruleGlobal trail updating provides a higher amount of trail to shorter solutions. In a sense this is similar to a reinforcement learning scheme in which better solutions get a higher reinforcement.Once all ants have completed their solutions, edges (r, s) belonging to the shortest solution made by an ant have their trail changed by applying the following global updating rule.Where Lbest-iter is the best solution obtained in an iteration that has the minimum total indexing time. ‘α’ is the pheromone decay parameter, which is a value in between 0 and 1. The parameter values [3] are set as β=2, q0=0.9, and..4.3 Local search mechanismMany ant systems are hybrid algorithms employing some kind of local optimization techniques such as 2-opt technique, tabu search, simulated annealing etc. Once each ant has constructed a solution, a local search mechanism is used to further improve the solution to its localoptimum and finally the pheromone levels are updated based on its solution. This integration significantly increases the effectiveness and efficiency of ant colony algorithms. In the present work, the 2-opt technique is used as the local search.Fig. 3 Convergence of ACA5 Case studyThe example part taken for the present work is shown in Fig. 1. It contains 18 features. The features and their abbreviations are listed in Table 1. The operations required to execute the features are exhibited in Table 2. The preassumed fixed sequence of operations and the assignment of a cutting tool to each operation are shown in Table 3. The maximum number of cutting tools and the indexing time of ATC are taken as 28 and 0.69 s, respectively. The objective lies in finding the positions of cutting tools on the tool magazine for completing the sequence of operations: M1-M2-M3-M4-M5-M6-M7-M8-M9-M10-M11-M12-M13-M14-M15-M16-M17-M18-M19-M20-M21-M22-M23-M24-M25-M26-M27. The corresponding tools required to perform the above operations in the sequential order are T1-T1-T2-T3-T4-T2-T2-T2-T2-T5-T6-T5-T7-T5-T5-T8-T9-T5-T10-T5-T11-T5-T12-T5-T13-T5-T14.The total number of different tools required here are 14and hence there are 14 (!) ways of sequencing the cutting tools.The problem described here falls into case 2(a) where the total number of index positions is greater than the number of cutting tools without duplication of tools. ACA is applied to get the set of positions of cutting tools that results in the minimum total indexing time to complete the above stated fixed sequence of operations.execution time has been reduced to 14 s. It is observed that ACA gets the optimal solution in quicker time than GA. Figure 3 exhibits the convergence of ACA. The best solution obtained in each iteration is plotted against the iteration number. The optimal solution is obtained in the 10th iteration. To ensure the optimal solution, the graph is extended for a maximum of 18 iterations.7 ConclusionSince the present problem can be modeled as a traveling salesman problem, the present work deals with the development of an ACA-based system for the optimization of turret index positions of cutting tools to be used on the turret or ATC magazine of the CNC machine tools. Even asmall saving in the total turret indexing time will cause a significant increase in machining time in high-volume production. This leads to increased utilization of CNC machine tools and hence the overall efficiency of the system.References1. Dereli T, Filiz H (2000) Allocating optimal index positions ontool magazines using genetic algorithms. Robotics Auton Syst33:155–1672. Dorigo M, Maniezzo V, Colorni A (1996) The ant system: optimisation by a colony of cooperating agents. IEEE TransSyst Man Cybern 26(1):29–413. Dorigo M, Gambardella LM (1997) Ant colony system: A cooperative learning approach to the traveling salesman problem.IEEE Trans Evol Comput 1(1)53–664. Krishna AG, Rao KM (2004) Optimisation of operationssequence in CAPP using ant colony algorithm. Int J Adv Manuf Technol (in press)5. Gambardella LM, Taillard ED, Dorigo M (1999) Ant coloniesfor the QAP. J Oper Res Soc 50:167–1766. Stutzle T, Dorigo M (1999) ACO algorithms for the quadratic assignment problems. In: Corne D, Dorigo M, Glover F (eds)New ideas in optimization. McGraw-Hill, New York7. Colorni A, Dorigo M, Maniezzo V, Trubian M (1994) Ant system for job-shop scheduling. Belg J Oper Res Stat Comput Sci 34(1):39–53用蚁群算法在刀库索引位置的优化配置摘要:生成最优的索引位置切割工具是一个重要的任务，以减少非加工时间数控机床和成就的最佳工艺计划.目前的工作提出了蚂蚁的应用蚁群算法，作为一个全球性的搜索技术，为迅速确定的最优或接近最优的索引位置刀具上使用数控刀库机器执行一组特定的制造业务。

∑=nj i ijij xc1,1 解非线性方程组⎪⎩⎪⎨⎧=+++=+4222222y y x x y x2 装配线平衡模型 一条装配线含有一系列的工作站，在最终产品的加工过程中每个工作站执行一种或几种特定的任务。

装配线周期是指所有工作站完成分配给它们各自的任务所化费时间中的最大值。

平衡装配线的目标是为每个工作站分配加工任务，尽可能使每个工作站执行相同数量的任务，其最终标准是装配线周期最短。

不适当的平衡装配线将会产生瓶颈——有较少任务的工作站将被迫等待其前面分配了较多任务的工作站。

问题会因为众多任务间存在优先关系而变得更复杂，任务的分配必须服从这种优先关系。

这个模型的目标是最小化装配线周期。

有2类约束：① 要保证每件任务只能也必须分配至一个工作站来加工； ② 要保证满足任务间的所有优先关系。

例 有11件任务（A —K ）分配到4个工作站（1—4），任务的优先次序如下图。

每件任务所花费的时间如下表。

3 旅行售货员问题（又称货郎担问题，Traveling Salesman Problem ）有一个推销员，从城市1出发，要遍访城市2，3，…，n 各一次，最后返回城市1。

已知从城市i 到j 的旅费为ij c，问他应按怎样的次序访问这些城市，使得总旅费最少？可以用多种方法把TSP 表示成整数规划模型。

这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次“巡回”。

在下述意义下，引入一些0-1整数变量：ij x ⎩⎨⎧≠=其它情况，且到巡回路线是从，0,1j i j i 其目标只是使为最小。

这里有两个明显的必须满足的条件：访问城市i 后必须要有一个即将访问的确切城市；访问城市j 前必须要有一个刚刚访问过的确切城市。

用下面的两组约束分别实现上面的两个条件。

ni xnj ij,,2,1,11 ==∑=nj xni ij,,2,1,11==∑=到此我们得到了一个模型，它是一个指派问题的整数规划模型。

第一章绪论1.1仿生学的提出和发展1.1.1仿生学的提出人类发展的历史就是了解自然、认识自然、利用自然和改造自然的漫长历史过程。

在远古时期，人类生产力的水平低下，不能和自然抗争，对自然充满了畏惧和崇拜。

到了工业革命以后，人类改造自然的能力得到极大的提高，逐渐出现一种认为人类可以主宰自然、征服自然的观念，但是随着人类对大自然的肆意践踏，土地荒漠化、臭氧层空洞、洪水肆虐、物种减少、生态污染、环境恶化正严重威胁着人类自身的生存，恩格斯说过“人类战胜自然的每一次胜利，第一步都确实取得了我们预期的结果，但在第二步和第三步却有了完全不同的、出乎预料的影响”。

社会发展到今天，越来越多的人认识到人类要发展就只有尊重大自然、与大自然和睦相处，虚心向大自然学习更可以使人类受益无穷。

一个看来很丑陋的螳螂能在1/20秒的瞬间计算出飞掠眼前的小昆虫的速度，方向和距离，非常准确的一举捕获，而人类目前生产的上吨重的电子跟踪系统与之相比都显得相形见绌；苍蝇可在10-4秒量级的时间内做180°的转向，很多昆虫能在空中悬停，这些功能都是当前人造航行器和飞行器望尘莫及的；萤火虫把化学能变成光能的效率几乎达百分之百，而目前人类利用能量的效率能达到50%以上就非常了不起了。

人类进化只有500万年的历史，而自然界的生命进化已经历了35亿年的历史，在这35亿年的生命演化与协同进化的过程中，生物体在宏观与微观结构、形态与功能，能量与物质转化、代谢、利用体系，运动方式与行为，遗传、复制、发育、调控、组装的过程与机制，修复、代偿、免疫机制，脑与神经的结构和功能，感觉器官，信息传递、处理和行为调控能力，适应环境的生存能力，与其他生物相互依存和协同进化的能力等都得到了优化，将生物35亿年进化的结果作为发明的参考；将35亿年演化形成的生物多样性作为技术方案选择的宝库；将35亿年演化形成的生态协调体系作为发展生态环境协调、可持续发展技术的宝贵教材；将35亿年演化形成的生命遗传、发育体系作为自复制、自补偿、自组装、自生长、自适应、自调控技术的天然蓝本；将35亿年演化形成的免疫、抗逆、代谢、抗毒、解毒机制作为免疫、医药、治疗、抗逆技术的科学依据；将35亿年演化形成的脑与神精系统结构与功能作为认知研究和智能机器的最好示范；将35亿年演化形成的生命现象中的精妙和多样的微结构和微系统作为微、纳米结构和微系统技术的极好参照；将35亿年形成的生物高效、可再生能量存储、转化、利用体系作为优化人类可再生能源与物质利用技术的参照；将35亿年形成的生物在复杂环境中感知、判断、捕食、伪装、轨避能力和适应机制作为传感、判断、控制、隐身、环境适应等技术的最好学习对象；将35亿年演化形成的简约、优美、复杂、多样化的结构、形态，运动和变化作为数和形优美、简洁描述的最好对象已经或者即将为人类带来无穷的技术创新和发明[1]。

4.算法方面：4.1对于文中出现的NP问题，经查资料了解到的信息如下：（1）相关概念＊P: 能在多项式时间内解决的问题＊NP: 不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间验证的问题＊NPC: NP完全问题，所有NP问题在多项式时间内都能约化(Reducibility)到它的NP问题，即解决了此NPC问题，所有NP问题也都得到解决。

＊NP hard:NP难问题，所有NP问题在多项式时间内都能约化(Reducibility)到它的问题(不一定是NP问题)。

（2）四者之间的联系即P问题⊂NP问题，NPC问题⊂NP问题，NPC问题也同时⊂NP hard问题，也就是NPC问题为NP问题与NP hard问题的交集。

（3）关于NP问题的一些案例和算法思想NP是指非确定性多项式（non-deterministic polynomial，缩写NP）。

所谓的非确定性是指，可用一定数量的运算去解决多项式时间内可解决的问题。

NP 问题通俗来说是其解的正确性能够被“很容易检查”的问题，这里“很容易检查”指的是存在一个多项式检查算法。

相应的，若NP中所有问题到某一个问题是图灵可归约的，则该问题为NP困难问题。

典型案例：著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，…，等n 个城市，最后返回香港。

任意两个城市之间都有飞机直达，但票价不等。

假设公司只给报销C元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于C？迄今为止，这类问题中没有一个找到有效算法。

倾向于接受NP完全问题（NP-Complete或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。

而对于NP 问题中最难的问题--NP-complete 问题，它的定义是，如果你可以找到一个解决某个NP-complete 问题的多项式算法，那么所有的NP 问题都将可以很容易地解决。

lecture 11.American Production and Inventory Control Society（APICS）美国生产与库存控制学会2.Supply Chain Council（SCC）供应链管理委员会3.Quick response（QR）快速反应4.Universal Product Code (UPC) 通用产品编码5.Electronic Data Interchange (EDI) 电子数据交换6.Point of sale (POS) 销售终端7.Efficient Consumer Response (ECR) 有效客户反应8.Continuous Replenishment Program (CRP) 连续库存补充计划9.Distribution requirements planning (DRP) 分配需求规划10.Vendor managed inventory (VMI) 供应商管理库存11.Supply chain operations reference model( SCOR) 供应链管理的参考模型12.Management information system (MIS) 管理信息系统13.Electronic order system（EOS）电子订货系统14.Radio frequency (RF) 射频15.Bar code（BC）条形码16.Global Position System (GPS) 全球定位系统17.Geographic Information System (GIS) 地理资讯系统18.Enterprise Resource Planning (ERP) 企业资源计划19.Decision Support Systems (DSS) 决策支持系统20.Integrated information system9 (IIS) 综合信息系统21.Electronic commerce (EC) 电子商务22.Raw materials 原材料23.Finished Product成品24.Work-in-process 在制品25.Value-chain价值链26.Marketplace市场27.Manufacturer 制造商28.Supplier供应商29.Carrier承运商30.Third-party company 第三方公司rmation systems provider信息系统供应商32.Retailer零售商33.Ultimate customer 最终客户34.Internal logistics 内部物流35.External logistics 外部物流36.Third party logistics 第三方物流37.Supply chain model供应链的模式38.Agile SC 敏捷供应链39.lean SC 精益供应链40.Supply and demand management供应和需求的管理41.Procument/Purchase 采购42.Order entry订单录入43.Order processing订单处理44.Order management订单管理45.Inbound 进货46.Outbound 出货47.Distribution center配送中心48.Channel distribution渠道分销49.Delivery交货50.Assembly装配51.Conveyer 传送带52.Pallet 托盘53.Warehousing仓储54.Inventory management库存管理55.Inventory tracking库存跟踪56.In process inventory 在制品库存57.Inventory turnover 库存周转率58.Outsoucing 外包59.Production scheduling生产调度60.Customer service/logistics cost客户服务/物流成本61.Vertical integration纵向一体化62.Horizontal integration 横向一体化63.Mass production大规模生产64.Customized product定制产品65.Employee empowerment员工授权rmation sharing信息共享lecture21.Facility Location 设施定位2.Facility layout 设施布置3.Strategy level 战略层次4.Tactical level 战术层次5.Operational level 运作层6.Inventory Management 库存管理yout Planning 布置计划8.Metric 度量标准9.Vendor 供应商10.Quantity discount 数量折扣11.Minimize 最小化12.Maximum 最大化13.Simultaneously 同时地14.Intricate 复杂的15.Transportation facilities 运输设备bor supply 劳动力供应17.Raw materials 原材料18.Proximity to existing plany 靠近现存工厂19.Floor space 地面空间20.cost of installation 安装成本21.work flow 工作流22.in-process inventory 在制品库存23.Qualitative methods 定性法24.weight average method 加权平均法25.Quantitative methods 定量法26.p-Median problem p-中值问题27.p-Center problem p-中心问题28.uncapacitated facility location problem 无容量限制设施定位问题29.capacitated facility location problem 有容量限制设施定位问题30.quadratic assignment problem 二次分配问题31.Point locations 点定位32.Line locations 线定位33.Two-dimensional locations/layouts 二维定位/布置34.Three-dimensional locations/lauouts 三维定位/布置35.Euclidean Metric 欧几里得度量36.The simple plant location problem (SPLP) 简单工厂定位问题37.capacitated plant location problem 有容量限制的定位问题38.undesirable facility locations 不想要的设施定位问题39.Process layout/function layout 程序布置/功能布置40.Product layout/ flow line layout 产品布置/流水线布置41.Fixed position layout/static layout 固定的定位布局/不变的布局42.work-in-process(WIP) 进程中的工作43.Back flow 回流44.Cross flow 交叉流动/横向流动45.From-to-Charts 从制表法46.Systematic layout Planning (SLP) 彻底的布局计划47.Deployment 部署48.Positioning 位置/placement 布置49.Sitting 选址50.sitting models 选址模型work location 网络定位52.Pragmatic/real 务实的/真实的53.SIAM: Society for Industry and Applied mathematics 工业和应用数学协会54.Distribution pattern 分配结构55.Optimum location 最优定位56.Duplicating/redundant facilities 多余的设备57.Feasible location 可行的位置58.Hub 中心59.Shuttle air traffic 空运60.PCB board /printed circuit board 印刷电路板61.Concession 特许（权）62.Subcontractor 转包合同者63.Agency 机构64.Maintenance department 维修部门65.Panel 控制盘、仪表盘66.Obnoxious/unlike 令人讨厌的67.Intricate /complex 复杂的68.Site selection 地址选择69.Proximity (n)/close/nearness 接近70.Turnover or labor unrest 周转率或者劳动骚乱71.Bulky items /big or heavy 大量货物72.Foundry items 铸造73.By-products 副产品74.Sawdust 锯屑75.Ample /enough 足够的76.Rights-of-way 通行权/筑路权77.Dispersed 分散的，散布的78. A rating procedure/ evaluation procedure 路线调度work configuration 网络结构80.Supply chain design 供应链设计81.Logistics system strategy 物流系统战略82.Warehouse location 仓库定位83.Mathematical programming 数学规划84.Linear programming 线性规划85.Mixed integer programming 混合整数规划86.Heuristics 启发法87.Dynamic programming 动态规划88.Aggregate planning 整合规划89.Hierarchical sitting problems 分等级的选址问题90.Hub location problems 中心定位问题Lecture 31.tacking 堆码2.Goods stack 货垛3.Handing/carrying 搬运4.Loading and unloading 装卸Unit loading and unloading 单元装卸5.Package/packaging 包装6.Palletizing 托盘包装7.sorting 分拣8.Goods collection 集货9.Automatic warehouse 自动化仓库10.Stereoscopic [,steriə'skɔpik] warehouse 立体化仓库11.Receiving space 收货区12.Shipping space 发货区13.Goods yard 货场Goods shelf 货架14.pallet 托盘15.Fork (lift) truck 叉车16.conveyor 运送机输送带17.Automatic guided vehicle自动导引车18.Box car 箱车19.Goods shed 料棚20.Dock月台21.Pallet Jacks板台起重机22.Depth道(Lane)/ 深度23.rack货架托盘货架(Pallet Rack)24.Container集装箱/容器架子/箱子/抽屉(Shelves/Bins/Drawers)25.Barcode条形码26.Swing mast转柱式堆高机27.Storage/Retrieva存贮和拣取[ri'tri:vəl]28.Crossdocking直接换装接驳式转运（Cross Docking）/交叉配送29.repository [ri'pɔzitəri] n. 贮藏室30.consolidation[kən,sɔli'deiʃən]装运整合31.crucial ['kru:ʃiəl, 'kru:ʃəl] adj. 关键的,决定性的32.production line生产线33.category ['kætigəri] n. 种类,类别34.vehicle ['vi:ikl]车辆35.conveyor [kən'veiə]运送带36.Terminal 中转37.dispatch [dis'pætʃ] 派遣38.reorder point在订货点39.Lead time 提前期40.safety inventory安全库存41.Periodic [piəri'ɔdik] inventory周期性库存42.Perpetual [pə'petjuəl] inventory永久库存43.stocktake ['stɔkteik]盘点44.gross profit毛利45.seasonal fluctuations[,flʌktju'eiʃən] 季节波动46.crude measure 粗略计算47.coupon ['ku:pɔn] 配给票48.preceding 前面的，先前的49.FIFO 先进先出50.Holding cost 库存保持成本51.Gross Margin Return on Inventory or GMROI库存总利润回报52.inbound trucks53.Outbound trucks54.the turnaround times for customer orders(卸货加油检修及再装货所需时间)55.Receiving, sorting, storing, retrieving [ri'tri:v]检索and shipping56.delivery and pickup57.Throughput(吞吐量）58.Product damages59.Product obsolescence [,ɔbsə'lesns] n. 荒废,退化ne/ the path in one way/direction61.Trailer ['treilə] n. 追踪者,拖车62.Implication/meaning63.Lever/杠杆,途经,工具,手段64.Consolidation /the places that pickup items together 整合65.Consolidation warehouse 拼货仓库66.Literature/papers67.Overlook忽略68.Payback投资回收率69.Whereby 靠什么? 靠那个70.Less than truck-load(LTL)71.Truck-load(TL)72.Reshipment重装,转载,重装货物73.Tactical/战术上的74.Skeleton ['skelitən] /structure 框要骨架75.Stage for /plan for76.Terminal77.Break-bulk terminal分装的,分件的78.Dispatch 分发79.Constant demand一致性需求80.Forecast81.Third-party logistics provider（3PL）82.Lease/出租83.Pack/Package84.Hassle 混乱，激战85.QR86.VMI87.UPC通用产品代码88.SCOR供应链运作参考模型89.EDI90.SPLP91.POS 销售点92.UFL93.ECR94.WIP Work In Process95.CRP能力需求计划96.SLP97.DRP配送需求计划98.LTL/TLLecture 41.Space Utility 空间效用2.Time Utility 时间效用3.Utility Creation 效用创造4.Road/highway 公路5.Train/rail way 铁路6.Water way/Ocean way 水路7.Aircraft way 航空8.Pipeline way 管道9.Coupon 优惠10.seat ratio上座率11.Scale effect 规模效应12.barge 泊船13.loading capacity 装载能力14.Transit time 在途时间15.Nature of the goods 货物的性质16.Freight 运费17.rates运价18.Cost of service pricing 服务成本定价法19.Full-cost pricing 全成本定价法20.Value-of-service pricing 服务价值定价法21.The variables cost 变动成本22.The fixed cost 固定成本23.third degree price discrimination 三级价格歧视24.Differential pricing:差别定价法25.Head-haul 去程26.Backhaul 返程27.Volume 体积28.Density 密度29.Stowability积载能力30.Accessibility 获得性31.Responsiveness 响应能力32.Claims record 索赔记录33.Reliability 可获得性34.Private Fleet 私人/自营车队35.For-Hire Carriage 雇佣运输36.asset-based logistics firms 以资产为基础的物流公司37.brokers 经纪人、掮客38.Hub terminal 枢纽终端39.satellite terminal 卫星终端40.Contract negotiations 合同谈判41.Efficiency improvement改进效率42.Evaluation of customer service quality levels 客户服务水平评估43.Supervision监控44.Skill requirements 技术要求45.deregulation [di:,regju'leiʃən] 撤消管制规定46.Asset utilization 资产利用率47.terms of sale 销售条款48.credit arrangement 信贷安排49.door to door transit time门到门在途时间50.transit time reliability or consistency 在途时间可靠性和一致性51.detention charge and demurrage fee 滞留费52.Break-bulk services 散货服务53.Transit privileges 在途特权54.Product tracking产品跟踪Lecture 51.Letter of Credit（L/C，信用证）2.Revocable/ irrevocable L/C; （可取消/不可取消信用证）3.Confirmed/unconfirmed L/C;(保兑信用证和不保兑信用证)4.Transferable/untransferable L/C (可转让信用证和不可转让信用证)5.Quay crane 岸桥(QC)6.Yard crane场桥(YC)7.Yard Truck集卡(MT)8.Multi-trailer多箱拖车9.Straddle carrier叉车10.AGV自动导引车11.Automated Loft vehicle自动提升车12.Twenty-foot Equivalent Unit标箱13.Stowage planning problem装船计划问题14.Berth Allocation problem泊位分配问题15.Storage Allocation problem堆场分配问题16.QC Scheduling problem岸桥调度问题17.YT scheduling Problem集卡调度问题18.YC Scheduling problem场桥调度问题19.Vehicle Routing problem车辆调度问题20.Counter-sign确认21.Clearance 清关22.Antidumping 反倾销政策的23.An import license system 进口许可证制24.In the covering letter 说明书25.Import Quota system 进口配额制26.Call for 需要plete Set of Bills of Lading 整套提单28.Shipped on board Bill of lading 已装船提单29.Marked Freight Prepaid (or Paid) 注明运费已付30.On Deck Bill of lading 甲板货提单31.Charter party bill of lading 租船契约提单32.En route在途中33.Oncarrier转运人/ shipowner船舶所有人34.FAS(Free alongside ship) 船边交货35.CIF（Cost,Insurance,Freight) 成本+保险费+运费（到岸价）36.CFR(Cost+Freight) 成本加运费37.Licence 出口许可证38.Quota 配额39.Proforma Invoicemercial Invoice 商业发票41.Consular Invoice 领事发票42.Letter of Credit 信用证43.Draft 汇票44.Custom Document 海关单据45.Certification of Origin 产地证46.bill of lading 提单47.Packing List 装箱单48.certificate of insurance 保险单49.E&O.E. (Errors and Omissions Excepted) 有错当查50.Consignment 货物的交托, 交货51.Tariffs 关税52.Bill of Lading B/L提单53.bill of receipt 收货单pensating limitation 赔偿限额55.Shipped on Board B/L 已装船提单56.Received for shipment B/L 备运提单57.Clean B/L 清洁提单58.unclean B/L 不清洁提单59.Straight B/L 记名提单60.Open B/L 不记名提单61.order B/L 指示提单62.direct shipment B/L 直达提单63.through B/L 联运提单64.transshipment B/L 转船提单65.On Deck B/L 舱面提单/甲板货提单66.Charter Party B/L 租船提单67.Modal-transport联合运输68.through transport直达运输69.transfer transport中转运输70.containerized transport集装运输71.container transport集装箱运输72.door-to-door门到门73.International modal-transport国际多式联运nd bridge transport大陆桥运输75.full container load (FCL)整箱货76.less than container load (LCL)拼箱货77.Less than a truck load (LTL)零担78. a truck load (TL)整担79.bulk goods大件货物80.valued goods高价值的货物81.Brokers经纪人82.Agency代理人83.Association 协会84.Custom海关85.Insurance保险86.Harbor港口87.International Commercial Terms国际商务条款88.Invoice发票89.Bills of lading提单90.Contract合同91.term of payment支付条款92.charge费用93.EXW:Work/ExFactory 工厂交货94.FCA:货交承运人（指定地点）Free Carrier95.FAS:船边交货（指定装运港）96.FOB:船上交货Free On Board97.CFR(cost and freight)成本加运费价98.CIF:成本、保险加海运费COST，INSURANCE，FRIGHT99.CPT:运费付至目的地Carriage Paid To100.CIP:运费、保险费付至目的地Carriage and Insurance Paid To101.DAF:边境交货Delivered At Frontier102.DES:目的港船上交货Delivered Ex Ship103.DEQ:目的港码头交货Delivered Ex Quay104.DDU:未完税交货Delivered Duty Unpaid ,DDP:完税后交货Delivered Duty Paid 105.Obligation义务106.transfer boundary货物权的运输边界107.title权利108.price off shore离岸价109.Ex-Works price 工厂内的费用110.clear customs dues清关费111.quality inspection charges质检费112.weight measurement charges 称重费113.shipment term装运条款114.Shipped on Board装上船115.Boarded越过船舷116.pays freight货运费117.transfer expenses递送费118.collecting vehicle收集车辆119.custody 保管120.nominates 负责121.FAS(Free alongside ship)船边交货/只适用海运/水运122.inland waterway 国内水路运输123.export clearance obligation 清关责任124.vessel 大船。

开题报告课题: 基于蚁群算法路由可视化动态模拟1.选题依据（1）课题研究意义DWDM全光通信网在我国已进入了高速发展期，正向着ASON（Automatically Switched Optical Network 自动交换光网络）为代表的新一代智能化光网络的方向发展。

而智能化的动态光路由和波长分配（Routing and Wavelength Assignment, RWA）算法则是构建ASON、实现对全光网的智能化控制和管理的关键技术之一。

蚁群算法是受真实蚁群觅食行为的启发而产生的一种模拟进化算法，是由有限个蚂蚁的个体行为组成的多agent系统[1、2]，已被成功应用于解决TSP（Traveling Salesman Problem 旅行家问题）[1]、JSP（Job-shop Scheduling Problem生产排程问题）、QAP（Quadratic Assignment Problem二次指派问题）等组合优化问题。

近来已有的大量研究表明，蚁群算法具有并行性、鲁棒性、可重构性、分布性等特质。

这些特性使得蚁群算法在解决动态RWA问题中表现出优异的性能。

在网络带宽的有效利用、波长资源的合理分配、以及网络路由的重构与恢复，基于蚁群思想都能找到对应的解决方法。

相关研究工作如达到预期目标将处于国际先进水平,也必然会加快我国构建智能光网络的步伐,因此具有良好的经济效益和社会效益.（2）国内外研究现状、水平和发展趋势至今为止，国内外比较成熟的动态RWA算法都把RWA问题强行拆分成路由和波长分配两个子问题分别加以解决,如First-Fit（最先适用）算法、LLR（least-loaded routing最小负载路由）算法、LI（Least Influence最小影响）算法[3]等，并且都为集中式算法，需要利用全网信息，没有考虑波长变换，无法完成在算法层面上的网络的自动恢复，路由和波长分配独立解决也导致这些算法难以得到全局最优解。