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

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

来源：评论

学校读者我要写书评

暂无评论

branch-and-price algorithm for fuzzy integer programming problems with block angular structure

引用

FUZZY SETS AND SYSTEMS 2016年 296卷 70-96页

作者： Niksirat, Malihe Hashemi, S. Mehdi Ghatee, Mehdi Amirkabir Univ Technol Dept Comp Sci 424 Hafez Ave Tehran 158754413 Iran Amirkabir Univ Technol Intelligent Transportat Syst Res Inst Tehran Iran

This paper deals with fuzzy integer linear programming problems with block angular structure in which the fuzzy constraints are simplified by using possibility and necessity relations. This main fuzzy problem is efficiently decomposed and is solved by a branch-and-price algorithm. In the nodes of the branch-and-price tree, the linear relaxation of the problem is solved by applying a column generation method. Also, the relationship between the optimal solutions of this problem under possibility and necessity relations is derived. To show the validation of the proposed algorithm, some results are proved. In addition, the application of this algorithm is illustrated on fuzzy multicommodity flow problem. For this case, a new branching scheme is proposed to preserve the network structure of the subproblems which are produced in the column generation method. Some examples are solved and their results are compared with the previous works. Also, the results of the proposed algorithm are reported on some large-scale benchmark instances. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Fuzzy optimization branch-and-price algorithm branching rule Column generation Integer multicommodity flow problem Possibility and necessity relations

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price algorithm for the robust graph coloring problem

引用

DISCRETE APPLIED MATHEMATICS 2014年第0期165卷 49-59页

作者： Archetti, Claudia Bianchessi, Nicola Hertz, Alain Univ Brescia Dept Quantitat Methods Brescia Italy Univ Brescia Dept Informat Engn Brescia Italy Ecole Polytech Dept Math & Ind Engn Montreal PQ H3C 3A7 Canada Ecole Hautes Etud Commerciales Gerad Montreal PQ Canada

Given a graph G, an integer k, and a cost c(uv) associated with all pairs uv of non-adjacent vertices in G, the robust graph coloring problem is to assign a color in {1, ..., k} to every vertex of G so that no edge has both endpoints with the same color, and the total cost of the pairs of vertices having the same color is minimum. We propose a branch-and-price algorithm for the solution of this problem. The pricing problem consists in finding a stable set of minimum total weight, and we propose both an exact and a heuristic algorithm for its solution. Computational experiments are reported for randomly generated and benchmark graph coloring instances. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Graph coloring Robust solution branch-and-price algorithm Tabu search

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems

引用

MANAGEMENT SCIENCE 2004年第6期50卷 786-796页

作者： Lulli, G Sen, S Univ Arizona Dept Syst & Ind Engn Tucson AZ 85721 USA

In this paper, we present. a branch-and-price method to solve special structured multistage stochastic integer programming problems: We validate our method on two different versions of a multistage stochastic batchsizing problem (SBSP). One version adopts a recourse formulation, and the other is based on probabilistic constraints. Our algorithmic approach is applicable to both formulations. Our computational results suggest that both classes of problems can be solved using relatively few nodes of a branch-and-price tree. The success of our approach calls for extensions in methodology as well as applications.

关键词： stochastic programming integer programming batch sizing branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

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 Multivehicle Covering Tour Problem

引用

NETWORKS 2014年第3期64卷 160-168页

作者： Jozefowiez, Nicolas CNRS LAAS F-31400 Toulouse France Univ Toulouse INSA LAAS F-31400 Toulouse France

This article proposes a mathematical model and a branch-and-price algorithm for the multivehicle covering tour problem. This problem consists in finding a set of routes on a weighted graph such that a set of nodes that cannot be visited is covered. A node is covered if it lies within a predefined distance of a visited node. The subproblem encountered during the column generation is a variant of the profitable tour problem. It is reduced to a ring star problem and a branch-and-cut algorithm is developed. Computational results are reported on randomly generated instances. (c) 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(3), 160-168 2014

关键词： vehicle routing problem covering tour problem integer programming column generation branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

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 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：