The heterogeneous vehicle routing and truck scheduling problem in a multi-door cross-dock system

Cross-docking is a logistics technique applied by many industrial firms to get substantial savings in two warehousing costly functions like storage and order picking. Incoming shipments are unloaded from inbound trucks on a cross-dock terminal with minimal storage space and directly transferred to outbound vehicles that carry them to their destinations. The major decisions at the operational level are the vehicle routing and scheduling, the dock door assignment and the truck scheduling at the cross-dock. Because such decisions are interdependent, all of them are simultaneously considered in the so-called vehicle routing problem with cross-docking (VRPCD). Previous contributions on VRPCD assume that pickup and delivery tasks are accomplished by a homogeneous vehicle fleet, and they mostly ignore the internal transportation of goods through the cross-dock. This work introduces a new rigorous mixed-integer linear programming (MILP) formulation for the VRPCD problem to determine the routing and scheduling of a mixed vehicle fleet, the dock door assignment, the truck docking sequence and the travel time required to move the goods to the assigned stack door all at once. To improve the computational efficiency of the branch-and-cut search, an approximate sweep-based model is developed by also considering a set of constraints mimicking the sweep algorithm for allocating nodes to vehicles. Numerous heterogeneous VRPCD examples involving up to 50 transportation requests and a heterogeneous fleet of 10 vehicles with three different capacities were successfully solved using the proposed approaches in acceptable CPU times.     

A sweep-heuristic based formulation for the vehicle routing problem with cross-docking

Cross-docking is a warehousing strategy in logistics used by process industries making products with high proportions of distribution costs. It is described as the process of moving goods from suppliers to customers through a cross-dock terminal without a long-term storage in this facility. The vehicle routing problem with cross-docking (VRPCD) consists of fulfilling a set of transportation requests using a fleet of homogeneous vehicles to sequentially accomplish the pickup and delivery tasks. Between those operations, there is a consolidation process of incoming shipments at the cross-dock. This work introduces a monolithic formulation for the VRPCD that determines pickup/delivery routes and schedules simultaneously with the truck scheduling at the terminal. To derive a more efficient formulation, a constraint set mimicking the widely known sweep algorithm was incorporated into the rigorous model. The resulting model based on the sweep heuristic can find near-optimal solutions to large problems at very acceptable CPU times.     

Computational strategies for large-scale MILP transshipment models for heat exchanger network synthesis

Determining the minimum number of units is an important step in heat exchanger network synthesis (HENS). The MILP transshipment model (Papoulias and Grossmann, 1983) and transportation model (Cerda and Westerberg, 1983) were developed for this purpose. However, they are computationally expensive when solving for large-scale problems. Several approaches are studied in this paper to enable the fast solution of large-scale MILP transshipment models. Model reformulation techniques are developed for tighter formulations with reduced LP relaxation gaps. Solution strategies are also proposed for improving the efficiency of the branch and bound method. Both approaches aim at finding the exact global optimal solution with reduced solution times. Several approximation approaches are also developed for finding good approximate solutions in relatively short times. Case study results show that the MILP transshipment model can be solved for relatively large-scale problems in reasonable times by applying the approaches proposed in this paper.     

Global Search Metaheuristics for planning transportation of multiple petroleum products in a multi-pipeline system

The objective of this work is to develop several metaheuristic algorithms to improve the efficiency of the MILP algorithm used for planning transportation of multiple petroleum products in a multi-pipeline system. The problem involves planning the optimal sequence of products assigned to each new package pumped through each polyduct of the network in order to meet product demands at each destination node before the end of the planning horizon. All the proposed metaheuristics are combinations of improvement methods applied to solutions resulting from different construction heuristics. These improvements are performed by searching the neighborhoods generated around the current solution by different Global Search Metaheuristics: Multi-Start Search, Variable Neighborhood Search, Taboo Search and Simulated Annealing. Numerical examples are solved in order to show the performance of these metaheuristics against a standard commercial solver using MILP. Results demonstrate how these metaheuristics are able to reach better solutions in much lower computational time.     

A monolithic approach to vehicle routing and operations scheduling of a cross-dock system with multiple dock doors

Cross-docking is a logistic strategy for moving goods from suppliers to customers via a cross-dock terminal with no permanent storage. The operational planning of a cross-dock facility involves different issues such as vehicle routing, dock door assignment and truck scheduling. The vehicle routing problem seeks the optimal routes for a homogeneous fleet of vehicles that sequentially collects goods at pickup points and delivers them to their destinations. The truck scheduling problem deals with the timing of unloading and reloading operations at the cross-dock. This work introduces a mixed-integer linear programming formulation for the scheduling of single cross-dock systems that, in addition to selecting the pickup/delivery routes, simultaneously decides on the dock door assignment and the truck scheduling at the cross-dock. The proposed monolithic formulation is able to provide near-optimal solutions to medium-size problems involving up to 70 transportation orders, 16 vehicles and 7 strip/stack dock doors at acceptable CPU times.     

Symmetry breaking in MILP formulations for Unit Commitment problems

This paper addresses the study of symmetry in Unit Commitment (UC) problems solved by Mixed Integer Linear Programming (MILP) formulations, and using Linear Programming based Branch & Bound MILP solvers. We propose three sets of symmetry breaking constraints for UC MILP formulations exhibiting symmetry, and its impact on three UC MILP models are studied. The case studies involve the solution of 24 instances by three widely used models in the literature, with and without symmetry breaking constraints. The results show that problems that could not be solved to optimality within hours can be solved with a relatively small computational burden if the symmetry breaking constraints are assumed. The proposed symmetry breaking constraints are also compared with the symmetry breaking methods included in two MILP solvers, and the symmetry breaking constraints derived in this work have a distinct advantage over the methods in the MILP solvers.     

Generic mathematical programming formulation and solution for computer-aided molecular design

This short communication presents a generic mathematical programming formulation for computer-aided molecular design (CAMD). A given CAMD problem, based on target properties, is formulated as a mixed integer linear/non-linear program (MILP/MINLP). The mathematical programming model presented here, which is formulated as an MILP/MINLP problem, considers first-order and second-order molecular groups for molecular structure representation and property estimation. It is shown that various CAMD problems can be formulated and solved through this model.     

Multi-period design and planning model of shale gas field development

Long-term design and planning of shale gas field development is challenging due to the complex development operations and a wide range of candidate locations. In this work, we focus on the multi-period shale gas field development problem, where the shale gas field has multiple formations and each well can be developed from one of several alternative pads. The decisions in this problem involve the design of the shale gas network and the planning of development operations. A mixed-integer linear programming (MILP) model is proposed to address this problem. Since the proposed model is a large-scale MILP, we propose a solution pool-based bilevel decomposition algorithm to solve it. Results on realistic instances demonstrate the value of the proposed model and the effectiveness of the proposed algorithm.     

Design of integrated batch processes with discrete and continuous equipment sizes

This paper presents a mathematical programming approach for the integrated design of batch processes involving multiple processing steps. Detailed dynamic models are used to describe the behaviour of individual batch operations. The mathematical formulation regards both the design (e.g. equipment items with discrete sizes) and operational characteristics (i.e. control variable profiles such as reflux ratio, cooling water flowrate) of each task as degrees-of-freedom, the values of which are selected to optimise a particular objective function (e.g. profit). The solution may be restricted by inequality constraints which hold throughout the task (e.g. reactor temperature violation) or at the end of the task (e.g. end-product purity specification). The sizes of the equipment items are treated as discrete decisions and are chosen from a selection of standard sizes. The mathematical formulation leads to a mixed integer dynamic optimisation problem and is solved using the outer approximation/augmented penalty (OA/AP) algorithm.     

An optimization framework for cost effective design of refueling station infrastructure for alternative fuel vehicles

Historically, gasoline and diesel fuels have been used for transportation, but the possible decline of oil supplies in the future is forcing nations to consider alternative fuels. Most technically and economically feasible alternative fuels have a lower energy density than gasoline, which results in a shorter range for these vehicles. This necessitates a greater need for convenient access to refueling facilities for alternative fuel vehicles. Since infrastructure development is expensive, there is a need to direct investments towards the establishment of refueling facilities in areas which result in maximum impact. This can be addressed by locating facilities at sites which service as many vehicles as possible. This work deals with the use of mathematical programming for determining the best locations for establishing alternative transportation fuel stations. The objective was to site the refueling stations at locations which maximize the number of vehicles served, while staying within budget constraints. The model used here is a modified form of the flow interception facility location model. For the case study we used the transportation network of Alexandria, Virginia, as a test bed for our model. Origin-destination travel demand data for this city is simulated through a transportation simulator to determine the routes taken by individual vehicles. The results are then compared with the service level offered by conventional gasoline refueling stations already located in the city. This work integrates the use of transportation modeling with mathematical programming for the solution of a complex large-scale problem on a real-life transportation network.     

ϵ-OA for the solution of bi-objective generalized disjunctive programming problems in the synthesis of nonlinear process networks

There has been an increasing interest in multicriteria optimization (MCO) of nonlinear process network problems in recent years. Several mathematical models have been developed and solved using MCO methodologies including ϵ-constraint, weighted sum, and minimum distance. In this paper, we investigate the bi-objective nonlinear network synthesis problem and propose an effective algorithm, ϵ-OA, based on augmented ϵ-constraint and logic-based outer approximation (OA). We provide theoretical characterization of the proposed algorithm and show that the solutions generated are efficient. We illustrate the effectiveness of our novel algorithm on two benchmark problems. The ϵ-OA is compared to the straightforward use of OA with augmented ϵ-constraint algorithm (ϵ-con + OA), the augmented ϵ-constraint without OA (ϵ-MINLP), and the traditional ϵ-constraint (T-ϵ-con). Based on the results, our novel algorithm is very effective in solving the bi-objective generalized disjunctive programming problems in the synthesis of process networks.     

Flexible mass transfer model for water minimization in batch plants

This paper presents the least constrained mass transfer mathematical formulation for freshwater minimization in multipurpose batch chemical processes with central reusable water storage. The mathematical formulation is an extension of the model developed by Majozi [T. Majozi, Wastewater minimization using central reusable water storage in batch processes, Computers and Chemical Engineering Journal 29 (7) (2005) 1631–1646]. In the latter model four scenarios were considered with various limitations or constraints. In the scenario presented in this paper only the mass load is fixed, whilst both the quantity of water used in a particular operation and outlet concentration are allowed to vary. In essence, fixing the mass load is more representative of the practical case. A solution procedure for the resultant nonconvex mixed integer nonlinear programming (MINLP) model is also presented. The solution procedure first involves reformulating the MINLP into a relaxed linear model (MILP). The MILP is first solved, the solution of which forms a feasible starting solution for the MINLP. Presented are two illustrative examples.     

An MILP-MINLP decomposition method for the global optimization of a source based model of the multiperiod blending problem

The multiperiod blending problem involves binary variables and bilinear terms, yielding a nonconvex MINLP. In this work we present two major contributions for the global solution of the problem. The first one is an alternative formulation of the problem. This formulation makes use of redundant constraints that improve the MILP relaxation of the MINLP. The second contribution is an algorithm that decomposes the MINLP model into two levels. The first level, or master problem, is an MILP relaxation of the original MINLP. The second level, or subproblem, is a smaller MINLP in which some of the binary variables of the original problem are fixed. The results show that the new formulation can be solved faster than alternative models, and that the decomposition method can solve the problems faster than state of the art general purpose solvers.     

A MILP model for N-dimensional allocation

This paper presents a Mixed Integer Linear Programming (MILP) model for the solution of N-dimensional allocation problems. The applicability of the model is presented and demonstrated through some illustrative examples with different numbers of dimensions. Several problems, previously presented in the literature, are solved using the proposed model, such as, one-dimensional scheduling problems, two-dimensional cutting problems, as well as plant layout problems and three-dimensional packing problems. Additionally, some problems in four dimensions are presented and solved using the considered model. The presented model is applicable to a wide variety of allocation problems as it offers a general framework for modelling allocation problems with any given number of continuous or discrete dimensions. The presented problems are formulated as MILP problems where the first four dimensions usually are continuous spatial and time dimensions. Additional dimensions are often of a discrete nature.     

Strategic planning optimization for natural gas to liquid transportation fuel (GTL) systems

A strategic planning optimization model is proposed for a network of natural gas to liquids (GTL) systems, and it is solved using a rolling horizon strategy. The model formulation determines the strategic and tactical decisions of the GTL supply chain over a long time horizon. The decisions to build new GTL refineries may be made over the span of 30 years and their operations cover the span of 60 years. Multiple capacities of GTL refineries (i.e., 1, 5, 10, 50, and 200 thousand barrels per day) that produce gasoline, diesel, and kerosene commensurate to the United States demand ratio may exist in the network. The parameter inputs include the locations, availabilities, and prices of natural gas in the United States discretized by county, the delivery locations of fuel products, and the transportation costs of every input and output of the refinery, defined for each time period. Formulated as a large-scale mixed-integer linear optimization (MILP) model, the problem is solved using a rolling horizon strategy for tractability. Case studies on the state of Pennsylvania are presented for different planning schemes and their impact on the economic performance of the GTL network is discussed.     

An efficient algorithm for community detection in complex weighted networks

Community detection decomposes large-scale, complex networks “optimally” into sets of smaller sub-networks. It finds sub-networks that have the least inter-connections and the most intra-connections. This article presents an efficient community detection algorithm that detects community structures in a weighted network by solving a multi-objective optimization problem. The whale optimization algorithm is extended to enable it to handle multi-objective optimization problems with discrete variables and to solve the problems on parallel processors. To this end, the population's positions are discretized using a transfer function that maps real variables to discrete variables, the initialization steps for the algorithm are modified to prevent generating unrealistic connections between variables, and the updating step of the algorithm is redefined to produce integer numbers. To identify the community configurations that are Pareto optimal, the non-dominated sorting concept is adopted. The proposed algorithm is tested on the Tennessee Eastman process and several benchmark community-detection problems.     

Design of multipurpose production facilities: A RTN decomposition-based algorithm

A general mathematical formulation for the design of multipurpose facilities has recently been presented by Barbosa-Póvoa and Pantelides (1997). The model proposed permits a detailed consideration of the design problem taking account of trade-offs between capital costs, revenues and operational flexibility. The optimal solution involves the selection of the required processing and storage equipment items and the required levels of provision of other production resources such as utilities, manpower, cleaning and transportation equipment.In order to guarantee solution optimality, the above design formulation has to consider a large number of equipment items, out of which it will select the ones that will actually be incorporated in the plant. This may result in large mixed-integer linear programming (MILP) problems that are expensive to solve.This paper presents a decomposition approach for the solution of large batch process design problems. The approach involves the iterative solution of a master problem (representing a relaxation of the original design problem) and a design sub-problem (in which several of the design decisions are already fixed).An example illustrating the effectiveness of the proposed decomposition approach is presented.     

基于遗传算法的焊接生产线工位平衡规划方法

在现代化大规模大批量的流水装配制造业中,数量众多的作用分配和多工位的合理安排使工位平衡问题显得更为突出。针对第一类工位平衡问题,即在给定的生产节拍下最小化工位数,首先分析了该问题并建立了数学模型,进而提出了一种基于改进遗传算法求解工位平衡问题的方法。该算法以焊接任务的操作顺序优先关系为约束前提,在初始种群的生产以及交叉和变异过程中保证了染色体解的可行性,同时在遗传算法的选择过程中考虑了具有相同工位数的最优作业方案的工时标准差,从而提高了算法的搜索效率和解的可靠性。最后通过实例求解验证了该算法的有效性。     

Modeling and measurement of granule attrition during pneumatic conveying in a laboratory scale system

A methodology combining theoretical and experimental techniques for characterizing and predicting the friability of granules in a laboratory scale pneumatic conveying systems is developed. Models of increasing mathematical complexity are used for analysis of experimental data. Firstly, a two-dimensional (2-D) computational fluid dynamics (CFD) model of the gas-solid flow within the Malvern Mastersizer laser diffraction equipment is developed to simulate impact of different inlet jet pressures on the flow properties and to calculate average velocity and average volume fraction of particles in the equipment. Secondly, a simple maximum-gradient population balance (MG-PB) mathematical model of breakage is developed. The model is solved using the Quadrature Method of Moments (QMOM) and used for evaluation of experimental data from the Malvern equipment. Different semi-empirical expressions for the breakage kernels and for the daughter distribution functions are tested. Multiple breakage distribution functions are needed to get satisfactory agreement with experimental data. Finally, a CFD-PB model combining CFD and QMOM methodologies is developed. The combined model employs different binary fragment distribution functions and a kernel with the breakage rate proportional to the characteristic particle size and to the square of the impact velocity between a particle and the equipment wall. Simulation results are compared with attrition experimental data indicating that the model is able to capture the qualitative trends and quantitatively predict the Sauter mean diameter d₃₂ at the outlet. However, the lower moments, in particular m₀ and m₁ are under predicted by the model. Based also on the MG-PB model results, it is our hypothesis that chipping, or breakage of particles in multiple fragments results in higher m₀ and m₁ than predicted. Further improvements of the model are proposed to incorporate multiple breakage effects. It is assumed that analogous physically based models combining properties of the gas-solid flow with the PB models can be employed to predict attrition and breakage in large-scale pneumatic conveying systems.     

A hybrid optimization strategy for simultaneous synthesis of heat exchanger network

The heat exchanger network synthesis problem often leads to large-scale non-convex mixed integer nonlinear programming formulations that contain many discrete and continuous variables, as well as nonlinear objective function or nonlinear constraints. In this paper, a novel method consisting of genetic algorithm and particle swarm optimization algorithm is proposed for simultaneous synthesis problem of heat exchanger networks. The simultaneous synthesis problem is solved in the following two levels: in the upper level, the network structures are generated randomly and reproduced using genetic algorithm; and in the lower level, heat load of units and stream-split heat flows are optimized through particle swarm optimization algorithm. The proposed approach is tested on four benchmark problems, and the obtained solutions are compared with those published in previous literature. The results of this study prove that the presented method is effective in obtaining the approximate optimal network with minimum total annual cost as performance index.