An official website of the United States government
The offline pickup and delivery problem with time windows (PDPTW) is a classical combinatorial optimization problem in the transportation community, which has proven to be very challenging computationally. Due to the complexity of the problem, practical problem instances can be solved only via heuristics, which trade-off solution quality for computational tractability. Among the various heuristics, a common strategy is problem decomposition, that is, the reduction of a large-scale problem into a collection of smaller sub-problems, with spatial and temporal decompositions being two natural approaches. While spatial decomposition has been successful in certain settings, effective temporal decomposition has been challenging due to the difficulty of stitching together the sub-problem solutions across the decomposition boundaries. In this work, we introduce a novel temporal decomposition scheme for solving a class of PDPTWs that have narrow time windows, for which it is able to provide both fast and high-quality solutions. We utilize techniques that have been popularized recently in the context of online dial-a-ride problems along with the general idea of rolling horizon optimization. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such an approach. To show the performance and scalability of our framework, we use the optimization of paratransit services as a motivating example. Due to the lack of benchmark solvers similar to ours (i.e., temporal decomposition with an online solver), we compare our results with an offline heuristic algorithm using Google OR-Tools. In smaller problem instances (with an average of 129 requests per instance), the baseline approach is as competitive as our framework. However, in larger problem instances (approximately 2,500 requests per instance), our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty, while the baseline algorithm often fails to find a feasible solution within comparable compute times.
more »
« less
Towards a solver-aware systems architecting framework: leveraging experts, specialists and the crowd to design innovative complex systems
Abstract This article proposes the solver-aware system architecting framework for leveraging the combined strengths of experts, crowds and specialists to design innovative complex systems. Although system architecting theory has extensively explored the relationship between alternative architecture forms and performance under operational uncertainty, limited attention has been paid to differences due to who generates the solutions. The recent rise in alternative solving methods, from gig workers to crowdsourcing to novel contracting structures emphasises the need for deeper consideration of the link between architecting and solver-capability in the context of complex system innovation. We investigate these interactions through an abstract problem-solving simulation, representing alternative decompositions and solver archetypes of varying expertise, engaged through contractual structures that match their solving type. We find that the preferred architecture changes depending on which combinations of solvers are assigned. In addition, the best hybrid decomposition-solver combinations simultaneously improve performance and cost, while reducing expert reliance. To operationalise this new solver-aware framework, we induce two heuristics for decomposition-assignment pairs and demonstrate the scale of their value in the simulation. We also apply these two heuristics to reason about an example of a robotic manipulator design problem to demonstrate their relevance in realistic complex system settings.
more »
« less
- PAR ID:
- 10352589
- Date Published:
- Journal Name:
- Design Science
- Volume:
- 8
- ISSN:
- 2053-4701
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Cascades of DNA strand displacement reactions enable the design of potentially large circuits with complex behaviour. Computational modelling of such systems is desirable to enable rapid design and analysis. In previous work, the expressive power of graph theory was used to enumerate reactions implementing strand displacement across a wide range of complex structures. However, coping with the rich variety of possible graph-based structures required enumeration rules with complicated side-conditions. This paper presents an alternative approach to tackle the problem of enumerating reactions at domain level involving complex structures by integrating with a geometric constraint solving algorithm. The rule sets from previous work are simplified by replacing side-conditions with a general check on the geometric plausibility of structures generated by the enumeration algorithm. This produces a highly general geometric framework for reaction enumeration. Here, we instantiate this framework to solve geometric constraints by a structure sampling approach in which we randomly generate sets of coordinates and check whether they satisfy all the constraints. We demonstrate this system by applying it to examples from the literature where molecular geometry plays an important role, including DNA hairpin and remote toehold reactions. This work therefore enables integration of reaction enumeration and structural modelling.more » « less
-
The performance of a simulation-optimization algorithm, a.k.a. a solver, depends on its parameter settings. Much of the research to date has focused on how a solver’s parameters affect its convergence and other asymptotic behavior. While these results are important for providing a theoretical understanding of a solver, they can be of limited utility to a user who must set up and run the solver on a particular problem. When running a solver in practice, good finite-time performance is paramount. In this article, we explore the relationship between a solver’s parameter settings and its finite-time performance by adopting a data farming approach. The approach involves conducting and analyzing the outputs of a designed experiment wherein the factors are the solver’s parameters and the responses are assorted performance metrics measuring the solver’s speed and solution quality over time. We demonstrate this approach with a study of the ASTRO-DF solver when solving a stochastic activity network problem and an inventory control problem. Through these examples, we show that how some of the solver’s parameters are set greatly affects its ability to achieve rapid, reliable progress and gain insights into the solver’s inner workings. We discuss the implications of using this framework for tuning solver parameters, as well as for addressing related questions of interest to solver specialists and generalists.more » « less
-
Problem solvers vary their approaches to solving problems depending on the context of the problem, the requirements of the solution, and the ways in which the problems and material to solve the problem are represented, or representations. Representations take many forms (i.e. tables, graphs, figures, images, formulas, visualizations, and other similar contexts) and are used to communicate information to a problem solver. Engagement with certain representations varies between problem solvers and can influence design and solution quality. A problem solver’s evaluation of representations and the reasons for using a representation can be considered factors in problem-solving heuristics. These factors describe unique problem-solving behaviors that can help understand problem solvers. These behaviors may lead to important relationships between a problem solver’s decisions and their ability to solve a problem and overall quality of the solution. Therefore, we pose the following research question: How do factors of problem-solving heuristics describe the unique behaviors of engineering students as they solve multiple problems? To answer this question, we interviewed 16 undergraduate engineering students studying civil engineering. The interviews consisted of a problem-solving portion that was followed immediately by a semi-structured retrospective interview with probing questions created based on the real time monitoring of the problem-solving interview using eye tracking techniques. The problem-solving portion consisted of solving three problems related to the concept of headloss in fluid flow through pipes. Each of the three problems included the same four representations that were used by the students as approaches to solving the problem. The representations are common ways to present the concept of headloss in pipe flow and included two formulas, a set of tables, and a graph. This paper presents a set of common reasons for why decisions were made during the problem-solving process that help to understand more about the problem-solving behavior of engineering students.more » « less
-
Mechanical metamaterials represent an innovative class of artificial structures, distinguished by their extraordinary mechanical characteristics, which are beyond the scope of traditional natural materials. The use of deep generative models has become increasingly popular in the design of metamaterial units. The effectiveness of using deep generative models lies in their capacity to compress complex input data into a simplified, lower-dimensional latent space, while also enabling the creation of novel optimal designs through sampling within this space. However, the design process does not take into account the effect of model uncertainty due to data sparsity or the effect of input data uncertainty due to inherent randomness in the data. This might lead to the generation of undesirable structures with high sensitivity to the uncertainties in the system. To address this issue, a novel uncertainty-aware deep learning framework-based robust design approach is proposed for the design of metamaterial units with optimal target properties. The proposed approach utilizes the probabilistic nature of the deep learning framework and quantifies both aleatoric and epistemic uncertainties associated with surrogate-based design optimization. We demonstrate that the proposed design approach is capable of designing high-performance metamaterial units with high reliability. To showcase the effectiveness of the proposed design approach, a single-objective design optimization problem and a multi-objective design optimization problem are presented. The optimal robust designs obtained are validated by comparing them to the designs obtained from the topology optimization method as well as the designs obtained from a deterministic deep learning framework-based design optimization where none of the uncertainties in the system are explicitly considered.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/dsj.2022.7
