A Lagrangian relaxation-based heuristic for the vehicle routing with full container load

We address a problem of vehicle routing that arises in picking up and delivering full container load from/to an intermodal terminal. The substantial cost and time savings are expected by efficient linkage between pickup and delivery tasks, if the time of tasks and the suitability of containers for cargo allow. As this problem is NP-hard, we develop a subgradient heuristic based on a Lagrangian relaxation which enables us to identify a near optimal solution. The heuristic consists of two sub-problems: the classical assignment problem and the generalized assignment problem. As generalized assignment problem is also NP-hard, we employ an efficient solution procedure for a bin packing based problem, which replaces the generalized assignment problem. The heuristic procedure is tested on a wide variety of problem examples. The test results demonstrate that the procedure developed here can efficiently solve large instances of the problem.     

Relaxation heuristics for a generalized assignment problem

We propose relaxation heuristics for the problem of maximum profit assignment of n tasks to m agents (n > m), such that each task is assigned to only one agent subject to capacity constraints on the agents. Using Lagrangian or surrogate relaxation, the heuristics perform a subgradient search obtaining feasible solutions. Relaxation considers a vector of multipliers for the capacity constraints. The resolution of the Lagrangian is then immediate. For the surrogate, the resulting problem is a multiple choice knapsack that is again relaxed for continuous values of the variables, and solved in polynomial time. Relaxation multipliers are used with an improved heuristic of Martello and Toth or a new constructive heuristic to find good feasible solutions. Six heuristics are tested with problems of the literature and random generated problems. Best results are less than 0.5% from the optimal, with reasonable computational times for an AT/386 computer. It seems promising even for problems with correlated coefficients.     

Heuristic Procedures for the Capacitated Vehicle Routing Problem

In this paper we present two new heuristic procedures for the Capacitated Vehicle Routing Problem (CVRP). The first one solves the problem from scratch, while the second one uses the information provided by a strong linear relaxation of the original problem. This second algorithm is designed to be used in a branch and cut approach to solve to optimality CVRP instances. In both heuristics, the initial solution is improved using tabu search techniques. Computational results over a set of known instances, most of them with a proved optimal solution, are given.     

Simple heuristics for the assembly line worker assignment and balancing problem

We propose simple heuristics for the assembly line worker assignment and balancing problem. This problem typically occurs in assembly lines in sheltered work centers for the disabled. Different from the well-known simple assembly line balancing problem, the task execution times vary according to the assigned worker. We develop a constructive heuristic framework based on task and worker priority rules defining the order in which the tasks and workers should be assigned to the workstations. We present a number of such rules and compare their performance across three possible uses: as a stand-alone method, as an initial solution generator for meta-heuristics, and as a decoder for a hybrid genetic algorithm. Our results show that the heuristics are fast, they obtain good results as a stand-alone method and are efficient when used as a initial solution generator or as a solution decoder within more elaborate approaches.     

Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints

In this paper, we consider a parallel machine scheduling problem in which machines have a limited workload capacity and jobs have deadlines and release dates. The problem is motivated by the operation of energy storage management systems for microgrids under emergency conditions and generalizes some problems that have already been studied in the literature for their theoretical value. In this work, we propose heuristic and exact algorithms to solve the problem. The heuristics are adaptations of classical bin packing heuristics in which additional conditions on the feasibility of a solution are imposed, whereas the exact method is a branch-and-price approach. The results show that the branch-and-price approach is able to optimally solve random instances with up to 250 jobs within a time limit of one hour, while the heuristic procedures provide near optimal solution within reduced running times. Finally, we also provide additional complexity results for a special case of the problem.     

Lagrangean/surrogate relaxation for generalized assignment problems

This work presents Lagrangean/surrogate relaxation to the problem of maximum profit assignment of n tasks to m agents (n > m), such that each task is assigned to only one agent subject to capacity constraints on the agents. The Lagrangean/surrogate relaxation combines usual Lagrangean and surrogate relaxations relaxing first a set of constraints in the surrogate way. Then, the Lagrangean relaxation of the surrogate constraint is obtained and approximately optimized (one-dimensional dual). The Lagrangean/surrogate is compared with the usual Lagrangean relaxation on a computational study using a large set of instances. The dual bounds are the same for both relaxations, but the Lagrangean/surrogate can give improved local bounds at the application of a subgradient method, resulting in less computational times. Three relaxations are derived for the problem. The first relaxation considers a vector of multipliers for the capacity constraints, the second for the assignment constraints and the other for the Lagrangean decomposition constraints. Relaxation multipliers are used with efficient constructive heuristics to find good feasible solutions. The application of a Lagrangean/surrogate approach seems very promising for large scale problems.     

A multi-space sampling heuristic for the vehicle routing problem with stochastic demands

The vehicle routing problem with stochastic demands consists in designing transportation routes of minimal expected cost to satisfy a set of customers with random demands of known probability distributions. This paper proposes a simple yet effective heuristic approach that uses randomized heuristics for the traveling salesman problem, a tour partitioning procedure, and a set partitioning formulation to sample the solution space and find high-quality solutions for the problem. Computational experiments on benchmark instances from the literature show that the proposed approach is competitive with the state-of-the-art algorithm for the problem in terms of both accuracy and efficiency. In experiments conducted on a set of 40 instances, the proposed approach unveiled four new best-known solutions (BKSs) and matched another 24. For the remaining 12 instances, the heuristic reported average gaps with respect to the BKS ranging from 0.69 to 0.15 % depending on its configuration.     

The crane scheduling problem: models and solution approaches

In this paper, we study the crane scheduling problem for a vessel after the vessel is moored on a terminal and develop both exact and heuristic solution approaches for the problem. For small-sized instances, we develop a time-space network flow formulation with non-crossing constraints for the problem and apply an exact solution approach to obtain an optimal solution. For medium-sized instances, we develop a Lagrangian relaxation approach that allows us to obtain tight lower bounds and near-optimal solutions. For large-sized instances, we develop two heuristics and show that the error bounds of our heuristics are no more than 100%. Finally, we perform computational studies to show the effectiveness of our proposed solution approaches.     

Generalized cover facet inequalities for the generalized assignment problem

The generalized assignment problem is that of finding an optimal assignment of agents to tasks, where each agent may be assigned multiple tasks and each task is performed exactly once. This is an NP-complete problem. Algorithms that employ information about the polyhedral structure of the associated polytope are typically more effective for large instances than those that ignore the structure. A class of generalized cover facet-defining inequalities for the generalized assignment problem is derived. These inequalities are based upon multiple knapsack constraints and are derived from generalized cover inequalities.     

An effective and fast heuristic for the Dial-a-Ride problem

Dial-a-Ride is an emerging transport system, in which a fleet of vehicles, without fixed routes and schedules, carries people from the desired pickup point to the desired delivery point, during a pre-specified time interval. It can be modeled as an -hard routing and scheduling problem, with a suitable mixed integer programming formulation. Exact approaches to this problem are too limited to tackle real-life instances (hundred of trips), therefore heuristics are needed. The heuristic method proposed in this paper builds an auxiliary graph and then solves an assignment problem on this graph. The auxiliary graph is obtained by replacing pairs of nodes with a single one and associating an ad hoc cost function to the new set of arcs. Two different simple methods are employed to transform the infeasible solution given by the assignment problem into a feasible one. The proposed algorithms have been tested on instances created using the Milan network and shown to be fast and effective.      

Worst case analysis of Max-Regret,Greedy and other heuristics for Multidimensional Assignment and Traveling Salesman Problems

Optimization heuristics are often compared with each other to determine which one performs best by means of worst-case performance ratio reflecting the quality of returned solution in the worst case. The domination number is a complement parameter indicating the quality of the heuristic in hand by determining how many feasible solutions are dominated by the heuristic solution. We prove that the Max-Regret heuristic introduced by Balas and Saltzman (Oper. Res. 39:150–161, 1991) finds the unique worst possible solution for some instances of the s-dimensional (s≥3) assignment and asymmetric traveling salesman problems of each possible size. We show that the Triple Interchange heuristic (for s=3) also introduced by Balas and Saltzman and two new heuristics (Part and Recursive Opt Matching) have factorial domination numbers for the s-dimensional (s≥3) assignment problem.     

A facility neighborhood search heuristic for capacitated facility location with single-source constraints and flexible demand

We consider a generalization of the well-known capacitated facility location problem with single source constraints in which customer demand contains a flexible dimension. This work focuses on providing fast and practically implementable optimization-based heuristic solution methods for very large scale problem instances. We offer a unique approach that utilizes a high-quality efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems.     

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.     

Effective algorithm and heuristic for the generalized assignment problem

We present new Branch-and-Bound algorithm for the generalized assignment problem. A standard subgradient method (SM), used at each node of the decision tree to solve the Lagrangian dual, provides an upper bound. Our key contribution in this paper is a new heuristic, applied at each iteration of the SM, which tries to exploit the solution of the relaxed problem, by solving a smaller generalized assignment problem. The feasible solution found is then subjected to a solution improvement heuristic. We consider processing the root node as a Lagrangian heuristic. Computational comparisons are made with new existing methods.     

同时加工排序问题的分支定界法和启发式算法

同时加工机器或者称为批加工机器是可以同时加工多个工件的机器．本文研究使带权总完工时间为最小的同时加工排序问题1|B|∑wjGj.这个问题的计算复杂性还没有解决．我们给出这个问题的精确解法——分支定界法和几个启发式算法，并且用较多实例对启发式算法的性能进行了比较．     

COSEARCH: A Parallel Cooperative Metaheuristic

In order to design a well-balanced metaheuristic for robustness, we propose the COSEARCH approach which manages the cooperation of complementary heuristic methods via an adaptive memory which contains a history of the search already done. In this paper, we present the idiosyncrasies of the COSEARCH approach and its application for solving large scale instances of the quadratic assignment problem (QAP). We propose an original design of the adaptive memory in order to focus on high quality regions of the search and avoid attractive but deceptive areas. For the QAP, we have hybridized three heuristic agents of complementary behaviours: a Tabu Search is used as the main search algorithm, a Genetic Algorithm is in charge of the diversification and a Kick Operator is applied to intensify the search. The evaluations have been executed on large scale network of workstations via a parallel environment which supports fault tolerance and adaptive dynamic scheduling of tasks.     

A hybrid tabu search/branch & bound approach to solving the generalized assignment problem

A new approach for solving the generalized assignment problem (GAP) is proposed that combines the exact branch & bound approach with the heuristic strategy of tabu search (TS) to produce a hybrid algorithm for solving GAP. The algorithm described uses commercial software to solve sub-problems generated by the TS guiding strategy. The TS approach makes use of the concept of referent domain optimisation and introduces novel add/drop strategies. In addition, the linear programming relaxation of GAP that forms part of the branch & bound approach is itself helpful in suggesting which variables might take binary values. Computational results on benchmark test instances are presented and compared with results obtained by the standard branch & bound approach and also several other heuristic approaches from the literature. The results show the new algorithm performs competitively against the alternatives and is able to find some new best solutions for several benchmark instances.     

Exact and heuristic methods for a full-load,multi-terminal,vehicle scheduling problem with backhauling and time windows

The problem considered is the full-load pickup and delivery problem with time windows (PDPTW), and heterogeneous products and vehicles, where the assignment of pickup points to requests is not predetermined. The problem is first formulated as a 0-1 LP, then a hybrid algorithm is developed, which chooses dynamically between a Greedy heuristic and one based on Regret costs. A multi-level constructive heuristic that consists of three post-optimizers is presented. Two lower bounds are used to evaluate the performance of the proposed heuristics when tested on random instances and selected data from a construction company.     

An empirical study of hyperheuristics for managing very large sets of low level heuristics

Hyperheuristics give us the appealing possibility of abstracting the solution method from the problem, since our hyperheuristic, at each decision point, chooses between different low level heuristics rather than different solutions as is usually the case for metaheuristics. By assembling low level heuristics from parameterised components we may create hundreds or thousands of low level heuristics, and there is increasing evidence that this is effective in dealing with every eventuality that may arise when solving different combinatorial optimisation problem instances since at each iteration the solution landscape is amenable to at least one of the low level heuristics. However, the large number of low level heuristics means that the hyperheuristic has to intelligently select the correct low level heuristic to use, to make best use of available CPU time. This paper empirically investigates several hyperheuristics designed for large collections of low level heuristics and adapts other hyperheuristics from the literature to cope with these large sets of low level heuristics on a difficult real-world workforce scheduling problem. In the process we empirically investigate a wide range of approaches for setting tabu tenure in hyperheuristic methods, for a complex real-world problem. The results show that the hyperheuristic methods described provide a good way to trade off CPU time and solution quality.     

Repulsive Assignment Problem

Standard assignment is the problem of obtaining a matching between two sets of respectively persons and positions so that each person is assigned exactly one position and each position receives exactly one person, while a linear decision maker utility function is maximized. We introduce a variant of the problem where the persons individual utilities are taken into account in a way that a feasible solution must satisfy not only the standard assignment constraints, but also an equilibrium constraint of the complementarity type, which we call repulsive. The equilibrium constraint can be, in turn, transformed into a typically large set of linear constraints. Our problem is NP-hard and it is a special case of the assignment problem with side constraints. We study an exact penalty function approach which motivates a heuristic algorithm. We provide computational experiments that show the usefulness of a heuristic mechanism inspired by the exact approach. The heuristics outperforms a state-of-the-art integer linear programming solver.