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

The Multiple Steiner TSP with order constraints: complexity and optimization algorithms

SOFT COMPUTING 2020年第23期24卷 17957-17968页

作者： Gabrel, Virginie Mahjoub, A. Ridha Taktak, Raouia Uchoa, Eduardo PSL Res Univ Univ Paris Dauphine CNRS LAMSADE F-75016 Paris France Univ Sfax CRNS ISIMS Sfax Tunisia Univ Sfax CRNS LT2S Sfax Tunisia Univ Fed Fluminense Dept Engn Prod Niteroi RJ Brazil

We consider a variant of the Travelling Salesman Problem (TSP), the Multiple Steiner TSP with Order constraints (MSTSPO). Consider a weighted undirected graph and a set of salesmen, and each salesman is associated with a set of compulsory vertices to visit, called terminals. The MSTSPO consists in finding a minimum-cost subgraph containing for each salesman a tour going in a specified order through its terminals. Along with its importance from a theoretical point of view, the problem is also challenging in practice since it has applications in telecommunication networks. We show that the problem is NP-hard even for a single salesman and propose integer programming formulations. We then devise both branch-and-cut and branch-and-Price algorithms to solve the problem. The extensive computational results are presented, showing the efficiency of our algorithms.

关键词： Steiner TSP Order constraints Integer linear programming branch-and-Price algorithm branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

On integer and bilevel formulations for the k-vertex cut problem

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2020年第2期12卷 133-164页

作者： Furini, Fabio Ljubic, Ivana Malaguti, Enrico Paronuzzi, Paolo Univ Paris 09 LAMSADE Paris France ESSEC Business Sch Paris Cergy France Univ Bologna DEI Bologna Italy

The family of critical node detection problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the k-vertex cut problem. The problem asks for determining the minimum weight subset of nodes whose removal disconnects a graph into at least k components. We provide two new integer linear programming formulations, along with families of strengthening valid inequalities. Both models involve an exponential number of constraints for which we provide poly-time separation procedures and design the respective branch-and-cut algorithms. In the first formulation one representative vertex is chosen for each of the k mutually disconnected vertex subsets of the remaining graph. In the second formulation, the model is derived from the perspective of a two-phase Stackelberg game in which a leader deletes the vertices in the first phase, and in the second phase a follower builds connected components in the remaining graph. Our computational study demonstrates that a hybrid model in which valid inequalities of both formulations are combined significantly outperforms the state-of-the-art exact methods from the literature.

关键词： Vertex cut Mixed-integer linear programming Bilevel programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A new formulation for the Weighted Safe Set Problem

引用

Procedia Computer Science 2021年 195卷 508-515页

作者： Enrico Malaguti Vagner Pedrotti Dipartimento di Ingegneria dell’Energia Elettrica e dell’Informazione “Guglielmo Marconi” Università di Bologna. Bologna Italy Faculty of Computing Federal University of Mato Grosso do Sul. Campo Grande Brazil

Given a connected graph G = ( V, E ), a Safe Set S is a subset of the vertex set V such that the cardinality of each connected component in the subgraph induced by V \ S does not exceed the cardinality of any connected component in the subgraph induced by S , whenever there is an edge in G between vertices of the two components. When the vertices of G are weighted, the weight of a component is defined as the sum of the weights of its vertices, and the notion of safe set is extended by considering the weight of connected components in subgraphs induced by S and by V \ S . We propose an integer linear formulation for the Weighted Safe Set Problem that uses only one variable per vertex. The formulation has an exponential number of constraints, which can be generated on-the-fly within a branch-and-cut algorithm. We describe a linear-time separation algorithm for these constraints. In addition, we describe families of cuts based on cliques and on minimum weight cut separators, and discuss separation algorithms. A branch-and-cut algorithm that solves the proposed formulation is computationally compared with two alternative formulations from the literature, and shows faster in solving most of benchmark instances with low edge density.

关键词： Safe Set Problem Weighted Safe Set Problem branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A new formulation for the Safe Set problem on graphs

引用

COMPUTERS & OPERATIONS RESEARCH 2019年 111卷 346-356页

作者： Uzeda Macambira, Ana Flavia Simonetti, Luidi Barbalho, Hugo Gonzalez, Pedro Henrique Maculan, Nelson Univ Fed Paraiba Dept Estatist Joao Pessoa Paraiba Brazil Univ Fed Rio de Janeiro Programa Engn Sistemas & Comp Rio De Janeiro Brazil Ctr Fed Educ Tecnol Celso Suckow da Fonseca Dept Informat Rio De Janeiro Brazil

Let G = (V, E) be a finite simple connected graph and S be a non-empty subset of V, the subgraph of G induced by the subset S is denoted by G[S]. Consider the function w, which assigns a positive real number as a weight to each vertex belonging to V and for a subset S of V, let w(S) be the sum of all weights of the vertices belonging to S. A subset S of V is a weighted Safe Set if, for any maximal component C of G[S], w(C) is greater or equal than w(D) for every maximal component D of G[V \ S] connected to C. A maximal component C of G[S] is a subset of vertices in which all its adjacent vertices do not belong to S. If every vertex belonging to V has a weight equal to one, the non-empty subset S of V is called a Safe Set. Furthermore, if G[S] is connected, it characterizes a Connected Safe Set. The optimal solution of the Safe Set Problem is a subset S which minimizes w(S). This work presents a mixed integer linear programming formulation and a branch and cut algorithm for both the Weighted Safe Set and the Safe Set problems. In addition, for the Safe Set problem, a pre-processing test is suggested. This work also contributes with a heuristic procedure for the Weighted Safe Set and the Safe Set problems. Computational experiments showed the efficiency of each of the proposed methods. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Safe set problem branch-and-cut algorithm Heuristic

来源：评论

学校读者我要写书评

暂无评论

An exact approach for the r-interdiction covering problem with fortification

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2019年第1期27卷 111-131页

作者： Roboredo, Marcos Costa Aizemberg, Luiz Pessoa, Artur Alves Univ Fed Fluminense Dept Engn Prod Rua Passo Patria 156 BR-24210240 Niteroi RJ Brazil Banco Nacl Desenvolvimento Ave Republ Chile 100 BR-20031917 Rio De Janeiro RJ Brazil

In this paper we treat the r-interdiction covering problem with fortification (RICF). The environment of this problem is composed of a set of customers J and a set of facilities I. For each customer j, there is set of facilities containing the facilities that can cover the demand of j. The system efficiency is given by the sum of the total covered demand. The facilities are subject to interdictions. When a facility is interdicted, it can not cover the demand of any customer. To mitigate the negative impact of the interdictions on the system efficiency, the system planner can fortify a subset of facilities. If a facility is fortified then it can not be interdicted. The RICF consists of choosing q facilities to be fortified knowing that r not fortified facilities will be interdicted at the worst case. We propose a branch-and-cut algorithm for the problem. Our results are compared with the exact method found in the literature, being faster for the most instances, mainly the large ones.

关键词： Integer programming branch-and-cut algorithm r-Interdiction covering problem with fortification

来源：评论

学校读者我要写书评

暂无评论

Tugboat scheduling for container ports

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2020年 142卷 102071-102071页

作者： Wei, Xiaoyang Jia, Shuai Meng, Qiang Tan, Kok Choon Natl Univ Singapore Dept Civil & Environm Engn Singapore 117576 Singapore Natl Univ Singapore Dept Ind Syst Engn & Management Singapore 117576 Singapore Shenzhen Univ Coll Management Inst Big Data Intelligent Management & Decis Shenzhen 518061 Peoples R China Natl Univ Singapore Inst Operat Res & Analyt Singapore 117602 Singapore Natl Univ Singapore Sch Business Dept Analyt & Operat Singapore 11924 Singapore

Container ports play an important role in global logistics and supply chains by providing container handling services for container ships. In a port, container ships usually need the assistance of tugboats in order to undergo berthing, shifting, and unberthing movements. Effective scheduling of the tugboats for serving the ships is thus of great importance for ensuring safe and efficient container ship movements in a port. However, research on tugboat scheduling is scarce in the literature. We contribute to the literature by studying a real-life tugboat scheduling problem (Tug-SP). We formulate the Tug-SP using a mixed-integer linear programming (MILP) model taking into consideration various practical constraints. In view of the specific problem structure, we further develop six families of valid inequalities to strengthen the MILP model. To efficiently solve the Tug-SP, we develop a tailored branch-and-cut algorithm by incorporating these valid inequalities into a standard branch-and-bound solution framework. We evaluate the computational performance of the proposed branch-and-cut algorithm using a set of test instances generated from real-life ship traffic data collected from the Port of Singapore. The computational results validate the effectiveness of the proposed valid inequalities, and show that the branch-and-cut algorithm can optimally solve instances of realistic sizes with a reasonable amount of computation time.

关键词： Container port Tugboat scheduling Mixed-integer linear programming Valid inequalities branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Vessel routing and optimization for marine debris collection with consideration of carbon cap

引用

JOURNAL OF CLEANER PRODUCTION 2020年 263卷 121399-121399页

作者： Duan, Gang Nur, Farjana Alizadeh, Morteza Chen, Li Marufuzzaman, Mohammad Ma, Junfeng Lanzhou Jiaotong Univ Sch Traff & Transportat Lanzhou 730070 Gansu Peoples R China Mississippi State Univ Dept Ind & Syst Engn Mississippi State MS 39762 USA Lanzhou City Univ Dept Math Lanzhou 730070 Gansu Peoples R China

Marine debris pollution is becoming an increasingly serious problem, affecting not only navigational safety but also the health of marine ecosystems. Carbon emission causes ocean acidification, which greatly harms marine lives. In order to respond to these environmental issues, this paper studies marine debris collection with consideration of carbon cap using logistics network. To the most of our knowledge, this is first work to study marine debris removal from logistics way. We proposed a three-phase marine debris collection framework: (1) identifying initial locations of the debris;(2) utilizing GNOME software to predict the drifting trajectory of the debris;and (3) formulating vessel routing as a mixed integer nonlinear programming with consideration of carbon emission. The model seeks to minimize the total costs including fuel cost, berth cost, unloading cost in the harbor, vessel rent, vessel insurance, and labor cost, with respect to the constraints of carbon cap, vessel capacities, and time windows. After the linearization process, a branch-and-cut (B&C) algorithm with multiple variable fixing techniques and valid inequalities is used to solve the proposed model. The debris dispersion located in Boston vicinity is used as a case study to validate the proposed model and algorithm. The results reveal that the farther away the debris location is from the shore, the higher the collection cost and the more the carbon emission would be. The daily collection cost in the closest location and in the farthest location is $140 lower and $210 higher than that in the initial location. The carbon emission in the farthest location is 21% and 32% higher than that in the initial location and in the closest location. Sensitivity analysis is also carried out for the fuel price and carbon cap to test their impact on total costs These results show that proposed model and algorithm can significantly improve the efficiency of marine debris collection process, reduce carbon emission

关键词： Marine debris collection GNOME Vessel routing problem Optimization Carbon cap branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast bounding technique for branch-and-cut algorithm based monthly SCUC

Fast bounding technique for branch-and-cut algorithm based m...

引用

General Meeting of the IEEE-Power-and-Energy-Society

作者： Wang, Peng Wang, Yang Xia, Qing Tsinghua Univ Dept Elect Engn State Key Lab Power Syst Beijing 100084 Peoples R China

ISBN: (纸本)9781467327299

Monthly unit commitment with energy constraints is crucial for reducing the energy consumption of generation scheduling. Restricted by the calculation complexity, most approaches for long-term SCUC have to sacrifice the optimality of the solution for the sake of the acceptable calculation time. In response to this issue, a fast bounding technique is proposed to improve the traditional branch and cut algorithm. This technique is able to quickly decrease the upper bound and increase the lower bound for the optimal solution of long-term SCUC in branch-and-cut search, and improve the calculation speed of monthly SCUC in the premise of guaranteeing the optimality of solution. A practical provincial power system in China is employed in cases study, and corresponding results demonstrate the effectiveness of the proposed algorithm.

关键词： branch-and-cut algorithm cut plane tech-nique energy efficiency energy constraints mixed integer program (MIP) long-term security constrained unit commit-ment (SCUC)

来源：评论

学校读者我要写书评

暂无评论

The Shared Customer Collaboration Vehicle Routing Problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2018年第3期265卷 1078-1093页

作者： Fernandez, Elena Roca-Riu, Mireia Speranza, M. Grazia Barcelona Tech UPC Dept Stat & Operat Res Carrer Jordi Girona1C5-208 Barcelona 08034 Spain Barcelona Grad Sch Math BGSMath Edifici C Bellaterra 08193 Spain Swiss Fed Inst Technol Zurich ETHZ Inst Transport Planning & Syst Stefano Franscini Pl 5HIL F 34-2 Zurich Switzerland Univ Brescia Dipartimento Metodi Quantitat Contrada Santa Chiara 50 I-25122 Brescia Italy

This paper introduces a new vehicle routing problem that arises in an urban area where several carriers operate and some of their customers have demand of service for more than one carrier. The problem, called Shared Customer Collaboration Vehicle Routing Problem, aims at reducing the overall operational cost in a collaboration framework among the carriers for the service of the shared customers. Alternative mathematical programming formulations are proposed for the problem that are solved with a branch-and-cut algorithm. Computational experiments on different sets of benchmark instances are run to assess the effectiveness of the formulations. Moreover, in order to estimate the savings coming from the collaboration, the optimal solutions are compared with the solutions obtained when carriers work independently from each other. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Vehicle routing problem Carriers collaboration Mixed integer programming branch-and-cut algorithm Urban logistics

来源：评论

学校读者我要写书评

暂无评论

A hybrid approach for biobjective optimization

引用

DISCRETE OPTIMIZATION 2018年 28卷 89-114页

作者： Stidsen, Thomas Andersen, Kim Allan Tech Univ Denmark DTU Management Lyngby Denmark Aarhus Univ Dept Econ & Business Econ Aarhus Denmark

A large number of the real world planning problems which are today solved using Operations Research methods are actually multiobjective planning problems, but most of them are solved using singleobjective methods. The reason for converting, i.e. simplifying, multiobjective problems to singleobjective problems is that no standard multiobjective solvers exist and specialized algorithms need to be programmed from scratch. In this article we will present a hybrid approach, which operates both in decision space and in objective space. The approach enables massive efficient parallelization and can be used to a wide variety of biobjective Mixed Integer Programming models. We test the approach on the biobjective extension of the classic traveling salesman problem, on the standard datasets, and determine the full set of nondominated points. This has only been done once before (Florios and Mavrotas, 2014), and in our approach we do it in a fraction of the time. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Biobjective optimization Mixed integer programming Traveling salesman problem branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：