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

A branch-and-price algorithm for the Urban Aerial Delivery Problem With Energy Constraints

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2025年 22卷 13269-13285页

作者： Pei, Zhi Liang, Zhaohui Huang, Jiayan Fang, Tao Li, Na Zhejiang Univ Technol Coll Mech Engn Hangzhou 310014 Peoples R China Shanghai Jiao Tong Univ Dept Ind Engn & Management Shanghai 200240 Peoples R China

In this paper, an urban aerial delivery problem (UADP) is investigated, where the parcel transportation service is accomplished by drones in an urban setting. The aim of the problem is to minimize the total service completion time, by taking into account of the flow balance, the energy consumption, and the response time window. To fully explore the structure of the UADP, a mixed integer linear programming (MILP) model is constructed based on an arc-flow scheme. However, directly handling the UADP with commercial solvers is time consuming. In order to enhance the responsiveness of urban courier services and speed up the solving process, a set-covering model (UADP-SC) is proposed with a linear programming based relaxation. Then a branch-and-price algorithm is designed with pricing accelerating strategies based on heuristics. The computational experiments show that the proposed branch-and-price algorithm outperforms the off-the-shelf commercial solvers in terms of computation efficiency. In the mean time, the proposed algorithm can also serve to obtain optimal battery swapping and path planing decisions in face of the large-scale urban aerial delivery problem with energy constraints.

关键词： Drones Batteries Logistics Routing Heuristic algorithms Computational modeling Approximation algorithms Automation Urban areas Energy consumption Drone-based logistics mixed integer programming battery swapping branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

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 two-echelon electric vehicle routing problem

引用

COMPLEX & INTELLIGENT SYSTEMS 2023年第3期9卷 2475-2490页

作者： Wu, Zhiguo Zhang, Juliang Beijing Jiaotong Univ Sch Econ & Management Beijing Peoples R China

Motivated by express and e-commerce companies' distribution practices, we study a two-echelon electric vehicle routing problem. In this problem, fuel-powered vehicles are used to transport goods from a depot to intermediate facilities (satellites) in the first echelon, whereas electric vehicles, which have limited driving ranges and need to be recharged at recharging stations, are used to transfer goods from the satellites to customers in the second echelon. We model the problem as an arc flow model and decompose the model into a master problem and pricing subproblem. We propose a branch-and-price algorithm to solve it. We use column generation to solve the restricted master problem to provide lower bounds. By enumerating all the subsets of the satellites, we generate feasible columns by solving the elementary shortest path problem with resource constraints in the first echelon. Then, we design a bidirectional labeling algorithm to generate feasible routes in the second echelon. Comparing the performance of our proposed algorithm with that of CPLEX in solving a set of small-sized instances, we demonstrate the former's effectiveness. We further assess our algorithm in solving two sets of larger scale instances. We also examine the impacts of some model parameters on the solution.

关键词： Two-echelon Electric vehicles branch-and-price algorithm Column generation Labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

An enhanced branch-and-price algorithm for the integrated production and transportation scheduling problem

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2022年第6期60卷 1874-1889页

作者： He, Peiyang Li, Kunpeng Kumar, P. N. Ram Huazhong Univ Sci & Technol Sch Management Wuhan Peoples R China Indian Inst Management Quantitat Methods & Operat Management Area Kozhikode India

Industry 4.0 technologies, such as artificial intelligence, the internet of things and 3D printing are aiding the manufacturers by complementing their skilled workforce and transforming the way factories are run. This paper studies an integrated production and transportation scheduling problem in the context of the spare parts supply chain by integrating 3D printing with JIT delivery systems. This work aims to find a synchronised production and distribution schedule that minimises the weighted sum of delivery times and transportation costs. Based on the characteristics of the problem, we propose a new set-covering formulation. An enhanced branch-and-price algorithm is designed to solve the problem instances to optimality. To expedite the column generation process, two acceleration strategies are also used. The computational results are in favour of the proposed algorithm and the acceleration strategies. Further, the results indicate that integrating the production and transportation scheduling decisions leads to an average savings of about 16.27% of the total costs.

关键词： 3D manufacturing JIT delivery integrated production and transportation scheduling set-covering formulation branch-and-price algorithm acceleration strategy

来源：评论

学校读者我要写书评

暂无评论

An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems

引用

JOURNAL OF SCHEDULING 2022年第5期25卷 589-621页

作者： Shahvari, Omid Logendran, Rasaratnam Tavana, Madjid Univ Missouri Ind Mfg & Syst Engn Dept Columbia MO USA Oregon State Univ Sch Mech Ind & Mfg Engn Corvallis OR 97331 USA La Salle Univ Business Syst & Analyt Dept Distinguished Chair Business Analyt Philadelphia PA 19141 USA Univ Paderborn Fac Business Adm & Econ Business Informat Syst Dept D-33098 Paderborn Germany

This paper presents the problem of batching and scheduling jobs belonging to incompatible job families on unrelated-parallel machines. More specifically, we investigate cost-efficient approaches for solving batching and scheduling problems concerning the desired lower bounds on batch sizes (LBb), which indirectly has a considerable impact on the production cost. Batch scheduling is a more realistic extension of the traditional group scheduling approach, in which the jobs belonging to a job family can be processed as multiple batches. The objective is to minimize the total weighted job completion time and tardiness subject to a machine- and sequence-dependent setup time, dynamic machine availability and job release times, customer segments and job priority, and different machine capability and eligibility criteria for processing. Solving this type of batch scheduling problem is a big challenge due to the high computational complexity incurred by both the sequencing assignment and batching composition. A machine learning random forest classification algorithm is used for the LBb determination. Then, an efficient mixed-integer linear programming model (MILP) is developed based on the flow conservation constraints of jobs on machines to reduce the computational complexity. By mapping the MILP model onto a network formulation, an equivalent integer set partitioning type formulation is developed for a branch-and-price optimization algorithm. Computational experiments carried out over different sets of instances, indicate the efficiency and effectiveness of the optimization algorithm, compared to the linear relaxation and relaxed MILP models. Regarding the only available benchmark in the literature, the optimization algorithm yields optimal solutions with affordable computational time.

关键词： Batch scheduling Unrelated-parallel machines Column generation Dantzig-Wolfe decomposition branch-and-price algorithm Random forest classification

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price algorithm for the Minimum Sum Coloring Problem

引用

DISCRETE APPLIED MATHEMATICS 2021年 303卷 39-56页

作者： Delle Donne, Diego Furini, Fabio Malaguti, Enrico Calvo, Roberto Wolfler Inst Polytech Paris Ecole Polytech LIX CNRS F-91128 Palaiseau France Consiglio Nazl Ric IASI CNR Ist Anal Sistemi Informat Antonio Ruberti Rome Italy Univ Bologna DEI Viale Risorgimento 2 I-40136 Bologna Italy Univ Paris 13 LIPN CNRS UMR 7030 F-93430 Villetaneuse France Univ Cagliari Dept Math & Comp Sci Via Osped 72 I-09124 Cagliari Italy

A proper coloring of a given graph is an assignment of a positive integer number (color) to each vertex such that two adjacent vertices receive different colors. This paper studies the Minimum Sum Coloring Problem (MSCP), which asks for finding a proper coloring while minimizing the sum of the colors assigned to the vertices. We propose the first branch-and-price algorithm to solve the MSCP to proven optimality. The newly developed exact approach is based on an Integer Programming (IP) formulation with an exponential number of variables which is tackled by column generation. We present extensive computational experiments, on synthetic and benchmark DIMACS graphs from the literature, to compare the performance of our newly developed branch-and-price algorithm against three compact IP formulations. On synthetic graphs, our algorithm outperforms the compact formulations in terms of: (i) number of solved instances, (ii) running times and (iii) exit gaps obtained when optimality is not achieved. For the DIMACS instances, our algorithm is competitive with the best compact formulation and provides very strong dual bounds. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Minimum Sum Coloring Vertex Coloring Integer linear programming Column generation 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price algorithm for the multi-trip multi-repairman problem with time windows

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2018年 116卷 25-41页

作者： Liu, Shixin Qin, Shujin Zhang, Ruiyou Northeastern Univ Coll Informat Sci & Engn Shenyang 110819 Liaoning Peoples R China

This study introduces the multi-trip multi-repairman problem with time windows where an integrated traveling cost involving distance-dependent and time-dependent costs needs to be minimized. The problem is formulated as two mixed integer programming models. A branch-and-price algorithm is proposed, in which two route-generating approaches are devised to handle the pricing sub-problem. A large number of instances are randomly generated based on an actual service network of China. The proposed algorithm is validated based on these instances and compared to the direct solving method using Cplex. The comparison to the single-trip mode indicates the advantages of the multi-trip mode.

关键词： Multi-trip multi-repairman problem Integrated traveling cost Route-generating approach branch-and-price algorithm Cloud branching strategy

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：