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

Mathematical models and an effective exact algorithm for unrelated parallel machine scheduling with family setup times and machine cost

引用

OR SPECTRUM 2025年第1期47卷 129-176页

作者： Li, Kai Xie, Fulong Chen, Jianfu Xiao, Wei Zhou, Tao Hefei Univ Technol Sch Management Hefei 230009 Peoples R China Minist Educ Key Lab Proc Optimizat & Intelligent Decis Making Hefei 230009 Peoples R China Hohai Univ Business Sch Nanjing 211100 Peoples R China

This paper investigates unrelated parallel machine scheduling problems, considering machine- and sequence-dependent family setup times and machine usage costs to minimise the sum of the total weighted completion time and the total machine usage cost. The machine usage cost consists of a fixed cost and a variable cost proportional to the processing times of jobs. These features align with numerous real-world applications that include machine usage costs, for example, rental fees when customers rent machines via a cloud manufacturing platform. To address the problem, five integer programming models are developed from different perspectives. Afterwards, a modified branch-and-price algorithm (B&P) based on the set-partitioning model is proposed. To enhance the performance of B&P, we introduce two dynamic programming algorithms and a heuristic pricing algorithm, and the initial solution is generated by an improved variable neighbourhood search algorithm. Extensive experimental results show that the proposed B&P outperforms state-of-the-art mathematical models and algorithms. Notably, B&P can optimally solve instances with up to 10 machines, 100 jobs, and 12 families within half an hour. Interestingly, experimental results also show that the B&P performs significantly better when total completion time is dominated by the total variable cost of machine usage.

关键词： Scheduling Unrelated parallel machines Family setup times Machine cost branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price Framework for Decomposing Graphs into Relaxed Cliques

引用

INFORMS JOURNAL ON COMPUTING 2021年第3期33卷 1070-1090页

作者： Gschwind, Timo Irnich, Stefan Furini, Fabio Calvo, Roberto Wolfler Johannes Gutenberg Univ Mainz Gutenberg Sch Management & Econ Dept Logist Management D-55122 Mainz Germany Tech Univ Kaiserslautern Dept Business Studies & Econ Chair Logist D-67663 Kaiserslautern Germany Consiglio Naziona Ric IASI CNR Ist Anal Sistemi Informat Antonio Ruberti I-00185 Rome Italy Univ Sorbonne Paris Nord LIPN CNRS UMR 7030 F-93430 Villetaneuse France Univ Cagliari Dept Math & Comp Sci I-09124 Cagliari Italy

We study the family of problems of partitioning and covering a graph into/with a minimum number of relaxed cliques. Relaxed cliques are subsets of vertices of a graph for which a clique-defining property-for example, the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices-is relaxed. These graph partitioning and covering problems have important applications in many areas such as social network analysis, biology, and disease-spread prevention. We propose a unified framework based on branch-and-price techniques to compute optimal decompositions. For this purpose, new, effective pricing algorithms are developed, and new branching schemes are invented. In extensive computational studies, we compare several algorithmic designs, such as structure-preserving versus dichotomous branching, and their interplay with different pricing algorithms. The final chosen branch-and-price setup produces results that demonstrate the effectiveness of all components of the newly developed framework and the validity of our approach when applied to social network instances.

关键词： graph decomposition clique relaxations branch-and-price algorithm social networks

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price approach for the partition coloring problem

引用

OPERATIONS RESEARCH LETTERS 2011年第2期39卷 132-137页

作者： Hoshino, Edna A. Frota, Yuri A. de Souza, Cid C. Univ Estadual Campinas Inst Comp BR-13083852 Campinas SP Brazil Univ Fed Mato Grosso do Sul Fac Comp Campo Grande Brazil Univ Fed Fluminense Dept Comp Sci Niteroi RJ Brazil

This work proposes a new integer programming model for the partition coloring problem and a branch-and-price algorithm to solve it. Experiments are reported for random graphs and instances originating from routing and wavelength assignment problems arising in telecommunication network design. We show that our method largely outperforms previously existing approaches. (c) 2011 Elsevier B.V. All rights reserved.

关键词： Graph coloring Integer programming Column generation branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price approach for trip sequence planning of high-speed train units

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2020年第0期92卷 102150-000页

作者： Gao, Yuan Schmidt, Marie Yang, Lixing Gao, Ziyou Beijing Inst Technol Sch Management & Econ Beijing 100081 Peoples R China Erasmus Univ Rotterdam Sch Management NL-3000 DR Rotterdam Netherlands Beijing Jiaotong Univ State Key Lab Rail Traff Control & Safety Beijing 100044 Peoples R China

In high-speed railway operations, a trip sequence plan is made once the timetable is determined, and serves as a reference in the subsequent operations of train units scheduling. In light of the maintenance requirements of train units and periodicity characteristics of trip sequences, we introduce a trip sequence graph to describe the train units' movement and coupling/splitting in a railway network. Based on the trip sequence graph, two integer linear programming models are then formulated, namely a path-based model and an arc-based model. Integrated with the characteristics of the trip sequence graph, a customized branch-and-price algorithm is developed to solve the path-based model. The two models are applied to the high-speed railway network in eastern China, and through numerical experiments, the effectiveness and applicability of the models are discussed. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Train units scheduling Trip sequence planning Maintenance High-speed railway branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price method for a two-echelon location routing problem with recommended satellites

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2023年 184卷

作者： Tian, Xi-Dan Hu, Zhi-Hua Shanghai Maritime Univ Logist Res Ctr Shanghai 200135 Peoples R China

In city logistics, the two-echelon location routing problem is crucial in coordinating resources and radiating nodes, enabling the efficient planning of relay stations and vehicle distribution routes. However, with the expansion of distribution scopes and changes in urban development, fixed relay stations may not be able to adapt to the evolving network demand structure, leading to reduced efficiency. This paper proposes a two-echelon location routing problem with recommended satellites (2E-LRPRS) to address this issue. These satellites are chosen from the customer set and can be reoptimized to enhance the network's adaptability. A mixed-integer linear program (MILP) is formulated to minimize the distribution cost of the two-echelon network. To solve this problem, a column-generation algorithm (CG) is proposed, which decomposes the original problem into a linear relaxation main problem and a series of two-stage shortest-path subproblems with resource constraints. The branch-and-pricing algorithm (B&P) is then designed to obtain the integer solution. The experimental results demonstrate that the proposed B&P is significantly more efficient and effective than the MILP solver - Cplex. Furthermore, by selecting relay stations from customers, the recommended satellites can be flexibly adjusted based on the locations and demands of distribution customers, leading to an average operating cost savings of 8.43%.

关键词： Logistics Two-echelon location routing problem Recommended satellites Column generation branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

A column-generation matheuristic approach for optimizing first-mile ridesharing services with publicly- and privately-owned autonomous vehicles

引用

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES 2024年 160卷

作者： He, Ping Jin, Jian Gang Trepanier, Martin Schulte, Frederik Shanghai Jiao Tong Univ Sch Naval Architecture Ocean & Civil Engn Shanghai Peoples R China Shanghai Jiao Tong Univ Key Lab Marine Intelligent Equipment & Syst Minist Educ Shanghai Peoples R China Interuniv Res Ctr Enterprise Networks Logist & Tra Montreal PQ Canada Polytech Montreal Dept Math & Ind Engn Montreal PQ Canada Delft Univ Technol Fac Mech Maritime & Mat Engn Delft Netherlands

The burden of first -mile connection to public transit stations is a key barrier that discourages riders from taking public transportation. Public transit agencies typically operate a modest fleet of vehicles to provide first -mile services due to the high operating costs, thus failing to adequately meet the first -mile travel demands, especially during peak hours. At the same time, private cars are underutilized and have a lot of idle time. With the emergence of self -driving vehicles, new opportunities for addressing the current dilemma arise, such as integrating idle private self -driving vehicles to provide first -mile services, which is beneficial for public transportation agencies to provide high -quality services at low costs. This study investigates the first -mile ridesharing problem in which public transit agencies utilize idle privately -owned autonomous vehicles to dynamically inflate their fleet. This problem is more challenging in decision -making than conventional first -mile problems, as it involves decisions on heterogeneous fleet scheduling, vehicle routing, and time scheduling, all while taking into account the service quality for riders. To address this problem, an arc -based mixed -integer linear programming (MILP) model and a trip -based set -partitioning model are developed, both aiming to minimize total operational costs. To identify promising trips, we propose a tailored labeling algorithm with a novel dominance rule, along with a time window shift algorithm to determine the best schedule. To yield high -quality solutions in a short computation time, a tailored column -generation matheuristic algorithm is introduced. A branch -and -price exact algorithm and an adaptive large neighborhood search algorithm are developed to assess the matheuristic algorithm. Numerical experiments are conducted to demonstrate the effectiveness and applicability of the proposed models and algorithms. Experiments also show that this kind of ridesharing service can

关键词： Public transportation Autonomous vehicles First-mile ridesharing branch-and-price algorithm Column-generation matheuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

Routing Optimization by Considering Multiple Uses of Vehicles and Demand Uncertainty: A Real-World Case Study

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2022年第12期23卷 24991-25003页

作者： Zhang, Li Chen, Tingting Ding, Chuan Yu, Bin Beihang Univ Sch Transportat Sci & Engn Beijing 100191 Peoples R China Beijing Jiaotong Univ Sch Traff & Transportat Beijing 100044 Peoples R China

This paper studies a novel routing optimization problem motivated by a practical application of urban corrugated box transportation. The problem involves several features originating from the practical application, such as multi-trip, demand uncertainty, and demand-dependent loading time. The robust arc-flow formulation based on the budget uncertainty set is given. Then, we have recourse to the branch-and-price algorithm to solve the problem. Specifically, the pricing subproblem is to find the robust feasible routes with several unique features, including demand uncertainty, trip duration limitation, and demand-dependent loading time. A tailored labeling algorithm with recursive resource extension functions is involved to identify the robust feasible routes. Several numerical experiments are conducted on a real-world case study and generated instances based on the real road network. The computational results indicate that the proposed algorithm is more efficient than the commercial solver, and the proposed algorithm can fit various scenarios in practical applications to generate conservative routes efficiently.

关键词： Routing optimization problem multiple uses of vehicles demand uncertainty branch-and-price algorithm robust optimization

来源：评论

学校读者我要写书评

暂无评论

Optimizing speed of a green truckload pickup and delivery routing problem with outsourcing: Heuristic and exact approaches

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2024年 198卷

作者： Zhang, Hui Huang, Min Fu, Yaping Wang, Xingwei Jiangsu Univ Sci & Technol Sch Econ & Management Zhenjiang 212003 Jiangsu Peoples R China Northeastern Univ Coll Informat Sci & Engn Shenyang 110819 Liaoning Peoples R China Qingdao Univ Sch Business Qingdao 266071 Peoples R China Northeastern Univ Coll Comp Sci & Engn Shenyang 110169 Liaoning Peoples R China

Optimizing fuel consumption cost alongside truck speed decisions is crucial for transportation enterprises when making outsourcing decisions. However, existing research on truck fuel consumption optimization is not stateof-the-art, leading to suboptimal outsourcing outcomes. This study addresses a green truckload pickup and delivery problem with outsourcing, focusing on speed optimization and fuel consumption cost. We model the problem as a multi-attribute directed graph and propose an arc-based mixed-integer programming model and a set-partitioning binary programming model. We then analyze the monotonic properties of arc cost, simplify the set-partitioning model, and develop a mixed-integer programming-based heuristic, a branch-and- price algorithm, and a column-generation-based heuristic. To tackle the challenge of speed decisions in fuel consumption optimization, we design specific extension and dominance rules within a labeling algorithm. All algorithms are tested on several sets of instances. Numerical experiments demonstrate the effectiveness of the proposed models and algorithms.

关键词： Green vehicle routing problem Optimizing speed Green truckload pickup and delivery routing problem with outsourcing Fuel consumption Heuristic branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the Partition Coloring Problem

引用

COMPUTERS & OPERATIONS RESEARCH 2018年 92卷 170-181页

作者： Furini, Fabio Malaguti, Enrico Santini, Alberto PSL Res Univ Univ Paris Dauphine CNRS F-75016 Paris France Univ Bologna DEI I-40136 Bologna Italy Univ Pompeu Fabra Dept Econ & Empresa Barcelona Spain Barcelona GSE Barcelona Spain

We study the Partition Coloring Problem (PCP), a generalization of the Vertex Coloring Problem where the vertex set is partitioned. The PCP asks to select one vertex for each subset of the partition in such a way that the chromatic number of the induced graph is minimum. We propose a new Integer Linear Programming formulation with an exponential number of variables. To solve this formulation to optimality, we design an effective branch-and-price algorithm. Good quality initial solutions are computed via a new metaheuristic algorithm based on adaptive large neighborhood search. Extensive computational experiments on a benchmark test of instances from the literature show that our branch-and-price algorithm, combined with the new metaheuristic algorithm, is able to solve for the first time to proven optimality several open instances, and compares favorably with the current state-of-the-art exact algorithm. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Vertex Coloring Partitioning coloring Selective coloring Column generation branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

Flexible Districting Policy for the Multiperiod Emergency Resource Allocation Problem With Demand Priority

引用

IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS 2024年第11期54卷 6977-6988页

作者： Xu, Xiaofeng Lin, Ziru Li, Xiang Yi, Wanli Pedrycz, Witold China Univ Petr Sch Econ & Management Qingdao 266580 Shandong Peoples R China Changan Univ Sch Econ & Management Xian 710064 Shaanxi Peoples R China Kunlun Digital Technol Co Ltd Dept Prod Serv Beijing 100007 Peoples R China Univ Alberta Dept Elect & Engn Edmonton AB T6R 2V4 Canada Polish Acad Sci Syst Res Inst PL-01447 Warsaw Poland

To address responsiveness, time-dependence, and limited emergency supply issues, we introduce a new flexible districting policy, aiming to improve satisfaction in multiperiod emergency resource allocation (MPERA), and set demand priorities to guarantee allocation balance in resource-limited scenarios. The modeling and solution process involves the following: 1) formulating a mixed-integer programming (MILP) model for MPERA with demand priority (MPERA-DP), aiming to maximize utility considering the transportation cost, districting change, and penalty for unsatisfied demand and 2) incorporating the justifiable granularity principle (JGP) and particle swarm optimization (PSO) into the brand-and-price (B&P) algorithm for initial districting and allocating decisions to improve the solution quality and calculation speed. The results of the experiments show that 1) the JGP-PSO-B&P algorithm achieves superior efficiency in terms of optimality and convergence for large-scale cases. This algorithm could improve the optimality by 13.42% compared with that of the JGP-PSO algorithm, 13.15% compared with that of the B&P algorithm, and 28.18% compared with that of the PSO algorithm, on average;2) the MPERA-DP model with flexible districting policy outperforms flexible MPERA without demand priority, emergency resource allocation with rescheduling (ERAR) and fixed emergency resource allocation with demand priority (FERA-DP), improving the utility by 20.56%, 5.14% and 41.84%, respectively;and 3) the scheme efficiency is influenced by the desirable satisfaction deviation, and when set to 0.6, it allows for the optimization of both demand satisfaction and utility.

关键词： Resource management Costs Optimization Heuristic algorithms Convergence Transportation Classification algorithms branch-and-price algorithm emergency management flexible districting policy justifiable granularity principle (JGP) resource allocation problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：