A new heuristic branching scheme for the crew pairing problem with base constraints

Airline crew scheduling is typically performed in two steps : crew pairing followed by crew assignment. The crew pairing problem (CPP) finds a set of pairings (sequences of flights separated by connections or rests starting and ending at the same crew base) that covers a set of flights at minimum cost. The crew assignment problem consists of assigning the crew members to these pairings to create their individual schedules. The main downside of this sequential approach is that the pairings generated in the first step are not all suitable for the crew assignment step, yielding poor-quality solutions. This paper studies an extension of the CPP that includes additional constraints limiting the total worked time at each crew base. This problem, called the CPP with base constraints (CPPBC), is designed to improve the coupling of the two scheduling steps. To solve the CPPBC, we develop four branch-and-price heuristics: three of them rely on known heuristic branching schemes, the other introduces a new branching method, called retrospective branching. This branching scheme is designed to detect and revise poor branching decisions made earlier in the search tree, without backtracking. We tested and compared these four heuristics on real-world datasets. Our results show that the algorithm with retrospective branching yields, most of the times, better-quality solutions than the other tested methods.     

A new algorithm for the directed chinese postman problem

The directed Chinese Postman Problem can be transformed into a minimum cost flow problem over a derived network, or be transformed into a transportation problem in which the coefficients are determined by a shortest path problem over an extended network. Based on the Complementary Slackness Theorem, this paper will present an algorithm for the directed Chinese Postman Problem, which can be applied directly to the original network and, compared with the existing algorithms, has a better computational complexity O(kn²) where k depends on the structure of the network. The algorithm is extended to the directed m-CPP case.     

A new bidirectional heuristic for the assembly line balancing problem

Assembly line balancing problem (ALBP) is one of the well-known NP-hard layout planning problems for mass production systems. Many exact solution approaches have been developed, including 0–1 integer programming model, branch and bound algorithm, dynamic programming model, etc.; however, all optimal approaches are computationally inefficient in solving large-scale problems, which makes heuristic approaches a necessity in practice. In this paper we propose a new efficient heuristic, based on a recent bidirectional approach and the famous critical path method (CPM) widely used in project management, to resolve the issue of task assignment for ALBP. An example is given for illustration, and numerical results of sample problems selected from the literature are also given to show the effectiveness of the proposed heuristic.     

A new heuristic algorithm for the operating room scheduling problem

Due to the great importance of operating rooms in hospitals, this paper studies an operating room scheduling problem with open scheduling strategy. According to this strategy, no time slot is reserved for a particular surgeon. The surgeons can use all available time slots. Based on Fei et al.’s model which is considered to be close to reality, we develop a heuristic algorithm to solve it. The idea of this heuristic algorithm is from dynamic programming by aggregating states to avoid the explosion of the number of states. The objective of this paper is to design an operating program to maximize the operating rooms’ use efficiency and minimize the overtime cost. Computational results show that our algorithm is efficient, especially for large size instances where our algorithm always finds feasible solutions while the algorithm of Fei et al. does not.     

A new heuristic for solving the p-median problem in the plane

This paper presents a new local search for solving the continuous p-median problem in the plane. The basic idea is to first find a good starting solution by overlaying the area containing the set of demand points with a grid and solving heuristically the location problem on this grid. The solution is then used as an initial point for running an improved version of Cooper's well-known alternating local search.     

A new heuristic recursive algorithm for the strip rectangular packing problem

A fast and new heuristic recursive algorithm to find a minimum height for two-dimensional strip rectangular packing problem is presented. This algorithm is mainly based on heuristic strategies and a recursive structure, and its average running time is T(n)=θ(n³)$T(n)=\theta (n^3)$. The computational results on a class of benchmark problems have shown that this algorithm not only finds shorter height than the known meta-heuristic ones, but also runs in shorter time. Especially for large test problems, it performs better.     

A GRASP algorithm based new heuristic for the capacitated location routing problem

Abstract

In this paper, the capacitated location-routing problem (CLRP) is studied. CLRP is composed of two hard optimisation problems: the facility location problem and the vehicle routing problem. The objective of CLRP is to determine the best location of multiple depots with their vehicle routes such that the total cost of the solution is minimal. To solve this problem, we propose a greedy randomised adaptive search procedure. The proposed method is based on a new heuristic to construct a feasible CLRP solution, and then a local search-based simulated annealing is used as improvement phase. We have used a new technique to construct the clusters around the depots. To prove the effectiveness of our algorithm, several LRP instances are used. The results found are very encouraging.     

A new heuristic algorithm for the circular packing problem with equilibrium constraints

The circular packing problem with equilibrium constraints is an optimization problem about simplified satellite module layout design.A heuristic algorithm based on tabu search is put forward for solving this problem.The algorithm begins from a random initial configuration and applies the gradient method with an adaptive step length to search for the minimum energy configuration.To jump out of the local minima and avoid the search doing repeated work,the algorithm adopts the strategy of tabu search.In the pr...     

A heuristic for the label printing problem

Label printing finds many applications in industry. However, this task is still labor intensive in many printing factories. Since each template can only accommodate a fixed number of labels, an important task is to work out the compositions of templates by allocating suitable labels to each template in order to fulfill the order requirements effectively. The template design could be rather arbitrary, which usually ends up with a lot of excessive printed labels. Enhancing the template design will significantly improve the efficiency of the printing process, and, at the same time, reduce the waste of resources. This motivates the study of more automatic design methods. In this paper, the problem is first formulated as a nonlinear integer programming problem. The main variables in the formulation are the compositions and the printing frequencies of templates. For practical purpose, each type of label is confined to one template only which allows automated packing and handling. The structure of the problems is carefully analyzed and a new algorithm is proposed. Numerical results show that the proposed method is a simple but effective way of generating good template designs.     

A new and efficient ant-based heuristic method for solving the traveling salesman problem

Abstract: In this paper, we present an efficient metaheuristic approach for solving the problem of the traveling salesman. We introduce the multiple ant clans concept from parallel genetic algorithms to search solution space using different islands to avoid local minima in order to obtain a global minimum for solving the traveling salesman problem. Our simulation results indicate that the proposed novel traveling salesman problem method (called the ACOMAC algorithm) performs better than a promising approach named the ant colony system. This investigation is concerned with a real life logistics system design which optimizes the performance of a logistics system subject to a required service level in the vehicle routing problem. In this work, we also concentrate on developing a vehicle routing model by improving the ant colony system and using the multiple ant clans concept. The simulation results reveal that the proposed method is very effective and potentially useful in solving vehicle routing problems.     

A decomposition-based heuristic for the multiple-product inventory-routing problem

The inventory-routing problem is an integrated logistics planning problem arising in situations where customers transfer the responsibility for inventory replenishment to the vendor. The vendor must then decide when to visit each customer, how much to deliver and how to sequence customers in vehicle routes. In this paper, we focus on the case where several different products have to be delivered by a fleet of vehicles over a finite and discrete planning horizon. We present a three-phase heuristic based on a decomposition of the decision process of the vendor. In the first phase, replenishment plans are determined by using a Lagrangian-based method. These plans do not specify delivery sequences for the vehicles. The sequencing of the planned deliveries is performed in the second phase in which a simple procedure is employed to construct vehicle routes. The third phase incorporates planning and routing decisions into a mixed-integer linear programming model aimed at finding a good solution to the integrated problem. Computational experiments show that our heuristic is effective on instances with up to 50 customers and 5 products.     

A new heuristic to solve the one-warehouse N-retailer problem

We deal with a multi-echelon inventory system in which one warehouse supplies an item to multiple retailers. Customer demand arrives at each retailer at a constant rate. The retailers replenish their inventories from the warehouse that in turn orders from an outside supplier. It is assumed that shortages are not allowed and lead times are negligible. The goal is to determine replenishment policies that minimize the overall cost in the system. We develop a heuristic to compute efficient policies, which also can easily be used in a spreadsheet application. The main idea consists of finding a balance between the replenishment and the inventory holding costs at each installation. This new heuristic we compare with two other approaches proposed in the literature; the computational studies show that in most of the instances generated the new method provides lower costs.     

A multi-phase heuristic for the production routing problem

This study considers the production routing problem where a plant produces and distributes a single item to multiple retailers over a multi-period time horizon. The problem is to decide on when and how much to produce and stock at the plant, when and how much to serve and stock at each retailer, and vehicle routes for shipments such that the sum of fixed production setup cost, variable production cost, distribution cost, and inventory carrying cost at the plant and retailers is minimized. A multi-phase heuristic is proposed for the problem. The proposed heuristic is a mathematical programming-based heuristic that relies on formulating and solving restricted versions of the problem as mixed integer programs. The computational experiments on benchmark instances show favorable results with regard to the quality of the solutions found at the expense of higher computing times on large instances. In particular, the heuristic managed to find new best solutions for the 65% of benchmark instances.     

A heuristic for the periodic rural postman problem

The periodic rural postman problem (PRPP) is variant of the classical rural postman problem whose applications arise in garbage collection and street sweeping. In the PRPP each required arc/edge of a graph must be visited a given number of times over an m-day planning period in such a way that service days are equally spaced. The PRPP amounts to select a service day combination for each required arc/edge and to determine a postman tour for each day of the planning period. The objective is to minimize the total distance travelled. In this paper a simple but effective heuristic for the undirected PRPP is presented. Extensive computational results indicate that the algorithm is capable of providing high quality solutions. To our knowledge this is the first methodological paper devoted to a periodic arc routing problem.     

A hybrid heuristic for the traveling salesman problem

The combination of genetic and local search heuristics has been shown to be an effective approach to solving the traveling salesman problem (TSP). This paper describes a new hybrid algorithm that exploits a compact genetic algorithm in order to generate high-quality tours, which are then refined by means of the Lin-Kernighan (LK) local search. The local optima found by the LK local search are in turn exploited by the evolutionary part of the algorithm in order to improve the quality of its simulated population. The results of several experiments conducted on different TSP instances with up to 13,509 cities show the efficacy of the symbiosis between the two heuristics     

A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure

A phylogeny is a tree that relates taxonomic units, based on their similarity over a set of characters. The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps. We propose a new neighborhood structure for the phylogeny problem. A greedy randomized adaptive search procedure heuristic based on this neighborhood structure and using variable neighborhood descent for local search is described. Computational results on randomly generated and benchmark instances are reported, showing that the new heuristic is quite robust and outperforms the other algorithms in the literature in terms of solution quality and time‐to‐target value.     

A heuristic manipulation technique for the sequential ordering problem

The sequential ordering problem is a version of the asymmetric travelling salesman problem where precedence constraints on vertices are imposed. A tour is feasible if these constraints are respected, and the objective is to find a feasible solution with minimum cost.The sequential ordering problem models many real-world applications, mainly in the fields of transportation and production planning.A problem manipulation technique to be used in conjunction with heuristic algorithms is discussed. The aim of the technique is to make the search space associated with each problem more attractive for the underlying heuristic algorithms.This novel methodology is tested in combination with the state-of-the-art method for the sequential ordering problem. Improved results are obtained, particularly for the largest problems considered.