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

Optimization algorithms for the k edge-connected L-hop-constrained network design problem

SOFT COMPUTING 2024年第11-12期28卷 7201页

作者： Diarrassouba, I. Mahjoub, A. R. Almudahka, I. M. Normandie Univ UNIHAVRE LMAH FR 3335CNRS F-76600 Le Havre France Kuwait Univ Coll Sci Dept Stat & Operat Res Kuwait Kuwait Univ Paris 09 Lab LAMSADE CNRSUMR 7243 PSL Pl Marechal Lattre Tassigny F-75775 Paris 16 France

In this paper, we study the k edge-connected L-hop-constrained network design problem. Given a weighted graph G=(V,E), a set D of pairs of nodes, two integers L >= 2 and k >= 2, the problem consists in finding a minimum weight subgraph of G containing at least k edge-disjoint paths of length at most L between every pair {s,t} of D. The problem has several applications in telecommunications network design. It also has applications in reliable container transportation network design and public transportation. Even if the problem has been studied for several decades, it appears, to the best of our knowledge, that the associated polytope is not well known, even when L is an element of{2,3}. In this paper, we are particularly interested in the polyhedral analysis of the problem as well as an exact solving of the problem for large-scale instances. We consider the case where L is an element of{2,3} and present two integer programming formulations introduced in Diarrassouba et al. (2016). Then, we consider the polytope associated with these formulations, and present several new classes of valid inequalities, involving the so-called design variables. We also present separation algorithms for these inequalities and devise branch-and-cut algorithms for solving the problem. Finally, we present an extensive computational study for L is an element of{2,3} and k is an element of{3,4,5}, in which we test the efficiency of our branch-and-cut algorithms. We also compare the algorithm against a resolution using CPLEX branch-and-cut and CPLEX Benders Decomposition frameworks. The results show that our branch-and-cut algorithm can be competitive against these two frameworks.

关键词： Hop-constrained survivable network Edge-disjoint paths Hop-constrained path Valid inequalities branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Benders Decomposition for the Hop-Constrained Survivable Network Design Problem

引用

INFORMS JOURNAL ON COMPUTING 2013年第1期25卷 13-26页

作者： Botton, Quentin Fortz, Bernard Gouveia, Luis Poss, Michael Catholic Univ Louvain Ctr Supply Chain Management Louvain Sch Management B-1348 Louvain Belgium Catholic Univ Louvain Ctr Operat Res & Econometr B-1348 Louvain Belgium Univ Libre Bruxelles Fac Sci Dept Comp Sci B-1050 Brussels Belgium Univ Lisbon Fac Ciencias Ctr Invest Operac Dept Estat Invest Operac P-1749016 Lisbon Portugal

Given a graph with nonnegative edge weights and node pairs Q, we study the problem of constructing minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L edges between each pair in Q. Using the layered representation introduced by Gouveia [Gouveia, L. 1998. Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. INFORMS J. Comput. 10(2) 180-188], we present a formulation for the problem valid for any K, L >= 1. We use a Benders decomposition method to efficiently handle the large number of variables and constraints. We show that our Benders cuts contain constraints used in previous studies to formulate the problem for L = 2, 3, 4, as well as new inequalities when L >= 5. Whereas some recent works on Benders decomposition study the impact of the normalization constraint in the dual subproblem, we focus here on when to generate the Benders cuts. We present a thorough computational study of various branch-and-cut algorithms on a large set of instances including the real-based instances from SNDlib. Our best branch-and-cut algorithm combined with an efficient heuristic is able to solve the instances significantly faster than CPLEX 12 on the extended formulation.

关键词： survivable network edge-disjoint paths hop-constrained paths Benders decomposition branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Blood inventory-routing problem under uncertainty

引用

JOURNAL OF INTELLIGENT & FUZZY SYSTEMS 2017年第1期32卷 467-481页

作者： Kazemi, Seyed Mahmood Rabbani, Masoud Tavakkoli-Moghaddam, Reza Shahreza, Farid Aboihassani Univ Tehran Sch Ind Engn Coll Engn Tehran Iran Univ Tehran Med Sci Natl Inst Hlth Res Tehran Iran

The problem of delivering blood products from community blood centers to the demand points including hospital blood banks falls within the context of perishable inventory-routing problems (PIRP). This is due to the fact that the delivery should be made on the right time with the right delivery quantity at the right place such that the total possible perished items as well as routing and inventory costs are minimized. However, some unique characteristics of blood logistics including assigned and unassigned inventories, crossmatch release period, transfusion to crossmatch ratio and older-first policy have made the problem more difficult than the routine PIRPs and thus proposing a new modeling of the problem is required. In this paper, we first develop a mixed integer programming formulation for blood inventory-routing problem. Then, to cope with uncertainties, a novel robust possibilistic programming (RPP) approach is proposed. Afterward, a novel iterative branch-and-cut is developed to solve a number of numerical examples to optimality. Finally, by implementing a test scenario on the data inspired from a real Iranian blood supply chain, the significance and applicability of the proposed model and RPP approach is proven.

关键词： Healthcare management blood inventory-routing perishable products robust possibilistic programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving a capacitated hub location problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第2期184卷 468-479页

作者： Rodriguez-Martin, Inmaculada Salazar-Gonzalez, Juan Jose Univ La Laguna Fac Matemat DEIOC San Cristobal la Laguna 38271 Spain

In this paper we address a problem consisting of determining the routes and the hubs to be used in order to send, at minimum cost, a set of commodities from sources to destinations in a given capacitated network. The capacities and costs of the arcs and hubs are given, and the arcs connecting the hubs are not assumed to create a complete graph. We present a mixed integer linear programming formulation and describe two branch-and-cut algorithms based on decomposition techniques. We evaluate and compare these algorithms on instances with up to 25 commodities and 10 potential hubs. One of the contributions of this paper is to show that a Double Benders' Decomposition approach outperforms the standard Benders' Decomposition, which has been widely used in recent articles on similar problems. For larger instances we propose a heuristic approach based on a linear programming relaxation of the mixed integer model. The heuristic turns out to be very effective and the results of our computational experiments show that near-optimal solutions can be derived rapidly. (C) 2006 Elsevier B.V. All rights reserved.

关键词： network design telecommunication capacitated hub location problem Benders decomposition branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal joint replenishment, delivery and inventory management policies for perishable products

引用

COMPUTERS & OPERATIONS RESEARCH 2014年第Jul.期47卷 42-52页

作者： Coelho, Leandro C. Laporte, Gilbert CIRRELT Interuniv Res Ctr Enterprise Networks Log Toronto ON Canada Univ Laval Fac Sci Adm Quebec City PQ G1K 0A6 Canada HEC Montreal Montreal PQ H3T 2A7 Canada

In this paper we analyze the optimal joint decisions of when, how and how much to replenish customers with products of varying ages. We discuss the main features of the problem arising in the joint replenishment and delivery of perishable products, and we model them under general assumptions. We then solve the problem by means of an exact branch-and-cut algorithm, and we test its performance on a set of randomly generated instances. Our algorithm is capable of computing optimal solutions for instances with up to 30 customers, three periods, and a maximum age of two periods for the perishable product. For the unsolved instances the optimality gap is always small, less than 1.5% on average for instances with up to 50 customers. We also implement and compare two suboptimal selling priority policies with an optimized policy: always sell the oldest available items first to avoid spoilage, and always sell the fresher items first to increase revenue. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Perishable products Inventory control Replenishment Inventory-routing Vendor-managed inventory 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

来源：评论

学校读者我要写书评

暂无评论

Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots

引用

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2014年 67卷 166-186页

作者： Braekers, Kris Caris, An Janssens, Gerrit K. Hasselt Univ Res Grp Logist B-3590 Diepenbeek Belgium Res Fdn Flanders FWO B-1000 Brussels Belgium

Dial-a-ride problems are concerned with the design of efficient vehicle routes for transporting individual persons from specific origin to specific destination locations. In real-life this operational planning problem is often complicated by several factors. Users may have special requirements (e.g. to be transported in a wheelchair) while service providers operate a heterogeneous fleet of vehicles from multiple depots in their service area. In this paper, a general dial-a-ride problem in which these three real-life aspects may simultaneously be taken into account is introduced: the Multi-Depot Heterogeneous Dial-A-Ride Problem (MD-H-DARP). Both a three- and two-index formulation are discussed. A branch-and-cut algorithm for the standard dial-a-ride problem is adapted to exactly solve small problem instances of the MD-H-DARP. To be able to solve larger problem instances, a new deterministic annealing meta-heuristic is proposed. Extensive numerical experiments are presented on different sets of benchmark instances for the homogeneous and the heterogeneous single depot dial-a-ride problem. Instances for the MD-H-DARP are introduced as well. The branch-and-cut algorithm provides considerably better results than an existing algorithm which uses a less compact formulation. All seven previously unsolved benchmark instances for the heterogeneous dial-a-ride problem could be solved to optimality within a matter of seconds. While computation times of the exact algorithm increase drastically with problem size, the proposed meta-heuristic algorithm provides near-optimal solutions within limited computation time for all instances. Several best known solutions for unsolved instances are improved and the algorithm clearly outperforms current state-of-the-art heuristics for the homogeneous and heterogeneous dial-a-ride problem, both in terms of solution quality and computation time. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Dial-a-ride Demand responsive transportation Heterogeneous users and vehicles branch-and-cut algorithm Deterministic annealing meta-heuristic Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Stochastic binary problems with simple penalties for capacity constraints violations

引用

MATHEMATICAL PROGRAMMING 2013年第1-2期138卷 199-221页

作者： Fortz, B. Labbe, M. Louveaux, F. Poss, M. Univ Libre Brussels Fac Sci Dept Comp Sci Brussels Belgium Univ Namur FUNDP Dept Business Adm Namur Belgium Univ Coimbra Dept Math CMUC P-3001454 Coimbra Portugal

This paper studies stochastic programs with first-stage binary variables and capacity constraints, using simple penalties for capacities violations. In particular, we take a closer look at the knapsack problem with weights and capacity following independent random variables and prove that the problem is weakly -hard in general. We provide pseudo-polynomial algorithms for three special cases of the problem: constant weights and capacity uniformly distributed, subset sum with Gaussian weights and strictly positively distributed random capacity, and subset sum with constant weights and arbitrary random capacity. We then turn to a branch-and-cut algorithm based on the outer approximation of the objective function. We provide computational results for the stochastic knapsack problem (i) with Gaussian weights and constant capacity and (ii) with constant weights and capacity uniformly distributed, on randomly generated instances inspired by computational results for the knapsack problem.

关键词： Stochastic programming Knapsack problem Pseudo-polynomial algorithm Mixed-integer non-linear programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A routing model and solution approach for alternative fuel vehicles with consideration of the fixed fueling time

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2020年 142卷 106364-106364页

作者： Shao, Yihuan Dessouky, Maged Univ Southern Calif Daniel J Dept Ind & Syst Engn Los Angeles CA 90089 USA

In this paper, we introduce the Vehicle Routing Problem for Alternative Fuel Vehicles with Fixed Fueling Time (VRPAFVFFT) to model decisions to be made with regards to the vehicle routes cons, dering fuel stations. A Mixed Integer Programming (MIP) model is proposed with improving methods, which includes an adaptive branch-and-cut algorithm. To solve large scale problems, we present a hybrid heuristic method, which combines an Adaptive Large Neighborhood Search (ALNS) with a local search and a MIP model. We conduct experiments to show the efficiency of our solving methods as well as insights from real world cases.

关键词： Green VRP Alternative fuel vehicles Fuel stations branch-and-cut algorithm ALNS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：