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

Multi-Mobile-Robot Transport and Production Integrated System Optimization

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2025年 22卷 7480-7491页

作者： Zhao, Ziyan Li, Xingyang Liu, Shixin Zhou, Mengchu Yang, Xiaochun Northeastern Univ State Key Lab Synthet Automat Proc Ind Shenyang 110819 Peoples R China Northeastern Univ Coll Informat Sci & Engn Shenyang 110819 Peoples R China Northeastern Univ Fac Robot Sci & Engn Shenyang 110169 Peoples R China Northeastern Univ Qinhuangdao Sch Control Engn Qinhuangdao 066004 Peoples R China Macau Univ Sci & Technol Macao Inst Syst Engn Macau 999078 Peoples R China New Jersey Inst Technol Dept Elect & Comp Engn Newark NJ 07102 USA Northeastern Univ Software Coll Shenyang 110169 Peoples R China

A production workshop with mobile robots can be considered as a hybrid system consisting of a production system and a transportation one. Mobile robots are responsible for transferring production tasks among the machines of a production system and constitute a multi-robot transport system. It is highly coupled with a production system because of the interdependency that exists between production scheduling and mobile robot assignment. In this work, we study their integrated optimization problem for a mobile robot-based job shop with blocking properties. Its aim is to minimize total completion time as an objective function to improve overall operational efficiency. We consider the speed of a robot that varies according to whether it is loaded or not. We formulate this new problem into a mixed integer linear program to provide an algebraic description. Then, we propose a constraint programming method to solve it with high efficiency. The superiority of constraint programming over mixed integer linear programming in terms of the number of variables and constraints is analyzed. Numerous experiments on benchmark examples show that constraint programming can well handle the concerned problem. Under a one-hour time limit, it can exactly solve its instances while mixed integer linear programming cannot. Under a one-minute time limit, it obtains much better solutions than mixed integer linear programming and heuristic strategies, thus implying its high potential to be put into industrial applications.

关键词： Robots Mobile robots Job shop scheduling constraint handling Task analysis Production systems Optimization Blocking job shop scheduling transfer robot multi-agent system mixed integer linear programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

Semiglobal exponential stability of the discrete-time Arrow-Hurwicz-Uzawa primal-dual algorithm for constrained optimization

引用

MATHEMATICAL programming 2024年第1-2期208卷 629-660页

作者： Bin, Michelangelo Notarnicola, Ivano Parisini, Thomas Univ Bologna Dept Elect Elect & Informat Engn Bologna Italy Imperial Coll London Dept Elect & Elect Engn London England Univ Cyprus KIOS Res & Innovat Ctr Excellence Nicosia Cyprus Univ Trieste Dept Engn & Architecture Trieste Italy

We consider the discrete-time Arrow-Hurwicz-Uzawa primal-dual algorithm, also known as the first-order Lagrangian method, for constrained optimization problems involving a smooth strongly convex cost and smooth convex constraints. We prove that, for every given compact set of initial conditions, there always exists a sufficiently small stepsize guaranteeing exponential stability of the optimal primal-dual solution of the problem with a domain of attraction including the initialization set. Inspired by the analysis of nonlinear oscillators, the stability proof is based on a non-quadratic Lyapunov function including a nonlinear cross term.

关键词： constraint programming Convex programming Primal-dual algorithm Discrete-time control/observation systems

来源：评论

学校读者我要写书评

暂无评论

Plotting: a case study in lifted planning with constraints

引用

constraintS 2024年第1-2期29卷 40-79页

作者： Espasa, Joan Miguel, Ian Nightingale, Peter Salamon, Andras Z. Villaret, Mateu Univ St Andrews Sch Comp Sci St Andrews KY16 9SX Fife Scotland Univ Girona Dept Informat Matemat Aplicada & Estadist Girona 17003 Spain Univ York Dept Comp Sci Deramore Lane York YO10 5GH N Yorkshire England

We study a planning problem based on Plotting, a tile-matching puzzle video game published by Taito in 1989. The objective of this turn-based game is to remove a target number of coloured blocks from a grid by sequentially shooting blocks into the same grid. Plotting features complex transitions after every shot: various blocks are affected directly, while others can be indirectly affected by gravity. We consider modelling and solving Plotting from two perspectives. The puzzle is naturally cast as an AI Planning problem and we first discuss modelling the problem using the Planning Domain Definition Language (PDDL). We find that a model in which planning actions correspond to player actions is inefficient with a grounding-based state-of-the-art planner. However, with a more fine-grained action model, where each change of a block is a planning action, solving performance is dramatically improved. We also describe two lifted constraint models, able to capture the inherent complexities of Plotting and enabling the application of efficient solving approaches from SAT and CP. Our empirical results with these models demonstrates that they can compete with, and often exceed, the performance of the dedicated planning solvers, suggesting that the richer languages available to constraint modelling can be of benefit when considering planning problems with complex changes of state. CP and SAT solvers solved almost all of the largest and most challenging instances within 1 hour, whereas the best planning approach solved approximately 30%. Finally, the flexibility provided by the constraint models allows us to easily curate interesting levels for human players.

关键词： Case study AI planning Modelling constraint programming

来源：评论

学校读者我要写书评

暂无评论

A compact model for the home healthcare routing and scheduling problem

引用

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION 2025年 13卷

作者： Montemanni, Roberto Ceschia, Sara Schaerf, Andrea Univ Modena & Reggio Emilia Dept Sci & Methods Engn Via Amendola 2 I-42122 Reggio Emilia Italy Univ Udine Polytech Dept Engn & Architecture Via Sci 206 I-33100 Udine Italy

Home healthcare has become more and more central in the last decades, due to the advantages it can bring to both healthcare institutions and patients. Planning activities in this context, however, presents significant challenges related to route planning and mutual synchronization of caregivers. In this paper we propose a new compact model for the combined optimization of scheduling (of the activities) and routing (of the caregivers) characterized by fewer variables and constraints when compared with the models previously available in the literature. The new model is solved by a constraint programming solver and compared experimentally with the exact and metaheuristic approaches available in the literature on the common datasets adopted by the community. The results show that the new model provides improved lower bounds for the vast majority of the instances, while producing at the same time high quality heuristic solutions, comparable to those of tailored metaheuristics, for small/medium size instances.

关键词： Home healthcare constraint programming Lower bounds Upper bounds

来源：评论

学校读者我要写书评

暂无评论

Perception-based constraint solving for sudoku images

引用

constraintS 2024年第1-2期29卷 112-151页

作者： Mulamba, Maxime Mandi, Jayanta Mahmutogullari, Ali Irfan Guns, Tias Vrije Univ Brussel Data Analyt Lab Pl laan 5 B-1050 Brussels Belgium Katholieke Univ Leuven Dept Comp Sci Celestijnenlaan 200A B-3001 Leuven Belgium

We consider the problem of perception-based constraint solving, where part of the problem specification is provided indirectly through an image provided by a user. As a pedagogical example, we use the complete image of a Sudoku grid. While the rules of the puzzle are assumed to be known, the image must be interpreted by a neural network to extract the values in the grid. In this paper, we investigate (1) a hybrid modeling approach combining machine learning and constraint solving for joint inference, knowing that blank cells need to be both predicted as being blank and filled-in to obtain a full solution;(2) the effect of classifier calibration on joint inference;and (3) how to deal with cases where the constraints of the reasoning system are not satisfied. More specifically, in the case of handwritten user errors in the image, a naive approach fails to obtain a feasible solution even if the interpretation is correct. Our framework identifies human mistakes by using a constraint solver and helps the user to correct these mistakes. We evaluate the performance of the proposed techniques on images taken through the Sudoku Assistant Android app, among other datasets. Our experiments show that (1) joint inference can correct classifier mistakes, (2) overall calibration improves the solution quality on all datasets, and (3) estimating and discriminating between user-written and original visual input while reasoning makes for a more robust system, even in the presence of user errors.

关键词： constraint programming Machine learning Visual sudoku Joint inference

来源：评论

学校读者我要写书评

暂无评论

A pattern-based timetabling strategy for a short-turning metro line

引用

PUBLIC TRANSPORT 2024年第1期16卷 1-37页

作者： Schettini, Tommaso Gendreau, Michel Jabali, Ola Malucelli, Federico HEC Montreal Montreal PQ H3T 2A7 Canada Ecole Technol Super Montreal PQ H3C 1K3 Canada GERAD Montreal PQ H3T 1J4 Canada Polytech Montreal Montreal PQ H3C 3A7 Canada CIRRELT Montreal PQ H3C 3J7 Canada Politecn Milan I-20133 Milan Italy

The planning of metro lines is typically done through a strictly hierarchical approach, which is effective but somewhat inflexible. In this paper, we propose a flexible semiperiodic timetabling strategy using short-turning;thus, allowing trains to turn before reaching the terminal station of a line. Our strategy produces timetables that are periodic with respect to a group of short-turning destinations. This is denoted by the term service pattern. We introduce the service pattern timetabling problem (SPTP). Given a service pattern, the SPTP optimizes the train timetable considering capacity restrictions. The SPTP is modeled as a constraint program. We develop a framework for producing a large set of diverse and high-quality timetables for a metro line. This is achieved by repeatedly solving the SPTP with different patterns. Then we select a restricted list of non-dominated solutions with respect to three objectives: (1) the average passenger waiting time, (2) the maximum load factor achieved by the trains, and (3) the number of transfers induced by short-turning. We evaluate the proposed framework on a number of test instances. Through our computational experiments, we demonstrate the effectiveness of the developed strategy.

关键词： Metro timetabling Short-turning Demand-driven timetabling constraint programming

来源：评论

学校读者我要写书评

暂无评论

A Study of TMA Aircraft Conflict-Free Routing and Operation: With Mixed Integer Linear programming, Multi-Agent Path Finding, and Metaheuristic-Based Neighborhood Search

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2024年第10期25卷 13976-13990页

作者： Zhang, Yi Zhang, Sheng Zhang, Yicheng Yin, Yifang ASTAR Inst Infocomm Res I2R Singapore 138632 Singapore

In this paper, we proposed a conflict-free routing strategy combined with scheduling for Terminal Manoeuvring Area (TMA) multi-aircraft to guarantee a safe separation. By incorporating Standard Terminal Arrival Routes (STARs) as route constraints, a mixed-logic model is designed to maximize the runway throughput while ensuring minimum separation between aircraft and avoiding overtaking on each STARs segment. Control techniques such as speed recommendation and holding operations are employed to the model to address potential conflicts. Three different algorithms are developed to solve the model: branch and bound with mixed-integer linear programming, multi-agent pathfinding with constraint programming, and meta-heuristics with evolutionary neighborhood search. These algorithms are tested on multiple cases of varying scales. Finally, we demonstrate the advantages of the proposed three algorithms by simulating realistic scenarios and comparing the results with Singapore ADS-B (Automatic dependent Surveillance-Broadcast) historical dataset. In one hour testing, results show that our method could reduce the last aircraft landing time nearly 10 minutes and save more than 80 minutes for total flight travel times for all aircraft, as well as non-vectoring flight trajectories, which indicates its potential to be used as an auxiliary decision-making tool for Air Traffic Controllers (ATCOs).

关键词： Aircraft Atmospheric modeling Routing Stars Sequential analysis Air traffic control Safety Air traffic management trajectory based operation mixed-integer linear programming constraint programming meta-heuristics harmony search priority-based multiagent path finding

来源：评论

学校读者我要写书评

暂无评论

DEPS: a model- and property-based language for system synthesis problems

引用

SOFTWARE AND SYSTEMS MODELING 2024年第4期23卷 973-1002页

作者： Yvars, Pierre-Alain Zimmer, Laurent Inst Super Mecan Paris ISAE Supmeca QUARTZ EA 7393 St Ouen France Dassault Aviat Direct Prospect St Cloud France

DEPS (design problem specification) is a new modeling language designed to pose and solve system design problems. DEPS addresses problems of sizing, configuration, resource allocation and of architecture generation for systems. Unlike system modeling languages, which are dedicated to the representation of a defined system for evaluation or analysis, we propose a problem modeling language for representing the design problem with a view to its automatic resolution. Compared with other declarative problem modeling languages, DEPS is a declarative structured and property-based language that combines structural modeling features specific to object-oriented languages with problem specification features from constraint programming. The mathematical nature of the problems is described by formal properties encapsulated in models organized according to the architecture of the studied system. The main features of the language are presented in details and are illustrated with examples in different domains. An integrated modeling and solving environment called DEPS Studio allows the designer to express its models in DEPS, to compile the models and to compute automatically the solutions. The validation of the approach is done through two case studies. Finally, we will conclude with the studies and developments in progress which will be integrated into the next version of DEPS Studio.

关键词： Model-based system synthesis Specification Design problem modeling language Problem solving constraint programming

来源：评论

学校读者我要写书评

暂无评论

Heuristic for Railway Crew Scheduling With Connectivity of Schedules

引用

TRANSPORTATION RESEARCH RECORD 2024年第8期2678卷 873-887页

作者： Bansal, Akshat Anoop, Kezhe Perumpadappu Rangaraj, Narayan Indian Inst Technol Bombay IITB Mumbai Maharashtra India

This paper addresses the crew scheduling for long-distance passenger train services. A heuristic with bin packing features is developed to generate repeatable crew schedules that satisfy the operational and crew allocation rules. By ensuring the connectivity of crew duties that can be repeated over periodic train schedules, a better estimate of the crew requirement in a region is also obtained. Further, the heuristic ensures a fair division of the total workload and creates long duty cycles, which also makes the process of cyclic rostering easier. The paper also presents an exact approach for crew scheduling using a combination of constraint programming and set covering formulations. The exact approach is not computationally viable for practical scale problem instances, but the heuristic generates good quality solutions (often very close to optimal) even on large data sets. We illustrate the approach on data from the Mumbai Division in Indian Railways and the computational results show that there is potential to reduce the total number of crew duties in the region by around 12%. The heuristic approach provides an efficient way to generate improved crew schedules every time there is a change in the train timetable.

关键词： railway crew scheduling Indian railways constraint programming bin packing Heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

A hybrid evolutionary approach for lexicographic green flexible jobshop with interval uncertainty

引用

NATURAL COMPUTING 2025年 1-14页

作者： Afsar, Sezin Puente, Jorge Palacios, Juan Jose Gonzalez-Rodriguez, Ines Vela, Camino R. Univ Oviedo Dept Comp Sci Campus Gijon Gijon 33204 Spain Univ Cantabria Dept Math Stat & Computat Santander 39005 Spain

This article addresses the flexible job shop problem with uncertain processing times modelled by intervals. Due to climate change and the need for energy efficiency, there is an increasing interest in sustainability in addition to traditional production-related objectives such as makespan. In this work, we tackle a lexicographical goal programming scenario minimising makespan firstly and total energy consumption lately. We propose a hybrid evolutionary algorithm based on a genetic algorithm, incorporating heuristic seeding and a post-processing step using constraint programming. The experimental study shows that the proposed approach is able to meet tighter makespan goals than previously published methods, while offering a 32% improvement in energy consumption when goals are met.

关键词： Flexible job shop scheduling Intervals Heuristic seeding constraint programming Lexicographic goal programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：