求解煤炭水运配船的免疫优化算法

煤炭水运配船属于多约束混合整数线性规划问题。当问题规模大、约束条件多时很难获得最优解,并且求解时间过长。针对上述问题,提出一种基于免疫克隆算法的求解方案。通过构建相应的数学模型,设计了基于二维矩阵的抗体表示形式和混合整数编码方式,构造了罚函数处理不等式约束。算法使用克隆、变异和抗体浓度抑制等免疫操作,保持了抗体的多样性,避免陷入局部最优。算法仿真表明,该算法在全局最优解和运行速度方面优于遗传算法,优化结果验证了算法的有效性。     

Efficient multiple objective optimal control of dynamic systems with integer controls

In practical optimal control problems both integer control variables and multiple objectives can be present. The current paper proposes a generic and efficient solution strategy for these multiple objective mixed-integer optimal control problems (MO-MIOCPs) based on deterministic approaches. Hereto, alternative scalar multiple objective optimisation techniques as normal boundary intersection and normalised normal constraint are used to convert the original problem into a series of parametric single objective optimisation problems. These single objective mixed-integer optimal control problems are then efficiently solved through direct multiple shooting techniques which exploit convex relaxations of the original problem. Moreover, these relaxations enable to quickly approximate the final solution to any desired accuracy (without the need of solving integer problems). Consequently, the set of Pareto optimal solutions of the MO-MIOCP can be accurately obtained in highly competitive computation times. The proposed method is illustrated on (i) a testdrive case study with a complex car model which includes different gears and conflicting minimum time–minimum fuel consumption objectives, and (ii) a jacketed tubular reactor case study with conflicting conversion, heat recovery and installation costs.     

A Branch and Bound Algorithm for Bi-level Discrete Network Design Problem

Discrete network design problem (DNDP) is generally formulated as a bi-level programming. Because of non-convexity of bi-level formulation of DNDP which stems from the equilibrium conditions, finding global optimal solutions are very demanding. In this paper, a new branch and bound algorithm being able to find exact solution of the problem is presented. A lower bound for the upper-level objective and its computation method are developed. Numerical experiments show that our algorithm is superior to previous algorithms in terms of both computation time and solution quality. The conducted experiments indicate that in most cases the first incumbent solution which is obtained within a few seconds is superior to the final solution of some of previous algorithms.     

连锁门店选址与配送中心选择联合决策的f-MIGP模型

建立了连锁门店选址和配送中心选择联合决策问题的模糊多目标混合整数规划模型．针对该模型的特殊结构。提出一种适用的求解策略：首先确定每个模糊目标的隶属度函数;然后将模糊多目标混合整数规划模型转化为等价的清晰多目标混合整数规划模型,通过最大最小算子求出目标值;最后借助于两阶段算法,求出问题的最优解．通过应用算例进一步说明了该模型的有效性和可行性．     

考虑堆场缓冲区容量的ASC与AGV集成调度

为提高自动化集装箱码头作业效率,针对卸船过程中自动化堆垛起重机(Automated Stacking Crane,ASC)与自动化导引小车(Automated Guided Vehicle,AGV)的集成调度问题,考虑缓冲区容量约束,以最小化总任务完成时间和总任务延迟时间为目标,建立带时间窗的混合整数规划模型,确定任务与缓冲位的分配关系,优化ASC的作业顺序。对比实验分析表明,在大规模算例上,遗传算法的目标函数值逐渐优于分支定界法,且遗传算法能在有限时间求出理想解,验证模型和算法的有效性。灵敏度实验分析表明,ASC作业时间的增加对总任务延迟时间有显著影响,总任务延迟时间的快速增加引起目标函数值的快速增加。     

Analysis of the single-vehicle cyclic inventory routing problem

The single-vehicle cyclic inventory routing problem (SV-CIRP) consists of a repetitive distribution of a product from a single depot to a selected subset of customers. For each customer, selected for replenishments, the supplier collects a corresponding fixed reward. The objective is to determine the subset of customers to replenish, the quantity of the product to be delivered to each and to design the vehicle route so that the resulting profit (difference between the total reward and the total logistical cost) is maximised while preventing stockouts at each of the selected customers. This problem appears often as a sub-problem in many logistical problems. In this article, the SV-CIRP is formulated as a mixed-integer program with a nonlinear objective function. After a thorough analysis of the structure of the problem and its features, an exact algorithm for its solution is proposed. This exact algorithm requires only solutions of linear mixed-integer programs. Values of a savings-based heuristic for this problem are compared to the optimal values obtained for a set of some test problems. In general, the gap may get as large as 25%, which justifies the effort to continue exploring and developing exact and approximation algorithms for the SV-CIRP.     

Algorithms for determining capacities of individual buffers in assembly/disassembly systems

We deal with a buffer allocation problem of assembly/disassembly (AD) systems with a finite buffer capacity. The problem is to determine capacities of individual buffers for a given total available capacity of buffers with the objective of maximizing throughput rate. We first present an algorithm (BA-G) in which a conventional gradient search is used for finding an initial solution and a two-optimization procedure is used for improving the initial solution. Since this algorithm may require an excessive computation time, especially when a procedure for performance evaluation employed in the algorithm takes a long computation time, a new algorithm (BA-P) is developed in which a sophisticated procedure is used for finding an initial solution. In this procedure, capacities of individual buffers are determined based on the efficiency of their upstream and downstream machines. Results of computational experiments show that the latter algorithm gives the same solutions as those obtained by the former algorithm in much shorter time.     

Multi-objective biogeography-based optimization for supply chain network design under uncertainty

This paper proposes a new two-stage optimization method for multi-objective supply chain network design (MO-SCND) problem with uncertain transportation costs and uncertain customer demands. On the basis of risk-neutral and risk-averse criteria, we develop two objectives for our SCND problem. We introduce two solution concepts for the proposed MO-SCND problem, and use them to define the multi-objective value of fuzzy solution (MOVFS). The value of the MOVFS measures the importance of uncertainties included in the model, and helps us to understand the necessity of solving the two-stage multi-objective optimization model. When the uncertain transportation costs and customer demands have joined continuous possibility distributions, we employ an approximation approach (AA) to compute the values of two objective functions. Using the AA, the original optimization problem becomes an approximating mixed-integer multi-objective programming model. To solve the hard approximating optimization problem, we design an improved multi-objective biogeography-based optimization (MO-BBO) algorithm integrated with LINGO software. We also compare the improved MO-BBO algorithm with the multi-objective genetic algorithm (MO-GA). Finally, a realistic dairy company example is provided to demonstrate that the improved MO-BBO algorithm achieves the better performance than MO-GA in terms of solution quality.     

A parametric branch and bound approach to suboptimal explicit hybrid MPC

In this article we present a parametric branch and bound algorithm for computation of optimal and suboptimal solutions to parametric mixed-integer quadratic programs and parametric mixed-integer linear programs. The algorithm returns an optimal or suboptimal parametric solution with the level of suboptimality requested by the user. An interesting application of the proposed parametric branch and bound procedure is suboptimal explicit MPC for hybrid systems, where the introduced user-defined suboptimality tolerance reduces the storage requirements and the online computational effort, or even enables the computation of a suboptimal MPC controller in cases where the computation of the optimal MPC controller would be intractable. Moreover, stability of the system in closed loop with the suboptimal controller can be guaranteed a priori.     

基于免疫克隆选择算法的混合流水车间调度问题的研究

本文针对混合流水车间调度问题,以最大流程时间最小为目标函数,建立了混合整数数学规划模型;将具有解决复杂组合优化问题的免疫克隆选择算法（ICA）应用于求解混合流水车间调度问题,详细描述了ICA算法求解HFSP问题的步骤;为了验证算法的有效性,仿真对比了遗传算法和ICA算法的性能,与文献结果比较,结果表明ICA算法求解HFSP问题可行性和有效性。     

Multiple- and single-objective approaches to laminate optimization with genetic algorithms

In this paper an application of a genetic algorithm to a material- and sizing-optimization problem of a plate is described. This approach has obvious advantages: it does not require any derivative information and it does not impose any restriction, in terms of convexity, on the solution space. The plate optimization problem is firstly formulated as a constrained mixed-integer programming problem with a single objective function. An alternative multiobjective formulation of the problem in which some constraints are included as additional objectives is also presented. Some numerical results are included that show the appropriateness of the algorithm and of the mathematical model for the solution of this optimization problem, as well as the superiority of the multiobjective approach.     

Optimal replenishment policies for the case of a demand function with product-life-cycle shape in a finite planning horizon

In this paper, we explore the demand function follows the product-life-cycle shape for the decision maker to determine the optimal number of inventory replenishments and the corresponding optimal inventory replenishment time points in the finite planning horizon. The objective function of the total relevant costs considered in our model is mathematically formulated as a mixed-integer nonlinear programming problem. A complete search procedure is provided to find the optimal solution by employing the properties derived in this paper and the Nelder–Mead algorithm. Also, based on the search procedure developed in this paper, a decision support system is implemented on a personal computer to solve the proposed problem.     

An improved hybrid particle swarm optimization algorithm for fuzzy p-hub center problem

The p-hub center problem is useful for the delivery of perishable and time-sensitive system such as express mail service and emergency service. In this paper, we propose a new fuzzy p-hub center problem, in which the travel times are uncertain and characterized by normal fuzzy vectors. The objective of our model is to maximize the credibility of fuzzy travel times not exceeding a predetermined acceptable efficient time point along all paths on a network. Since the proposed hub location problem is too complex to apply conventional optimization algorithms, we adapt an approximation approach (AA) to discretize fuzzy travel times and reformulate the original problem as a mixed-integer programming problem subject to logic constraints. After that, we take advantage of the structural characteristics to develop a parametric decomposition method to divide the approximate p-hub center problem into two mixed-integer programming subproblems. Finally, we design an improved hybrid particle swarm optimization (PSO) algorithm by combining PSO with genetic operators and local search (LS) to update and improve particles for the subproblems. We also evaluate the improved hybrid PSO algorithm against other two solution methods, genetic algorithm (GA) and PSO without LS components. Using a simulated data set of 10 nodes, the computational results show that the improved hybrid PSO algorithm achieves the better performance than GA and PSO without LS in terms of runtime and solution quality.     

Determining the prices of remanufactured products,capacity of internal workstations and the contracting strategy within queuing framework

This paper studies a remanufacturing facility with several types of incoming nonconforming products and different independent remanufacturing workstations. The workstations have limited capacities so that an outsourcing strategy can be practiced. Each workstation is modeled with an M/M/1/k queuing system considering k as a decision variable. Additionally, a binary decision variable is taken into account to determine the contracting strategy along with some decision variables for the prices of remanufactured products. Thus, a bi-objective mixed-integer nonlinear programming is built to obtain optimal values of the decision variables. The first objective attempts to maximize the total profit and the second minimizes the average length of queuing at workstations. To solve the complex bi-objective mixed-integer nonlinear programming problem, the best out of six multi-objective decision-making (MODM) methods is selected in order to make the bi-objective optimization problem a single-objective one. Afterward, a genetic algorithm (GA) is developed to find a near-optimum solution of the single-objective problem. Besides, all of the important parameters of the algorithm are calibrated using regression analysis. To validate the results obtained, the solutions of some test problems are compared to the ones obtained by the GAMS software. The applicability of the proposed model and the solution procedure are shown with an illustrative example.     

The center location-dependent relocation problem with a probabilistic line barrier

This paper presents a new mixed-integer nonlinear programming (MINLP) for a multi-period rectilinear distance center location-dependent relocation problem in the presence of a probabilistic line-shaped barrier that uniformly occurs on a given horizontal route. In this problem, the demand and location of the existing facilities have a dynamic nature and the relocation is dependent to the location of new facilities in previous period. The objective function of the presented model is to minimize the maximum expected weighted barrier distance between the new facility and the existing facilities during the planning horizon. The optimum solution of small-sized test problems is obtained by the optimization software. For large-size test problems which the optimization software is unable to find the optimum solution in the runtime limitation, two meta-heuristics based on the genetic algorithm (GA) and imperialist competitive algorithm (ICA) are applied. To validate the meta-heuristics, a lower bound problem based on the forbidden region instead of the line barrier is generated. Related results of numerical experiments are illustrated and are then compared.     

A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents

This paper addresses a two-agent scheduling problem on a single machine where the objective is to minimize the total weighted earliness cost of all jobs, while keeping the earliness cost of one agent below or at a fixed level Q. A mixed-integer programming (MIP) model is first formulated to find the optimal solution which is useful for small-size problem instances. To solve medium- to large-size problem instances, a branch-and-bound algorithm incorporating with several dominance properties and a lower bound is then provided to derive the optimal solution. A simulated annealing heuristic algorithm incorporating with a heuristic procedure is developed to derive the near-optimal solutions for the problem. A computational experiment is also conducted to evaluate the performance of the proposed algorithms.     

Combining DC-programming and steepest-descent to solve the single-vehicle inventory routing problem

The single-vehicle cyclic inventory routing problem (SV-CIRP) is concerned with a repeated distribution of a product from a single depot to a selected subset of retailers having stable demands. If a retailer is selected for replenishment, the supplier collects a retailer-related fixed reward. The objective is to determine the subset of retailers to cyclically replenish, the quantities to be delivered to each, and to design the vehicle delivery routes so that the expected total distribution and inventory cost is minimized while the total collected rewards from the selected retailers is maximized. The resulting distribution plan must prevent stockouts from occurring at each retailer. In this paper, the underlying optimization problem for the SV-CIRP is formulated as a mixed-integer program with linear constraints and a nonlinear objective function. An optimization approach combining DC-programming and Branch-and-Bound within a steepest descent hybrid algorithm, denoted by DCA-SDHA, is developed for its solution. The approach is tested on some randomly generated problems and the obtained results are compared with results from the standard steepest descent hybrid algorithm (SDHA). These encouraging results show that the proposed approach is indeed computationally more effective and is worth being further investigated for the solution of medium to large instances.     

A modified genetic algorithm for the flow shop sequencing problem to minimize mean flow time

A modified genetic algorithm (MGA) is developed for solving the flow shop sequencing problem with the objective of minimizing mean flow time. To improve the general genetic algorithm (GA) procedure, two additional operations are introduced into the algorithm. One replaces the worst solutions in each generation with the best solutions found in previous generations. The other improves the most promising solution, through local search, whenever the best solution has not been updated for a certain number of generations. Computational experiments on randomly generated problems are carried out to compare the MGA with the general GA and special-purpose heuristics. The results show that the MGA is superior to general GA in solution quality with similar computation times. The MGA solutions are also better than those given by special-purpose heuristics though MGA takes longer computation time.     

A heuristic algorithm based on Lagrangian relaxation for the closest string problem

The closest string problem that arises in both computational biology and coding theory is to find a string minimizing the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristic algorithm for this NP-hard problem. The key idea is to apply the Lagrangian relaxation technique to the problem formulated as a mixed-integer programming problem. This enables us to decompose the problem into trivial subproblems corresponding to each position of the strings. Furthermore, a feasible solution can be easily obtained from a solution of the relaxation. Based on this, a heuristic algorithm is constructed by combining a Lagrangian multiplier adjustment procedure and a tabu search. Computational experiments will show that the proposed algorithm can find good approximate solutions very fast.     

Solving cold-standby reliability redundancy allocation problems using a new swarm intelligence algorithm

A powerful new hybrid algorithm based on Simplified Swarm Optimization (SSO), Elite Selection and Boundary Search (BS), called the SEB, is proposed for solving the cold-standby reliability redundancy allocation problem (RRAP). The RRAP is a famous mixed-integer nonlinear programming problem in system design that requires that the reliability objective be set to satisfy the resource consumption constraint. In order to balance the exploration and exploitation abilities, the proposed SEB implements a new SSO to update the solutions, an elite selection is performed to select the solutions for subsequent iterations, and the new BS improves the best solution. The performance of the proposed SEB is evaluated by comparing the results with those obtained using existing algorithms and three RRAP benchmark problems taken from the literature.