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

A branch-and-price algorithm for placement routing for a multi-head beam-type component placement tool

OR SPECTRUM 2008年第3期30卷 515-534页

作者： Sun, Dong-Seok Lee, Tae-Eog Korea Adv Inst Sci & Technol Dept Ind Engn Taejon 305701 South Korea Samsung Elect Syst Engn Team Taean Eup Hwasung City Geonggi Do South Korea

We develop a branch-and-price procedure for a placement routing problem for a multi-head beam-type component placement tool. The problem is modelled as an integer programming model with a huge number of variables, each of which corresponds to a placement route. Its linear programming relaxation is solved by a column generation method. For the column generation subproblem to determine the columns to be added, we develop a dynamic programming procedure. We also propose an effective branching rule to partition the current solution space to eliminate the current fractional solution. Through experiments using real tool data, we observe that the LP relaxation solution value is noticeably close to an integer optimal solution value and hence the integer program formulation and the column generation approach are effective.

关键词： component placement tool placement routing column generation branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

Research on Train Formation Plan Optimization in Railway Network Based on branch-and-price algorithm 6

Research on Train Formation Plan Optimization in Railway Net...

引用

6th International Conference on Behavioral, Economic and Socio-Cultural Computing (BESC)

作者： Xiao, Wei Yue, Yixiang Chen, Feng Beijing Jiaotong Univ Sch Traff & Transportat Beijing Peoples R China China Acad Railway Sci Corp Ltd Signal & Commun Res Inst Beijing Peoples R China

ISBN: (纸本)9781728147628

Freight train formation plan is the basic technical document of railway freight transport organization, it decides the efficiency of railway freight transport. In this paper, we introduce the train formation plan optimization problem in railway network. Then we propose the 0-1 integrated optimization model with the object function to minimize the sum of accumulation time, running time and transit time. According to the characteristics of the model, an improved solution algorithm is designed based on the branch-and-price algorithm. The algorithm is programmed in C# language to solve the model. Finally, the computation results on a case study of simplified China's railway network with 14 large marshalling stations demonstrate the effectiveness and feasibility of the proposed optimization method, which shows the application on the actual railway engineering industry.

关键词： railway network train formation plan car flow organization column generation algorithm branch-and-price algorithm optimization

来源：评论

学校读者我要写书评

暂无评论

On the Design of Complex Networks through a branch-and-price algorithm

On the Design of Complex Networks through a Branch-and-Price...

引用

Globecom Workshops

作者： Souza, Fernanda S. H. Cunha, Alexandre S. Mateus, Geraldo R. Univ Fed Minas Gerais Dept Comp Sci Belo Horizonte MG Brazil

ISBN: (纸本)9781424488650

In this paper, we present a branch-and-price algorithm for solving the Optimal Topology Design Problem of complex networks, based on a tightened deterministic formulation for the problem. The algorithm, which incorporates a delayed column generation approach within a branch-and-bound framework, was proven to work well, being capable of finding optimal topologies within very low computational times, for networks with up to 6 0 nodes and different budget ranges. The algorithm allowed us to conclude that, by modifying the budget size values in our optimization model, different network features are found in optimal solutions. Accordingly, the budget size plays a similar role played by the probability of addition or rewiring arcs in randomized procedures for generating network topologies.

关键词： branch-and-price algorithm complex network design delayed column generation approach optimal topology design problem optimisation optimization model probability probability telecommunication network topology tightened deterministic formulation

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price algorithm for the temporal bin packing problem

引用

COMPUTERS & OPERATIONS RESEARCH 2020年 114卷 104825-000页

作者： Dell'Amico, Mauro Furini, Fabio Iori, Manuel Univ Modena & Reggio Emilia DISMI Via Amendola 2 I-42122 Reggio Emilia Italy PSL Res Univ Univ Paris Dauphine LAMSADE F-75016 Paris France

We study an extension of the classical Bin Packing Problem, where each item consumes the bin capacity during a given time window that depends on the item itself. The problem asks for finding the minimum number of bins to pack all the items while respecting the bin capacity at any time instant. A polynomial-size formulation, an exponential-size formulation, and a number of lower and upper bounds are studied. A branch-and-price algorithm for solving the exponential-size formulation is introduced. An overall algorithm combining the different methods is then proposed and tested through extensive computational experiments. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Bin packing problem branch-and-price algorithm Temporal bin packing problem

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems

引用

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2024年 183卷

作者： Feng, Tao Lusby, Richard M. Zhang, Yongxiang Tao, Siyu Zhang, Bojian Peng, Qiyuan Southwest Jiaotong Univ Sch Transportat & Logist Natl United Engn Lab Integrated & Intelligent Tran Natl Engn Lab Integrated Transportat Big Data Appl Chengdu 610031 Peoples R China Tech Univ Denmark Dept Technol Management & Econ DK-2800 Lyngby Denmark

Crew planning, involving how to best schedule crew members during a given period, is a significant problem for urban rail transit companies. This paper proposes a new integer linear programming (ILP) model that can simultaneously optimize urban rail crew scheduling and rostering problems. The proposed ILP model is a set partitioning-based model with only one type of important duty selection variable that connects the two-level problem and circumvents the drawbacks of conventional approaches that usually formulate the crew scheduling and rostering problems separately and couple these two problems through linking constraints. This study demonstrates that the structure of the underlying network used to model the problem enables the development of an effective, heuristic branch-and-price procedure. The study compares the proposed approach with two other decomposition methods, namely Lagrangian relaxation and alternating direction method of multipliers (ADMM), on problems of different sizes and shows that the method provides lower bounds that are on average 16.4% better than Lagrangian relaxation and 5.03% better than ADMM, respectively. Furthermore, the study shows that, with an average optimality gap of 3.28%, the proposed approach obtains high-quality integer solutions to the integrated problem.

关键词： Urban rail transit Crew scheduling and rostering problems Integrated optimization branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price algorithm for the robust single-source capacitated facility location problem under demand uncertainty

引用

EURO JOURNAL ON TRANSPORTATION AND LOGISTICS 2022年 11卷

作者： Ryu, Jaehyeon Park, Sungsoo Korea Adv Inst Sci & Technol Dept Ind & Syst Engn 291 Daehak Ro Daejeon 34141 South Korea Korea Adv Inst Sci & Technol Daejeon South Korea

We consider the robust single-source capacitated facility location problem with uncertainty in customer demands. A cardinality-constrained uncertainty set is assumed for the robust problem. To solve it efficiently, we propose an allocation-based formulation derived by Dantzig-Wolfe decomposition and a branch-and-price algorithm. The computational experiments show that our branch-and-price algorithm outperforms CPLEX in many cases, which solves the ordinary robust reformulation. We also examine the trade-off relationship between the empirical probability of infeasibility and the additional costs incurred and observe that the robustness of solutions can be improved significantly with small additional costs.

关键词： Robust optimization Demand uncertainty Dantzig-Wolfe decomposition branch-and-price algorithm Single-source capacitated facility location problem

来源：评论

学校读者我要写书评

暂无评论

Parallel branch-and-price algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times

引用

COMPUTERS & OPERATIONS RESEARCH 2025年 173卷

作者： Speckenmeyer, Philipp Hilmer, Constanze Rauchecker, Gerhard Schryen, Guido Warburger Str 100 D-33098 Paderborn Germany Unaffiliated Munich Germany Unaffiliated Passau Germany

Scheduling problems occur in a broad range of real-world application fields and have attracted a huge set of research articles. However, there is only little research on exact algorithms for scheduling problems, many of which are NP-hard in the strong sense. We investigate the problem on a single machine with a total weighted tardiness objective function and sequence-dependent setup times. First, we adopt a serial branch-and-price algorithm from the literature and present a modified branching strategy and a primal heuristic. Second, we use the potential of parallel computing architectures by presenting two parallel versions of the branch- and-price algorithm. Third, we conduct extensive computational experiments to show that our parallelization approaches provide substantial parallel speedups on well-known benchmark instances from the literature. We further observe that the parallel speedups achieved by our parallel algorithms are very robust among all tested instances.

关键词： Single machine scheduling Weighted tardiness Sequence-dependent setup times branch-and-price algorithm Dynamic programming Shared-memory parallelization

来源：评论

学校读者我要写书评

暂无评论

Resilience enhancement of multi-modal public transportation system via electric bus network redesign

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2025年 193卷

作者： Liu, Zhongshan Yu, Bin Zhang, Li Sun, Yuxuan Beihang Univ Sch Transportat Sci & Engn Beijing 100191 Peoples R China Beihang Univ Key Lab Intelligent Transportat Technol & Syst Minist Educ Beijing 100191 Peoples R China Natl Univ Singapore Dept Civil & Environm Engn Singapore 117576 Singapore

The multi-modal public transportation system incorporating the electric bus network and the metro network plays a crucial role in meeting the daily transportation demands in urban areas. However, the inadequate connectivity between the electric bus network and the metro network has resulted in poor resilience of the multi-modal public transportation system. When disruptions occur at metro links or metro stations, stranded passengers cannot be rapidly evacuated through bus lines. Therefore, operators need to redesign the multi-modal public transportation system to enhance the integration between the electric bus network and the metro network. Since it is challenging to modify the fixed metro network, we thus focus on introducing redesign plans for the electric bus network, enabling the multi-modal public transportation system to exhibit the desired resilience in scenarios of disruptions. This paper proposes a two-level framework integrating electric bus network redesign at the tactical level and resource deployment at the planning level. For the redesign problem at the tactical level, this paper designs a tailored branch-andprice algorithm to generate high-quality redesign solutions for the electric bus network. For the resource deployment problem at the planning level, this paper determines the locations of charging facilities and the number of electric buses based on the redesigned electric bus network, considering uncertain passenger demands and metro capacities. We propose a two-layer robust optimization model for the resource deployment problem and develop a tailored column-andconstraint generation algorithm to solve it. Finally, this paper tests the performance of the developed models and algorithms on a set of instances in Beijing. The impact of the uncertainty budget, the number of electric buses, bus capacity, and charging time of electric buses on the system performance is discussed.

关键词： Multi-modal public transportation system Electric bus network Redesign plans Resilience improvement branch-and-price algorithm Column-and-constraint generation

来源：评论

学校读者我要写书评

暂无评论

Solving capacitated vehicle routing problem with three-dimensional loading and relocation constraints

引用

COMPUTERS & OPERATIONS RESEARCH 2025年 173卷

作者： Chi, Jushang He, Shiwei Song, Rui Beijing Jiaotong Univ Frontiers Sci Ctr Smart High speed Railway Syst Beijing Peoples R China

In capacitated vehicle routing problem with three-dimensional loading constraints (3L-CVRP) that combines the container loading and capacitated vehicle routing problems, the relationship between vehicle visiting sequence and item loading sequence is reflected through relocation-ban constraint. This widely applied constraint prohibits the temporarily unloading and repositioning of loaded items during the entire transportation process, simplifying loading operations but also limiting the volume utilization of each vehicle and increasing transportation costs. To address this issue and obtain a trade-off between transportation cost and operational complexity (reflected in relocation cost), two improved relocation constraints that seek to allow necessary and restricted relocations are developed in this study. Under pickup scenario, a mixed integer-linear programming model is developed to describe the 3L-CVRP with the relocation constraints. An improved branch-and-price algorithm is employed to solve the model. Two loading algorithms, incorporated with a backward dynamic programming method, are proposed to simultaneously generate loading and relocation plans. Enhancement strategies, including an improved label-correcting-based algorithm and memory components that collect loading feasibility and relocation cost information, are developed. Numerical experiments were designed to test the performance of the proposed algorithms and validate the significance of necessary relocations. In pure loading instances, necessary relocations bring an increase in volume utilization by 3.75 % on average and 36.48 % at maximum. In large-scale benchmark instances, allowing necessary relocations decrease the overall costs by 4.86 % on average and 13.08 % at maximum. Abbreviations: 3L-CVRP, capacitated vehicle routing problem with three-dimensional loading constraints;CLP, container loading problem;CVRP, capacitated vehicle routing problem;RC, relocation constraints;MILP, mixed integer linear

关键词： Transportation Three-dimensional loading Relocation Backward dynamic programming branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

Scheduling and dynamic charging optimizations for electric buses with time-varying electricity tariffs

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2025年 204卷

作者： Feng, Dejian Dong, Ming Dong, Jiaqi Shanghai Jiao Tong Univ Antai Coll Econ & Management Shanghai 200030 Peoples R China Jinan Univ Univ Birmingham & Jinan Univ Joint Inst Guangzhou 511400 Peoples R China

With the rapidly increasing popularity of electric buses (EBs), their scheduling and charging decisions have become an important issue. This paper proposes a novel approach to simultaneously optimize scheduling and dynamic charging problems for EBs considering a nonlinear charging function, time-varying electricity tariffs, stochastic energy consumption, and other realistic conditions concurrently. The framework comprises a set partitioning master problem for selecting scheduling plans and a stochastic dynamic programming subproblem for generating scheduling plans and charging policies. An efficient branch-and-price algorithm is then proposed to solve the problem of interest, and several acceleration subalgorithms are designed. Finally, the effectiveness and efficiency of the proposed method are verified through numerical experiments. The results show that the proposed method can accurately and quickly obtain near-optimal solutions for realistic scale problems, thereby providing a certain decision reference for the operation and management of EB companies.

关键词： Scheduling Dynamic charging Electric buses Nonlinear charging Time-varying electricity tariffs branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：