物流设施选址设计与集装箱堆场物流作业建模优化

摘要

随着国民经济的快速增长、生产规模的不断扩大以及电子商务的高速发展，产品和商品的物流量显著增长，迫切需要对物流进行科学规划和统筹管理。本文分别从物流设施选址设计和物流作业管理两个层面进行了建模优化研究。对物流设施选址进行科学规划和设计将有利于物流的集中管理，从而提高物流服务水平、减少设施冗余和降低物流成本;而对于已建物流设施的作业进行精细化管理将提高物流设施运行效率，进一步减少物流作业成本和提高服务水平。
　　本文以某资源型城市的物流设施选址设计为背景，针对带有已有物流设施能力扩充的物流设施选址问题和两阶段有能力约束的物流设施选址设计问题，分别从模型描述、Benders分解算法设计及其改进策略等方面进行了研究;以集装箱堆场物流作业为背景，针对集装箱码头堆场中的静态倒垛问题、动态堆垛和倒垛问题以及出港集装箱箱位分配问题，分别从模型描述、模型改进、算法设计及动画仿真等方面进行了研究。主要工作概述如下:
　　1)针对改进Benders分解算法产生的Pareto最优cut密度低、不能有效地限制主问题解空间而导致算法收敛慢的缺点，提出高密度Pareto cut产生方法对Pareto最优cut进行升维，使其更好地逼近主问题整数解的凸包。高密度Pareto cut通过尽可能多的覆盖主问题的决策变量，克服了Pareto最优cut密度低的缺点，提升了Pareto最优cut的维数，加快了主问题的求解速度，从而达到了加速算法收敛的效果。该方法是一种最优算法。同时，提出一种用于快速近似求解的禁忌搜索和Benders分解混合算法（简称为TS&Benders混合算法）。
　　2)针对带有已有物流设施能力扩充的物流设施选址问题进行研究。该问题与通常的物流设施选址问题相比，主要特点是在选择新建物流设施时，同时考虑了已有物流设施的运行状态，整个问题需要在已有物流设施的开放、关闭、扩充以及候选物流设施的建立间作出权衡来实现整个系统的总费用最小。对该问题建立混合整数规划模型，并构造Benders分解算法对其进行求解，同时提出加速Benders分解算法收敛的三种改进策略:(1)有效不等式;(2)分离子问题产生不聚合cut;(3)高密度Pareto cut和一种混合策略。实验结果表明，所有有效不等式的组合能有效提升下界;在所有类型的不聚合cut中，基于变量分离和设施分离的不聚合cut的效果最好;高密度Paretocut产生方法对迭代次数多和求解时间长的实例具有明显改进，混合策略具有最好的平均性能。与基本Benders分解算法和优化软件CPLEX相比，改进的Benders分解算法能有效减少迭代次数和CPU运行时间，特别是对大规模的实例。
　　3)针对两阶段有能力约束的设施选址设计问题，研究TS&Benders混合算法。两阶段有能力约束的设施选址设计问题是在供应商的供货能力、客户的需求和候选物流设施的能力已知的情况下来决策选择开放哪些设施使得建设费用和运输费用之和最小。针对Benders分解的主问题求解慢的缺点，采用禁忌搜索算法快速求解主问题获得近优解来改进Benders分解算法的求解速度。实验结果表明TS&Benders混合算法可以在较短的时间内获得问题的近优解。
　　4)针对集装箱堆场静态情况下的倒垛问题和动态情况下的堆垛与倒垛问题进行研究。静态倒垛问题是指在一个贝位的堆垛状态给定的情况下将贝位中所有集装箱按离开时间的先后顺序依次取出的过程中怎样决策倒垛箱的存储位置使得总倒垛数最少。动态堆垛和倒垛问题是指当一个贝位中不断有集装箱存入和离开的情况下，怎样决策新进箱的堆垛位置和倒垛箱的倒垛位置使得所考虑时段内的总倒垛数最少。针对静态倒垛问题，改进已有的数学模型，并提出五个多项式时间启发式算法及其扩展版本对其进行求解，同时对启发式算法性能进行理论分析。针对动态堆垛和倒垛问题，通过变换将静态情况下提出的启发式算法及基于改进模型的启发式算法应用到动态情况中，并开发基于离散事件的仿真模型对各种算法进行仿真和动画演示。实验结果表明，与已有模型相比，改进的模型可以更快地获得问题的最优解或可行解。提出的启发式算法及其扩展版本的性能分别优于已有的启发式算法及其扩展版本的性能。
　　5)针对码头堆场出港集装箱的箱位分配问题进行研究。出港集装箱的箱位分配问题是指当出港集装箱由外部卡车运到堆场时怎样分配存储位置以便提高装船效率。在对出港箱按属性分类和定义组、簇、批概念的基础上，从新的视角重新对出港集装箱的箱位分配问题进行建模，实现从优化物流输入环节来减少装船时倒垛数的目的。对该问题以装船时各街区箱量均衡、集卡运输距离最短和装船时必要倒垛次数最少为目标建立非线性整数规划模型。利用等价变换将该模型转化为标准优化软件可直接求解的线性模型，并实例验证模型的有效性。