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

11th Latin and American algorithms, Graphs and Optimization Symposium (LAGOS)

作者： Malaguti, Enrico Pedrotti, Vagner Univ Bologna Dipartimento Ingn Energia Elettr & Informaz Gugli Bologna Italy Univ Fed Mato Grosso do Sul Fac Comp Campo Grande MS 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. (C) 2021 The Authors. Published by Elsevier B.V.

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

来源：评论

学校读者我要写书评

暂无评论

A Bilevel Model for Centralized Optimization of Charging Stops for EV on Highways 10th

A Bilevel Model for Centralized Optimization of Charging Sto...

引用

10th International Conference on Network Games, Control and Optimization (NetGCooP)

作者： Woznica, Anthony Quadri, Dominique Hayel, Yezekael Beaude, Olivier Univ Paris Sud Univ Paris Saclay LRI Bat 650 F-91405 Orsay France Univ Avignon 339 Chemin Meinajaries F-84911 Avignon 9 France EDF Lab Paris Saclay Palaiseau France

ISBN: (纸本)9783030874735;9783030874728

This paper addresses the multi-period problem of fixing the energy charging price at a set of charging stations deployed to support long journeys of electric vehicles along highways. In order to model the problem, we propose a non-linear bilevel program, in which the leader (a single centralized operator) fixes the charging price over the time horizon to maximize its profit and the follower (the operator of the electric vehicles) chooses the optimal assignment of the electric vehicles to the stations so to minimize a cost function. To solve the resulting model, we suggest to adopt an adaption of the branch-and-cut algorithm for Mixed Integer Linear Bilevel Programming proposed by Fischetti et al. (2018). Preliminary computational results are provided to show the interesting performance of the new modeling and algorithmic approach.

关键词： Electrical vehicles Bilevel programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

The Multi-Depot VRP with Vehicle Interchanges

The Multi-Depot VRP with Vehicle Interchanges

引用

作者： Victoria Rebillas Loredo Universitat Politecnica de Catalunya

学位级别：博士

In real-world logistic operations there are a lot of situations that can be exploited to get better operational strategies. It is important to study these new alternatives, because they can represent significant cost reductions to the companies working with physical distribution. This thesis defines the Multi-Depot Vehicle Routing Problem with Vehicle Interchanges. In this problem, both vehicle capacities and duration limits on the routes of the drivers are imposed. To favor a better utilization of the available capacities and working times, it is allowed to combine pairs of routes at predefined interchange locations. The objective of this thesis is to analyze and solve the Multi-Depot Vehi- cle Routing Problem adding the possibility to interchange vehicles at predefined points. With this strategy, it is possible to reduce the total costs and the number of used routes with respect to the classical approach: the Multi-Depot Vehicle Rout- ing Problem. It should be noted that the Multi-Depot Vehicle Routing Problem is more challenging and sophisticated than the single-depot Vehicle Routing Problem. Besides, most exact algorithms for solving the classical Vehicle Routing Problem are difficult to adapt in order to solve the Multi-Depot Vehicle Routing Problem (Montoya-Torres et al., 2015). From the complexity point of view, the Multi-Depot Vehicle Routing Problem with Vehicle Interchanges is NP-Hard, since it is an exten- sion of the classical problem, which is already NP-Hard. We present a tight bound on the costs savings that can be attained allowing interchanges. Three integer programming formulations are proposed based on the classical vehicle-flow formulations of the Multi-Depot Vehicle Routing Problem. One of these formulations was solved with a branch-and-bound algorithm, and the other two formulations, with branch-and-cut algorithms. Due to its great symmetry, the first formulation is only able to solve small instances. To increase the dimension of the instances

关键词： combinatorial optimization routing the Multi-Depot Vehicle Routing Problem Rich Vehicle Routing Problem vehicle interchanges branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

The multi-terminal vertex separator problem: Complexity, Polyhedra and algorithms

The multi-terminal vertex separator problem: Complexity, Pol...

引用

作者： Youcef Magnouche PSL Research University

学位级别：博士

This thesis deals with the multi-terminal vertex separator problem. Given a graph G = (V ∪T, E) with V ∪T the set of vertices, where T is a set of terminals, and a weight function w: V → Z, associated with nonterminal nodes, the multi-terminal vertex separator problem consists in partitioning V ∪ T into k + 1 subsets {S, V 1,..., V k } such that there is no edge between two different subsets V i and V j, each V i contains exactly one terminal and the weight of S is minimum. In this thesis, we consider the problem from a polyhedral point of view. We give two integer programming formulations for the problem, for one of them, we investigate the related polyhedron and discuss its polyhedral structure. We describe some valid inequalities and characterize when these inequalities define facets. We also derive separation algorithms for these inequalities. Using these results, we develop a branch-and-cut algorithm for the problem, along with an extensive computational study is presented. We also study the multi-terminal vertex separator polytope in the graphs decompos- able by one node cutsets. If G is a graph that decomposes into G 1 and G 2, we show that the multi-terminal vertex separator polytope in G can be described from two lin- ear systems related to G 1 and G 2. This gives rise to a technique for characterizing the multi-terminal vertex separator polytope in the graphs that are recursively decompos- able. We also obtain a procedure to describe facets for this polytope and show that the multi-terminal vertex separator problem can also be decomposed. Applications of this technique are also discussed. Moreover, we propose three extended formulations for the problem and derive branch- and-Price and branch-and-cut-and-Price algorithms. For each formulation we present a column generation scheme to solve the linear relaxation, the way to compute the dual bound and the branching scheme. We present computational results and discuss the performance of each algorithm. Further,

关键词： Combinatorial optimization Polytope Facet branch-and-cut algorithm branch-and-Price algorithm Composition of polyhedra

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A location-routing problem for local supply chains

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2023年第1期183卷

作者： Soto-Mendoza, Valeria Ruiz-y-Ruiz, Efrain Garcia-Calvillo, Irma Nucamendi-Guillen, Samuel Cardona-Valdes, Yajaira Univ Autonoma Coahuila Res Ctr Appl Math Unidad Camporredondo Prolongac David Berlanga Y 16 Septiembre S-N Saltillo 25280 Coahuila Mexico Tecnol Nacl Mex IT Saltillo Div Postgrad Studies & Res Blvd Venustiano Carranza 2400 Saltillo 25280 Coahuila Mexico Univ Panamericana Fac Ingn Campus GuadalajaraAlvaro Portillo 49 Zapopan 45010 Jalisco Mexico

This study addresses a local Supply Chain problem by proposing the Collection and Delivery Location Open Routing Problem (CDLORP), a variant of the classical location-routing problem that considers both collection and distribution routes to decide where to locate facilities. Collection routes are responsible for picking up the required raw material from local suppliers, while distribution routes deliver the final product to local customers. This study is motivated by a public initiative that desires to seize the by-product generated by the agroindustrial local sector to produce and provide healthy and nutritional snacks to students in the public elementary school system in Saltillo, Coahuila, Mexico. A node-based formulation and a flow-based formulation are proposed to solve instances of the problem. The formulations are valid for the symmetric and asymmetric cases of the problem. Four families of valid inequalities from the literature are adapted for the problem and are used to implement two branch-and-cut algorithms based on the proposed formulations. Computational experiments using 42 benchmark instances of different sizes (25 to 260 vertices) are performed to assess the efficacy of the proposed formulations and algorithms. The best results are obtained by the branch-and-cut algorithm using the node-based formulation. Finally, a case study is also addressed and optimally solved with the branch-and-cut algorithm using the node-based formulation. The results obtained for the benchmark instances and the case study show that the proposed approach can solve real-life problems to develop local supply chains for new products.

关键词： Local Supply Chain Location-routing Collection and Delivery Mixed Integer Linear Programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A computational study on the Maximum-Weight Bounded-Degree Rooted Tree Problem

引用

APPLIED MATHEMATICS AND COMPUTATION 2022年 413卷 126623-126623页

作者： Kerivin, Herve Zhao, Jinhua CNRS LIMOS UMR 6158 F-63178 Aubiere France Cent China Normal Univ Fac Artificial Intelligence Educ Cent China Normal Univ Wollongong Joint Inst Wuhan 430079 Peoples R China

This paper contributes to the computational study of the Maximum-Weight Bounded-Degree Rooted Tree Problem. Based on previous work, two types of formulations are introduced for the problem, along with some newly discovered constraints that can enhance the formulations. The separation problem for each family of constraints are studied in terms of their complexity and associated algorithms. We then compare the performance of four branch-and-cut frameworks in extensive computational simulations, especially the performance difference between original models and enhanced models with newly discovered constraints. Results show that the enhanced models have a significantly better performance than the original ones. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Bounded-degree rooted tree branch-and-cut algorithm Separation

来源：评论

学校读者我要写书评

暂无评论

Robust model and solution algorithm for the railroad blocking problem under uncertainty

引用

SCIENTIA IRANICA 2018年第4期25卷 1916-1930页

作者： Hasany, R. M. Shafahi, Y. Sharif Univ Technol Dept Civil Engn POB 11155-8639 Tehran Iran

The railroad blocking problem emerges as an important issue at the tactical level of planning in freight rail transportation. This problem consists of determining the optimal paths for freight cars in a rail network. Often, demand and supply resource indicators are assumed certain;hence, the solution obtained from a certain model might not be optimal or even feasible in practice due to the stochastic nature of these parameters. To address this issue, this paper develops a robust model for this problem with uncertain demand and travel time as supply resource indicators. Since the model combines integer variables and nonlinear functions, a branch-and-cut algorithm is used to solve the linearized version of the robust model. The performance of the proposed algorithm in several instances is examined and discussed. The high efficiency and effectiveness of the proposed algorithm are demonstrated through a comparison with a well-known solver. Finally, this algorithm is applied to a blocking problem of the railways of Iran. The results show that, by ignoring approximately 10% of the optimal value of the deterministic model, we have an optimal solution that remains unchanged with a probability of more than 0.98. (C) 2018 Sharif University of Technology. All rights reserved.

关键词： Railroad blocking problem Robust optimization branch-and-cut algorithm Uncertainty Railway planning

来源：评论

学校读者我要写书评

暂无评论

Robust MILP formulations for the two-stage weighted vertex p-center problem

引用

COMPUTERS & OPERATIONS RESEARCH 2023年第1期159卷

作者： Duran-Mateluna, Cristian Ales, Zacharie Elloumi, Sourour Jorquera-Bravo, Natalia Inst Polytech Paris UMA ENSTA Paris F-91120 Palaiseau France CEDRIC Conservatoire Natl Arts & Metiers F-75003 Paris France Univ Santiago Chile USACH Fac Engn Program Dev Sustainable Prod Syst PDSPS Santiago Chile Univ Santiago Chile USACH Fac Engn Ind Engn Dept Santiago Chile

The weighted vertex p-center problem (PCP ) consists of locating p facilities among a set of available sites such that the maximum weighted distance (or travel time) from any demand node to its closest located facility is minimized. This paper studies the exact solution of the two-stage robust weighted vertex p-center problem (RPCP2). In this problem, the location of the facilities is fixed in the first stage while the demand node allocations are recourse decisions fixed once the uncertainty is revealed. The problem is modeled by box uncertainty sets on both the demands and the distances. We introduce five different robust reformulations based on MILP formulations of (PCP ) from the literature. We prove that considering a finite subset of scenarios is sufficient to obtain an optimal solution of (RPCP2). We leverage this result to introduce a column-and-constraint generation algorithm and a branch-and-cut algorithm to efficiently solve this problem optimally. We highlight how these algorithms can also be adapted to solve the single-stage problem (RPCP1) which is obtained when no recourse is considered. We present a numerical study to compare the performances of these formulations on randomly generated instances and on a case study from the literature.

关键词： Discrete location p-center problem Robust MILP formulations Column-and-constraint generation algorithm branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Benders decomposition applied to profit maximizing hub location problem with incomplete hub network

引用

COMPUTERS & OPERATIONS RESEARCH 2022年 142卷 105715-105715页

作者： Oliveira, Fabricio Alves de Sa, Elisangela Martins de Souza, Sergio Ricardo Fed Inst Minas Gerais IFMG Rua Afonso Sardinha 90 BR-36420000 Ouro Branco MG Brazil Fed Ctr Technol Educ Minas Gerais CEFET MG Ave Amazonas 7675 BR-30510000 Belo Horizonte MG Brazil

This paper addresses a profit maximizing multiple allocation hub network design problem, which is a hub location problem with incomplete hub network, aiming to determine the quantity and location of the hubs, allocate demand nodes to these hubs, establish the network topology, and route the demand flows to satisfy the demands between the origin and destination pairs that were selected to be served in order to obtain the highest profit. This problem also considers the multiple allocation strategy, does not allow direct connections between non-hub nodes, does not impose capacity constraints, and assumes that there are fixed costs involved in installing hubs and installing hub arcs. A new formulation for the problem is presented and it is proved that this formulation is stronger than another one in the literature, which models the same problem. Several versions of the Benders decomposition method, combining the generation of Pareto-optimal cuts, multiple cuts strategies, and Benders branch-and-cut scheme, are proposed and analyzed through extensive computational experiments on benchmark instances. The best-proposed Benders decomposition versions were compared with the CPLEX solver, with and without the activation of its Benders decomposition algorithm. The results showed that these algorithms perform much better than the solver versions. The proposed Benders decomposition approach can solve benchmark instances with up to 150 nodes.

关键词： Hub network design problem Profit maximization Incomplete hub network Hub location problem Benders decomposition method branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：