基于禁忌搜索算法的联合运输组合优化研究

发布时间：2016-07-29 07:54

第 1 章 引言 

1.1 研究背景及意义 
去年国务院常务会议上，讨论通过了《物流业发展中长期规划（2014—2020）》，确立了建设我国现代物流服务体系的新目标，同时要求全面地提升我国物流的社会化水平及专业化水平。物流业近年来始终属于我国经济发展的基础性产业之一，而今又被提升至“战略性产业”的高度。该《规划》的相关内容自然而然地可以视为物流行业在我国国内产业地位进一步提升的重要标志。 2014 年，全年的社会物流总额超过 210 万亿元，同比增长约 8%；物流业增加值超过 3.4 万亿元，同比增长约 9%。虽然这两项指标的增速均略小于上一年，但仍然高于同期的 GDP 增速，仍属于中高速增长。社会物流总费用超过 9.7 万亿元，同比增长约 8%，增速延续小幅回落态势。社会物流总费用与 GDP  的比率约为 16.6%，与上年相比该比率略有下降（见图 1-1），这也表明物流业发展的质量和效率有所提升[1]。在我国的物流市场中，随着各方资本不断增长的大力介入，快递快运、冷链物流、物流平台、物流地产等细分市场成为投资热点；以企业为主导的技术变革加快，物流企业纷纷推出各类 App 及在线服务，并借助大数据平台提升服务质量；硬件上，自动化、智能化装备不断上线，一些企业的分拣、处理能力已经达到世界一流水平；物流的组织模式、管理模式和商业模式不断创新，货运平台、电商物流、物流金融等平台不断涌现。同时，各相关部门陆续发布了一系列支持物流业发展的政策文件，例如，发改委明确表态大力支持冷链物流、粮食物流和公共信息平台建设；商务部开展城市共同配送试点，通过加快发展共同配送，倡导连锁经营等方式，着力解决城市物流“最后一公里”难题；工业和信息化部印发推进物流信息化工作指导意见，，旨在提高全社会物流信息资源开发利用水平和物流行业的信息化水平；为打造内外资企业一视同仁、公平竞争的营商环境，国内包裹快递市场现已全面开放。  
........

1.2 国内外研究综述
本节将从对于联合运输（包括联合运输中重要的组成部分——集装箱多式联运）的基础理论研究及数学模型及其优化研究两方面进行国内外相关文献综述，后一部分又包括具有时间约束的模型研究与具有动态不确定性的联合运输问题研究。有很多研究者从不同角度对联合运输的优点进行了评价，对其组织方式、社会意义和现存问题等方面进行了基础理论的研究。 Rondinelli 和 Berry[3]探讨了推动联合运输服务和联合运输的交通基础设施的增长力，研究了运输业务对环境的主要影响，试图为防止交通运输对环境的危害提供依据。Panayides[4]详细考虑了联合运输组织环境中发生的战略变化，讨论了组织联合运输系统时对于有效性评估的经济手段的应用。Chen[5]引入模糊记分卡测量网络的 KPI，提出了一种评估联合运输供应链物流网络的实时整体性能方法。Hu[6]通过分析供应与运输的关系构建了集装箱多式联运紧急救援系统模型，讨论了在灾害救援下多式联运最优路径的选择设计和应急物流管理系统的协调运作问题。 很多国内的学者针对我国联合运输的现有水平和具体情况做出了相关研究。樊润洁[7]指出了多式联运具有常规分段独立运输方式不可比拟的优势，分析了我国联合运输目前存在的诸多落后问题，并从国外联合运输的成功经验着手，对于现阶段我国联合运输的发展提出了若干建议和措施。周勇等[8]分析了联合运输过程的一般作业流程和信息流程（见图 1-5），认为发展我国联合运输的重要任务在于技术标准的一致、运输信息系统的不断建设和相关设备工具的专业化等。傅占勇[9]对我国国际集装箱多式联运发展滞后的根源进行了探究，提出了一定的解决思路，并与湛江港口合作进行了多式联运经营全过程的探索，取得了显著成效。宋炳良[10]应用货主决策模型和概率型交通量分配模型，估算了经上海、青岛和连云港转运的全程广义运输成本，就我国东部港口之间的竞争力水平进行了实证研究。黄章黎[11]使用 SWOT 分析法对我国的联合运输发展进行了多方面的分析与总结，并提出了统筹管理运输体系、统筹规划基础建设、行业环境市场化等发展建议。 
........

第 2 章 联合运输组织过程及系统分析 

2.1 主要交通运输方式的优缺点比较 

自从 19 世纪火车与铁路在全世界得到大规模通行以来，迄今为止，铁路仍是最主要的交通运输方式之一，并且与公路运输一起，成为陆地运输中无法取代的运输方式。火车在运输领域中发挥的作用，使其重要地位在接下来很长的时间内都不可撼动。铁路运输相较其他运输方式的优点主要有： ①受气候和自然条件影响较小，且运输速度较快，可靠性高； ②运输能力及单车装载量大大，且高运输能力极大降低了单位成本； ③通用性高，几乎可以不受重量和容积的限制，能承运绝大多数商品。这一点是公路和航空运输无法比拟的。 ④燃料消耗少，污染较低。 铁路运输的主要劣势为：使用前所需的投资大，铁路的建设周期长；维修保养费用较高。当然这两点仅针对国家宏观建设而言，在具体的物流运输过程中，并不是承运人需要考虑的缺点。一般货物的出发地和铁路始发站、货物目的地和铁路终点站都是分离的，因此火车运输的灵活性不强。

.........

2.2 联合运输系统概述
联合运输网络是一个区别于其他运输系统的复杂系统，可以单独作为一个领域加以研究[37]。联合运输的核心是“一体化运输”，统筹协调不同的运输方式并加以组合。联合运输简化了托运、计费、单证、报关及保险的流程或手续。联合运输经营人负责签发全程提单，各运输区间的承运人协同处理整个运输过程[38]。 联合运输网络通常包括不同运输方式、运输线路以及中转枢纽这些核心要素。在上一小节中已经分析了不同的运输方式在速度、运输能力、运输成本、服务灵活性与可靠性等方面的特点和区别，这些区别就是选择运输方式的重要依据。例如，企业除了进出口大宗货物很多时候只能采用水路运输外，一般在较近距离的情况下通常选择公路运输作为首选方式，而对于价值高、体积小、易腐烂、客户要求迅速交货的产品则只能通过航空运输。运输线路包括公路线、铁路线、航空线、水运线等各种运输方式的线路，而出发地和目的地之间的运输路径可以由多条不同的路线组成。运输枢纽是几条运输干线交汇并且可以办理客货运输作业的地点。一般包括车站、港口、机场、仓库以及运输工具的装卸、中转、维修和物资供应的设施，用来完成货流的集散和运输方式的转换等工作。运输枢纽在交通运输网中的布局，枢纽内部各项设备的配置，各种运输方式的组织管理水平、相互协调的程度等，对整个运输网络的运输能力、效率及成本均有影响。 
.........

第 3 章 联合运输组合优化模型研究及构建 ............ 17 
3.1 问题描述与假设条件 ......... 18 
3.2  符号说明 ......... 19 
3.3  模型构建 ......... 20 
3.4  本章小结 ......... 21 
第 4 章 基于禁忌搜索算法的联合运输模型求解 .... 22 
4.1  组合优化算法概述 ............. 22 
4.2  禁忌搜索算法的基本概念与原理 ......... 23 
4.3  算法要素设计 ........... 24 
4.4  算法流程与步骤 ....... 26
4.5  本章小结 ......... 27 
第 5 章 算例仿真分析 ........ 28 
5.1  测试算例 ......... 28 
5.2  计算结果与对比分析 ......... 32 
5.3  本章小结 ......... 34 

第 4 章 基于禁忌搜索算法的联合运输模型求解 

4.1 组合优化算法概述 
组合优化问题属于最优化问题中的一类，也是运筹学的一个重要分支。最优化问题可以分为两类：一类是一定区间内连续变量的问题，即函数优化问题；另一类是解空间中的离散变量问题，即组合优化问题。组合优化问题是要在所有离散状态构成的解空间中找到最优解，使之对应的目标函数值为解空间中所有元素对应的目标函数值之中的最小（大）值。绝大多数组合优化问题都是有限问题，即解空间为有限的集合[44]。 组合优化问题涉及到的实际生产领域很广泛，在如生产管理、厂房选址、交通运输等问题中都具有广泛应用。有些组合优化问题规模较小，可以使用传统的算法来求解，例如使用单纯形法（Simplex algorithm）解决简单的线性规划问题，使用分枝定界法（Branch & Bound）或割平面法（Cutting-plane）解决整数规划以及混合整数规划问题等，使用牛顿法或共轭梯度法解决简单的非线性规划问题。但是当问题规模较大时，传统方法求解组合优化问题将变得十分繁琐甚至根本无法得到结果，因此要寻求其他的算法求解复杂的问题。 上世纪后期，出现了一些通过模拟自然界中某些现象或过程而对组合优化问题进行求解的算法，例如模拟自然选择规则和遗传学机理的遗传算法（Genetic algorithm）、基于固体的退火过程与组合优化问题之间相似性的模拟退火算法（Simulated annealing algorithm）、模拟群体中信息的社会共享优势的粒子群优化（Particle  Swarm  Optimization）算法等等，也包括本文使用的禁忌搜索算法。这些现代优化算法与现代信息技术相结合，使用电子计算机程序语言加以实现，为解决大规模的复杂优化问题提供了有效的方法和更广阔的思路。此类算法的目的并不完全是在多项式时间内求得精确的最优解，而是权衡了缩短计算时间和得到最好解这两个方面，最终比较迅速地获得近似的最优解或满意解。当使用这些优化算法进行求解时，往往要根据具体问题进行算法的参数或其他一些因素的设计；而这些基于直观或经验构造的算法，也往往被称为启发式算法（heuristic algorithm）。 
.......

总结 

联合运输是当代物流运输业发展的大势所趋，凭借其节约成本、合理组织、时效性强、手续简便等优势，成为目前交通运输行业最重要的运输方式之一。由于联合运输涉及到的因素较多，且其中很多难以界定和量化，因此尚无通用的模型和算法，仍有很多问题值得探究。  本文的研究工作总结如下： 
（1）通过对国内外文献的查阅与综述，了解了联合运输问题的国内外研究现状，其中重点是学者们对联合运输问题的数学模型与算法及其优化的研究。由于联合运输涉及到的因素较多，且其中很多难以界定和量化，因此尚无通用的模型和算法，仍有很多问题值得探究。  
（2）比较不同运输方式的不同技术经济特点，综合分析了联合运输的优势、组织形式及影响因素等。 
（3）将联合运输问题与传统旅行商问题加以结合，在各城市均有货物需求且到达顺序不固定的情况下，设置了同时包含运输顺序、前后两段运输方式的 0-1决策变量，构建了以总成本最小为目标函数的组合优化数学模型；在约束条件中对运输总时间以及各个城市不同运输方式的运输能力加以约束。 
（4）设计了基于禁忌搜索算法的启发式算法用来求解本文提出的组合优化问题，提出了将目标函数值、禁忌对象、城市访问顺序以及对应的运输方式等元素直接排列的解的编码方式。该算法解的表达直观简便、算法策略易于理解。随后通过仿真算例对问题进行求解，结果表明该算法对类似的联合运输组合优化问题求解效果良好。 
.........
参考文献(略)

本文编号：78070