检索结果-内蒙古大学图书馆

Large neighborhood search with constraint programming for a vehicle routing problem with synchronization constraints

引用

COMPUTERS & OPERATIONS RESEARCH 2018年第Apr.期92卷 87-97页

作者： Hojabri, Hossein Gendreau, Michel Potvin, Jean-Yves Rousseau, Louis-Martin Univ Montreal Dept Informat & Rech Operat CP 6128Succ Ctr Ville Montreal PQ H3C 3J7 Canada Ecole Polytech Montreal Dept Math & Genie Ind CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada Univ Montreal Ctr Interuniv Rech Reseaux Entreprise Logist & Tr CP 6128Succ Ctr Ville Montreal PQ H3C 3J7 Canada

This paper considers an extension of the vehicle routing problem with time windows, where the arrival of two vehicles at different customer locations must be synchronized. That is, one vehicle has to deliver some product to a customer, like a home theater system, while the crew on another vehicle must install it. This type of problem is often encountered in practice and is very challenging due to the interdependency among the vehicle routes, but has received little attention in the literature. A constraint programming-based adaptive large neighborhood search is proposed to solve this problem. The search abilities of the large neighborhood search and the constraint propagation abilities of constraint programming are combined to determine the feasibility of any proposed modification to the current solution. Numerical results are reported on instances derived from benchmark instances for the vehicle routing problem with time windows with up to 200 customers. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Vehicle routing Synchronization Large neighborhood search constraint programming

来源：评论

学校读者我要写书评

暂无评论

Mining Time-constrained Sequential Patterns with constraint programming

引用

constraintS 2017年第4期22卷 548-570页

作者： Aoga, John O. R. Guns, Tias Schaus, Pierre Univ Catholique Louvain UCLouvain Inst Informat & Commun Technol Elect & Appl Math Louvain Belgium UAC Ecole Doctorale Sci Ingn ED SDI Calavi Benin Vrije Univ Brussel Brussels Belgium Katholieke Univ Leuven Leuven Belgium

constraint programming (CP) has proven to be an effective platform for constraint based sequence mining. Previous work has focused on standard frequent sequence mining, as well as frequent sequence mining with a maximum 'gap' between two matching events in a sequence. The main challenge in the latter is that this constraint can not be imposed independently of the omnipresent frequency constraint. Indeed, the gap constraint changes whether a subsequence is included in a sequence, and hence its frequency. In this work, we go beyond that and investigate the integration of timed events and constraining the minimum/maximum gap as well as minimum/maximum span. The latter constrains the allowed time between the first and last matching event of a pattern. We show how the three are interrelated, and what the required changes to the frequency constraint are. Key in our approach is the concept of an extension window defined by gap/span and we develop techniques to avoid scanning the sequences needlessly, as well as using a backtracking-aware data structure. Experiments demonstrate that the proposed approach outperforms both specialized and CP-based approaches in almost all cases and that the advantage increases as the minimum frequency threshold decreases. This paper is an extension of the original manuscript presented at CPAIOR'17 [5].

关键词： Data mining Sequential pattern mining constraint programming Global constraint Gap constraint Span constraint Time constraint

来源：评论

学校读者我要写书评

暂无评论

A study of constraint programming heuristics for the car-sequencing problem

引用

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2015年 38卷 34-44页

作者： Siala, Mohamed Hebrard, Emmanuel Huguet, Marie-Jose CNRS LAAS F-31400 Toulouse France Univ Toulouse INSA F-31400 Toulouse France Univ Toulouse LAAS F-31400 Toulouse France

In the car-sequencing problem, a number of cars have to be sequenced on an assembly line respecting several constraints. This problem was addressed by both Operations Research (OR) and constraint programming (CP) communities, either as a decision problem or as an optimization problem. In this paper, we consider the decision variant of the car sequencing problem and we propose a systematic way to classify heuristics for solving it. This classification is based on a set of four criteria, and we consider all relevant combinations for these criteria. Some combinations correspond to common heuristics used in the past, whereas many others are novel. Not surprisingly, our empirical evaluation confirms earlier findings that specific heuristics are very important for efficiently solving the car-sequencing problem (see for instance Smith, 1996), in fact, often as important or more than the propagation method. Moreover, through a criteria analysis, we are able to get several new insights into what makes a good heuristic for this problem. In particular, we show that the criterion used to select the most constrained option is critical, and the best choice is fairly reliably the "load" of an option. Similarly, branching on the type of vehicle is more efficient than branching on the use of an option. Overall, we can therefore indicate with a relatively high confidence which is the most robust strategy, or at least outline a small set of potentially best strategies. Last, following a remark in Regin and Puget (1997) stating that the notion of slack used in heuristics induces a pruning rule, we propose an algorithm for this method and experimentally evaluate it, showing that, although computationally cheap and easy to implement, this is in practice a very efficient way to solve car-sequencing benchmarks. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Car-sequencing Heuristics Tree search methods constraint programming

来源：评论

学校读者我要写书评

暂无评论

A combined integer/constraint programming approach to a resource-constrained parallel machine scheduling problem with machine eligibility restrictions

引用

ENGINEERING OPTIMIZATION 2011年第2期43卷 135-157页

作者： Edis, Emrah B. Ozkarahan, Irem Dokuz Eylul Univ Dept Ind Engn TR-35160 Izmir Turkey Troy Univ Dept Comp Sci Montgomery AL 36104 USA

A resource-constrained identical parallel machine scheduling problem with machine eligibility restrictions is investigated in this study. For the considered problem, three optimization models;an integer programming (IP) model, a constraint programming (CP) model and a combined IP/CP model are developed. A problem-based search procedure to be used in CP and IP/CP combined models is also proposed to give quick and efficient results. All three optimization models are constructed and solved in OPL Studio 3.7 setting 1000 second run-time limit. Computational results show that the combined IP/CP OPL model with the proposed problem-based search procedure not only achieves magnitude reduction in computational time but also gives optimal results in 174 out of 200 test problems, while IP and CP models prove optimality in only 47 and 6 problems, respectively. Finally, computational results are also analysed and discussed in terms of various problem parameters.

关键词： parallel machine scheduling integer programming constraint programming additional resources machine eligibility

来源：评论

学校读者我要写书评

暂无评论

A hybrid constraint programming/Mixed Integer programming framework for the preventive signaling maintenance crew scheduling problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2018年第1期269卷 341-352页

作者： Pour, Shahrzad M. Drake, John H. Ejlertsen, Lena Secher Rasmussen, Kourosh Marjani Burke, Edmund K. Tech Univ Denmark DTU Management Engn DK-2800 Lyngby Denmark Queen Mary Univ London Operat Res Grp Mile End Rd London E1 4NS England Banedanmark Amer Plads 15 DK-2100 Copenhagen Denmark

A railway signaling system is a complex and interdependent system which should ensure the safe operation of trains. We introduce and address a mixed integer optimisation model for the preventive signal maintenance crew scheduling problem in the Danish railway system. The problem contains many practical constraints, such as temporal dependencies between crew schedules, the splitting of tasks across multiple days, crew competency requirements and several other managerial constraints. We propose a novel hybrid framework using constraint programming to generate initial feasible solutions to feed as 'warm start' solutions to a Mixed Integer programming solver for further improvement. We apply this hybrid framework to a section of the Danish rail network and benchmark our results against both direct application of a Mixed Integer programming solver and modelling the problem as a constraint Optimisation Problem. Whereas the current practice of using a general purpose Mixed Integer programming solver is only able to solve instances over a two-week planning horizon, the hybrid framework generates good results for problem instances over an eight-week period. In addition, the use of a Mixed Integer programming solver to improve the initial solutions generated by constraint programming is shown to be significantly superior to addressing the problem as a constraint Optimisation Problem. (C) 2017 The Authors. Published by Elsevier B.V.

关键词： Transportation Scheduling constraint programming Mixed Integer programming Hybrid approaches

来源：评论

学校读者我要写书评

暂无评论

Integrated production and material handling scheduling using mathematical programming and constraint programming

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2006年第3期175卷 1818-1832页

作者： El Khayat, Ghada Langevin, Andre Riopel, Diane Ecole Polytech Montreal Montreal PQ H3C 3A7 Canada Gerad Montreal PQ H3C 3A7 Canada

In this article, we propose an integrated formulation of the combined production and material handling scheduling problems. Traditionally, scheduling problems consider the production machines as the only constraining resource. This is however no longer true as material handling vehicles are becoming more and more valuable resources requiring important investments. Their operations should be optimized and above all synchronized with machine operations. In the problem addressed in this paper, a job shop context is considered. Machines and vehicles are both considered as constraining resources. The integrated scheduling problem is formulated as a mathematical programming model and as a constraint programming model which are compared for optimally solving a series of test problems. A commercial software (ILOG OPLStudio) was used for modeling and testing both models. (c) 2005 Elsevier B.V. All rights reserved.

关键词： scheduling job shop material handling mixed integer programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

Mixing Static and Dynamic Partitioning to Parallelize a constraint programming Solver

引用

INTERNATIONAL JOURNAL OF PARALLEL programming 2016年第3期44卷 486-505页

作者： Menouer, Tarek Rezgui, Mohamed Le Cun, Bertrand Regin, Jean-Charles Univ Versailles St Quentin En Yvelines Prism Lab 45 Ave des Etats Unis F-78035 Versailles France Univ Nice Sophia Antipolis Lab I3S 28 Ave Valombrose F-06100 Nice France

This paper presents an external parallelization of constraint programming (CP) search tree mixing both static and dynamic partitioning. The principle of the parallelization is to partition the CP search tree into a set of sub-trees, then assign each sub-tree to one computing core in order to perform a local search using a sequential CP solver. In this context, static partitioning consists of decomposing the CP variables domains in order to split the CP search tree into a set of disjoint sub-trees to assign them to the cores. This strategy performs well without adding an extra cost to the parallel search, but the problem is the load imbalance between computing cores. On the other hand, dynamic partitioning is based on preservation of the search state to generate, dynamically or on demand, the sub-trees that are assigned to the cores. This strategy offers good load balancing between the different computing cores, but computing overcosts appear due to the initialisation of the search when a sub-tree is migrated from one core to another. In this paper, we propose a new partitioning strategy that mixes the static and dynamic partitioning and enjoys the benefits of each strategy. This mixed partitioning is designed to run on shared and distributed memory architectures. The performances obtained are illustrated by solving the CP problems modelled using the FlatZinc format and solved using the Google OR-Tools solver on top of the parallel Bobpp framework.

关键词： Parallelism constraint programming Work Stealing Dynamic load balancing

来源：评论

学校读者我要写书评

暂无评论

A new variable neighbourhood search with a constraint programming search strategy for the open shop scheduling problem with operation repetitions

引用

ENGINEERING OPTIMIZATION 2022年第9期54卷 1563-1582页

作者： de Abreu, Levi Ribeiro Guimaraes Araujo, Kennedy Anderson Prata, Bruno de Athayde Nagano, Marcelo Seido Moccellin, Joao Vitor Univ Sao Paulo Dept Prod Engn Sao Carlos Brazil Univ Sao Paulo Dept Appl Math Sao Paulo Brazil Univ Fed Ceara Dept Ind Engn Fortaleza Ceara Brazil

This article presents a new variant for the open shop scheduling problem, the open shop scheduling problem with repetitions (OSSPR), where the jobs can be processed on any machine more than once (operation by operation). Thereby, all the jobs can be scheduled in an unconstrained way, substantially increasing the number of feasible solutions in comparison with the classical open shop. The OSSPR has many applications in automotive and maintenance actives. To solve the problem, a mixed-integer linear programming model is presented and a new constraint programming model is proposed. Since the problem under study is NP-hard, a new efficient variable neighbourhood search is proposed using variable search strategies through the proposed constraint programming model. The objective function is makespan minimization, and it uses the lower bound deviation as performance criterion. Computational results show very good performance of the proposed metaheuristic on the instances tested.

关键词： Production sequencing makespan constraint programming exact methods

来源：评论

学校读者我要写书评

暂无评论

constraint programming-based virtual machines placement algorithm in datacenter

Constraint programming-based virtual machines placement algo...

引用

7th IFIP International Conference on Intelligent Information Processing, IIP 2012

作者： Yu, Yonghong Gao, Yang State Key Lab. for Novel Software Technology Nanjing University Nanjing 210093 China College of Tongda Nanjing University of Posts and Telecommunications Nanjing 210003 China

ISBN: (纸本)9783642328909

As underlying infrastructure of cloud computing platform, datacenter is seriously underutilized, however, its operating costs is high. In this paper, we implement virtual machines placement algorithm in CloudSim using constraint programming approach. We first formulate the problem of virtual machines placement in virtualized datacenters as a variant of multi-dimensions bin packing problem, and then exploit constraint solver to solve this problem with the objective of minimizing number of physical machines that host virtual machines. Finally, we compare different virtual placement algorithms for evaluating constraint programming-based virtual machine placement algorithm including the built-in virtual machine placement algorithm in CloudSim and FFD algorithm. The experimental results show that constraint programming-based virtual machines placement algorithm can efficiently reduce the number of physical machines to achieve the goal of reducing datacenter operating costs and improving resource utilization. © 2012 IFIP International Federation for Information Processing.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

constraint programming and a usability quest

Constraint programming and a usability quest

引用

18th International Conference on Principles and Practice of constraint programming, CP 2012

作者： Michel, Laurent D. University of Connecticut Storrs CT 06269-2155 United States

ISBN: (纸本)9783642335570

In 2004, Jean-Francois Puget presented [2] an analysis of the "simplicity of Use" of constraint programming from which he articulated a series of challenges to make constraint programming systems accessible and easier to use. The core of the argument was a contrast between mathematical programming and constraint programming tools. Mathematical programming adopts a model and run paradigm, rely on a simple vocabulary to model problems (i.e., linear constraints), support standard formats for sharing models and benefit from extensive documentation on how to model [5]. constraint programming features a model and search paradigm, rich modeling languages with combinatorial objects and has a distinctive flavor of programming. While it can be construed as CP's Achilles' heel, it is also its most potent strength and is supported by modeling aids [3,4]. The very existence of sophisticated parameter tuning solutions for SAT solvers and Math programming solvers to determine ideal parameters (e.g., ParamILS [1]) certainly cast a major shadow on the potency of the model and run mantra that is evolving into model and search for the right parameters. © 2012 Springer-Verlag.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：