The idea of deploying unmanned aerial vehicles, also known as drones, for final-mile delivery in logistics operations has vitalized this new research stream. One conceivable scenario of using a drone in conjunction wi...
详细信息
The idea of deploying unmanned aerial vehicles, also known as drones, for final-mile delivery in logistics operations has vitalized this new research stream. One conceivable scenario of using a drone in conjunction with a traditional delivery truck to distribute parcels is discussed in earlier literature and termed the parallel drone scheduling traveling salesman problem (PDSTSP). This study extends the problem by considering two different types of drone tasks: drop and pickup. After a drone completes a drop, the drone can either fly back to depot to deliver the next parcels or fly directly to another customer for pickup. Integrated scheduling of multiple depots hosting a fleet of trucks and a fleet of drones is further studied to achieve an operational excellence. A vehicle that travels near the boundary of the coverage area might be more effective to serve customers that belong to the neighboring depot. This problem is uniquely modeled as an unrelated parallel machine scheduling with sequence dependent setup, precedence-relationship, and reentrant, which gives us a framework to effectively consider those operational challenges. A constraint programming approach is proposed and tested with problem instances of m-truck, m-drone, m-depot, and hundred-customer distributed across an 8-mile square region.
In two-dimensional nesting problems (irregular packing problems) small pieces with irregular shapes must be packed in large objects. A small number of exact methods have been proposed to solve nesting problems, typica...
详细信息
In two-dimensional nesting problems (irregular packing problems) small pieces with irregular shapes must be packed in large objects. A small number of exact methods have been proposed to solve nesting problems, typically focusing on a single problem variant, the strip packing problem. There are however several other variants of the nesting problem which were identified in the literature and are very relevant in the industry. In this paper, constraint programming (CP) is used to model and solve all the variants of irregular cutting and packing problems proposed in the literature. Three approaches, which differ in the representation of the variable domains, in the way they deal with the core constraints and in the objective functions, are the basis for the three models proposed for each variant of the problem. The non-overlap among pieces, which must be enforced for all the problem variants, is guaranteed through the new global constraint NoOverlap in one of the proposed approaches. Taking the benchmark instances for the strip-packing problem, new instances were generated for each problem variant. Extensive computational experiments were run with these problem instances from the literature to evaluate the performance of each approach applied to each problem variant. The models based on the global constraint NoOverlap performed consistently better for all variants due to the increased propagation and to the low memory usage. The performance of the CP model for the strip packing problem with the global constraint NoOverlap was then compared with the Dotted Board with Rotations using larger instances from the literature. The experiments show that the CP model with global constraint NoOverlap can quickly find good quality solutions in shorter computational times even for large instances.
Unexpected events can compromise the execution of the production schedule in low-volume assembly lines. When a disruption occurs because of a delayed part supply, a quality problem or an operator absence, a reactive s...
详细信息
Unexpected events can compromise the execution of the production schedule in low-volume assembly lines. When a disruption occurs because of a delayed part supply, a quality problem or an operator absence, a reactive scheduling approach should be used in a short time in order to prevent significant deviations in final performances. In this study, we propose a new approach based on constraint programming to deal with disruptions. It is tested on a large dataset of problem instances and the obtained results are discussed.
With increasing implementation of off-site prefabrication and modular construction technologies, the complexity of material supply chain management on construction projects has grown substantially. However, research o...
详细信息
With increasing implementation of off-site prefabrication and modular construction technologies, the complexity of material supply chain management on construction projects has grown substantially. However, research on construction scheduling has yet to take dynamic material logistics as an explicit constraint in analytically deriving construction schedules and addressing impacts of uncertainties in material supply on project budget. This study proposes a two-step analytical approach to tackle the identified problem. First, a constraint programming-based scheduling optimization model is developed to derive project schedules subject to variable material delivery times and finite crew resource availability. The second step is to take advantage of the valid optimization model for evaluating the impact of different input settings of material logistics on project budget. An example project adapted from the literature is used to illustrate the effectiveness of the proposed optimization model in coping with variable material delivery times. Based on the same case, the delivery date of a particular material is singled out as the risk factor of interest in order to derive the complex relationship between material delivery date and total project cost. In addition, a case study based on a bridge girder fabrication project is presented to demonstrate the applicability of the proposed optimization model on projects of practical size. In conclusion, this study adds to the body of knowledge by developing an analytical methodology that factors material supply constraints into the resource-constrained scheduling optimization model so as to analyze the impact of uncertainties in material deliveries on project budget.
The emerging field of Compressive Sensing (CS) has shown that sparse signals can be acquired using a rate far less than the one required by the classical Shannon-Nyquist theorem. In that, CS acquires a sparse signal b...
详细信息
ISBN:
(纸本)9781538673300
The emerging field of Compressive Sensing (CS) has shown that sparse signals can be acquired using a rate far less than the one required by the classical Shannon-Nyquist theorem. In that, CS acquires a sparse signal by correlating it with the rows of a sensing matrix to form a small set of measurements. And then these measurements are used to reconstruct the original sparse signal using an optimization algorithm. In this paper, we extend our recently published work, to more investigate the power of constraint programming (CP) solvers with the CS problem. We show that a statistical property of the sensing matrix can highly affects the performance of CP solvers in the case of CS problem. Which enable us to improve the CP solvers performance and even reach the optimal case. The effectiveness of our method is demonstrated via simulation results.
This paper proposes a scheduling method for malleable tasks based on constraint programming (CP). For a given task-graph, the proposed method decides the execution order of tasks and the number of cores to execute eac...
详细信息
ISBN:
(纸本)9781538654576
This paper proposes a scheduling method for malleable tasks based on constraint programming (CP). For a given task-graph, the proposed method decides the execution order of tasks and the number of cores to execute each task simultaneously in such a way that the overall schedule length is minimized Experimental results show that our CP-based scheduling method could find better schedules than the state-of-the-art method which is based on integer linear programming.
Formal reasoning about finite sets and cardinality is important for many applications, including software verification, where very often one needs to reason about the size of a given data structure. The constraint Log...
详细信息
Juxtapositianing manuallycreated business process models with diagrams generated using process discovery algorithms exposes high complexity of the latter. As a consequence, their formal verification requires significa...
详细信息
ISBN:
(纸本)9788394941956
Juxtapositianing manuallycreated business process models with diagrams generated using process discovery algorithms exposes high complexity of the latter. As a consequence, their formal verification requires significant computational resources due to a large state space. Nevertheless, an analysis of the generated model is needed to assure its correctness and the ability to represent source data. As a solution to this problem, we present an approach for constraint-based generation of a complete workflow log for a given BPMN model. In this paper, we propose a method to extract directed subgraphs representing token flows in the process together with a set of predefined constraints. Likewise, in the case of process simulation, these constraints ensure the correctness of the generated traces. Ultimately, the obtained results can be compared to the original workflow log used for process discovery in order to verify the obtained model.
With the rapid growth of Online Social Networks (OSNs) and the information involved in them, research studies concerning OSNs, as well as the foundation of businesses, have become popular. Privacy on OSNs is typically...
详细信息
ISBN:
(纸本)9783319735214;9783319735207
With the rapid growth of Online Social Networks (OSNs) and the information involved in them, research studies concerning OSNs, as well as the foundation of businesses, have become popular. Privacy on OSNs is typically protected by anonymisation methods. Current methods are not sufficient to ensure privacy and they impose restrictions on the network making it not suitable for research studies. This paper introduces an approach to find an optimal anonymous graph under user-defined metrics using constraint programming, a technique that provides well-tested and optimised engine for combinatorial problems. The approach finds a good trade-off between protection of sensitive data and quality of the information represented by the network.
The Traveling Tournament Problem with Predefined Venues (TTPPV) is a practical problem arising from sports scheduling. We describe two different modeling approaches for this problem, each of which is suitable for diff...
详细信息
ISBN:
(数字)9783030059187
ISBN:
(纸本)9783030059187;9783030059170
The Traveling Tournament Problem with Predefined Venues (TTPPV) is a practical problem arising from sports scheduling. We describe two different modeling approaches for this problem, each of which is suitable for different sizes of instance. The experimental results show that our modeling approaches lead to improved performance compared to previous techniques in terms of the number of feasible solutions and the optimal value. Furthermore, we present how to execute the models in parallel through data-level parallelism. The parallel versions do not only gain speedup but also attain significant improvement on optimal value since more subtrees are searched independently.
暂无评论