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

Models and algorithms for the Traveling Salesman Problem with Time-dependent Service times

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第3期283卷 825-843页

作者： Cacchiani, Valentina Contreras-Bolton, Carlos Toth, Paolo Univ Bologna DEI Viale Risorgimento 2 I-40136 Bologna Italy

The Traveling Salesman Problem with Time-dependent Service times (TSP-TS) is a generalization of the Asymmetric TSP, in which the service time at each customer is given by a (linear or quadratic) function of the corresponding start time of service. TSP-TS calls for determining a Hamiltonian tour (i.e. a tour visiting each customer exactly once) that minimizes the total tour duration, given by the sum of travel and service times. We propose a new Mixed Integer Programming model for TSP-TS, that is enhanced by lower and upper bounds that improve previous bounds from the literature, and by incorporating exponentially many subtour elimination constraints, that are separated in a dynamic way. In addition, we develop a multi-operator genetic algorithm and two branch-and-cut methods, based on the proposed model. The algorithms are tested on benchmark symmetric instances from the literature, and compared with an existing approach. The computational results show that the proposed exact methods are able to prove the optimality of the solutions found for a larger set of instances in shorter computing times. We also tested the branch-and-cut algorithms on larger size symmetric instances with up to 58 nodes and on asymmetric instances with up to 45 nodes, demonstrating the effectiveness of the proposed algorithms. In addition, we tested the genetic algorithm on symmetric and asymmetric instances with up to 200 nodes. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Travelling Salesman Time-dependent Service times Mathematical model branch-and-cut algorithm Genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Beyond symmetry: best submatrix selection for the sparse truncated SVD

引用

MATHEMATICAL PROGRAMMING 2024年第1-2期208卷 1-50页

作者： Li, Yongchun Xie, Weijun Georgia Inst Technol Atlanta GA 30332 USA

The truncated singular value decomposition (SVD), also known as the best low-rank matrix approximation with minimum error measured by a unitarily invariant norm, has been applied to many domains such as biology, healthcare, among others, where high-dimensional datasets are prevalent. To extract interpretable information from the high-dimensional data, sparse truncated SVD (SSVD) has been used to select a handful of rows and columns of the original matrix along with the best low-rank approximation. Different from the literature on SSVD focusing on the top singular value or compromising the sparsity for the seek of computational efficiency, this paper presents a novel SSVD formulation that can select the best submatrix precisely up to a given size to maximize its truncated Ky Fan norm. The fact that the proposed SSVD problem is NP-hard motivates us to study effective algorithms with provable performance guarantees. To do so, we first reformulate SSVD as a mixed-integer semidefinite program, which can be solved exactly for small- or medium-sized instances within a branch-and-cut algorithm framework with closed-form cuts and is extremely useful for evaluating the solution quality of approximation algorithms. We next develop three selection algorithms based on different selection criteria and two searching algorithms, greedy and local search. We prove the approximation ratios for all the approximation algorithms and show that all the ratios are tight when the number of rows or columns of the selected submatrix is no larger than half of the data matrix, i.e., our derived approximation ratios are unimprovable. Our numerical study demonstrates the high solution quality and computational efficiency of the proposed algorithms. Finally, all our analysis can be extended to row-sparse PCA.

关键词： Sparse truncated SVD Mixed-integer semidefinite program branch-and-cut algorithm Approximation algorithms Row-sparse PCA

来源：评论

学校读者我要写书评

暂无评论

The family capacitated vehicle routing problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第3期314卷 836-853页

作者： Bernardino, Raquel Paias, Ana Univ Lisbon ISEG Sch Econ & Management Lisbon Portugal CEMAPRE REM Res Econ & Math Lisbon Portugal Univ Lisbon Fac Ciencias DEIO C6Piso 4 P-1749016 Lisbon Portugal Univ Lisbon Fac Ciencias CMAFcIO Lisbon Portugal

In this article, we address the family capacitated vehicle routing problem (F-CVRP), an NP-hard problem that generalizes both the FTSP and the capacitated vehicle routing problem. The F-CVRP has practical application in warehouse management in warehouses with scattered storage. We present several mixed integer linear programming formulations for this problem and establish a theoretical and empirical comparison. We also propose valid inequalities adapted from known routing problems from the literature. Some formulations are solved using a branch-and-cut algorithm, which is tested with a newly generated data set. The computational experiment allows us to identify the instances' most challenging characteristics and the exact methods' limitations. Finally, we develop an iterated local search (ILS) algorithm to efficiently obtain feasible solutions for the instances that could not be solved to proven optimality. The ILS algorithm is very efficient and can improve the upper bounds obtained by the exact methods within the set time limit.

关键词： Routing Family traveling salesman problem Projection results branch-and-cut algorithm Iterated local search algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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 node capacitated graph partitioning problem: A computational study

引用

MATHEMATICAL PROGRAMMING 1998年第2期81卷 229-256页

作者： Ferreira, CE Martin, A de Souza, C Weismantel, R Wolsey, LA Univ Sao Paulo BR-05014 Sao Paulo Brazil Univ Estadual Campinas BR-13081970 Campinas SP Brazil Catholic Univ Louvain CORE B-1348 Louvain Belgium

In this paper we consider the problem of k-partitioning the nodes of a graph with capacity restrictions on the sum of the node wrights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities. we present a variety of separation heuristics for cycle, cycle with ears, knapsack tree and path-block cycle inequalities among others. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including variables for the edges with nonzero costs and node partition variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

关键词： branch-and-cut algorithm clustering compiler design equipartitioning finite element method graph partitioning layout of electronic circuits separation heuristics

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Customized bus scheme design of large transport terminals with jointly optimization of departure time, vehicle allocation and routing

引用

IET INTELLIGENT TRANSPORT SYSTEMS 2023年第1期17卷 85-101页

作者： Wu, Yuelin Yuan, Zhenzhou Xiao, Qingyu Yang, Dong Beijing Jiaotong Univ Sch Traff & Transportat Key Lab Transport Ind Big Data Applicat Technol C Minist Transport 3 Shangyuan Village Beijing 100044 Peoples R China China Acad Transportat Sci Ctr Comprehens Transportat Beijing Peoples R China

The customized bus (CB) service of large transport terminals can provide passengers with convenient transfers and door-to-door services, which has the potential to help ease the pressure of arriving passenger flow in large transport terminals. Considering the costs of operators and passengers, this paper establishes a multi-commodity network flow optimization model to simultaneously obtain departure schedule, passenger-to-vehicle assignment and routing under the condition of multiple vehicle types. It provides more passengers with high-quality CB service and obtains higher vehicle capacity utilization. Accordingly, the solution is proposed that combines a branch-and-cut algorithm with grid-density-based clustering. An illustrative example verifies the effectiveness and tests the impact of the departure time-window. The case study of Chengdu city compares the results under different types of vehicle schemes and conducts the sensitivity analysis of penalty and minimum load ratio. The experiments conclude: (i) The proposed algorithm stably improves computation speed (76.38%) without affecting the optimal results;(ii) a loose time-window can serve more people, but the excessively loose one no longer has impacts on the results. (iii) The multi-type of vehicle scheme performs best compared to the single type of vehicle schemes.

关键词： transportation jointly optimization Optimisation techniques vehicle capacity utilization pattern clustering branch-and-cut algorithm vehicle routing multiple vehicle types Systems theory applications in transportation passenger flow departure time-window sensitivity analysis scheduling customized bus scheme design passenger-to-vehicle assignment Data handling techniques transport terminals door-to-door services convenient transfers customized bus service high-quality CB service Chengdu city multicommodity network flow optimization model vehicle scheme departure schedule loose time-window optimisation vehicle allocation road vehicles Combinatorial mathematics grid-density-based clustering

来源：评论

学校读者我要写书评

暂无评论

Models and algorithms for the Weighted Safe Set Problem

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期329卷 23-34页

作者： Malaguti, Enrico Pedrotti, Vagner Univ Bologna Dipartimento Ingn Energia Elettr & Informaz Guglie Bologna Italy Univ Fed Mato Grosso Fac Comp 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 neighbor connected component in the subgraph induced by S. 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 which can tackle the four variants of the problem which arise by imposing connectivity of the safe set, and by considering weighted or unweighted vertices, respectively. Despite alternative formulations from the literature, that require a large number of variables, our formulation only uses one variable per vertex. The formulation has an exponential number of constraints, which are needed to define the structure of the safe set, and can be generated on-the-fly within a branch-and-cut algorithm. We describe linear-time separation procedures for these constraints, as well as families of additional inequalities 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 the state-of-the-art alternative formulation from the literature, and shows faster in solving most of benchmark instances.(c) 2022 Elsevier B.V. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：