A combined ship scheduling and allocation problem

We present a bulk ship scheduling problem that is a combined multi-ship pickup and delivery problem with time windows (m-PDPTW) and multi-allocation problem. In contrast to other ship scheduling problems found in the literature, each ship in the fleet is equipped with a flexible cargo hold that can be partitioned into several smaller holds in a given number of ways. Therefore, multiple products can be carried simultaneously by the same ship. The scheduling of the ships constitutes the m-PDPTW, while the partition of the ships' flexible cargo holds and the allocation of cargoes to the smaller holds make the multi-allocation problem. A set partitioning approach consisting of two phases is proposed for the combined ship scheduling and allocation problem. In the first phase, a number of candidate schedules (including allocation of cargoes to the ships' cargo holds) is generated for each ship. In the second phase, we minimise transportation costs by solving a set partitioning problem where the columns are the candidate schedules generated in phase one. The computational results show that the proposed approach works, and optimal solutions are obtained on several cases of a real ship planning problem.     

Solving nonconvex economic load dispatch problem using particle swarm optimization with time varying acceleration coefficients

This article presents the design and application of an efficient hybrid heuristic search method to solve the practical economic dispatch problem considering many nonlinear characteristics of power generators, and their operational constraints, such as transmission losses, valve‐point effects, multi‐fuel options, prohibited operating zones, ramp rate limits and spinning reserve. These practical operation constraints which can usually be found at the same time in realistic power system operations make the economic load dispatch (ELD) problem a nonsmooth optimization problem having complex and nonconvex features with heavy equality and inequality constraints. A particle swarm optimization with time varying acceleration coefficients is proposed to determine optimal ELD problem in this paper. The proposed methodology easily takes care of solving nonconvex ELD problems along with different constraints like transmission losses, dynamic operation constraints, and prohibited operating zones. The proposed approach has been implemented on the 3‐machines 6‐bus, IEEE 5‐machines 14‐bus, IEEE 6‐machines 30‐bus systems and 13 thermal units power system. The proposed technique is compared with solve the ELD problem with hybrid approach by using the valve‐point effect. The comparison results prove the capability of the proposed method give significant improvements in the generation cost for the ELD problem. © 2015 Wiley Periodicals, Inc. Complexity 21: 299–308, 2016     

Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems

Numerous planning problems can be formulated as multi-stage stochastic programs and many possess key discrete (integer) decision variables in one or more of the stages. Progressive hedging (PH) is a scenario-based decomposition technique that can be leveraged to solve such problems. Originally devised for problems possessing only continuous variables, PH has been successfully applied as a heuristic to solve multi-stage stochastic programs with integer variables. However, a variety of critical issues arise in practice when implementing PH for the discrete case, especially in the context of very difficult or large-scale mixed-integer problems. Failure to address these issues properly results in either non-convergence of the heuristic or unacceptably long run-times. We investigate these issues and describe algorithmic innovations in the context of a broad class of scenario-based resource allocation problem in which decision variables represent resources available at a cost and constraints enforce the need for sufficient combinations of resources. The necessity and efficacy of our techniques is empirically assessed on a two-stage stochastic network flow problem with integer variables in both stages.     

Optimal multiple-objective resource allocation using hybrid particle swarm optimization and adaptive resource bounds technique

The multiple-objective resource allocation problem (MORAP) seeks for an allocation of resource to a number of activities such that a set of objectives are optimized simultaneously and the resource constraints are satisfied. MORAP has many applications, such as resource distribution, project budgeting, software testing, health care resource allocation, etc. This paper addresses the nonlinear MORAP with integer decision variable constraint. To guarantee that all the resource constraints are satisfied, we devise an adaptive-resource-bound technique to construct feasible solutions. The proposed method employs the particle swarm optimization (PSO) paradigm and presents a hybrid execution plan which embeds a hill-climbing heuristic into the PSO for expediting the convergence. To cope with the optimization problem with multiple objectives, we evaluate the candidate solutions based on dominance relationship and a score function. Experimental results manifest that the hybrid PSO derives solution sets which are very close to the exact Pareto sets. The proposed method also outperforms several representatives of the state-of-the-art algorithms on a simulation data set of the MORAP.     

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.     

A tabu search heuristic for ship routing and scheduling with flexible cargo quantities

This paper presents a planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies typically have a certain amount of contract cargoes that they are committed to carry, while trying to maximize their profit from optional spot cargoes. The cargo quantities are often flexible within an interval. Therefore, interwoven with the routing and scheduling decisions, the planner also has to decide the optimal cargo quantities. A tabu search algorithm embedding a specialized heuristic for deciding the optimal cargo quantities in each route is proposed to solve the problem. Computational results show that the heuristic gives optimal or near-optimal solutions to real-life cases of the problem within reasonable time. It is also shown that utilizing the flexibility in cargo quantities gives significantly improved solutions.     

Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.     

Decentralization of responsibility for site decontamination projects: A budget allocation approach

A major problem currently confronting central governments is how to optimally allocate resources for decontamination of polluted sites. ‘Optimally’ here refers to obtaining maximum environmental benefits with the limited resources available. An important issue in budget allocation is that of decentralization, given the magnitude of the information flows between regional and central level necessary in a fully centralized approach. This paper investigates the use of mathematical programming models to support allocation procedures to obtain maximum environmental effectiveness and economic efficiency. We consider the situation where regional authorities provide limited, summary information to the central government, which then allocates budgets. The central government aims to maximize total environmental benefits, subject to a central budget constraint (and constraints on other resources). The problem can be formulated as a mixed integer programming problem, but the size of the problem precludes the search for optimal solutions. We present an effective heuristic and include computational results on its performance.     

Real-time dispatch of trams in storage yards

Real-time dispatch problems arise when preparing and executing the daily schedule of local transport companies. We consider the daily dispatch of transport vehicles like trams in storage yards. Immediately on arrival, each tram has to be assigned to a location in the depot and to an appropriate round trip of the next schedule period. In order to achieve a departure order satisfying the scheduled demand, shunting of vehicles may be unavoidable. Since shunting takes time and causes operational cost, the number of shunting movements should be minimized without violation of operational constraints. As an alternative, we may serve some round trips with trams of type differing from the requested type. In practice, the actual arrival order of trams may differ substantially from the scheduled arrival order. Then, dispatch decisions are due within a short time interval and have to be based on incomplete information. For such real-time dispatch problems, we develop combinatorial optimization models and exact as well as heuristic algorithms. Computational experience for real-world and random data shows that the derived methods yield good (often optimal) solutions within the required tight time bounds. This revised version was published online in June 2006 with corrections to the Cover Date.     

A tabu search heuristic for ship routing and scheduling

The purpose of this paper is to solve a planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies are committed to carrying some contract cargoes and will try to derive additional revenue from optional spot cargoes. An efficient tabu search algorithm has been developed to ensure quick decision support for the planners. The solutions generated by the tabu search heuristic are compared with those produced by a previously published multi-start local search heuristic. Computational results show that the tabu search heuristic yields optimal or near-optimal solutions to real-life instances within reasonable time. For large and tigthly constrained cases, the tabu search heuristic provides much better solutions than the multi-start local search heuristic. A version of the tabu search heuristic will be integrated as an improved solver in a prototype decision support system used by several shipping companies.     

A school bus scheduling problem

This paper introduces a school bus scheduling problem wherein trips for each school are given. A trip consists of a sequence of bus stops and their designated school. Each school has its fixed time window within which trips should be completed. A school bus can serve multiple trips for multiple schools. The school bus scheduling problem seeks to optimize bus schedules to serve all the given trips considering the school time windows. We first model the problem as a vehicle routing problem with time windows (VRPTW) by treating a trip as a virtual stop. Two assignment problem based exact approaches are then proposed for special cases and a heuristic algorithm is proposed for more general cases. Benchmark problems and computational experiments are presented. Computational experiments show the effectiveness of the proposed approaches.     

An evolutionary approach for the target allocation problem

We propose an evolutionary approach for target allocation in tactical level land combat. The purpose is to assign friendly military units to enemy units such that the total weapon effectiveness used is minimised while the attrition goals set for the enemy units are satisfied. A repair algorithm is developed to ensure feasibility with respect to the attrition goal constraints. A tightness measure is devised to determine the population size of the genetic algorithm as a function of constraint tightness. Also, a local improvement algorithm is used to further improve the solution quality. Experimental results indicate that the genetic algorithm can find solutions with acceptable quality in reasonable computation time. Although the approach is developed for the target allocation problem, it can be adapted for other assignment problems.     

Routing and scheduling in project shipping

Tramp shipping companies are committed to transport a set of contracted cargoes and try to derive additional revenue from carrying optional spot cargoes. Here, we present a real life ship routing and scheduling problem for a shipping company operating in project shipping, a special segment of tramp shipping. This segment differs from more traditional tramp segments, as the cargoes are usually transported on a one-time basis. Because of the special nature of the cargoes, complicating requirements regarding stowage onboard the ships and cargo coupling must be considered while determining routes and schedules for the ships in the fleet. A mathematical model is presented and a tabu search heuristic is proposed to solve the problem. Computational results show that the tabu search heuristic provides optimal or near-optimal solutions in a reasonable amount of time, and that it can give significant improvements to manual planning for the shipping company.     

The offshore wind farm array cable layout problem: a planar open vehicle routing problem

In an offshore wind farm (OWF), the turbines are connected to a transformer by cable routes that cannot cross each other. Finding the minimum cost array cable layout thus amounts to a vehicle routing problem with the additional constraints that the routes must be embedded in the plane. For this problem, both exact and heuristic methods are of interest. We optimize cable layouts for real-world OWFs by a hop-indexed integer programming formulation, and develop a heuristic for computing layouts based on the Clarke and Wright savings heuristic for vehicle routing. Our heuristic computes layouts on average only 2% more expensive than the optimal layout. Finally, we present two problem extensions arising from real-world OWF cable layouts, and adapt the integer programming formulation to one of them. The thus obtained optimal layouts are up to 13% cheaper than the actually installed layouts.     

Tackling the edge dynamic graph colouring problem with and without future adjacency information

Many real world operational research problems, such as frequency assignment and exam timetabling, can be reformulated as graph colouring problems (GCPs). Most algorithms for the GCP operate under the assumption that its constraints are fixed, allowing us to model the problem using a static graph. However, in many real-world cases this does not hold and it is more appropriate to model problems with constraints that change over time using an edge dynamic graph. Although exploring methods for colouring dynamic graphs has been identified as an area of interest with many real-world applications, to date, very little literature exists regarding such methods. In this paper we present several heuristic methods for modifying a feasible colouring at time-step t into an initial, but not necessarily feasible, colouring for a “similar” graph at time-step \(t+1\). We will discuss two cases; (1) where changes occur at random, and (2) where probabilistic information about future changes is provided. Experimental results are also presented and the benefits of applying these particular modification methods are investigated.     

On some methods for entropy maximization and matrix scaling

We describe and survey in this paper iterative algorithms for solving the discrete maximum entropy problem with linear equality constraints. This problem has applications e.g. in image reconstruction from projections, transportation planning, and matrix scaling. In particular we study local convergence and asymptotic rate of convergence as a function of the iteration parameter. For the trip distribution problem in transportation planning and the equivalent problem of scaling a positive matrix to achieve a priori given row and column sums, it is shown how the iteration parameters can be chosen in an optimal way. We also consider the related problem of finding a matrix X, diagonally similar to a given matrix, such that corresponding row and column norms in X are all equal. Reports of some numerical tests are given.     

Integrated logistics planning for the air and space expeditionary force

The shift to a US Air Force structured for expeditionary operations has presented the Air Force with a number of challenges in planning, executing, and support operations involving resources such as munitions, fuel, engines, avionics, and war reserve material. In an expeditionary world, the logistics support processes must be capable of responding to rapidly deployed forces, either by deploying along with the fighting units or by connecting support processes in permanent locations to the remote forces. In this paper, we present a general approach for reshaping logistics processes to meet Air Force expeditionary operational goals. We develop capability-based logistics models consisting of rules and algorithms that compute process timelines and requirements for material, equipment, and personnel. We use both optimization and heuristic techniques to formulate a location–allocation solution that can further refine the process.     

Allocation of dependent divisional resources

A resource allocation problem is considered with resources that are dependent in the sense that an allocation to an activity requires the application of several resources, except for certain activities which are divisional in the sense that an allocation to such an activity requires the use of only a single resource. Return and cost functions are assumed to be continuous and increasing, and the allocation variables are continuous. Conditions are given for the replacement of the continuous problem by an associated problem with discrete variables and a single constraint, and to a given degree of accuracy. The associated problem can be efficiently solved by dynamic programming. Certain divisional resource allocation problems with discrete variables and several linear constraints are shown to be equivalent to a discrete problem with a single constraint. A numerical example is given.     

Constraint Handling in Genetic Algorithms: The Set Partitioning Problem

In this paper we present a genetic algorithm-based heuristic for solving the set partitioning problem (SPP). The SPP is an important combinatorial optimisation problem used by many airlines as a mathematical model for flight crew scheduling.A key feature of the SPP is that it is a highly constrained problem, all constraints being equalities. New genetic algorithm (GA) components: separate fitness and unfitness scores, adaptive mutation, matching selection and ranking replacement, are introduced to enable a GA to effectively handle such constraints. These components are generalisable to any GA for constrained problems.We present a steady-state GA in conjunction with a specialised heuristic improvement operator for solving the SPP. The performance of our algorithm is evaluated on a large set of real-world problems. Computational results show that the genetic algorithm-based heuristic is capable of producing high-quality solutions.