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

The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm

MATHEMATICAL PROGRAMMING 2010年第2期121卷 269-305页

作者： Dumitrescu, Irina Ropke, Stefan Cordeau, Jean-Francois Laporte, Gilbert HEC Montreal Canada Res Chair Distribut Management Montreal PQ H3T 2A7 Canada Univ Sydney Sch Math & Stat Sydney NSW 2052 Australia HEC Montreal Canada Res Chair Logist & Transportat Montreal PQ H3T 2A7 Canada

The Traveling Salesman Problem with Pickup and Delivery (TSPPD) is defined on a graph containing pickup and delivery vertices between which there exists a one-to-one relationship. The problem consists of determining a minimum cost tour such that each pickup vertex is visited before its corresponding delivery vertex. In this paper, the TSPPD is modeled as an integer linear program and its polyhedral structure is analyzed. In particular, the dimension of the TSPPD polytope is determined and several valid inequalities, some of which are facet defining, are introduced. Separation procedures and a branch-and-cut algorithm are developed. Computational results show that the algorithm is capable of solving to optimality instances involving up to 35 pickup and delivery requests, thus more than doubling the previous record of 15.

关键词： Traveling salesman problem Pickup and delivery Precedence relationships Polyhedral results Valid inequalities Separation procedures branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A disaster evacuation network model for transporting multiple priority evacuees

引用

IIE TRANSACTIONS 2015年第11期47卷 1287-1299页

作者： Na, Hyeong Suk Banerjee, Amarnath Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA

There is an increasing number of natural disasters occurring worldwide, particularly in populated areas. These events affect a large number of people, causing injuries and fatalities. Providing rapid medical treatment is of utmost importance in such circumstances. The problem of transporting patients to medical facilities has been studied to only a small extent. One of the challenges is to find a strategy that can simultaneously maximize the number of survivors and minimize the total evacuation cost under a given set of resource and geographic constraints. We propose a mathematical optimization model called Triage-Assignment-Transportation (TAT) model that decides on the tactical routing assignment of several classes of evacuation vehicles between staging areas and shelters in the nearby area. The model takes into account the level of injury to the evacuees, the capacities of vehicles, and available resources at each shelter. TAT is a mixed-integer linear programming and minimum-cost flow model. Comprehensive computational experiments are performed to examine the applicability of the TAT model. TAT can offer valuable insights for decision-makers about the number of staging areas, evacuation vehicles, and medical resources that are required to complete a large-scale evacuation based on the estimated number of evacuees.

关键词： humanitarian logistics branch-and-cut algorithm mixed-integer linear programming large-scale deterministic optimization Disaster evacuation model

来源：评论

学校读者我要写书评

暂无评论

The Stacker Crane Problem and the Directed General Routing Problem

引用

NETWORKS 2015年第1期65卷 43-55页

作者： Avila, Thais Corberan, Angel Plana, Isaac Sanchis, Jose M. Univ Valencia Dept Estadist & Invest Operat Valencia Spain Univ Politecn Valencia Dept Matemat Aplicada E-46071 Valencia Spain

In this article, we deal with the polyhedral description and the resolution of the directed general routing problem (DGRP) and the stacker crane problem (SCP). The DGRP, in which the service activity occurs both at some of the nodes and at some of the arcs of a directed graph, contains a large number of important arc and node routing problems as special cases, including the SCP. We describe large families of facet-defining inequalities for the DGRP. Furthermore, a branch-and-cut algorithm for these problems is presented. Extensive computational experiments over different sets of DGRP and SCP instances are included. These results show that our algorithm is among the best solution procedures proposed for both problems. (c) 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(1), 43-55. 2015

关键词： directed rural postman problem directed general routing problem stacker crane problem branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimum edge blocker dominating set problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第1期247卷 16-26页

作者： Pajouh, Foad Mahdavi Walteros, Jose L. Boginski, Vladimir Pasiliao, Eduardo L. Univ Massachusetts Management Sci & Informat Syst Dept Boston MA 02125 USA SUNY Buffalo Dept Ind & Syst Engn Buffalo NY 14260 USA Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Air Force Res Lab Munit Directorate Eglin AFB FL 32542 USA

This paper introduces and studies the minimum edge blocker dominating set problem (EBDP), which is formulated as follows. Given a vertex-weighted undirected graph and r> 0, remove a minimum number of edges so that the weight of any dominating set in the remaining graph is at least r. Dominating sets are used in a wide variety of graph-based applications such as the analysis of wireless and social networks. We show that the decision version of EBDP is NP-hard for any fixed r> 0. We present an analytical lower bound for the value of an optimal solution to EBDP and formulate this problem as a linear 0-1 program with a large number of constraints. We also study the convex hull of feasible solutions to EBDP and identify facet-inducing inequalities for this polytope. Furthermore, we develop the first exact algorithm for solving EBDP, which solves the proposed formulation by a branch-and-cut approach where nontrivial constraints are applied in a lazy fashion. Finally, we also provide the computational results obtained by using our approach on a test-bed of randomly generated instances and real-life power-law graphs. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.

关键词： Network interdiction Minimum weighted dominating set NP-hardness branch-and-cut algorithm Critical elements detection

来源：评论

学校读者我要写书评

暂无评论

A Heuristic Method Based on the branch and cut algorithm to the Transmission System Expansion Planning Problem

A Heuristic Method Based on the Branch and Cut Algorithm to ...

引用

IEEE Power and Energy Society General Meeting

作者： Aldir S. Sousa Eduardo N. Asada Department of Electrical Engineering Sao Carlos School of Engineering University of Sao Paulo

ISBN: (纸本)9781457710001

In this paper we introduce a new heuristic algorithm to the centralized long-term transmission system expansion planning problem. The proposed method introduces cuts (new constraints) to the mathematical model to force generating feasible solutions to the DC model. The application of the strategy resulted in good solutions for the DC model. The computational results demonstrate the efficiency of the proposed method when applied to IEEE-24 bus system, Brazilian Southern System and Colombian system.

关键词： Transmission System Expansion Planning Heuristic Methods branch-and-Bound algorithm branch-and-cut algorithm heuristic methods branch and bound algorithms power system expansion planning expansion plan Transmission systems branch cut Heuristic algorithms branches

来源：评论

学校读者我要写书评

暂无评论

A branch-AND-cut FOR THE NON-DISJOINT m-RING-STAR PROBLEM

引用

RAIRO-OPERATIONS RESEARCH 2014年第2期48卷 167-188页

作者： Fouilhoux, Pierre Questel, Auralien Univ Paris 06 Lab LIP6 F-75005 Paris France

In this article we study the realistic network topology of Synchronous Digital Hierarchy (SDH) networks. We describe how providers fulfill customer connectivity requirements. We show that SDH Network design reduces to the Non-Disjoint m-Ring-Star Problem (NDRSP). We first show that there is no two-index integer formulation for this problem. We then present a natural 3-index formulation for the NDRSP together with some classes of valid inequalities that are used as cutting planes in a branch-and-cut approach. We propose a polyhedral study of a polytope associated with this formulation. Finally, we present our branch-and-cut algorithm and give some experimental results on both random and real instances.

关键词： Realistic SDH network non-disjoint m-ring-star problem polyhedral approach 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Solving the Close-Enough Arc Routing Problem

引用

NETWORKS 2014年第1期63卷 107-118页

作者： Minh Hoang Ha Bostel, Nathalie Langevin, Andre Rousseau, Louis-Martin LUNAM Univ IRCCyN F-44307 Nantes 3 France Ecole Mines Nantes IRCCyN F-44307 Nantes 3 France Ecole Polytech Dept Math & Ind Engn Montreal PQ H3C 3A7 Canada Ecole Polytech CIRRELT Montreal PQ H3C 3A7 Canada LUNAM Univ IRCCyN F-44606 St Nazaire France Univ Nantes F-44606 St Nazaire France

The close-enough arc routing problem has an interesting real-life application to routing for meter reading. In this article, we propose a new mathematical formulation for this problem. We analyze our formulation and compare it with two formulations in the literature. We also develop branch-and-cut algorithms to solve the problem to optimality. We present computational results for instances based on three types of graphs: directed, undirected, and mixed. Copyright (c) 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(1), 107-118 2014

关键词： close-enough arc routing problem close-enough traveling salesman problem automated meter reading radio frequency identification branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Formulations for an inventory routing problem

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2014年第3期21卷 353-374页

作者： Archetti, Claudia Bianchessi, Nicola Irnich, Stefan Speranza, M. Grazia Univ Brescia Dept Econ & Management Brescia Italy Johannes Gutenberg Univ Mainz Chair Logist Management D-55122 Mainz Germany

In this paper, we present and compare formulations for the inventory routing problem (IRP) where the demand of customers has to be served, over a discrete time horizon, by capacitated vehicles starting and ending their routes at a depot. The objective of the IRP is the minimization of the sum of inventory and transportation costs. The formulations include known and new mathematical programming formulations. Valid inequalities are also presented. The formulations are tested on a large set of benchmark instances. One of the most significant conclusions is that the formulations that use vehicle-indexed variables are superior to the more compact, aggregate formulations.

关键词： supply chain management branch-and-cut algorithm integer programming routing problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：