The stop-and-drop problem in nonprofit food distribution networks

In this paper, we introduce the stop-and-drop problem (SDRP), a new variant of location-routing problems, that is mostly applicable to nonprofit food distribution networks. In these distribution problems, there is a central warehouse that contains food items to be delivered to agencies serving the people in need. The food is delivered by trucks to multiple sites in the service area and partner agencies travel to these sites to pick up their food. The tactical decision problem in this setting involves how to jointly select a set of delivery sites, assign agencies to these sites, and schedule routes for the delivery vehicles. The problem is modeled as an integrated mixed-integer program for which we delineate a two-phase sequential solution approach. We also propose two Benders decomposition-based solution procedures, namely a linear programming relaxation based Benders implementation and a logic-based Benders decomposition heuristic. We show through a set of realistic problem instances that given a fixed time limit, these decomposition based methods perform better than both the standard branch-and-bound solution and the two-phase approach. The general problem and the realistic instances used in the computational study are motivated by interactions with food banks in southeastern United States.     

A methodology to solve large-scale cooperative transportation planning problems

In this paper, we suggest a methodology to solve a cooperative transportation planning problem and to assess its performance. The problem is motivated by a real-world scenario found in the German food industry. Several manufacturers with same customers but complementary food products share their vehicle fleets to deliver their customers. After an appropriate decomposition of the entire problem into sub problems, we obtain a set of rich vehicle routing problems (VRPs) with time windows for the delivery of the orders, capacity constraints, maximum operating times for the vehicles, and outsourcing options. Each of the resulting sub problems is solved by a greedy heuristic that takes the distance of the locations of customers and the time window constraints into account. The greedy heuristic is improved by an appropriate Ant Colony System (ACS). The suggested heuristics to solve the problem are assessed within a dynamic and stochastic environment in a rolling horizon setting using discrete event simulation. We describe the used simulation infrastructure. The results of extensive simulation experiments based on randomly generated problem instances and scenarios are provided and discussed. We show that the cooperative setting outperforms the non-cooperative one.     

A branch-and-price algorithm for a vehicle routing with demand allocation problem

We investigate the vehicle routing with demand allocation problem where the decision-maker jointly optimizes the location of delivery sites, the assignment of customers to (preferably convenient) delivery sites, and the routing of vehicles operated from a central depot to serve customers at their designated sites. We propose an effective branch-and-price (B&P) algorithm that is demonstrated to greatly outperform the use of commercial branch-and-bound/cut solvers such as CPLEX. Central to the efficacy of the proposed B&P algorithm is the development of a specialized dynamic programming procedure that extends works on elementary shortest path problems with resource constraints in order to solve the more complex column generation pricing subproblem. Our computational study demonstrates the efficacy of the proposed approach using a set of 60 problem instances. Moreover, the proposed methodology has the merit of providing optimal solutions in run times that are significantly shorter than those reported for decomposition-based heuristics in the literature.     

A vehicle routing problem with multi-trips and time windows for circular items

This article presents a vehicle routing problem with time windows, multiple trips, a limited number of vehicles and loading constraints for circular objects. This is a real problem experienced by a home delivery service company. A linear model is proposed to handle small problems and a two-step heuristic method to solve real size instances: the first step builds an initial solution through the modification of the Solomon I1 sequential insertion heuristic, and the second step improves the initial solution through the Tabu search algorithm proposed; in both steps, the problems related to circle packing with different sizes and bin packing are solved jointly with the use of heuristics. Finally, the computing results for two different sets of instances are presented.     

A guided local search metaheuristic for the team orienteering problem

In the team orienteering problem (TOP) a set of locations is given, each with a score. The goal is to determine a fixed number of routes, limited in length, that visit some locations and maximise the sum of the collected scores. This paper describes an algorithm that combines different local search heuristics to solve the TOP. Guided local search (GLS) is used to improve two of the proposed heuristics. An extra heuristic is added to regularly diversify the search in order to explore more areas of the solution space. The algorithm is compared with the best known heuristics of the literature and applied on a large problem set. The obtained results are almost of the same quality as the results of these heuristics but the computational time is reduced significantly. Applying GLS to solve the TOP appears to be a very promising technique. Furthermore, the usefulness of exploring more areas of the solution space is clearly demonstrated.     

A basic variable neighborhood search heuristic for the uncapacitated multiple allocation <Emphasis Type="Italic">p</Emphasis>-hub center problem

The uncapacitated multiple allocation p-hub center problem (UMApHCP) consists of choosing p hub locations from a set of nodes with pairwise traffic demands in order to route the traffic between the origin-destination pairs such that the maximum cost between origin-destination pairs is minimum. It is assumed that transportation between non-hub nodes is possible only via chosen hub nodes. In this paper we propose a basic variable neighborhood search (VNS) heuristic for solving this NP hard problem. In addition we apply two mathematical formulations of the UMApHCP in order to detect limitations of the current state-of-the-art solver used for this problem. The heuristics are tested on benchmark instances for p-hub problems. The obtained results reveal the superiority of the proposed basic VNS over the state-of-the-art as well as over a multi-start local search heuristic developed by us in this paper.     

Design of manufacturing cells in the presence of alternative cell locations and material transporters

This paper addresses two significant issues in the design of cellular manufacturing (CM) systems: (i) the availability of alternative locations for a cell, and (ii) the use of alternative routes to move part loads between cells when the capacity of the material transporter (MT) employed is limited. In addition, several other important factors in the design of CM systems including machine capacity limitations, batches of part demands, non-consecutive operations of parts, and maximum number of machines assigned to a cell are considered. A nonlinear programming model, comprised of binary and general integer variables, is formulated for the research problem. A higher-level heuristic solution algorithm based upon a concept known as ‘tabu search’ is presented for solving industry-size problems. Six different versions of the heuristic are developed to investigate the impact of long-term memory and the use of fixed versus variable tabu-list sizes. Explicit method-based techniques are developed to convert the original nonlinear programming model into an equivalent mixed (binary)-integer linear programming model in order to test the efficacy of the proposed solution technique for solving small problem instances. The solutions obtained from the heuristics have average deviation of less than 3% of the optimal solutions, and require less than a minute in comparison with optimizing methods that needed 1–10 h of computation time. A carefully designed statistical experiment is used to compare the performance of the heuristics by solving three different problem structures, ranging from four to 30 parts, and three to nine locations. The experiment shows that as the problem size increases, the tabu-search-based heuristic using fixed tabu list size and long-term memory based on minimal frequency strategy is preferred over the other heuristics.     

Generalized hyper-heuristics for solving 2D Regular and Irregular Packing Problems

The idea behind hyper-heuristics is to discover some combination of straightforward heuristics to solve a wide range of problems. To be worthwhile, such a combination should outperform the single heuristics. This article presents a GA-based method that produces general hyper-heuristics that solve two-dimensional regular (rectangular) and irregular (convex polygonal) bin-packing problems. A hyper-heuristic is used to define a high-level heuristic that controls low-level heuristics. The hyper-heuristic should decide when and where to apply each single low-level heuristic, depending on the given problem state. In this investigation two kinds of heuristics were considered: for selecting the figures (pieces) and objects (bins), and for placing the figures into the objects. Some of the heuristics were taken from the literature, others were adapted, and some other variations developed by us. We chose the most representative heuristics of their type, considering their individual performance in various studies and also in an initial experimentation on a collection of benchmark problems. The GA included in the proposed model uses a variable-length representation, which evolves combinations of condition-action rules producing hyper-heuristics after going through a learning process which includes training and testing phases. Such hyper-heuristics, when tested with a large set of benchmark problems, produce outstanding results for most of the cases. The testbed is composed of problems used in other similar studies in the literature. Some additional instances for the testbed were randomly generated.     

Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls

Metaheuristics are a class of approximate methods designed to solve hard combinatorial optimization problems arising within various different areas. The importance of metaheuristics results from their ability to continue the search beyond a local optimum so that near-optimal or optimal solutions are efficiently found. In order to solve the backhauling problem associated with mixed and simultaneous delivery and pick-ups, this paper presents a hybrid algorithm which is comprised of the two metaheuristics of tabu search and variable neighbourhood descent. The primary challenge associated with backhauling consists of creating routes in which vehicles are not only required to deliver goods, but also to perform pick-ups at customer locations. The problems associated with these two categories of problems, however, have received little attention in the literature to date. A set of examples taken from the literature with Euclidean cost matrices are presented. Finally, some numerical results are illustrated to show the effectiveness of the proposed approach.     

Single Machine Scheduling with a Common Delivery Window

In this paper we consider the single machine scheduling problem of minimizing the mean absolute deviation (MAD) of job completion times from a restricted common delivery window. This problem is NP-hard. A Lagrangian relaxation procedure is proposed to solve the problem. Two efficient heuristics are also proposed. An experimental study on randomly generated problems is carried out to test the performance of the proposed methods. The computational results show that the obtained lower bounds are very good and the proposed heuristics generate near-optimal solutions.     

Real-time split-delivery pickup and delivery time window problems with transfers

In this research we present the design and implementation of heuristics for solving split-delivery pickup and delivery time window problems with transfer (SDPDTWP) of shipments between vehicles for both static and real-time data sets. In the SDPDTWP each shipment is constrained with the earliest possible pickup time from the origin and the latest acceptable delivery time to a destination. Split-deliveries occur when two or more vehicles service the same origin or destination. The proposed heuristics were applied to both static and real-time data sets. The heuristics computed a solution, in a few seconds, for a static problem from the literature, achieving an improvement of 60% in distance in comparison to the published solution. In the real-time SDPDTWP problems, requests for pickup and delivery of a package, breakdown of a truck or insertion of a truck can occur after the vehicle has left the origin and is enroute to service the customers. Thirty data sets, each consisting of one to seven real-time customer or truck events, were used to test the efficiency of the heuristics. The heuristics obtained solutions to real-time data sets in under five seconds of CPU time.      

Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms

The probabilistic traveling salesman problem concerns the best way to visit a set of customers located in some metric space, where each customer requires a visit only with some known probability. A solution to this problem is an a priori tour which visits all customers, and the objective is to minimize the expected length of the a priori tour over all customer subsets, assuming that customers in any given subset must be visited in the same order as they appear in the a priori tour. This problem belongs to the class of stochastic vehicle routing problems, a class which has received increasing attention in recent years, and which is of major importance in real world applications.Several heuristics have been proposed and tested for the probabilistic traveling salesman problem, many of which are a straightforward adaptation of heuristics for the classical traveling salesman problem. In particular, two local search algorithms (2-p-opt and 1-shift) were introduced by Bertsimas.In a previous report we have shown that the expressions for the cost evaluation of 2-p-opt and 1-shift moves, as proposed by Bertsimas, are not correct. In this paper we derive the correct versions of these expressions, and we show that the local search algorithms based on these expressions perform significantly better than those exploiting the incorrect expressions.     

Set covering location models with stochastic critical distances

This paper formulates a new version of set covering models by introducing a customer-determined stochastic critical distance. In this model, all services are provided at the sites of facilities, and customers have to go to the facility sites to obtain the services. Due to the randomness of their critical distance, customers patronize a far or near facility with a probability. The objective is to find a minimum cost set of facilities so that every customer is covered by at least one facility with an average probability greater than a given level α. We consider an instance of the problem by embedding the exponential effect of distance into the model. An algorithm based on two searching paths is proposed for solutions to the instance. Experiments show that the algorithm performs well for problems with greater α, and the experimental results for smaller α are reported and analysed.     

Integrating two-dimensional cutting stock and lot-sizing problems

The two-dimensional cutting stock problem (2DCSP) consists in the minimization of the number of plates used to cut a set of items. In industry, typically, an instance of this problem is considered at the beginning of each planning time period, what may result in solutions of poor quality, that is, excessive waste, when a set of planning periods is considered. To deal with this issue, we consider an integrated problem, in which the 2DCSP is extended from the solution in only a single production planning period to a solution in a set of production planning periods. The main difference of the approach in this work and the ones in the literature is to allow sufficiently large residual plates (leftovers) to be stored and cut in a subsequent period of the planning horizon, which may further help in the minimization of the waste. We propose two integrated integer programming models to optimize the combined two-dimensional cutting stock and lot-sizing problems, minimizing the total cost, which includes material, waste and storage costs. Two heuristics based on the industrial practice to solve the problem were also presented. Computational results for the proposed models and for the heuristics are presented and discussed.     

Reducing work-in-process movement for multiple products in one-dimensional layout problems

This research describes a method to assign M machines, which are served by a material handling transporter, to M equidistant locations along a track, so that the distance traveled by a given set of jobs is minimized. Traditionally, this problem (commonly known as a machine location problem) has been modeled as a quadratic assignment problem (QAP), which is NP-hard, thus motivating the need for efficient procedures to solve instances with several machines. In this paper we develop a branching heuristic to obtain sub-optimum solutions to the problem; a lower bound on the optimum solution has also been presented. Results obtained from the heuristics are compared with results obtained from other heuristics with similar objectives. It is observed that the results are promising, and justify the usage of developed methods.     

A multi-level composite heuristic for the multi-depot vehicle fleet mix problem

The problem of simultaneously allocating customers to depots, finding the delivery routes and determining the vehicle fleet composition is addressed. A multi-level composite heuristic is proposed and two reduction tests are designed to enhance its efficiency. The proposed heuristic is tested on benchmark problems involving up to 360 customers, 2 to 9 depots and 5 different vehicle capacities. When tested on the special case, the multi-depot vehicle routing, our heuristic yields solutions almost as good as those found by the best known heuristics but using only 5 to 10% of their computing time. Encouraging results were also obtained for the case where the vehicles have different capacities.     

A single-resource revenue management problem with random resource consumptions

We study a single-resource multi-class revenue management problem where the resource consumption for each class is random and only revealed at departure. The model is motivated by cargo revenue management problems in the airline and other shipping industries. We study how random resource consumption distribution affects the optimal expected profit and identify a preference acceptance order on classes. For a special case where the resource consumption for each class follows the same distribution, we fully characterize the optimal control policy. We then propose two easily computable heuristics: (i) a class-independent heuristic through parameter scaling, and (ii) a decomposition heuristic that decomposes the dynamic programming formulation into a collection of one-dimensional problems. We conduct extensive numerical experiments to investigate the performance of the two heuristics and compared them with several widely studied heuristic policies. Our results show that both heuristics work very well, with class-independent heuristic slightly better between the two. In particular, they consistently outperform heuristics that ignore demand and/or resource consumption uncertainty. Our results demonstrate the importance of considering random resource consumption as another problem dimension in revenue management applications.     

Variable neighbourhood search heuristics for the probabilistic multi-source Weber problem

The Multi-source Weber Problem (MWP) is concerned with locating m facilities in the Euclidean plane, and allocating these facilities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation for the probabilistic MWP called the PMWP. For its solution, we propose two heuristics based on variable neighbourhood search (VNS). Computational results obtained on a number of test instances show that the VNS heuristics improve the performance of a probabilistic alternate location-allocation heuristic referred to as PALA. In its original form, the applicability of the new heuristics depends on the existence of a closed-form expression for the expected distances between facilities and customers. Unfortunately, such an expression exists only for a few distance function and probability distribution combinations. We therefore use two approximation methods for the expected distances, which make the VNS heuristics applicable for any distance function and bivariate distribution of customer locations.     

Heuristics for vehicle routing on tree-like networks

This paper presents two new heuristics for the vehicle routing problem on tree-like road networks. These networks occur, for example, in rural road systems where the supply (or delivery) nodes are located on rural roads leading off from a few highways which form the ‘trunks’ of a tree-like network. The heuristics have the conventional objective of minimising the total distance travelled by the vehicles. The development of the heuristics takes advantage of the tree-like structure of the network. These two new heuristics and two other heuristics from the published literature are applied to some test problems and computational results are presented. The computational experience indicates that one of the new heuristics provides superior solutions to the existing heuristics and in reasonable computing time. It therefore appears suitable for large-scale practical routing problems.     

Heuristic,meta-heuristic and hyper-heuristic approaches for fresh produce inventory control and shelf space allocation

The allocation of fresh produce to shelf space represents a new decision support research area which is motivated by the desire of many retailers to improve their service due to the increasing demand for fresh food. However, automated decision making for fresh produce allocation is challenging because of the very short lifetime of fresh products. This paper considers a recently proposed practical model for the problem which is motivated by our collaboration with Tesco. Moreover, the paper investigates heuristic and meta-heuristic approaches as alternatives for the generalized reduced gradient algorithm, which becomes inefficient when the problem size becomes larger. A simpler single-item inventory problem is firstly studied and solved by a polynomial time bounded procedure. Several dynamic greedy heuristics are then developed for the multi-item problem based on the procedure for the single-item inventory problem. Experimental results show that these greedy heuristics are much more efficient and provide competitive results when compared to those of a multi-start generalized reduced gradient algorithm. In order to further improve the solution, we investigated simulated annealing, a greedy randomized adaptive search procedure and three types of hyper-heuristics. Their performance is tested and compared on a set of problem instances which are made publicly available for the research community.