1,720,980 research outputs found
A local-search-based heuristic for the demand-constrained multidimensional knapsack problem
No full textWe consider an extension of the 0–1 multidimensional knapsack problem in which there are greater-than-or-
equal-to inequalities, called demand constraints, in addition to the standard less-than-or-equal-to constraints.
Moreover, the objective function coefficients are not constrained in sign. This problem is worth considering
because it is embedded in models of practical application, it has an intriguing combinatorial structure,
and it appears to be a challenging problem for commercial ILP solvers. Our approach is based on a nested tabu-search
algorithm in which neighborhoods with different structures are exploited. First, a tabu-search procedure
is carried out in which mainly the infeasible region is explored. Once feasibility has been established, a second
tabu-search procedure, which analyzes only feasible solutions, is applied. The algorithm has been tested on a
wide set of instances. Computational results are discussed
Symmetric and Asymmetric Parallelization of a Cost-Decomposition Algorithm for Multi-Commodity Flow Problems
No full textWe study the coarse-grained parallelization of an efficient bundle-based cost-decomposition algorithm for the solution of multicommodity min-cost flow (MMCF) problems. We show that a code exploiting only the natural parallelism inherent in the cost-decomposition approach, i.e., solving the min-cost flow subproblems in parallel, obtains satisfactory efficiencies even with many processors on large, difficult MMCF problems with many commodities. This is exactly the class of instances where the decomposition approach attains its best results in sequential. The parallel code we developed is highly portable and flexible, and it can be used on different machines. We also show how to exploit a common characteristic of current supercomputer facilities, i.e., the side-to-side availability of massively parallel and vector supercomputers, to implement an asymmetric decomposition algorithm where each architecture is used for the tasks for which it is best suited
Balanced paths in acyclic networks: tractable cases and related approaches
No full textGiven a weighted acyclic network G and two nodes s and t in G, we consider the problem of computing k balanced paths from s to t, that is, k paths such that the difference in cost between the longest and the shortest path is minimized.The problem has several variants. We show that, whereas the general problem is solvable in pseudopolynomial time, both the arc-disjoint and the node-disjoint variants (i.e., the variants where the k paths are required to be arc-disjoint and node-disjoint, respectively) are strongly NP-Hard. We then address some significant special cases of such variants, and propose exact as well as approximate algorithms for their solution. The proposed approaches are also able to solve versions of the problem in which k origin-destination pairs are provided, and a set of k paths linking the origin-destination pairs has to be computed in such a way to minimize the difference in cost between the longest and the shortest path in the set
Home Care optimization: impact of pattern generation policies on scheduling and routing decisions
No full textIn Home Care optimization, operators have to be assigned to patients by taking into account compatibility skill constraints, and patient visits have to be scheduled in a given planning horizon. Moreover, operator tours have to be determined. Integer Linear Programming models have been proposed which use the concept of patterns, i.e. a priori scheduling profiles, to combine the diverse decision levels. Computational results on real instances show that pattern generation policies are crucial to address scheduling and routing in large Home Care instances
Color-Coding Algorithms to the Balanced Path Problem: Computational Issues
No full text Given a weighted directed network G, we consider the problem of computing k balanced paths from given source nodes to given destination nodes of G, i.e., k paths such that the difference in cost between the longest path and the shortest path is minimized. Although not yet investigated by the OR scientific community, except for some preliminary theoretical results concerning the special case of acyclic networks, balanced path problems arise in several interesting applications, such as in transportation and in telecommunication settings. In this work, the focus is on the computation of node-disjoint balanced paths in the general case, where the input graph G could have any structure. Starting from some algorithmic ideas proposed for acyclic networks, a general framework based on the color-coding method for computing simple paths is first described. Then the general framework is specialized, and a pool of algorithms is designed that includes both an exact approach as well as alternative heuristics. The algorithms have been tested on a large suite of instances generated from some benchmark telecommunication instances. An additional set of instances, generated from some benchmark crew scheduling instances, has been used to get an idea of the behavior of the algorithms in the context of transportation applications. The obtained computational results are very interesting. For the telecommunication instances, in some cases the exact algorithm produced the optimal solution very rapidly; in the remaining cases, some of the proposed heuristics were able to generate high-quality solutions in a very quick time. As for the crew scheduling instances, which are larger and sometimes appear more difficult than the telecommunication ones, a suitable combination of the proposed color-coding issues allowed us to compute the optimal solutions in very short times. </jats:p
Hazmat routing by compulsory check points: a new risk mitigation strategy
No full textThis paper introduces a new strategy for the mitigation of risk due to hazardous material transportation on a road network. We propose to assign to each vehicle a compulsory check point to be crossed along the orgin destination trip. The authority locates k check points on the network and assigns one check point to each vehicle. Drivers will travel along the minimum cost itinerary which complies with the obligation. As the authority is risk driven and drivers are cost driven, we have to solve a bilevel optimization problem. We present computational results on literature benchmarcks that show the effectiveness of the method
- …
