共查询到20条相似文献,搜索用时 46 毫秒
1.
In this paper, we present a simple algorithm to obtain mechanically SDP relaxations for any quadratic or linear program with bivalent variables, starting from an existing linear relaxation of the considered combinatorial problem. A significant advantage of our approach is that we obtain an improvement on the linear relaxation we start from. Moreover, we can take into account all the existing theoretical and practical experience accumulated in the linear approach. After presenting the rules to treat each type of constraint, we describe our algorithm, and then apply it to obtain semidefinite relaxations for three classical combinatorial problems: the K-CLUSTER problem, the Quadratic Assignment Problem, and the Constrained-Memory Allocation Problem. We show that we obtain better SDP relaxations than the previous ones, and we report computational experiments for the three problems. 相似文献
2.
《Omega》2017
In this paper, a multi-depot dial-a-ride problem arising from a real-world healthcare application is addressed, concerning the non-emergency transportation of patients. The problem presents several constraints and features, such as heterogeneous vehicles, vehicle–patient compatibility constraints, quality of service requirements, patients׳ preferences, tariffs depending on the vehicles׳ waiting. Variable Neighborhood Search and Tabu Search algorithms are proposed able to tackle all the characteristics of the problem. A Mixed Integer Linear Programming formulation is also presented. Computational results on large real-world and random instances based on real data show the effectiveness of the proposed approaches. 相似文献
3.
4.
Hybridization techniques are very effective for the solution of combinatorial optimization problems. This paper presents a
genetic algorithm based on Expanding Neighborhood Search technique (Marinakis, Migdalas, and Pardalos, Computational Optimization and Applications, 2004) for the solution of the traveling salesman problem: The initial population of the algorithm is created not entirely
at random but rather using a modified version of the Greedy Randomized Adaptive Search Procedure. Farther more a stopping
criterion based on Lagrangean Relaxation is proposed. The combination of these different techniques produces high quality
solutions. The proposed algorithm was tested on numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons
with the algorithms of the DIMACS Implementation Challenge are also presented. 相似文献
5.
6.
7.
8.
Yannis Marinakis Athanasios Migdalas Panos M. Pardalos 《Journal of Combinatorial Optimization》2009,17(2):134-156
In this paper, a new modified version of Greedy Randomized Adaptive Search Procedure (GRASP), called Multiple Phase Neighborhood
Search—GRASP (MPNS-GRASP), is proposed for the solution of the Traveling Salesman Problem. In this method, some procedures
have been included to the classical GRASP algorithm in order to improve its performance and to cope with the major disadvantage
of GRASP which is that it does not have a stopping criterion that will prevent the algorithm from spending time in iterations
that give minor, if any, improvement in the solution. Thus, in MPNS-GRASP a stopping criterion based on Lagrangean Relaxation
and Subgradient Optimization is proposed. Also, a different way for expanding the neighborhood search is used based on a new
strategy, the Circle Restricted Local Search Moves strategy. A new variant of the Lin-Kernighan algorithm, called Random Backtracking
Lin-Kernighan that helps the algorithm to diversify the search in non-promising regions of the search space is used in the
Expanding Neighborhood Search phase of the algorithm. Finally, a Path Relinking Strategy is used in order to explore trajectories
between elite solutions. The proposed algorithm is tested on numerous benchmark problems from TSPLIB with very satisfactory
results. 相似文献
9.
多车场带时间窗车辆路径问题的变邻域搜索算法 总被引:3,自引:1,他引:2
多车场带时间窗车辆路径问题是车辆路径问题集合中的一个极为复杂、且仍未得到较好解决的问题。针对这一问题,建立了它的整数规划数学模型,提出了一种改进型变邻域搜索算法。该算法在初始解的构造阶段采用聚类方法完成客户的分配,运用混合算子进行局部搜索,通过后优化过程增强寻优效果,引入模拟退火模型对新解的接受进行控制。最后,在Cordeau提出的标准用例上对改进型变邻域算法进行了实验,实验结果更新了大部分目前该问题的最优解,并在算法的稳定性和求解时间上体现出一定优势。实验表明,该算法是一种求解多车场带时间窗车辆路径问题的有效方法。 相似文献
10.
《Omega》2014
This paper addresses a periodic vehicle routing problem encountered in home health care (HHC) logistics. It extends the classical Periodic Vehicle Routing Problem with Time Windows (PVRPTW) to three types of demands of patients at home. Demands include transportation of drugs/medical devices between the HHC depot and patients׳ homes, delivery of special drugs from the hospital to patients, and delivery of blood samples from patients to the lab. Each patient requires a certain number of visits within a planning horizon and has a set of possible combinations of visit days. Daily routing should meet time window constraints associated with patients, the hospital and the lab. The problem consists in determining the visit days of each patient and vehicle routes for each day in order to minimize the maximal routing costs among all routes over the horizon. We propose a Tabu Search method combined with different local search schemes including both feasible and infeasible local searches. The proposed approaches are tested on a range of instances derived from existing Vehicle Routing Problem with Time Window (VRPTW) benchmarks and benchmarks on special cases of our problem. Numerical results show that local search scheme starting with an infeasible local search with a small probability followed by a feasible local search with high probability is an interesting hybridization. Experiments with field data from a HHC company show that the proposed approach reduces the total cost and better balances the workloads of vehicles. 相似文献
11.
企业的置换装配线调度问题(Permutation Assembly-line Scheduling Problem,PASP)是一类典型的NP-hard型生产调度问题,是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器,这n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同,问题的主要目标是找到n个工件在每台机器上的最优加工顺序,使得最大完工时间最小。由于PASP问题的NP-hard性质,本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题,但其选择与交叉机制易导致局部最优及收敛慢。因此,本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因,然后将具有较优结果的基因组合为优势区块,产生具优势的人工解,并引入高收敛性的局部搜索方法,提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率,结果证明:本文所提算法与其它求解调度问题的现有5种知名算法相比,不仅收敛速度较快,同时求解质量优于它们。 相似文献
12.
Tao Zhang W. Art Chaovalitwongse Yuejie Zhang 《Journal of Combinatorial Optimization》2014,28(1):288-309
Today manufacturers have become much more concerned with the coordination of both manufacturing (of new products) and recycling (of reusable resources) operations. This requires simultaneous scheduling of both forward and reverse flows of goods over a supply chain network. This paper studies time dependent vehicle routing problems with simultaneous pickup and delivery (TD-VRPSPD). We formulate this problem as a mixed integer programming model, where the time step function is used to calculate the travel time. To efficiently solve this complex problem, we develop a hybrid algorithm that integrates both Ant Colony System (ACS) and Tabu Search (TS) algorithms. Our algorithm uses the pheromones, travel time and vehicle residual loading capacity as a factor structure according to the characteristics of TD-VRPSPD. In our computational experiments, 56 groups of benchmark instances are used to evaluate the performance of our hybrid algorithm. In addition, we compare the performance of our hybrid algorithm with those of individual ACS and TS algorithms. The computational results suggest that our hybrid algorithm outperform stand-alone ACS and the TS algorithms. 相似文献
13.
针对中小批量单件车间生产作业计划生成与再生问题,集成Visual Foxpro5.0与Siman 3.51开发了一个系统原型,包括模拟模型生成器、时间参数推算器和禁忌搜索算法。用模拟模型生成器得到一个比较详细的中小批量单件车间生产作业计划方案,以此为初始可行解,再用时间参数推算器和禁忌搜索算法进行优化,得到一个优化了的车间生产作业计划方案。实验表明,本系统较好地解决了中小批量单件车间生产作业计划生成问题。 相似文献
14.
Almost optimal solutions for bin coloring problems 总被引:1,自引:1,他引:0
In this paper we study two interesting bin coloring problems: Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin
Coloring Problem (OMaxBC), motivated from several applications in networking. For the MinBC problem, we present two near linear
time approximation algorithms to achieve almost optimal solutions, i.e., no more than OPT+2 and OPT+1 respectively, where OPT is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then
give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds
show that our deterministic algorithm achieves the best possible competitive ratio.
The research of this paper was partially supported by an NSF CAREER award CCF-0546509. 相似文献
15.
Problem analysis is a critical element of managerial problem solving that has not been included in or explicated by traditional stage models of the process. This paper argues that an analysis stage is needed to develop the implications of a problem's definition and to direct the selection and pursuit of solution strategies. Problem analysis is a beuristic activity. The paper explains and applies seven heuristic methods of analysis to a classic management case, generating a richer understanding and broader set of solution alternatives. Strategies for future research on problem analysis are discussed. 相似文献
16.
蚁群算法是一种新型的模拟进化算法,具有许多优良的性质,可以很好地解决TSP问题.在分析车辆路径问题(VRP)与TSP区别的基础上,论文将蚁群算法应用于VRP的求解,针对VRP的具体特点,构造了具有自适应功能的混合蚁群算法.该算法对基本规则作了进一步改进,并有机结合了爬山法、节约法等方法,以减少计算时间,避免算法停滞.指出可行解问题是蚁群算法的关键问题,提出了大蚂蚁数、近似解可行化等四个解决策略.计算机仿真结果表明,自适应混合蚁群算法性能优良,能够有效地求解VRP. 相似文献
17.
We introduce an exponential neighborhood for the Vehicle Routing Problem (vrp) with unit customers’ demands, and we show that it can be explored efficiently in polynomial time by reducing its exploration to a particular
case of the Restricted Complete Matching (rcm) problem that we prove to be polynomial time solvable using flow techniques. Furthermore, we show that in the general case
with non-unit customers’ demands the exploration of the neighborhood becomes an
-hard problem. 相似文献
18.
This paper describes a case assignment (calendaring) algorithm for a multi-judge appellate court system. In the algorithm, cases of unequal work content are selected for assignment to one of m panels (or clusters) from a set of N available cases. Each panel of cases is heard by a team of three judges. Each appellate case has an estimated work load and a priority ranking based on the type of appeal and filing date with the court. The algorithm balances both the total work load and the number of cases assigned to each panel while insuring that the highest priority cases are assigned to those available. The assignment problem is normally capacity constrained in that not all of the N cases can be assigned to one of the m panels on the monthly calendar. The algorithm is based on a neighborhood search and bounding principle that continually improves upon an initial feasible solution. Empirical results are presented to demonstrate the effectiveness and efficiency of the algorithm. 相似文献
19.
In this paper, we consider the center location improvement problems under the sum-type and bottleneck-type Hamming distance. For the sum-type problem, we show that achieving an algorithm with a worst-case ratio of O(log |V|) is NP-hard, and for the bottleneck-type problem, we present a strongly polynomial algorithm. 相似文献
20.
车辆路径问题的模型及算法研究综述 总被引:21,自引:0,他引:21
本文在文献[1,2,3,4]的基础上,首先,介绍了车辆路径问题的分类和限制条件;然后,全面综述了国内外关于车辆路径问题的模型及算法研究现状,重点探讨了车辆路径问题的模型构造、求解算法及其适用范围;最后,展望了其研究的前景。 相似文献