This paper introduces a hybrid algorithm for the dynamic dial-a-ride problem in which service requests arrive in real time. The hybrid algorithm combines an exact constraint programming algorithm and a tabu search heu...
详细信息
This paper introduces a hybrid algorithm for the dynamic dial-a-ride problem in which service requests arrive in real time. The hybrid algorithm combines an exact constraint programming algorithm and a tabu search heuristic. An important component of the tabu search heuristic consists of three scheduling procedures that are executed sequentially. Experiments show that the constraint programming algorithm is sometimes able to accept or reject incoming requests, and that the hybrid method outperforms each of the two algorithms when they are executed alone.
This paper studies the scheduling of jobs of different families on parallel machines, where not all machines are qualified (eligible) to process all job families. Originating from semiconductor manufacturing, an impor...
详细信息
This paper studies the scheduling of jobs of different families on parallel machines, where not all machines are qualified (eligible) to process all job families. Originating from semiconductor manufacturing, an important constraint imposes that the time between the processing of two consecutive jobs of the same family on a machine does not exceed a given time limit. Otherwise, the machine becomes disqualified for this family. The goal is to minimize both the flow time and the number of disqualifications of job families on machines. To solve this problem, an integer linear programming model and a constraint programming model are proposed, as well as two improvement procedures of existing heuristics: A Recursive Heuristic and a Simulated Annealing algorithm. Numerical experiments on randomly generated instances compare the performances of each method. (C) 2019 Published by Elsevier Ltd.
In this paper, the bilevel programming model of the public transport network considering factors such as the per capita occupancy area and travel cost of different groups was established, to alleviate the urban transp...
详细信息
In this paper, the bilevel programming model of the public transport network considering factors such as the per capita occupancy area and travel cost of different groups was established, to alleviate the urban transportation equity and optimize the urban public transport network under fairness constraints. The upper layer minimized the travel cost deprivation coefficient and the road area Gini coefficient as the objective function, to solve the optimization scheme of public transport network considering fairness constraints;the lower layer was a stochastic equilibrium traffic assignment model of multimode and multiuser, used to describe the complex selection behavior of different groups for different traffic modes in the bus optimization scheme given by the upper layer. The model in addition utilised the noninferior sorting genetic algorithm II to validate the model via a simple network. The results showed that (1) the travel cost deprivation coefficient of the three groups declined from 33.42 to 26.51, with a decrease of 20.68%;the Gini coefficient of the road area declined from 0.248 to 0.030, with a decrease of 87.76%;it could be seen that the transportation equity feeling of low-income groups and objective resource allocation improved significantly;(2) before the optimization of public transport network, the sharing rate of cars, buses, and bicycles was 42%, 47%, and 11%, respectively;after the optimization, the sharing rate of each mode was 7%, 82%, and 11%, respectively. Some of the high and middle income users who owned the car were transferred to the public transportation. It could be seen that the overall travel time of the optimized public transport network reduced, enhancing the attraction of the public transport network to various travel groups. The model improves the fairness of the urban public transport system effectively while ensuring the travel demand of the residents. It provides theoretical basis and model foundation for the optimization of publ
In this article, we consider the problem of planning preventive maintenance of railway signals in Denmark. This case is particularly relevant as the entire railway signalling system is currently being upgraded to the ...
详细信息
In this article, we consider the problem of planning preventive maintenance of railway signals in Denmark. This case is particularly relevant as the entire railway signalling system is currently being upgraded to the new European Railway Traffic Management System (ERTMS) standard. This upgrade has significant implications for signal maintenance scheduling in the system. We formulate the problem as a multi-depot vehicle routing and scheduling problem with time windows and synchronisation constraints, in a multi-day time schedule. The requirement that some tasks require the simultaneous presence of more than one engineer means that task synchronisation must be considered. A multi-stage constructive framework is proposed, which first distributes maintenance tasks using a clustering formulation. Following this, a constraint programming (CP) based approach is used to generate feasible monthly plans for large instances of practical interest. Experimental results indicate that the proposed framework can generate feasible solutions and schedule a monthly plan of up to 1000 tasks for eight crew members, in a reasonable amount of computational time.
The quorumcast routing problem is a generalization of multicasting which arises in many distributed applications. It consists of finding a minimum cost tree that spans the source node r and at least q out of m specifi...
详细信息
The quorumcast routing problem is a generalization of multicasting which arises in many distributed applications. It consists of finding a minimum cost tree that spans the source node r and at least q out of m specified nodes on a given undirected weighted graph. This paper proposes a complete and an incomplete approach, both based on the same constraint programming (CP) model, but with two different specific search heuristics based on shortest paths. Experimental results show the efficiency of the two proposed approaches. Our complete approach (CP model + complete search) is better than the state of the art complete algorithm and our incomplete approach (CP model + incomplete search) is better than the state of the art incomplete algorithm. Moreover, the proposed complete search is better than the standard First-Fail search in the same CP model.
The assembly line balancing problem employs traditional precedence graphs to model precedence relations among assembly tasks. Yet they cannot address alternative ways of assembling a product. That is, they only model ...
详细信息
The assembly line balancing problem employs traditional precedence graphs to model precedence relations among assembly tasks. Yet they cannot address alternative ways of assembling a product. That is, they only model conjunctions, not disjunctions. Moreover, some additional constraints need also to be considered, but these constraints cannot be modeled effectively through precedence graphs, e.g., constraints indicating certain tasks cannot be assigned into the same station. To address these issues, this paper proposes to model assembly constraints through the well known If-then rules, and to solve the rule-based model through constraint programming (CP), as CP naturally models logical assertions. The paper also shows how to map a rule-based model to a CP or an integer programming (IP) model. Finally, a computational experiment is carried out to analyze the performances of CP and IP models with respect to modeling capability, solution quality and time. The results reveal that CP is more effective and efficient than IP. (C) 2011 Elsevier Ltd. All rights reserved.
An intelligent robotic system must be capable of making the best decision at any given moment. The criteria for which task is "best" can be derived by performance metrics as well as the ability for it to sat...
详细信息
An intelligent robotic system must be capable of making the best decision at any given moment. The criteria for which task is "best" can be derived by performance metrics as well as the ability for it to satisfy all constraints upon the robot and its mission. constraints may exist based on safety, reliability, accuracy, etc. This paper presents a decision framework capable of assisting a robotic system to select a task that satisfies all constraints as well as is optimized based upon one or more performance criteria. The framework models this decision process as a constraint satisfaction problem using techniques and algorithms from constraint programming and constraint optimization in order to provide a solution in real-time. This paper presents this framework and initial results provided through two demonstrations. The first utilizes simulation to provide an initial proof of concept, and the second, a security robot demonstration, is performed using a physical robot.
The thesis defense timetabling problem consists in composing the suitable committee for a set of defense sessions and assigning each graduation candidate to one of the sessions. In this work, we define the problem for...
详细信息
The thesis defense timetabling problem consists in composing the suitable committee for a set of defense sessions and assigning each graduation candidate to one of the sessions. In this work, we define the problem formulation that applies to some Italian universities and we provide three alternative solution methods, based on Integer programming, constraint programming and Local Search, respectively. We also develop a principled instance generator, in order to expand the set of available instances. We perform an experimental analysis and we compare our solvers among themselves, using a testbed composed of both real-world and artificial instances. Even though there is no dominant method, the outcome is that Integer programming gives the best average results, with Local Search being second, and constraint programming last on our testbed. All data is available on the web for verification and future comparisons.
This paper presents an optimal constraint programming approach for the open-shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized ...
详细信息
This paper presents an optimal constraint programming approach for the open-shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized restart policies combined with nogood recording allow us to search diversification and learning from restarts. This approach is compared with the best-known metaheuristics and exact algorithms, and it shows better results on a wide range of benchmark instances.
作者：
He, FangQu, RongUniv Nottingham
Sch Comp Sci Automated Scheduling Optimisat & Planning ASAP Gr Nottingham NG8 1BB England
This paper presents our investigations on a hybrid constraint programming based column generation (CP-CG) approach to nurse rostering problems. We present a complete model to formulate all the complex real-world const...
详细信息
This paper presents our investigations on a hybrid constraint programming based column generation (CP-CG) approach to nurse rostering problems. We present a complete model to formulate all the complex real-world constraints in several benchmark nurse rostering problems. The hybrid CP-CG approach is featured with not only the effective relaxation and optimality reasoning of linear programming but also the powerful expressiveness of constraint programming in modeling the complex logical constraints in nurse rostering problems. In solving the CP pricing subproblem, we propose two strategies to generate promising columns which contribute to the efficiency of the CG procedure. A Depth Bounded Discrepancy Search is employed to obtain diverse columns. A cost threshold is adaptively tightened based on the information collected during the search to generate columns of good quality. Computational experiments on a set of benchmark nurse rostering problems demonstrate a faster convergence by the two strategies and justify the effectiveness and efficiency of the hybrid CP-CG approach. (c) 2012 Elsevier Ltd. All rights reserved.
暂无评论