【作者】 姜伟；

【导师】 唐立新；

【作者基本信息】 东北大学 ， 物流优化与控制， 2012， 博士

【摘要】 随着国民经济的快速增长、生产规模的不断扩大以及电子商务的高速发展,产品和商品的物流量显著增长,迫切需要对物流进行科学规划和统筹管理。本文分别从物流设施选址设计和物流作业管理两个层面进行了建模优化研究。对物流设施选址进行科学规划和设计将有利于物流的集中管理,从而提高物流服务水平、减少设施冗余和降低物流成本；而对于已建物流设施的作业进行精细化管理将提高物流设施运行效率,进一步减少物流作业成本和提高服务水平。本文以某资源型城市的物流设施选址设计为背景,针对带有已有物流设施能力扩充的物流设施选址问题和两阶段有能力约束的物流设施选址设计问题,分别从模型描述、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)针对码头堆场出港集装箱的箱位分配问题进行研究。出港集装箱的箱位分配问题是指当出港集装箱由外部卡车运到堆场时怎样分配存储位置以便提高装船效率。在对出港箱按属性分类和定义组、簇、批概念的基础上,从新的视角重新对出港集装箱的箱位分配问题进行建模,实现从优化物流输入环节来减少装船时倒垛数的目的。对该问题以装船时各街区箱量均衡、集卡运输距离最短和装船时必要倒垛次数最少为目标建立非线性整数规划模型。利用等价变换将该模型转化为标准优化软件可直接求解的线性模型,并实例验证模型的有效性。更多还原

【Abstract】 With the rapaid growth of the national economy, the continual expansion of the production scale and the rapaid development of e-commerce, the logistics volume of products and goods is significantly increasing, and thus it is urgent to make scientific planning and integrated management for the logistics. In this paper, the research on the modelling and optimization methods respectively for the design of facilities and the management of logistics operations is made. The scientific design for facilities will favor the centralized management, and thus improving service levels, reducing facility redundancy and the logistics cost. The fine management for the logistics operations of the existing facilities will improve the operation efficiency of the facilities, which will further reduce the logistics cost and enhance service levels.In this paper, taking the design of the facilities for a domestic resource-based city as background, the research on the facility location problem with capacity expansions of the existing facilities and the two-stage capacitated facility location problem is conducted in the way of modelling description, the design of Benders decomposition algorithm and some acceleration strategies of it; taking the logistics operations in container terminals as background, the research on the static reshuffling problem, dynamic stacking and reshuffling problem and the slot allocation problem of outbound containers in terminal yards is conducted in the way of modelling description, model improvement, algorithm design and animation simulation. The main contents of dissertation are summarized as follows:1) For the fault that the densities of the Pareto optimal cuts is low produced by the improved Benders decomposition algorithm to not restrict the solution space of the master problem effectively, a high density Pareto cut generation method which lifts the primal Benders cut to be closer to the convex hull constructed by the integer solutions of the master problem is proposed. The high density Pareto cut overcomes the weakness of the Pareto optimal cut which density is low, lifts the Pareto optimal cut, accelerate the solution speed of the master problem, and thus achieve the acceleration of the algorithm. This method is an optimization algorithm. At the same time, a fast approximate algorithm called TS&Benders hybrid algorithm is proposed.2) The facility location problem with the capacity expansions of the existing facilities is investigated. Compared with the ordinary facility location problem, the main feature of the problem is to consider the operation state of the existing facilities when selecting the establishment of new facilities, and the whole problem needs to find a tradeoff among opening, closing, expanding the existing facilities and establishing new facilities to minimize the total cost of the system. For this problem, a mixed-integer programming model is built, and Benders decomposition algorithm is applied. At the same time, three acceleration techniques of the Benders decomposition algorithm are proposed:(1) valid inequalities;(2) disaggregated cuts produced by separating the subproblem;(3) high density Pareto cut and a hybrid technique. The experimental results show that the combination of all the valid inequalities is the most effective to improve the lower bounds. The disaggregated cuts obtained by variable separation and facility separation have the best performance among all the types of the disaggregated cuts. The high density Pareto cut generation method has significant improvement for some instances where the number of iterations is relatively intensive and the CPU time is longer, and the hybrid technique has the best average performance. Compared to the standard Benders algorithm and optimization solver CPLEX, the improved Benders decomposition algorithm is advantageous in decreasing the total number of iterations and CPU time, especially for large-scale instances.3) TS&Benders hybrid algorithm is investigated based on the two-stage capacitated facility location problem. The two-stage capacitated facility location problem is to determine selecting which candidate facilities to open to minimize the sum of the the fixed setup costs and the transportation costs. To overcome the shortcoming that the solution speed of the master problem is slow, Tabu search algorithm is applied to solve the master problem to obtain an approximate solution to improve the speed of the Benders decomposition algorithm. The experimental results show that TS&Benders hybrid algorithm can obtain an approximate-optimal solution in a short time.4) The static reshuffling problem and the dymamic stacking and reshuffling problem in terminal yards are investigated. The static reshuffling problem is how to determine the storage locations of the reshuffled containers so that the total number of reshuffles is minimized when the configuration of a bay is given and all the containers are pickup according to their pickup priorities. For the static reshuffling problem, the existing model is improved and five polynomial-time heuristic algorithms and their extended versions are proposed to solve it, and their performance is analyzed from theory aspect. For the dynamic stacking and reshuffling problem, the proposed heuristic algorithms in the static situation and the heuristic algorithms based on the improved model are applied to the dynamic situation by some transformation, and a discrete-event simulation model is developed to simulate the different algorithms and display the animation. The experimental results show that the improved model can quickly obtain optimal solutions or feasible solutins compared with the existing model, and the performance of the five developed heuristics and their extended versions are superior to the existing heuristics and their extended versions, respectively.5) The slot allocation problem of outbound containers in terminal yard is investigated. The solt allocation problem of outbound containers is how to allocate the storage locations of outbound containers to improve the efficiency of loading when they are transported to the yard by external trucks. Based on the classification of outbound containers and the definitions of group, family and batch, remodel the slot allocation problem for outbound containers from a new perspective to achieve reducing the number of reshuffles when loading by controlling the input operations of logistics. The problem is formulated by a nonlinear integer programming model to balance the workloads among blocks, and the objective is to minimize the transportation distance of internal trucks and the number of confirmed reshuffles when loading. Through the equivalent transformation, convert the model to a linear model that can be directly solved by the standard optimization software CPLEX, and then verify the validity by a specific case.更多还原