A transportation problem formulation for the MAC Airlift Planning problem

The Military Airlift Command (MAC) is responsible for planning the allocation of airlift resources for the movement of cargo and passengers. A heuristic algorithm, the Airlift Planning Algorithm (APA), has recently been developed under subcontract to the Oak Ridge National Laboratory to assist MAC in scheduling airlift resources. In this paper, we present a transportation problem formulation which can be used as a preprocessor to the APA or as an estimator for the APA. This paper examines the robustness and sensitivity of the transportation problem formulation. In particular, the performance of the APA improves by approximately 10% when the transportation problem is used as a preprocessor for two hypothetical problems and improves by up to 50% for derived airlift constrained problems.     

A simple algorithm to search for all MCs in networks

Evaluating the network reliability is an important topic in the planning, designing, and control of systems. The minimal cut (MC, an edge set) set is one of the major and fundamental tools for evaluating the network reliability. In this study, an alternative method is given to define a MC using a node set (called MCV). A very simple algorithm based on some intuitive theorems that characterize the structure of the MCV and the relationship between MC and MCV is developed to find the MCs between two special nodes. The proposed algorithm is then generalized to find all MCs between all pairs of nodes. The proposed algorithm is not only easier to understand and implement, but is also better than the existing best-known algorithm. The correctness of the proposed algorithm will be analyzed and proven. One example is illustrated to show how all MCs are generated and verified in a network using the proposed algorithm.     

An ILS-biased randomization algorithm for the two-dimensional loading HFVRP with sequential loading and items rotation

This paper discusses the Two-dimensional Loading Vehicle Routing Problem with Heterogeneous Fleet, Sequential Loading, and Item Rotation (2L-HFVRP-SR). Despite the fact that the 2L-HFVRP-SR can be found in many real-life situations related to the transportation of voluminous items, where heterogeneity of fleets, two-dimensional packing restrictions, sequential loading, and items rotation have to be considered, this rich version of vehicle routing-and-packing problem has been rarely analysed in the literature. Accordingly, this paper contributes to filling the gap by presenting a relatively simple-to-implement algorithm which is able to provide state-of-the-art solutions for such a complex problem in relatively short computational times. The proposed algorithm integrates inside an Iterated Local Search framework, biased-randomized versions of both vehicle routing and packing heuristics. The efficiency of the proposed algorithm is validated throughout an extensive set of computational tests.     

An exact depth-first algorithm for the pallet loading problem

This paper proposes a fast exact algorithm to solve the Pallet Loading Problem (PLP) using depth-first strategy. A new concept called Maximal Breadth Filling Sequence (MBFS) is introduced to bring down the size of the search tree. The algorithm makes use of two pruning rules — lower-bound pruning and state-dominance pruning. Although depth-first search, by itself, requires very little memory, the dominance pruning rule makes effective utilization of the available memory. For large problems, more the memory available, more effective is the dominance pruning. The algorithm has been tested on standard problem sets. It has been found to be quite fast in outputting optimal solutions. Empirical findings are given in detail.     

A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem

This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP generalizes the classical Capacitated Vehicle Routing Problem by considering the existence of different vehicle types, with distinct capacities and costs. The objective is to determine the best fleet composition as well as the set of routes that minimize the total costs. The proposed hybrid algorithm is composed by an Iterated Local Search (ILS) based heuristic and a Set Partitioning (SP) formulation. The SP model is solved by means of a Mixed Integer Programming solver that interactively calls the ILS heuristic during its execution. The developed algorithm was tested in benchmark instances with up to 360 customers. The results obtained are quite competitive with those found in the literature and new improved solutions are reported.     

An Ant Colony Algorithm for the Capacitated Vehicle Routing

The Vehicle Routing Problem (VRP) requires the determination of an optimal set of routes for a set of vehicles to serve a set of customers. We deal here with the Capacitated Vehicle Routing Problem (CVRP) where there is a maximum weight or volume that each vehicle can load. We developed an Ant Colony algorithm (ACO) for the CVRP based on the metaheuristic technique introduced by Colorni, Dorigo and Maniezzo. We present preliminary results that show that ant algorithms are competitive with other metaheuristics for solving CVRP.     

Solving the pallet loading problem

This paper presents new bounds, heuristics, and an exact algorithm for the Pallet Loading Problem (PLP). PLP maximizes the number of boxes placed on a rectangular pallet. All boxes have identical rectangular dimensions and, when placed, must be located completely within the pallet. Boxes may be rotated 90° so long as they are placed with edges parallel to the pallet’s edges. The set of all PLP instances with an area ratio (pallet area divided by box area) less than 101 boxes can be represented by 3,080,730 equivalent classes. Our G5-heuristic finds optimal solutions to 3,073,724 of these 3,080,730 classes and in the remaining 7006 classes only differs from the best known bound by one box. We develop three other heuristics that solve another 54 instances. Finally, we solve the 6952 remaining classes with our exact HVZ algorithm. Only a subset of these classes has been solved previously.     

A unified exact method for solving different classes of vehicle routing problems

This paper presents a unified exact method for solving an extended model of the well-known Capacitated Vehicle Routing Problem (CVRP), called the Heterogenous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles having different capacities, routing and fixed costs is used to supply a set of customers. The HVRP model considered in this paper contains as special cases: the Single Depot CVRP, all variants of the HVRP presented in the literature, the Site-Dependent Vehicle Routing Problem (SDVRP) and the Multi-Depot Vehicle Routing Problem (MDVRP). This paper presents an exact algorithm for the HVRP based on the set partitioning formulation. The exact algorithm uses three types of bounding procedures based on the LP-relaxation and on the Lagrangean relaxation of the mathematical formulation. The bounding procedures allow to reduce the number of variables of the formulation so that the resulting problem can be solved by an integer linear programming solver. Extensive computational results over the main instances from the literature of the different variants of HVRPs, SDVRP and MDVRP show that the proposed lower bound is superior to the ones presented in the literature and that the exact algorithm can solve, for the first time ever, several test instances of all problem types considered.      

The minimum size instance of a Pallet Loading Problem equivalence class

The Pallet Loading Problem (PLP) maximizes the number of identical rectangular boxes placed within a rectangular pallet. Boxes may be rotated 90° so long as they are packed with edges parallel to the pallet’s edges, i.e., in an orthogonal packing. This paper defines the Minimum Size Instance (MSI) of an equivalence class of PLP, and shows that every class has one and only one MSI. We develop bounds on the dimensions of box and pallet for the MSI of any class. Applying our new bounds on MSI dimensions, we present an algorithm for MSI generation and use it to enumerate all 3,080,730 equivalence classes with an area ratio (pallet area divided by box area) smaller than 101 boxes. Previous work only provides bounds on the ratio of box dimensions and only considers a subset of all classes presented here.     

An empirical study on the benefit of split loads with the pickup and delivery problem

Splitting loads such that the delivery of certain loads is completed in multiple trips rather than one trip has been shown to have benefit for both the classic Vehicle Routing Problem (VRP) and the Pickup and Delivery Problem (PDP). However, the magnitude of the benefit may be affected by various problem characteristics. In this paper, we characterize those real world environments in which split loads are most likely to be beneficial. Based on practitioner interest, we determine how the benefit is affected by the mean load size and variance, number of origins relative to the number of destinations, the percentage of origin–destination pairs with a load requiring service, and the clustering of origin and destination locations. We find that the magnitude of benefit is greatest for load sizes just over one half vehicle capacity as these loads can not be combined without splitting, while they are the easiest to combine on a vehicle with splitting; increases as the number of loads sharing an origin or destination increases because there are more potential load combinations to split at each stop; and increases as the average distance from an origin to a destination increases because splitting loads reduces the trips from origins to destinations.     

The mixed general routing polyhedron

 In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the associated polyhedron and some large families of facet-inducing inequalities are described. A preliminary cutting-plane algorithm has produced very good lower bounds over a set of 100 randomly generated instances of the Mixed Rural Postman Problem. Finally, applications of this study to other known routing problems are described. Received: June 30, 1999 / Accepted: March 2002 Published online: March 21, 2003 Key Words. polyhedral combinatorics – facets – routing – arc routing – rural postman problem – general routing problem – mixed chinese postman problem     

A fast algorithm for identifying minimum size instances of the equivalence classes of the Pallet Loading Problem

In this paper, a novel and fast algorithm for identifying the Minimum Size Instance (MSI) of the equivalence class of the Pallet Loading Problem (PLP) is presented. The new algorithm is based on the fact that the PLP instances of the same equivalence class have the property that the aspect ratios of their items belong to an open interval of real numbers. This interval characterises the PLP equivalence classes and is referred to as the Equivalence Ratio Interval (ERI) by authors of this paper. The time complexity of the new algorithm is two polynomial orders lower than that of the best known algorithm. The authors of this paper also suggest that the concept of MSI and its identifying algorithm can be used to transform the non-integer PLP into its equivalent integer MSI.     

Metric inequalities and the Network Loading Problem

Given a simple graph G(V,E) and a set of traffic demands between the nodes of G, the Network Loading Problem consists of installing minimum cost integer capacities on the edges of G allowing routing of traffic demands.In this paper we study the Capacity Formulation of the Network Loading Problem, introducing the new class of Tight Metric Inequalities, that completely characterize the convex hull of the integer feasible solutions of the problem.We present separation algorithms for Tight Metric Inequalities and a cutting plane algorithm, reporting on computational experience.     

Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery

This work proposes a Branch-cut-and-price (BCP) approach for the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). We also deal with a particular case of the VRPSPD, known as the Vehicle Routing Problem with Mixed Pickup and Delivery. The BCP algorithm was tested in well-known benchmark instances involving up to 200 customers. Four instances were solved for the first time and some LBs were improved.     

Model and algorithms for multi-period sea cargo mix problem

In this paper, we consider the sea cargo mix problem in international ocean container shipping industry. We describe the characteristics of the cargo mix problem for the carrier in a multi-period planning horizon, and formulate it as a multi-dimensional multiple knapsack problem (MDMKP). In particular, the MDMKP is an optimization model that maximizes the total profit generated by all freight bookings accepted in a multi-period planning horizon subject to the limited shipping capacities. We propose two heuristic algorithms that can solve large scale problems with tens of thousands of decision variables in a short time. Finally, numerical experiments on a wide range of randomly generated problem instances are conducted to demonstrate the efficiency of the algorithms.     

Fuel treatment planning: Fragmenting high fuel load areas while maintaining availability and connectivity of faunal habitat

Reducing the fuel load in fire-prone landscapes is aimed at mitigating the risk of catastrophic wildfires but there are ecological consequences. Maintaining habitat for fauna of both sufficient extent and connectivity while fragmenting areas of high fuel loads presents land managers with seemingly contrasting objectives. Faced with this dichotomy, we propose a Mixed Integer Programming (MIP) model that can optimally schedule fuel treatments to reduce fuel hazards by fragmenting high fuel load regions while considering critical ecological requirements over time and space. The model takes into account both the frequency of fire that vegetation can tolerate and the frequency of fire necessary for fire-dependent species. Our approach also ensures that suitable alternate habitat is available and accessible to fauna affected by a treated area. More importantly, to conserve fauna the model sets a minimum acceptable target for the connectivity of habitat at any time. These factors are all included in the formulation of a model that yields a multi-period spatially-explicit schedule for treatment planning. Our approach is then demonstrated in a series of computational experiments with hypothetical landscapes, a single vegetation type and a group of faunal species with the same habitat requirements. Our experiments show that it is possible to fragment areas of high fuel loads while ensuring sufficient connectivity of habitat over both space and time. Furthermore, it is demonstrated that the habitat connectivity constraint is more effective than neighbourhood habitat constraints. This is critical for the conservation of fauna and of special concern for vulnerable or endangered species.     

Ship routing and scheduling with flexible cargo sizes

Here, we describe a real planning problem in the tramp shipping industry. A tramp shipping company may have a certain amount of contract cargoes that it is committed to carry, and tries to maximize the profit from optional cargoes. For real long-term contracts, the sizes of the cargoes are flexible. However, in previous research within tramp ship routing, the cargo quantities are regarded as fixed. We present an MP-model of the problem and a set partitioning approach to solve the multi-ship pickup and delivery problem with time windows and flexible cargo sizes. The columns are generated a priori and the most profitable ship schedule for each cargo set–ship combination is included in the set partitioning problem. We have tested the method on several real-life cases, and the results show the potential economical effects for the tramp shipping companies by utilizing flexible cargo sizes when generating the schedules.     

COMPUTING THE NEAREST BISYMMETRIC POSITIVE SEMIDEFINITE MATRIX UNDER THE SPECTRAL RESTRICTION

Let A and C denote real n × n matrices. Given real n-vectors x1, ... ,xm, m ≤ n, and a set of numbers L = {λ1,λ2,... ,λm}. We describe (I) the set (?) of all real n × n bisymmetric positive seidefinite matrices A such that Axi is the "best" approximate to λixi, i = 1,2,...,m in Frobenius norm and (II) the Y in set (?) which minimize Frobenius norm of ||C - Y||.An existence theorem of the solutions for Problem I and Problem II is given and the general expression of solutions for Problem I is derived. Some sufficient conditions under which Problem I and Problem II have an explicit solution is provided. A numerical algorithm of the solution for Problem II has been presented.