共查询到20条相似文献,搜索用时 31 毫秒
1.
In this paper, we propose an exact algorithm for the knapsack sharing problem. The proposed algorithm seems quite efficient in the sense that it solves quickly some large problem instances. The problem is decomposed into a series of single constraint knapsack problems; and by applying the dynamic programming and another strategy, we solve optimally the original problem. The performance of the exact algorithm is evaluated on a set of medium and large problem instances (a total of 240 problem instances). This algorithm is parallelizable and this is one of its important feature. 相似文献
2.
3.
最短时限运输问题及解法 总被引:17,自引:0,他引:17
提出了存在于实际中的最短时限运输问题,研究了其解的最优性充分条件,并给出了求解这一问题的具体步骤,最后用实例说明了解法的可操作性,该解法是解决这一类问题的一个好算法。 相似文献
4.
用混合遗传算法求解物流配送路径优化问题的研究 总被引:75,自引:5,他引:75
论文建立了物流配送路径优化问题的数学模型,并针对遗传算法在局部搜索能力方面的不足,提出将爬山算法与遗传算法相结合,从而构造了求解物流配送路径优化问题的混合遗传算法,并进行了实验计算。计算结果表明,用混合遗传算法求解物流配送路径优化问题,可以在一定程度上克服遗传算法在局部搜索能力方面的不足和爬山算法在全局搜索能力方面的不足,从而得到质量较高的解。 相似文献
5.
6.
车辆路径问题的禁忌搜索算法研究 总被引:19,自引:1,他引:19
论文在对车辆路径问题进行简单描述的基础上,通过设计一种新的解的表示方法构造了求解该问题的一种新的禁忌搜索算法,并进行了实验计算。计算结果表明,用本文设计的禁忌搜索算法求解车辆路径问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定。 相似文献
7.
8.
《Omega》2016
In this paper, we propose a branch-and-cut algorithm and a branch-and-price algorithm to solve the pickup and delivery problem with loading cost (PDPLC), which is a new problem derived from the classic pickup and delivery problem (PDP) by considering the loading cost in the objective function. Applications of the PDPLC arise in healthcare transportation where the objective function is customer-centric or service-based. In the branch-and-price algorithm, we devise an ad hoc label-setting algorithm to solve the pricing problem and employ the bounded bidirectional search strategy to accelerate the label-setting algorithm. The proposed algorithms were tested on a set of instances generated by a common data generator in the literature. The computational results showed that the branch-and-price algorithm outperformed the branch-and-cut algorithm by a large margin, and can solve instances with 40 requests to optimality in a reasonable time frame. 相似文献
9.
考虑到无人仓系统补货阶段货架上只有部分空余储位的特点,研究了补货商品储位分配问题的优化模型与算法。以同一货架上存放的商品之间关联度之和最大化为目标建立了混合整数规划模型;结合贪婪算法和邻域搜索算法设计了求解模型的两阶段方法。第一阶段利用贪婪算法求初始可行解;第二阶段利用邻域搜索算法对初始可行解进行优化。利用一个具体算例验证了邻域搜索算法的优化效果,结果显示,通过邻域搜索算法对初始可行解的优化,可以使目标函数值至少提升27%。进一步利用多个小规模算例分析了两阶段算法的近似比和求解速度,验证了算法的快速有效性。本文的研究结果不仅解决了货架初始状态非空情况下的储位分配问题,同样适合解决货架初始状态为空的情况,因此更加符合实际场景,可以作为无人仓管理信息系统的核心模型和算法。 相似文献
10.
Khaled S. Al-sultan 《生产规划与管理》2013,24(3):231-236
The part family problem in group technology can be stated as the problem of finding the best grouping of parts into families such that the parts within each family are as similar to each other as possible. In this paper, the part family formation problem is considered. The problem is cast into a hard clustering model, and the k-means algorithm is proposed for solving it. Preliminary computational experience on the algorithm is very encouraging and it shows that real-life problems of large sizes can efficiently be handled by this approach. 相似文献
11.
A discrete location problem is formulated for the design of a postal service network. The cost objective of this problem includes a nonlinear concave component. A parametric integer programming algorithm is developed to find an approximate solution to the problem. The algorithm reduces the problem into a sequence of p-median problems and deals with the nonlinear cost by a node-replacement scheme. Preliminary computational results are presented. 相似文献
12.
Ananya Christman William Forcier Aayam Poudel 《Journal of Combinatorial Optimization》2018,35(2):512-529
We consider the on-line dial-a-ride problem, where a server fulfills requests that arrive over time. Each request has a source, destination, and release time. We study a variation of this problem where each request also has a revenue that the server earns for fulfilling the request. The goal is to serve requests within a time limit while maximizing the total revenue. We first prove that no deterministic online algorithm can be competitive unless the input graph is complete and edge weights are unit. We therefore focus on these graphs and present a 2-competitive algorithm for this problem. We also consider two variations of this problem: (1) the input graph is complete bipartite and (2) there is a single node that is the source for every request, and present a 1-competitive algorithm for the former and an optimal algorithm for the latter. We also provide experimental results for the complete and complete bipartite graphs. Our simulations support our theoretical findings and demonstrate that our algorithms perform well under settings that reflect realistic dial-a-ride systems. 相似文献
13.
14.
15.
It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical
knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively studied, and some effective exact
or approximation algorithms exist. A natural approach for the multiple knapsack problem is to pack the knapsacks successively
by using an effective algorithm for the 0-1 knapsack problem. This paper considers such an approximation algorithm that packs
the knapsacks in the nondecreasing order of their capacities. We analyze this algorithm for 2 and 3 knapsack problems by the
worst-case analysis method and give all their error bounds. 相似文献
16.
Wen-Jinn Chen 《Omega》2009
This paper considers a single-machine scheduling problem with periodic maintenance. In this study, a schedule consists of several maintenance periods and each maintenance period is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the number of tardy jobs subject to periodic maintenance and nonresumable jobs. Based on the Moore's algorithm, an effective heuristic is developed to provide a near-optimal schedule for the problem. A branch-and-bound algorithm is also proposed to find the optimal schedule. Some important theorems associated with the problem are implemented in the algorithm. Computational results are presented to demonstrate the effectiveness of the proposed heuristic. 相似文献
17.
本文研究了集成生产批量、配送中心定位和车辆运输路径问题的一个复杂大系统,并建立了相应的数学模型。为了便于理解和求解这一大系统,将这一系统运用Lagrange松弛法分解成了生产、配送中心和定位-路径等三个相对独立的子系统。基于次梯度优化算法提出了一种优化协调机制,实现了系统的整体优化,并进行了数值实验分析。 相似文献
18.
Nicos Christofides 《Omega》1973,1(6):719-732
For a given graph (network) having costs [cij] associated with its links, the present paper examines the problem of finding a cycle which traverses every link of the graph at least once, and which incurs the minimum cost of traversal. This problem (called thegraph traversal problem, or theChinese postman problem [9]) can be formulated in ways analogous to those used for the well-known travelling salesman problem, and using this apparent similarity, Bellman and Cooke [1] have produced a dynamic programming formulation. This method of solution of the graph traversal problem requires computational times which increase exponentially with the number of links in the graph. Approximately the same rate of increase of computational effort with problem size would result by any other method adapting a travelling salesman algorithm to the present problem.This paper describes an efficient algorithm for the optimal solution of the graph traversal problem based on the matching method of Edmonds [5, 6]. The computational time requirements of this algorithm increase as a low order (2 or 3) power of the number of links in the graph. Computational results are given for graphs of up to 50 vertices and 125 links.The paper then discusses a generalised version of the graph traversal problem, where not one but a number of cycles are required to traverse the graph. In this case each link has (in addition to its cost) a quantity qij associated with it, and the sum of the quantities of the links in any one cycle must be less than a given amount representing the cycle capacity. A heuristic algorithm for the solution of this problem is given. The algorithm is based on the optimal algorithm for the single-cycle graph traversal problem and is shown to produce near-optimal results.There is a large number of possible applications where graph traversal problems arise. These applications include: the spraying of roads with salt-grit to prevent ice formation, the inspection of electric power lines, gas, or oil pipelines for faults, the delivery of letter post, etc. 相似文献
19.
The hierarchical model for load balancing on two machines 总被引:1,自引:1,他引:0
Following previous work, we consider the hierarchical load balancing model on two machines of possibly different speeds. We
first focus on maximizing the minimum machine load and show that no competitive algorithm exists for this problem. We overcome
this barrier in two ways, both related to previously known models. The first one is fractional assignment, where each job
can be arbitrarily split between the machines. The second one is a semi-online model where the sum of jobs is known in advance.
We design algorithms of best possible competitive ratios for both these cases. Furthermore, we show that the combination of
the two models leads to the existence of an optimal algorithm (i.e., an algorithm of competitive ratio 1). This algorithm
is clearly optimal for the makespan minimization problem as well. For the latter problem, we consider the fractional assignment
model and design an algorithm of best possible competitive ratio for it.
This work was submitted as the M.Sc. thesis of the first author. 相似文献
20.
《Omega》2016
The team orienteering problem is an important variant of the vehicle routing problem. In this paper, a new algorithm, called Pareto mimic algorithm, is proposed to deal with it. This algorithm maintains a population of incumbent solutions which are updated using Pareto dominance. It uses a new operator, called mimic operator, to generate a new solution by imitating an incumbent solution. Furthermore, to improve the quality of a solution, it employs an operator, called swallow operator which attempts to swallow (or insert) an infeasible node and then repair the resulting infeasible solution. A comparative study supports the effectiveness of the proposed algorithm, especially, our algorithm can quickly find new better results for several large-scale instances. We also demonstrate that Pareto mimic algorithm can be generalized to solve other routing problems, e.g., the capacitated vehicle routing problem. 相似文献