A truck scheduling problem arising in intermodal container transportation

We address a truck scheduling problem that arises in intermodal container transportation, where containers need to be transported between customers (shippers or receivers) and container terminals (rail or maritime) and vice versa. The transportation requests are handled by a trucking company which operates several depots and a fleet of homogeneous trucks that must be routed and scheduled to minimize the total truck operating time under hard time window constraints imposed by the customers and terminals. Empty containers are considered as transportation resources and are provided by the trucking company for freight transportation. The truck scheduling problem at hand is formulated as Full-Truckload Pickup and Delivery Problem with Time Windows (FTPDPTW) and is solved by a 2-stage heuristic solution approach. This solution method was specially designed for the truck scheduling problem but can be applied to other problems as well. We assess the quality of our solution approach on several computational experiments.     

MIP approaches for the integrated berth allocation and quay crane assignment and scheduling problem

In this paper we consider an integrated berth allocation and quay crane assignment and scheduling problem motivated by a real case where a heterogeneous set of cranes is considered. A first mathematical model based on the relative position formulation (RPF) for the berth allocation aspects is presented. Then, a new model is introduced to avoid the big-M constraints included in the RPF. This model results from a discretization of the time and space variables. For the new discretized model several enhancements, such as valid inequalities, are introduced. In order to derive good feasible solutions, a rolling horizon heuristic (RHH) is presented. A branch and cut approach that uses the enhanced discretized model and incorporates the upper bounds provided by the RHH solution is proposed. Computational tests are reported to show (i) the quality of the linear relaxation of the enhanced models; (ii) the effectiveness of the exact approach to solve to optimality a set of real instances; and (iii) the scalability of the RHH based on the enhanced mathematical model which is able to provide good feasible solutions for large size instances.     

A heuristic multi-start decomposition approach for optimal design of serial machining lines

We study an optimal design problem for serial machining lines. Such lines consist of a sequence of stations. At every station, the operations to manufacture a product are grouped into blocks. The operations within each block are performed simultaneously by the same spindle head and the blocks of the same station are executed sequentially. The inclusion and exclusion constraints for combining operations into blocks and stations as well as the precedence constraints on the set of operations are given. The problem is to group the operations into blocks and stations minimizing the total line cost. A feasible solution must respect the given cycle time and all given constraints. In this paper, a heuristic multi-start decomposition approach is proposed. It utilizes a decomposition of the initial problem into several sub-problems on the basis of a heuristic solution. Then each obtained sub-problem is solved by an exact algorithm. This procedure is repeated many times, each time it starts with a new heuristic solution. Computational tests show that the proposed approach outperforms simple heuristic algorithms for large-scale problems.     

Open vehicle routing problem with driver nodes and time deadlines

In this paper, we consider a variant of the open vehicle routing problem in which vehicles depart from the depot, visit a set of customers, and end their routes at special nodes called driver nodes. A driver node can be the home of the driver or a parking lot where the vehicle will stay overnight. The resulting problem is referred to as the open vehicle routing problem with driver nodes (OVRP-d). We consider three classes of OVRP-d: with no time constraints, with a maximum route duration, and with both a maximum route duration as well as time deadlines for visiting customers. For the solution of these problems, which are not addressed previously in the literature, we develop a new tabu search heuristic. Computational results on randomly generated instances indicate that the new heuristic exhibits a good performance both in terms of the solution quality and computation time.     

Repulsive Assignment Problem

Standard assignment is the problem of obtaining a matching between two sets of respectively persons and positions so that each person is assigned exactly one position and each position receives exactly one person, while a linear decision maker utility function is maximized. We introduce a variant of the problem where the persons individual utilities are taken into account in a way that a feasible solution must satisfy not only the standard assignment constraints, but also an equilibrium constraint of the complementarity type, which we call repulsive. The equilibrium constraint can be, in turn, transformed into a typically large set of linear constraints. Our problem is NP-hard and it is a special case of the assignment problem with side constraints. We study an exact penalty function approach which motivates a heuristic algorithm. We provide computational experiments that show the usefulness of a heuristic mechanism inspired by the exact approach. The heuristics outperforms a state-of-the-art integer linear programming solver.     

Heuristics for Large Constrained Vehicle Routing Problems

This paper presents a heuristic for solving very large routing problems (thousands of customers and hundreds of vehicles) with side constraints such as time windows. When applied to traditional benchmarks (Solomon's), we obtain high quality results with short resolution time (a few seconds). We also introduce a LDS (Limited Discrepancy Search) variation that produces state-of-the-art results. The heart of this heuristic is a combination of a look-ahead insertion algorithm, an incremental local optimization scheme and a constraint solver for constrained traveling salesman problems. The incrementality means that instead of visiting some large neighborhood after an initial solution has been found, a limited number of moves is examined, after each insertion, on the partial solution. This incremental version is not only faster, it also yields better results than using local optimization once a full solution has been built. We also show how additional constraints can be used in order to guide the insertion process. Because of its use of separate CP (Constraint Programming) modules, this method is flexible and may be used to solve large dispatching problems that include many additional constraints such as setup times (asymmetrical distance) or skill matching.     

Roster evaluation based on classifiers for the nurse rostering problem

The personnel scheduling problem is a well-known NP-hard combinatorial problem. Due to the complexity of this problem and the size of the real-world instances, it is not possible to use exact methods, and thus heuristics, meta-heuristics, or hyper-heuristics must be employed. The majority of heuristic approaches are based on iterative search, where the quality of intermediate solutions must be calculated. Unfortunately, this is computationally highly expensive because these problems have many constraints and some are very complex. In this study, we propose a machine learning technique as a tool to accelerate the evaluation phase in heuristic approaches. The solution is based on a simple classifier, which is able to determine whether the changed solution (more precisely, the changed part of the solution) is better than the original or not. This decision is made much faster than a standard cost-oriented evaluation process. However, the classification process cannot guarantee 100 % correctness. Therefore, our approach, which is illustrated using a tabu search algorithm in this study, includes a filtering mechanism, where the classifier rejects the majority of the potentially bad solutions and the remaining solutions are then evaluated in a standard manner. We also show how the boosting algorithms can improve the quality of the final solution compared with a simple classifier. We verified our proposed approach and premises, based on standard and real-world benchmark instances, to demonstrate the significant speedup obtained with comparable solution quality.     

Multiple crane scheduling in a batch annealing process with no-delay constraints for machine unloading

In this work, we focus on the scheduling of multi-crane operations in an iron and steel enterprise for a two-stage batch annealing process. The first stage is the heating process, and the second stage is the cooling process. To start the heating (cooling) stage, a special machine called a furnace (cooler) must be loaded. The real constraints of no-delay machine unloading are defined as follows: once the heating (cooling) is completed, the furnace (cooler) must be unloaded by crane immediately. The goal is to schedule limited machines (furnaces and coolers) operated by multiple cranes to minimize the completion time of the last annealed coil (makespan). We formulate a mixed-integer linear programming model to address this problem. Certain feasible properties are identified to avoid crane conflicts and ensure that the machine unloading no-delay constraints are met. Based on these necessary conditions, we then present a heuristic algorithm with running time in connection with the number of cranes, coils and machines. A lower bound to the problem is also developed. Through theoretical analysis, we show the worst-case bound of our heuristic algorithm. The average performances of the solution approaches are computationally evaluated. The computational results show that the proposed heuristic algorithm is capable of generating good quality solutions.     

Jointly pricing and ordering for a multi-product multi-constraint newsvendor problem with supplier quantity discounts

We present an extension to the multi-product newsvendor problem by incorporating the retailer’s pricing decision as well as considering supplier quantity discount. The objective is to maximize the expected profit of the retailer through jointly determining the ordering quantities and selling prices for the products, subject to multiple capacity constraints. We formulate the problem as a Generalized Disjunctive Programming (GDP) model and develop a Lagrangian heuristic approach for its solution. Randomly produced instances involving up to 1000 products are used to test the proposed approach. Computational results show that the Lagrangian heuristic approach can present very good solutions to all instances in reasonable time.     

Maritime inventory routing with multiple products: A case study from the cement industry

This paper considers a maritime inventory routing problem faced by a major cement producer. A heterogeneous fleet of bulk ships transport multiple non-mixable cement products from producing factories to regional silo stations along the coast of Norway. Inventory constraints are present both at the factories and the silos, and there are upper and lower limits for all inventories. The ship fleet capacity is limited, and in peak periods the demand for cement products at the silos exceeds the fleet capacity. In addition, constraints regarding the capacity of the ships’ cargo holds, the depth of the ports and the fact that different cement products cannot be mixed must be taken into consideration. A construction heuristic embedded in a genetic algorithmic framework is developed. The approach adopted is used to solve real instances of the problem within reasonable solution time and with good quality solutions.     

A heuristic algorithm for the asymmetric capacitated vehicle routing problem

We consider the Asymmetric Capacitated Vehicle Routing Problem (ACVRP[, a particular case of the standard asymmetric Vehicle Routing Problem arising when only the vehicle capacity constraints are imposed. ACVRP is known to be NP-hard and finds practical applications, e.g. in distribution and scheduling. In this paper we describe the extension to ACVRP of the two well-known Clarke-Wright and Fisher-Jaikumar heuristic algorithms. We also propose a new heuristic algorithm for ACVRP that, starting with an initial infeasible solution, determines the final set of vehicle routes through an insertion procedure as well as intea-route and inter-route arc exchanges. The initial infeasible solution is obtained by using the additive bounding procedures for ACVRP described by Fischetti, Toth and Vigo in 1992. Extensive computational results on several classes of randomly generated test problems involving up to 300 customers and on some real instances of distribution problems in urban areas, are presented. The results obtained show that the proposed approach favourably compares with previous algorithms from the literature.     

A facility neighborhood search heuristic for capacitated facility location with single-source constraints and flexible demand

We consider a generalization of the well-known capacitated facility location problem with single source constraints in which customer demand contains a flexible dimension. This work focuses on providing fast and practically implementable optimization-based heuristic solution methods for very large scale problem instances. We offer a unique approach that utilizes a high-quality efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems.     

The Express heuristic for probabilistically constrained integer problems

Integer problems under joint probabilistic constraints with random coefficients in both sides of the constraints are extremely hard from a computational standpoint since two different sources of complexity are merged. The first one is related to the challenging presence of probabilistic constraints which assure the satisfaction of the stochastic constraints with a given probability, whereas the second one is due to the integer nature of the decision variables. In this paper we present a tailored heuristic approach based on alternating phases of exploration and feasibility repairing which we call Express (Explore and Repair Stochastic Solution) heuristic. The exploration is carried out by the iterative solution of simplified reduced integer problems in which probabilistic constraints are discarded and deterministic additional constraints are adjoined. Feasibility is restored through a penalty approach. Computational results, collected on a probabilistically constrained version of the classical 0–1 multiknapsack problem, show that the proposed heuristic is able to determine good quality solutions in a limited amount of time.     

A new method for mean-variance portfolio optimization with cardinality constraints

Several portfolio selection models take into account practical limitations on the number of assets to include and on their weights in the portfolio. We present here a study of the Limited Asset Markowitz (LAM) model, where the assets are limited with the introduction of quantity and cardinality constraints. We propose a completely new approach for solving the LAM model based on a reformulation as a Standard Quadratic Program, on a new lower bound that we establish, and on other recent theoretical and computational results for such problem. These results lead to an exact algorithm for solving the LAM model for small size problems. For larger problems, such algorithm can be relaxed to an efficient and accurate heuristic procedure that is able to find the optimal or the best-known solutions for problems based on some standard financial data sets that are used by several other authors. We also test our method on five new data sets involving real-world capital market indices from major stock markets. We compare our results with those of CPLEX and with those obtained with very recent heuristic approaches in order to illustrate the effectiveness of our method in terms of solution quality and of computation time. All our data sets and results are publicly available for use by other researchers.     

Learning Interactions via Hierarchical Group-Lasso Regularization

We introduce a method for learning pairwise interactions in a linear regression or logistic regression model in a manner that satisfies strong hierarchy: whenever an interaction is estimated to be nonzero, both its associated main effects are also included in the model. We motivate our approach by modeling pairwise interactions for categorical variables with arbitrary numbers of levels, and then show how we can accommodate continuous variables as well. Our approach allows us to dispense with explicitly applying constraints on the main effects and interactions for identifiability, which results in interpretable interaction models. We compare our method with existing approaches on both simulated and real data, including a genome-wide association study, all using our R package glinternet.     

Real-time management of vehicle breakdowns in urban freight distribution

This paper considers a problem in which an unexpected event immobilises a vehicle of a distribution fleet permanently, and the remaining vehicles are rerouted to serve some of the clients of the failed vehicle. We model this case as a variation of the Team Orienteering Problem (TOP), constraining all vehicle routes to an upper time, or distance, limit, and taking into account the limited capacity of the fleet vehicles. The problem requires an effective solution in almost real time. We propose a new heuristic to provide efficient solutions within this strict computational time constraint. To test the quality of the heuristic, we have developed and validated a Genetic Algorithm (GA) that obtains high quality (but computationally expensive) solutions. The solutions of the heuristic compare favorably to those obtained by the GA. The latter has also been tested successfully in a real-time fleet management system.     

Price-directive decomposition applied to routing in telecommunication networks

The telecommunication network design problem is considered to study the level of transmission network. A heuristic approach is defined to solve the combined routing-grouping problem, where the grouping one is solved by a heuristic approach. The routing problem is defined considering reliability constraints, supplementary circuits demands and a piecewise linear objective function to take into account the influence of the grouping. This last model is solved using a price-directive decomposition method, which has allowed us to solve real networks using an exact method.     

Heuristic Techniques for Single Line Train Scheduling

Optimising a train schedule on a single line track is known to be NP-Hard with respect to the number of conflicts in the schedule. This makes it difficult to determine optimum solutions to real life problems in reasonable time and raises the need for good heuristic techniques. The heuristics applied and compared in this paper are a local search heuristic with an improved neighbourhood structure, genetic algorithms, tabu search and two hybrid algorithms. When no time constraints are enforced on solution time, the genetic and hybrid algorithms were within five percent of the optimal solution for at least ninety percent of the test problems.     

Fuzzy optimization for distribution of frozen food with imprecise times

Problems concerning the distribution routes for frozen products need to incorporate constraints that avoid breaks in the cold chain. The decision making process under uncertain environments is a common one in real logistics problems. The purpose of this study is to apply a fuzzy approach which will provide an optimal solution to the distribution of frozen food with uncertainty in its time values. A soft computing approach is used where fuzzy constraints are included in the modeling and the solution of the problem.     

Solving a Real World Assignment Problem with a Metaheuristic

This paper investigates a real world assignment problem, which slightly differs from the classical generalized assignment problem (GAP). The large-scale number of variables in the related 0-1 linear program makes the use of commercial optimization packages impractical. We present here a metaheuristic using simulated annealing. It is based on successive reductions of the search space by identification of locally active constraints. Our approach employs a heuristic procedure to compute an initial (feasible or infeasible) 0/1 solution, and a double-criterion acceptance rule. The performance of the algorithm is demonstrated on real data sets.