A service flow model for the liner shipping network design problem

Global liner shipping is a competitive industry, requiring liner carriers to carefully deploy their vessels efficiently to construct a cost competitive network. This paper presents a novel compact formulation of the liner shipping network design problem (LSNDP) based on service flows. The formulation alleviates issues faced by arc flow formulations with regards to handling multiple calls to the same port. A problem which has not been fully dealt with earlier by LSNDP formulations. Multiple calls are handled by introducing service nodes, together with port nodes in a graph representation of the problem, and by introducing numbered arcs between a port and a novel service node. An arc from a port node to a service node indicate whether a service is calling the port or not. This representation allows recurrent calls of a service to a port, which previously could not be handled by LSNDP models. The model ensures strictly weekly frequencies of services, ensures that port-vessel draft capabilities are not violated, respects vessel capacities and the number of vessels available. The profit of the generated network is maximized, i.e. the revenue of flowed cargo subtracted operational costs of the network and a penalty for not flowed cargo. The model can be used to design liner shipping networks to utilize a container carrier’s assets efficiently and to investigate possible scenarios of changed market conditions. The model is solved as a Mixed Integer Program. Results are presented for the two smallest instances of the benchmark suite LINER-LIB-2012 presented in Brouer, Alvarez, Plum, Pisinger, and Sigurd (2013).     

Relaxations and discretizations for the pooling problem

The pooling problem is a folklore NP-hard global optimization problem that finds applications in industries such as petrochemical refining, wastewater treatment and mining. This paper assimilates the vast literature on this problem that is dispersed over different areas and gives new insights on prevalent techniques. We also present new ideas for computing dual bounds on the global optimum by solving high-dimensional linear programs. Finally, we propose discretization methods for inner approximating the feasible region and obtaining good primal bounds. Valid inequalities are derived for the discretized models, which are formulated as mixed integer linear programs. The strength of our relaxations and usefulness of our discretizations is empirically validated on random test instances. We report best known primal bounds on some of the large-scale instances.     

Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk,Part I: Applications and model

This paper formulates a model for finding a minimum cost routing in a network for a heterogeneous fleet of ships engaged in pickup and delivery of several liquid bulk products. The problem is frequently encountered by maritime chemical transport companies, including oil companies serving an archipelago of islands. The products are assumed to require dedicated compartments in the ship. The problem is to decide how much of each product should be carried by each ship from supply ports to demand ports, subject to the inventory level of each product in each port being maintained between certain levels that are set by the production rates, the consumption rates, and the storage capacities of the various products in each port. This important and challenging inventory constrained multi-ship pickup–delivery problem is formulated as a mixed-integer nonlinear program. We show that the model can be reformulated as an equivalent mixed-integer linear program with special structure. Over 100 test problems are randomly generated and solved using CPLEX 7.5. The results of our numerical experiments illuminate where problem structure can be exploited in order to solve larger instances of the model. Part II of the sequel will deal with new algorithms that take advantage of model properties.     

Simulated annealing for order spread minimization in sequencing cutting patterns

The Order Spread Minimization Problem (OSMP) is a sequencing problem that arises in the process of planning industrial cutting operations. As it can be looked upon as a generalization of the Travelling-Salesman Problem (TSP), it has to be classified as NP-complete. Thus heuristic algorithms are required in order to solve large problem instances. In this paper the authors suggest to apply Simulated Annealing (SA) to the OSMP. A specific version of SA is developed and compared to both an approach previously introduced into the literature by Madsen and a traditional 3-opt-procedure. The performance of these methods is compared on a set of 2400 randomly generated problem instances. SA appears to provide solutions which - in terms of solution quality - are equivalent to those generated by the 3-opt-procedure. However, computing times of the latter for solving large instances are prohibitive. In relation to Madsen's approach SA provides significantly improved solutions at the expense of a moderate increase in computing times.     

Grasp Embedded Scatter Search for the Multicommodity Capacitated Network Design Problem

A GRASP embedded Scatter Search is developed for the multicommodity capacitated network design problem. Difficulty for this problem arises from the fact that selection of the optimal network design is an NP-complete combinatorial problem. There exist no polynomial exact algorithms which can solve this problem in a reasonable period of time for realistically sized instances. In such cases, heuristic procedures are commonly used. Two strategies were designed for GRASP: a traditional approach and a memory based technique. As for Scatter Search, 5 different strategies were used to update the reference set. Computational results on a large set of randomly generated instances show the convenience of the proposed procedures.     

A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we highlight the differences in operations between bulk ports and container terminals which highlights the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on a branch and price framework to solve the integrated problem. In the proposed model, the master problem is formulated as a set-partitioning problem, and subproblems to identify columns with negative reduced costs are solved using mixed integer programming. To obtain sub-optimal solutions quickly, a metaheuristic approach based on critical-shaking neighborhood search is presented. The proposed algorithms are tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithms can be successfully used to solve instances containing up to 40 vessels within reasonable computational time.     

Classical and new heuristics for the open-shop problem: A computational evaluation

We study the problem of constructing minimum makespan schedules for the Open-Shop problem. This paper presents two new heuristics: the first one is a list scheduling algorithm with two priorities. The second is based on the construction of matchings in a bipartite graph. We develop several versions of these two heuristics. A computational evaluation shows that around 90% of randomly generated instances are solvable optimally, whereas classical (list scheduling) heuristics achieve less than 20% on average. Therefore, our algorithms make most Open-Shop instances easy to solve in practice, and this raises the problem of generating hard instances. We extend the evaluation to two kinds of such instances: the results are not so good, but remain better than classical heuristics.     

Knapsack problem with probability constraints

This paper is dedicated to a study of different extensions of the classical knapsack problem to the case when different elements of the problem formulation are subject to a degree of uncertainty described by random variables. This brings the knapsack problem into the realm of stochastic programming. Two different model formulations are proposed, based on the introduction of probability constraints. The first one is a static quadratic knapsack with a probability constraint on the capacity of the knapsack. The second one is a two-stage quadratic knapsack model, with recourse, where we introduce a probability constraint on the capacity of the knapsack in the second stage. As far as we know, this is the first time such a constraint has been used in a two-stage model. The solution techniques are based on the semidefinite relaxations. This allows for solving large instances, for which exact methods cannot be used. Numerical experiments on a set of randomly generated instances are discussed below.     

The break scheduling problem: complexity results and practical algorithms

Break scheduling problems arise in working areas where breaks are indispensable, e.g., in air traffic control, supervision, or assembly lines. We regard such a problem from the area of supervision personnel. The objective is to find a break assignment for an existing shiftplan such that various constraints reflecting legal demands or ergonomic criteria are satisfied and such that staffing requirement violations are minimised. We prove the NP-completeness of this problem when all possible break patterns for each shift are given explicitly as part of the input. To solve our problem we propose two variations of a memetic algorithm. We define genetic operators, a local search based on three neighbourhoods, and a penalty system that helps to avoid local optima. Parameters influencing the algorithms are experimentally evaluated and assessed with statistical methods. We compare our algorithms, each with the best parameter setting according to the evaluation, with the state-of-the-art algorithm on a set of 30 real-life and randomly generated instances that are publicly available. One of our algorithms returns improved results on 28 out of the 30 benchmark instances. To the best of our knowledge, our improved results for the real-life instances constitute new upper bounds for this problem     

HOPS – Hamming-Oriented Partition Search for production planning in the spinning industry

In this paper, we investigate a two-stage lot-sizing and scheduling problem in a spinning industry. A new hybrid method called HOPS (Hamming-Oriented Partition Search), which is a branch-and-bound based procedure that incorporates a fix-and-optimize improvement method is proposed to solve the problem. An innovative partition choice for the fix-and-optimize is developed. The computational tests with generated instances based on real data show that HOPS is a good alternative for solving mixed integer problems with recognized partitions such as the lot-sizing and scheduling problem.     

Stowage planning in maritime container transportation

We consider a stowage-planning problem of arranging containers on a container ship in the maritime transportation system. Since containers are accessible only from the top of the stack, temporary unloading and reloading of containers, called shifting, is unavoidable if a container required to be unloaded at the current port is stacked under containers to be unloaded at later ports on the route of the ship. The objective of the stowage planning problem is to minimize the time required for shifting and crane movements on a tour of a container ship while maintaining the stability of the ship. For the problem, we develop a heuristic solution method in which the problem is divided into two subproblems, one for assigning container groups into the holds and one for determining a loading pattern of containers assigned to each hold. The former subproblem is solved by a greedy heuristic based on the transportation simplex method, while the latter is solved by a tree search method. These two subproblems are solved iteratively using information obtained from solutions of each other. To see the performance of the suggested algorithm, computational tests are performed on problem instances generated based on information obtained from an ocean container liner. Results show that the suggested algorithm works better than existing algorithms.     

Constrained group balancing: Why does it work

We consider a problem where a set of objects possessing multiple attributes must be partitioned into a certain number of groups so that the groups are as balanced as possible with respect to the number of objects possessing each attribute. This multi-criteria decision problem arises in a variety of practical applications, ranging from assigning students to study groups to designing level schedules for JIT assembly lines. A direct approach, enforcing balance through hard constraints, may lead to infeasibility, but works well in practice. We analyze this phenomenon from the worst-case and empirical perspectives, as well as through an in-depth analysis of one representative practical application – the design of student groups at the Rotman School of Management, University of Toronto. The goals of the analysis are to understand what classes of balancing problems may contain infeasible instances and how prevalent such instances are within these classes, as well as to synthesize practical managerial insights that a decision maker could follow in order to increase the chances that balanced groups can be found.     

Heuristics for flight and maintenance planning of mission aircraft

Flight and Maintenance Planning (FMP) of mission aircraft addresses the question of which available aircraft to fly and for how long, and which grounded aircraft to perform maintenance operations on, in a group of aircraft that comprise a unit. The objective is to achieve maximum fleet availability of the unit over a given planning horizon, while also satisfying certain flight and maintenance requirements. The application of exact methodologies for the solution of the problem is quite limited, as a result of their excessive computational requirements. In this work, we prove several important properties of the FMP problem, and we use them to develop two heuristic procedures for solving large-scale FMP instances. The first heuristic is based on a graphical procedure which is currently used for generating flight and maintenance plans of mission aircraft by many Air Force organizations worldwide. The second heuristic is based on the idea of splitting the original problem into smaller sub-problems and solving each sub-problem separately. Both heuristics have been roughly sketched in earlier works that have appeared in the related literature. The present paper develops the theoretical background on which these heuristics are based, provides in detail the algorithmic steps required for their implementation, analyzes their worst-case computational complexity, presents computational results illustrating their computational performance on random problem instances, and evaluates the quality of the solutions that they produce. The size and parameter values of some of the randomly tested problem instances are quite realistic, making it possible to infer the performance of the heuristics on real world problem instances. Our computational results demonstrate that, under careful consideration, even large FMP instances can be handled quite effectively. The theoretical results and insights that we develop establish a fundamental background that can be very useful for future theoretical and practical developments related to the FMP problem.     

Crane scheduling with non-crossing constraint

In this paper, we examine crane scheduling for ports. This important component of port operations management is studied when the non-crossing spatial constraint, which is common to crane operations, is considered. We assume that ships can be divided into holds and that cranes can move from hold to hold but jobs are not pre-emptive, so that only one crane can work on one hold or job to complete it. Our objective is to minimize the latest completion time for all jobs. We formulate this problem as an integer programming problem. We provide the proof that this problem is NP-complete and design a branch-and-bound algorithm to obtain optimal solutions. A simulated annealing meta-heuristic with effective neighbourhood search is designed to find good solutions in larger size instances. The elaborate experimental results show that the branch-and-bound algorithm runs much faster than CPLEX and the simulated annealing approach can obtain near optimal solutions for instances of various sizes.     

Scatter search for project scheduling with resource availability cost

This paper considers a project scheduling problem with the objective of minimizing resource availability costs, taking into account a deadline for the project and precedence relations among the activities. Exact methods have been proposed for solving this problem, but we are not aware of existing heuristic methods. Scatter search is used to tackle this problem, and our implementation incorporates advanced strategies such as dynamic updating of the reference set, the use of frequency-based memory within the diversification generator, and a combination method based on path relinking. We also analyze the merit of employing a subset of different types when combining solutions. Extensive computational experiments involving more than 2400 instances are performed. For small instances, the performance of the proposed procedure is compared to optimal solutions generated by an exact cutting plane algorithm and upper and lower bounds from the literature. For medium and larger size instances, we developed simple multi-start heuristics and comparative results are reported.     

Algorithms for common due-date assignment and sequencing on a single machine with sequence-dependent setup times

This paper focuses on the single machine sequencing and common due-date assignment problem for the objective of minimizing the sum of the penalties associated with earliness, tardiness and due-date assignment. Unlike the previous research articles on this class of scheduling problem, we consider sequence-dependent setup times that make the problem much more difficult. To solve the problem, a branch and bound algorithm, which incorporates the method to obtain lower and upper bounds as well as a dominance property to reduce the search space, is suggested that gives the optimal solutions for small-sized instances. Heuristic algorithms are suggested to obtain solutions for large-sized problems within a reasonable computation time. The performances of both the optimal and heuristic algorithms, in computational experiments on randomly generated test instances, are reported.     

A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes

Multi-compartment vehicle routing problems arise in a variety of problem settings in which different product types have to be transported separated from each other. In this paper, a problem variant which occurs in the context of glass waste recycling is considered. In this problem, a set of locations exists, each of which offering a number of containers for the collection of different types of glass waste (e.g. colorless, green, brown glass). In order to pick up the contents from the containers, a fleet of homogeneous disposal vehicles is available. Individually for each disposal vehicle, the capacity can be discretely separated into a limited number of compartments to which different glass waste types are assigned. The objective of the problem is to minimize the total distance to be travelled by the disposal vehicles. For solving this problem to optimality, a branch-and-cut algorithm has been developed and implemented. Extensive numerical experiments have been conducted in order to evaluate the algorithm and to gain insights into the problem structure. The corresponding results show that the algorithm is able to solve instances with up to 50 locations to optimality and that it reduces the computing time by 87% compared to instances from the literature. Additional experiments give managerial insights into the use of different variants of compartments with flexible sizes.

     

Constructive generation of very hard 3-colorability instances

Graph colorability (COL), is a typical constraint satisfaction problem to which phase transition phenomena (PTs), are important in the computational complexity of combinatorial search algorithms. PTs are significant and subtle because, in the PT region, extraordinarily hard problem instances are found, which may require exponential-order computational time to solve. To clarify PT mechanism, many studies have been undertaken to produce very hard instances, many of which were based on generate-and-test approaches. We propose a rather systematic or constructive algorithm that repeats the embedding of 4-critical graphs to arbitrarily generate large extraordinarily hard 3-colorability instances. We demonstrated experimentally that the computational cost to solve our generated instances is of an exponential order of the number of vertices by using a few actual coloring algorithms and constraint satisfaction algorithms.     

Exact algorithms for the traveling salesman problem with draft limits

This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance compared through extensive computational experiments. Optimal solutions are reported for open instances of benchmark problems available in the literature.