检索结果-内蒙古大学图书馆

Train service design in an urban rail transit line incorporating multiple service routes and multiple train compositions

引用

TRANSPORTATION REsearch PART C-EMERGING TECHNOLOGIES 2021年 123卷 102959-102959页

作者： Li, Zhengyang Zhao, Jun Peng, Qiyuan Southwest Jiaotong Univ Sch Transportat & Logist Chengdu 611756 Sichuan Peoples R China Southwest Jiaotong Univ Natl United Engn Lab Integrated & Intelligent Tra Chengdu 611756 Sichuan Peoples R China Hong Kong Polytech Univ Dept Civil & Environm Engn Hong Kong Peoples R China

This paper focuses on the train service design problem within a given period in an urban rail transit line, where multiple either full-length or short-turn service routes can be operated, and each service route can utilize one of several different train compositions. The problem lies on determining the turn-back stations, train composition and frequency of each service route operated on the line. Considering the interests of operators and passengers, we decompose the problem as two subproblems namely train service configuration and passenger assignment. The first subproblem is formulated as an integer linear programming model with the objective of minimizing operators' cost. Given a train service scheme, the second subproblem is modelled as a capacitated continuous multi-commodity flow model to minimize passengers' waiting time cost and transfer cost. The optimal strategy is extended to determine the behaviour of passengers and capture the extra waiting time of passengers under capacity constraint. The two sub-models are weighted and integrated into a mixed integer nonlinear programming model, which is further transformed into a mixed integer linear programming model using a novel linearization method. By exploiting the special characteristics of the model, a tailored and easy to implement local search algorithm is developed to solve large-scale instances. Starting from the operator-optimum solution which can be easily obtained, the algorithm solves the two sub-models iteratively to search better solutions within a precalculated search range which is smaller than the complete feasible domain. Finally, different sizes of instances constructed from two urban rail transit lines are utilized to demonstrate the performance and practicability of the proposed approaches.

关键词： Urban rail transit Train service design Multiple service routes Multiple train compositions local search algorithm

来源：评论

学校读者我要写书评

暂无评论

Data-independent neighborhood functions and strict local optima

引用

DISCRETE APPLIED MATHEMATICS 2005年第3期146卷 233-243页

作者： Armstrong, DE Jacobson, SH BAE Syst Arlington VA 22203 USA Univ Illinois Dept Mech & Ind Engn Urbana IL 61801 USA

The paper proves that data-independent neighborhood functions with the smooth property (all strict local optima are global optima) for maximum 3-satisfiability (MAX 3-SAT) must contain all possible solutions for large instances. Data-independent neighborhood functions with the smooth property for 0-1 knapsack are shown to have size with the same order of magnitude as the cardinality of the solution space. Data-independent neighborhood functions with the smooth property for traveling salesman problem (TSP) are shown to have exponential size. These results also hold for certain polynomially solvable sub-problems of MAX 3-SAT, 0-1 knapsack and TSP. (C) 2004 Elsevier B.V. All rights reserved.

关键词： computational complexity local search algorithm exponential neighborhood

来源：评论

学校读者我要写书评

暂无评论

Heuristic approaches for the family traveling salesman problem

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL REsearch 2021年第1期28卷 262-295页

作者： Bernardino, Raquel Paias, Ana Univ Lisbon Fac Ciencias DEIO C6Piso 4 P-1749016 Lisbon Portugal Univ Lisbon Fac Ciencias Ctr Matemat Aplicacoes Fundamentais & Invest Oper C6Piso 1 P-1749016 Lisbon Portugal

In this article, we address the family traveling salesman problem (FTSP), an NP-hard problem that may be seen as a generalization of the traveling salesman problem. In the FTSP, the set of cities is partitioned into several families and one wants to find the minimum cost route that visits a given number of cities in each family. We propose two metaheuristics, a population-based method and a local search method, and a hybrid algorithm, which combines a branch-and-cut algorithm with a local search procedure. All the proposed methods improve the best known upper bounds from the literature. The local search method and the hybrid algorithm improve the best known upper bounds for all the benchmark instances with unknown optimal value, while the population-based method improves the best known upper bounds for all instances, except two. Furthermore, we developed an instance generator to create additional test instances with different visit patterns. These newly generated instances were considered in the computational experiment and, thus, we provide optimal values or upper bounds for each instance. Additionally, we created a website dedicated to the FTSP, where this information is made available to the scientific community ().

关键词： family traveling salesman problem genetic algorithm local search algorithm hybrid algorithm

来源：评论

学校读者我要写书评

暂无评论

A new circle/ellipse detector using genetic algorithms

引用

PATTERN RECOGNITION LETTERS 1999年第7期20卷 731-740页

作者： Yin, PY Ming Chuan Univ Dept Informat Management Taipei 111 Taiwan

A new circle and ellipse detector is presented in this paper. The proposed method adopts a hybrid scheme which consists of a genetic algorithm (GA) phase and a local search phase. In the GA phase, an efficient fitness evaluation procedure and specific genetic operators are proposed for this application. The candidates with fitness values above a threshold are added into a candidate list. In the local search phase, the members of the candidate list are locally improved and their fitness values fall into two groups. The candidates belonging to the group with higher fitness values are output. The experimental results show that the proposed method can detect circles and ellipses correctly, and the computation and storage cost is very little. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： circle detection ellipse detection hough transform hybrid scheme genetic algorithms local search algorithm

来源：评论

学校读者我要写书评

暂无评论

Photovoltaic Output Power Fluctuations Smoothing by Selecting Optimal Capacity of Battery for a Photovoltaic-Diesel Hybrid System

引用

ELECTRIC POWER COMPONENTS AND SYSTEMS 2011年第7期39卷 621-644页

作者： Datta, Manoj Senjyu, Tomonobu Yona, Atsushi Funabashi, Toshihisa Univ Ryukyus Dept Elect & Elect Engn Nakagami Okinawa Japan Meidensha Corp Shinagawa Ku Tokyo Japan

This article explains a battery-based control method to reduce the photovoltaic output power fluctuations, which, in turn, will reduce the frequency deviations of the power system. The battery control method introduced here will maintain the state of charge near 50%. Therefore, it will increase the lifetime of the battery, as well as decreasing the maintenance cost. A local search algorithm is provided with this battery control method to search the optimal capacity of the battery required for smoothing the photovoltaic output power fluctuations. Then, a cost comparison is provided to realize the performance of the search algorithm. To verify the effectiveness of the proposed method, simulation results are presented using the actual insolation and load data.

关键词： photovoltaic power fluctuation optimal capacity of battery frequency deviation reduction local search algorithm

来源：评论

学校读者我要写书评

暂无评论

A PAM approach to handling disruptions in real-time vehicle routing problems

引用

DECISION SUPPORT SYSTEMS 2013年第3期54卷 1380-1393页

作者： Hu, Xiangpei Sun, Lijun Liu, Linlin Dalian Univ Technol Sch Management & Econ Inst Syst Engn Dalian 116023 Liaoning Provin Peoples R China

During the urban distribution process, unexpected events may frequently result in disruptions to the current distribution plan, which need to be handled in real-time vehicle routing. In this paper, a knowledge-based modeling approach, PAM (disruption-handling Policies, local search algorithms and object-oriented Modeling), is developed, which combines the scheduling knowledge of experienced schedulers with the optimization knowledge concerning models and algorithms in the field of Operations Research to obtain an effective solution in real time. Experienced schedulers can respond to different disruptions promptly with heuristic adjustment based on their experience, but their solutions may be inaccurate, inconsistent, or even infeasible. This method is limited when the problem becomes large-scale. The model-algorithm method can handle large-scale problems, but it has to predefine a specific disruption and a specific distribution state for constructing a model and algorithm, which is inflexible, time-consuming and consequently unable to promptly obtain solutions for responding to different disruptions in real time. PAM modeling approach combines the advantages and eliminates the disadvantages of the two methods aforementioned. Computational experiments show that solutions achieved by this modeling approach are practical and the speed of achieving the solutions is fast enough for responding to disruptions in real time. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Knowledge representation Object-oriented modeling local search algorithm Disruption Real-time Vehicle Routing Problem (RVRP)

来源：评论

学校读者我要写书评

暂无评论

Clustering of search trajectory and its application to parameter tuning

引用

JOURNAL OF THE OPERATIONAL REsearch SOCIETY 2013年第12期64卷 1742-1752页

作者： Lindawati Lau, H. C. Lo, D. Singapore Management Univ Singapore 178902 Singapore

This paper is concerned with automated classification of Combinatorial Optimization Problem instances for instance-specific parameter tuning purpose. We propose the CluPaTra Framework, a generic approach to CLUster instances based on similar PAtterns according to search TRAjectories and apply it on parameter tuning. The key idea is to use the search trajectory as a generic feature for clustering problem instances. The advantage of using search trajectory is that it can be obtained from any local-search based algorithm with small additional computation time. We explore and compare two different search trajectory representations, two sequence alignment techniques (to calculate similarities) as well as two well-known clustering methods. We report experiment results on two classical problems: Travelling Salesman Problem and Quadratic Assignment Problem and industrial case study.

关键词： generic feature search trajectory instance-based automated parameter tuning sequence alignment local search algorithm

来源：评论

学校读者我要写书评

暂无评论

Attractive force search algorithm for piecewise convex maximization problems

引用

OPTIMIZATION LETTERS 2012年第7期6卷 1317-1333页

作者： Fortin, Dominique Tseveendorj, Ider Univ Versailles Lab PRiSM F-78035 Versailles France INRIA F-78153 Le Chesnay France

We consider mathematical programming problems with the so-called piecewise convex objective functions. A solution method for this interesting and important class of nonconvex problems is presented. This method is based on Newton's law of universal gravitation, multicriteria optimization and Helly's theorem on convex bodies. Numerical experiments using well known classes of test problems on piecewise convex maximization, convex maximization as well as the maximum clique problem show the efficiency of the approach.

关键词： Global search algorithm local search algorithm Nonconvex optimization Convex maximization Piecewise convex maximization

来源：评论

学校读者我要写书评

暂无评论

Piece adding technique for convex maximization problems

引用

JOURNAL OF GLOBAL OPTIMIZATION 2010年第4期48卷 583-593页

作者： Fortin, Dominique Tseveendorj, Ider Univ Versailles Lab PRiSM F-78035 Versailles France INRIA F-78153 Le Chesnay France

In this article we provide an algorithm, where to escape from a local maximum y of convex function f over D, we (locally) solve piecewise convex maximization max{min{f (x) - f (y), p (y) (x)} | x is an element of D} with an additional convex function p (y) (center dot). The last problem can be seen as a strictly convex improvement of the standard cutting plane technique for convex maximization. We report some computational results, that show the algorithm efficiency.

关键词： Global search algorithm local search algorithm Nonconvex optimization Convex maximization Piecewise convex maximization

来源：评论

学校读者我要写书评

暂无评论

Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem: Scalable algorithms and Performance Guarantees

引用

OPERATIONS REsearch 2024年第2期72卷 493页

作者： Li, Yongchun Xie, Weijun Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta 30332 Georgia

This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to develop a sampling algorithm and derive its approximation bound for MESP, which improves the best known bound in literature. We then provide an efficient deterministic implementation of the sampling algorithm with the same approximation bound. Besides, we investigate the widely used local search algorithm and prove its first known approximation bound for MESP. The proof techniques further inspire for us an efficient implementation of the local search algorithm. Our numerical experiments demonstrate that these approximation algorithms can efficiently solve medium-size and large-scale instances to near optimality. Finally, we extend the analyses to the A-optimal MESP, for which the objective is to minimize the trace of the inverse of the selected principal submatrix.

关键词： maximum entropy sampling problem convex integer program sampling algorithm local search algorithm A-optimality

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：