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.
We introduce function variables to constraint programs (CP), variables whose values are one of (exponentially many) possible functions between two sets. Such variables are useful for modelling problems from domains su...
详细信息
We introduce function variables to constraint programs (CP), variables whose values are one of (exponentially many) possible functions between two sets. Such variables are useful for modelling problems from domains such as configuration, planning, scheduling, etc. We show that a function variable can be mapped into different representations in terms of integer and set variables, and illustrate how to map constraints stated on a function variable into constraints on integer and set variables. As a result, a constraint model expressed using function variables allows for the generation of alternate CP models. Furthermore, we present an extensive theoretical comparison of models of problems involving injective functions supported by asymptotic and empirical studies. Finally, we present and evaluate a practical modelling tool that is based on a high-level language that supports function variables. The tool helps users explore different alternate CP models starting from a function model that is easy to develop, understand, and maintain.
The concept of domain views is a powerful abstraction in constraint programming It permits to define variables that do not declare any domain but instead rely on a variable x and a function f, such that y = f(x) where...
详细信息
The concept of domain views is a powerful abstraction in constraint programming It permits to define variables that do not declare any domain but instead rely on a variable x and a function f, such that y = f(x) where y is the view. In addition to making modelling easier by providing an expressive layer of abstraction, views provide an alternative to constraint decomposition that does not involve auxiliary variables and propagators. In this article, we introduce the notion of global domain view and illustrate it on set and graph views. A global domain view relies on an arbitrary number of variables and a function such that y = f(x(1),...,x(n)). The combination of global domain views with set and graph variables extends the expressiveness of constraint programming by allowing the definition of complex relationships between different types of variables within a light and simple framework.
The diameter-constrained minimum spanning tree problem consists in finding a minimum spanning tree of a given graph, subject to the constraint that the maximum number of edges between any two vertices in the tree is b...
详细信息
The diameter-constrained minimum spanning tree problem consists in finding a minimum spanning tree of a given graph, subject to the constraint that the maximum number of edges between any two vertices in the tree is bounded from above by a given constant. This problem typically models network design applications where all vertices communicate with each other at a minimum cost, subject to a given quality requirement. We propose alternative formulations using constraint programming that circumvent weak lower bounds yielded by most mixed-integer programming formulations. Computational results show that the proposed formulation, combined with an appropriate search procedure, solves larger instances and is faster than other approaches in the literature.
Mining web access patterns consists in extracting knowledge from server log files. This problem is represented as a sequential pattern mining problem (SPM) which allows to extract patterns which are sequences of acces...
详细信息
Mining web access patterns consists in extracting knowledge from server log files. This problem is represented as a sequential pattern mining problem (SPM) which allows to extract patterns which are sequences of accesses that occur frequently in the web log file. There are in the literature many efficient algorithms to solve SMP (e.g., GSP, SPADE, PrefixSpan, WAP-tree, LAPIN, PLWAP). Despite the effectiveness of these methods, they do not allow to express and to handle new constraints defined on patterns, new implementations are required. Recently, many approaches based on constraint programming (CP) was proposed to solve SPM in a declarative and generic way. Since no CP-based approach was applied for mining web access patterns, the authors introduce in this paper an efficient CP-based approach for solving the web log mining problem. They bring back the problem of web log mining to SPM within a CP environment which enables to handle various constraints. Experimental results on non-trivial web log mining problems show the effectiveness of the authors' CP-based mining approach.
This paper addresses the crew scheduling problem for a mass rapid transit (MRT) system. The problem is to find a minimum number of duties to cover all tasks while satisfying all the hard and soft scheduling rules. Suc...
详细信息
This paper addresses the crew scheduling problem for a mass rapid transit (MRT) system. The problem is to find a minimum number of duties to cover all tasks while satisfying all the hard and soft scheduling rules. Such rules are complicated in real-world operations and difficult to follow through optimization methods alone. In this paper, we propose a constraint programming (CP)-based approach to solve the problem. The approach involves a CP model for duty generation, a set covering problem model for duty optimization, and alternative ways to identify the final solution in different situations. We applied the proposed CP-based approach to solve a case problem for the Taipei MRT. Case application results using real-world data showed that our approach is capable of reducing the number of daily duties from 58 to 55 and achieving a 5.2 % savings in labor costs. We also incorporated the soft rule considerations into the CP model in order to generate alternative optimum solutions that would improve the workload balance. The coefficient of variation of the work time distribution improves significantly, falling from 21 % to approximately 5 %. Given the CP model's comprehensive coverage of various scheduling rules, our proposed approach and models would also be applicable to other MRT systems.
In this paper we propose a new algorithm called MCS for the search for solutions to multicriteria combinatorial optimisation problems. To quickly produce a solution that offers a good trade-off between criteria, the M...
详细信息
In this paper we propose a new algorithm called MCS for the search for solutions to multicriteria combinatorial optimisation problems. To quickly produce a solution that offers a good trade-off between criteria, the MCS algorithm alternates several Branch & Bound searches following diversified search strategies. It is implemented in CP in a dedicated framework and can be specialised for either complete or partial search.
Within the area of short term airline operational planning, Tail Assignment is the problem of assigning flight legs to individual identified aircraft while satisfying all operational constraints, and optimizing some o...
详细信息
Within the area of short term airline operational planning, Tail Assignment is the problem of assigning flight legs to individual identified aircraft while satisfying all operational constraints, and optimizing some objective function. In this article, we propose that Tail Assignment should be solved as part of both the short and the long term airline planning. We further present a hybrid column generation and constraint programming solution approach. This approach can be used to quickly produce solutions for operations management, and also to produce close-to-optimal solutions for long and mid term planning scenarios. We present computational results which illustrate the practical usefulness of the approach.
Purpose: The manuscript presents an investigation into a constraint programming-based genetic algorithm for capacity output optimization in a back-end semiconductor manufacturing company. Design/methodology/approach: ...
详细信息
Purpose: The manuscript presents an investigation into a constraint programming-based genetic algorithm for capacity output optimization in a back-end semiconductor manufacturing company. Design/methodology/approach: In the first stage, constraint programming defining the relationships between variables was formulated into the objective function. A genetic algorithm model was created in the second stage to optimize capacity output. Three demand scenarios were applied to test the robustness of the proposed algorithm. Findings: CPGA improved both the machine utilization and capacity output once the minimum requirements of a demand scenario were fulfilled. Capacity outputs of the three scenarios were improved by 157%, 7%, and 69%, respectively. Research limitations/implications: The work relates to aggregate planning of machine capacity in a single case study. The constraints and constructed scenarios were therefore industry-specific. Practical implications: Capacity planning in a semiconductor manufacturing facility need to consider multiple mutually influenced constraints in resource availability, process flow and product demand. The findings prove that CPGA is a practical and an efficient alternative to optimize the capacity output and to allow the company to review its capacity with quick feedback Originality/value: The work integrates two contemporary computational methods for a real industry application conventionally reliant on human judgement. .
Real-life management decisions are usually made in uncertain environments, and decision support systems that ignore this uncertainty are unlikely to provide realistic guidance. We show that previous approaches fail to...
详细信息
Real-life management decisions are usually made in uncertain environments, and decision support systems that ignore this uncertainty are unlikely to provide realistic guidance. We show that previous approaches fail to provide appropriate support for reasoning about reliability under uncertainty. We propose a new framework that addresses this issue by allowing logical dependencies between constraints. Reliability is then defined in terms of key constraints called "events", which are related to other constraints via these dependencies. We illustrate our approach on three problems, contrast it with existing frameworks, and discuss future developments.
暂无评论