To address challenges inherent in the scheduling of public bus transportation, such as disparities in peak and off-peak operational demands, amalgamated single and double shift operations, this study endeavors to mode...
详细信息
ISBN:
(纸本)9798350389913;9798350389906
To address challenges inherent in the scheduling of public bus transportation, such as disparities in peak and off-peak operational demands, amalgamated single and double shift operations, this study endeavors to model and optimize the daily operational schedules for bus routes, grounded in empirical data reflecting actual operational requirements. The formulation of the bus scheduling problem entails the integration of various parameters including planned trip quantities, peak-hour road conditions, station dwell durations, inter-departure intervals, and driver shift change dynamics. In the optimization process, a hybrid algorithm, combining Genetic Algorithm (GA) and Tabu Search (TS), is proposed. GA serves as a heuristic for a global exploration of the solution space, while TS is for a detailed exploration of local regions. Leveraging the operational parameters of actual bus schedules in Nanjing, the proposed hybrid algorithm is applied to refine the scheduling plan for a specific bus route. The actual scheduling results demonstrate that, in comparison to stand-alone implementations of GA, greedy algorithms, and manually crafted schedules, the hybrid GA-Tabu algorithm yields a noteworthy 7.88 percent improvement in the utilization rate of working hours. Furthermore, the departure frequency seamlessly adapts to peak periods, aligning with passenger demand patterns and augmenting the overall system efficiency. The proposed hybrid GA-Tabu algorithm proves efficacious in enhancing system efficiency, catering to passenger demands, and ensuring compliance with driver work hour regulations. Besides, its applicability showcases a degree of generality within the realm of public bus transportation scheduling.
The shift from centralized to decentralized systems is increasing the complexity of many problems in control and optimization. However, it also presents the opportunity to exploit parallelized computational schemes. T...
详细信息
ISBN:
(纸本)9798331540920;9783907144107
The shift from centralized to decentralized systems is increasing the complexity of many problems in control and optimization. However, it also presents the opportunity to exploit parallelized computational schemes. This paper shows how the solution process of mixed-integer problems, which often arise in areas like production scheduling or logistics, can be supported by employing parallel computations. To this end, dual variables are introduced that enable the decomposition of these complex problems into subproblems that can then be solved in parallel. The presented dual decomposition-based approach provides a lower bound for the optimal solution of the original problem, which can support the overall solution process. The focus of this paper is on the parallelizability of the computation of this lower bound. The bounds from three different dual decomposition-based distributed optimization algorithms are compared to the lower bounds provided by several commercial solvers within their branch-&-cut framework.
The Geometric Buchberger algorithm is a specialization of the classical Buchberger algorithm to the case of toric ideals, with applications in the solution of families of integer programming problems. In this paper, w...
详细信息
ISBN:
(纸本)9798400706967
The Geometric Buchberger algorithm is a specialization of the classical Buchberger algorithm to the case of toric ideals, with applications in the solution of families of integer programming problems. In this paper, we investigate the performance of the Geometric Buchberger algorithm in a variety of combinatorial optimization problems with both integer and binary variables, introducing algorithmic improvements for the latter case in the form of an efficient criterion for detecting S-binomials that can be truncated away. Our experiments show that our implementation, available in the package ***, computes Grobner bases for toric ideals of combinatorial optimization problems more efficiently than the previous state-of-the-art.
Detailed routing is a crucial and time-consuming stage for ASIC design. As the number and complexity of design rules increase, it is challenging to achieve high solution quality and fast speed at the same time in deta...
详细信息
ISBN:
(纸本)9798350393545
Detailed routing is a crucial and time-consuming stage for ASIC design. As the number and complexity of design rules increase, it is challenging to achieve high solution quality and fast speed at the same time in detailed routing. In this work, a high performance detailed routing algorithm named IPAG with integer programming (IP) is proposed. The IP formulation uses the selection of candidate routes as decision variables. High quality candidate routes are generated by queue-based rip-up and reroute with adaptive global route guidance. A design rule checking engine which can simultaneously process nets with multiple routes is designed, to efficiently construct penalty parameters in the IP formulation. Experimental results on ISPD 2018 detailed routing benchmark show that IPAG achieves better solution quality in shorter or comparable runtime, as compared to the state-of-the-art academic detailed router.
Over the years, countries have been exploring options to solve the current global energy crisis. It hinders economic development due to a lack of proper energy management infrastructure and higher energy consumption, ...
详细信息
ISBN:
(纸本)9798350371345
Over the years, countries have been exploring options to solve the current global energy crisis. It hinders economic development due to a lack of proper energy management infrastructure and higher energy consumption, resulting in an imbalance between demand and supply. Thus, this paper presents the application of integer programming in home energy management to develop an integer programming model that monitors and controls energy consumption trends in real-time while considering available energy units balance based on which devices are turned on at that particular time. The energy consumption optimization problem was formulated by considering prepaid billing consumers who can only switch their devices as per limited available energy at any given time. The devices were controlled with the help of a mobile application, and real-time power consumption was obtained from the deployed sensors on our system. The results confirm that the proposed model can predict the amount of time it takes for the available electricity balance to run out based on energy consumed by powered-on devices. This interval gets dynamically updated in real-time and also considers device status change. Hence, this will help consumers to make data-driven decisions on energy usage allocation and device activation prioritization while considering the availability of remaining energy units as one of the constraints leading to improved energy usage efficiency and sustainability as well as cost savings.
Satellites underpin all economic, military, and scientific activity in space. Ground-based telescope observations provide much of the tracking information that enables collision avoidance and space traffic management,...
详细信息
ISBN:
(纸本)9798350304626
Satellites underpin all economic, military, and scientific activity in space. Ground-based telescope observations provide much of the tracking information that enables collision avoidance and space traffic management, but recent growth in the size and dynamism of the satellite population divides the available observing capacity between multiple competing observation objectives. The task of selecting an optimal assignment of telescope observing capacity to observation objectives is NP-hard and involves domain-specific considerations such as sequence-dependent transition times, observability constraints, occlusion avoidance, and astrodynamic limitations. These features conspire to prevent direct and efficient application of traditional scheduling approaches over long time horizons. This work maps the task of scheduling ground-based sensor observations to an unrelated parallel machine scheduling problem with sequence-dependent transition times, restricted time windows, and a fixed time horizon. We contribute an integer programming model of the task, complete with inequality formulations of domain-specific constraints, and a decomposition algorithm that discovers reward-optimal schedules. Using the open-source CBC solver, the integer programming model can reliably be solved for problem instances with up to 6 sensors and 40 targets for a 4 minute time horizon within an equal runtime limit. To address more challenging problem instances, we propose a decomposition algorithm that supports early termination and returns suboptimal schedules along with an associated optimality gap for instances with up to 6 sensors and 200 targets over a 15 minute time horizon.
In this paper, we conduct numerical experiments to test the effectiveness of several integer programming formulations of the cycle selection problem. Specifically, we carry out experiments to identify a maximum weight...
详细信息
ISBN:
(纸本)9783031609237;9783031609244
In this paper, we conduct numerical experiments to test the effectiveness of several integer programming formulations of the cycle selection problem. Specifically, we carry out experiments to identify a maximum weighted cycle selection in random or in structured digraphs. The results show that random instances are relatively easy and that two formulations outperform the other ones in terms of total running time. We also examine variants of the problem obtained by adding a budget constraint and/or a maximum cycle length constraint. These variants are more challenging, especially when a budget constraint is imposed. To investigate the cycle selection problem with a maximum cycle length equal to 3, we provide an arc-based formulation with an exponential number of constraints that can be separated in polynomial time. All inequalities in the formulation are facet-defining for complete digraphs.
Relaxed correlation clustering (RCC) is a vertex partitioning problem that aims at minimizing the so-called relaxed imbalance in signed graphs. RCC is considered to be an NP-hard unsupervised learning problem with app...
详细信息
Relaxed correlation clustering (RCC) is a vertex partitioning problem that aims at minimizing the so-called relaxed imbalance in signed graphs. RCC is considered to be an NP-hard unsupervised learning problem with applications in biology, economy, image recognition and social network analysis. In order to solve it, we propose two linear integer programming formulations and a local search-based metaheuristic. The latter relies on auxiliary data structures to efficiently perform move evaluations during the search process. Extensive computational experiments on existing and newly proposed benchmark instances demonstrate the superior performance of the proposed approaches when compared to those available in the literature. While the exact approaches obtained optimal solutions for open problems, the proposed heuristic algorithm was capable of finding high quality solutions within a reasonable CPU time. In addition, we also report improving results for the symmetrical version of the problem. Moreover, we show the benefits of implementing the efficient move evaluation procedure that enables the proposed metaheuristic to be scalable, even for large-size instances.
The epsilon-constraint method is a well-known scalarization technique used for multiobjective optimization. We explore how to properly define the step size parameter of the method in order to guarantee its exactness w...
详细信息
The epsilon-constraint method is a well-known scalarization technique used for multiobjective optimization. We explore how to properly define the step size parameter of the method in order to guarantee its exactness when dealing with biobjective nonlinear integer problems. Under specific assumptions, we prove that the number of subproblems that the method needs to address to detect the complete Pareto front is finite. We report numerical results on portfolio optimization instances built on real-world data and show a comparison with an existing criterion space algorithm. (c) 2022 Elsevier B.V. All rights reserved.
Molecular biology advances in the past few decades have contributed to the rapid increase in genome sequencing of various organisms;sequence alignment is usually considered the first step in understanding a sequence&#...
详细信息
Molecular biology advances in the past few decades have contributed to the rapid increase in genome sequencing of various organisms;sequence alignment is usually considered the first step in understanding a sequence's molecular function. Understanding such a function is made possible by aligning an unknown sequence with known sequences based on evolution. An optimal alignment adjusts two or more sequences in a way that it could compare the maximum number of identical or similar residues. The two sequence alignments types are Pairwise Sequence Alignment (PSA) and Multiple Sequence Alignment (MSA). The MSA enjoys a higher advantage than PSA since it predicts the similarity in a family of similar sequences, providing more biological data. Moreover, while the dynamic programming (DP) technique is used in PSA to provide the optimal method, it will lead to more complexity if used in MSA. So, the MSA mainly uses heuristic and approximation methods. Such methods include progressive alignment, iterative alignment, Hidden Markov Model (HMM), and Metaheuristic algorithms. This paper presents a genetic algorithm and chromosome design to solve a mathematical model for MSA. This model uses a basis for an optimal solution in different ways, and an X-mediated matrix with binary elements is used to model the sequence. Then, the model is implemented using the Genetic Algorithm method on the web, and the final results indicate the success of GA for the MSA approach.
暂无评论