|   | 
Details
   web
Records
Author Lagos, F.; Pereira, J.
Title Multi-arme d bandit-base d hyper-heuristics for combinatorial optimization problems Type
Year 2023 Publication European Journal Of Operational Research Abbreviated Journal Eur. J. Oper. Res.
Volume 312 Issue 1 Pages 70-91
Keywords Metaheuristics; Combinatorial optimization; Hyper-heuristics; Machine learning
Abstract There are significant research opportunities in the integration of Machine Learning (ML) methods and Combinatorial Optimization Problems (COPs). In this work, we focus on metaheuristics to solve COPs that have an important learning component. These algorithms must explore a solution space and learn from the information they obtain in order to find high-quality solutions. Among the metaheuristics, we study Hyper-Heuristics (HHs), algorithms that, given a number of low-level heuristics, iteratively select and apply heuristics to a solution. The HH we consider has a Markov model to produce sequences of low-level heuristics, which we combine with a Multi-Armed Bandit Problem (MAB)-based method to learn its parameters. This work proposes several improvements to the HH metaheuristic that yields a better learning for solving problem instances. Specifically, this is the first work in HHs to present Exponential Weights for Exploration and Exploitation (EXP3) as a learning method, an algorithm that is able to deal with adversarial settings. We also present a case study for the Vehicle Routing Problem with Time Windows (VRPTW), for which we include a list of low-level heuristics that have been proposed in the literature. We show that our algorithms can handle a large and diverse list of heuristics, illustrating that they can be easily configured to solve COPs of different nature. The computational results indicate that our algorithms are competitive methods for the VRPTW (2.16% gap on average with respect to the best known solutions), demonstrating the potential of these algorithms to solve COPs. Finally, we show how algorithms can even detect low-level heuristics that do not contribute to finding better solutions to the problem.& COPY
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0377-2217 ISBN Medium
Area Expedition Conference
Notes WOS:001060399900001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1877
Permanent link to this record
 

 
Author Lagos, F.; Boland, N.; Savelsbergh, M.
Title Dynamic discretization discovery for solving the Continuous Time Inventory Routing Problem with Out-and-Back Routes Type
Year 2022 Publication Computers & Operations Research Abbreviated Journal Comput. Oper. Res.
Volume 141 Issue Pages 105686
Keywords NETWORK DESIGN; CUT ALGORITHM; DECOMPOSITION; POLICIES
Abstract In time dependent models, the objective is to find the optimal times (continuous) at which activities occur and resources are utilized. These models arise whenever a schedule of activities needs to be constructed. A common approach consists of discretizing the planning time and then restricting the decisions to those time points. However, this approach leads to very large formulations that are intractable in practice. In this work, we study the Continuous Time Inventory Routing Problem with Out-and-Back Routes (CIRP-OB). In this problem, a company manages the inventory of its customers, resupplying a single product from a single facility during a finite time horizon. The product is consumed at a constant rate (product per unit of time) by each customer. The customers have local storage capacity. The goal is to find the minimum cost delivery plan with out-and-back routes only that ensures that none of the customers run out of product during the planning period. We study the Dynamic Discovery Discretization algorithm (DDD) to solve the CIRP-OB by using partially constructed time-expanded networks. This method iteratively discovers time points needed in the network to find optimal continuous time solutions. We test this method by using randomly generated instances in which we find provable optimal solutions.
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0305-0548 ISBN Medium
Area Expedition Conference
Notes WOS:000762974200008 Approved
Call Number UAI @ alexi.delcanto @ Serial 1541
Permanent link to this record
 

 
Author Lagos, F.; Klapp, M.A.; Toriello, A.
Title Branch-and-price for routing with probabilistic customers Type
Year 2023 Publication Computers & Industrial Engineering Abbreviated Journal Comput. Ind. Eng.
Volume 183 Issue Pages 109429
Keywords Vehicle routing; Probabilistic routing; Column generation
Abstract We study the Vehicle Routing Problem with Probabilistic Customers (VRP-PC), a two-stage optimization model, which is a fundamental building block within the broad family of stochastic routing problems. This problem is mainly motivated by logistics distribution networks in which customers receive frequent delivery services, and by the last mile problem faced by companies such as UPS and FedEx. In a first stage before customer service requests realize, a dispatcher determines a set of vehicle routes serving all potential customer locations. In a second stage occurring after observing all customer requests, vehicles execute planned routes skipping all locations of customers not requiring service. The objective is to minimize the expected vehicle travel cost assuming known customer realization probabilities. We propose a column generation framework to solve the VRP-PC to a given optimality tolerance. Specifically, we present two novel algorithms, one that under -approximates a solution's expected cost, and another that uses its exact expected cost. Each algorithm is equipped with a route pricing mechanism that iteratively improves the approximation precision of a route's reduced cost; this produces fast route insertions at the start of the algorithm and reaches termination conditions at the end of the execution. Compared to branch-and-cut algorithms for arc-based formulations, our framework can more readily incorporate sequence-dependent constraints, which are typically required in routing problems. We provide a priori and a posteriori performance guarantees for these algorithms, and demonstrate their effectiveness via a computational study on instances with realization probabilities ranging from 0.5 to 0.9.
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0360-8352 ISBN Medium
Area Expedition Conference
Notes WOS:001047678500001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1858
Permanent link to this record
 

 
Author Lagos, F.; Moreno, S.; Yushimito, W.F.; Brstilo, T.
Title Urban Origin–Destination Travel Time Estimation Using K-Nearest-Neighbor-Based Methods Type
Year 2024 Publication Mathematics Abbreviated Journal Mathematics
Volume 12 Issue 8 Pages 1255
Keywords origin� destination travel time; machine learning; k-nearest neighbor; adaptive algorithm; haversine distance
Abstract Improving the estimation of origin�destination (O-D) travel times poses a formidable challenge due to the intricate nature of transportation dynamics. Current deep learning models often require an overwhelming amount of data, both in terms of data points and variables, thereby limiting their applicability. Furthermore, there is a scarcity of models capable of predicting travel times with basic trip information such as origin, destination, and starting time. This paper introduces novel models rooted in the k-nearest neighbor (KNN) algorithm to tackle O-D travel time estimation with limited data. These models represent innovative adaptations of weighted KNN techniques, integrating the haversine distance of neighboring trips and incorporating correction factors to mitigate prediction biases, thereby enhancing the accuracy of travel time estimations for a given trip. Moreover, our models incorporate an adaptive heuristic to partition the time of day, identifying time blocks characterized by similar travel-time observations. These time blocks facilitate a more nuanced understanding of traffic patterns, enabling more precise predictions. To validate the effectiveness of our proposed models, extensive testing was conducted utilizing a comprehensive taxi trip dataset sourced from Santiago, Chile. The results demonstrate substantial improvements over existing state-of-the-art models (e.g., MAPE between 35 to 37% compared to 49 to 60% in other methods), underscoring the efficacy of our approach. Additionally, our models unveil previously unrecognized patterns in city traffic across various time blocks, shedding light on the underlying dynamics of urban mobility.
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 2227-7390 ISBN Medium
Area Expedition Conference
Notes Approved
Call Number UAI @ alexi.delcanto @ Serial 1962
Permanent link to this record
 

 
Author Lagos, F.; Schreiber, M.R.; Parsons, S.G.; Zurlo, A.; Mesa, D.; Gansicke, B.T.; Brahm, R.; Caceres, C.; Canovas, H.; Hernandez, M.S.; Jordan, A.; Koester, D.; Schmidtobreick, L.; Tappert, C.; Zorotovic, M.
Title The White Dwarf Binary Pathways Survey -III. Contamination from hierarchical triples containing a white dwarf Type
Year 2020 Publication Monthly Notices Of The Royal Astronomical Society Abbreviated Journal Mon. Not. Roy. Astron. Soc.
Volume 494 Issue 1 Pages 915-922
Keywords methods: numerical; methods: statistical; binaries: close; stars: kinematics and dynamics
Abstract The White Dwarf Binary Pathways Survey aims at increasing the number of known detached A, F, G, and K main-sequence stars in close orbits with white dwarf companions (WD+AFGK binaries) to refine our understanding about compact binary evolution and the nature of Supernova Ia progenitors. These close WD+AFGK binary stars are expected to form through common envelope evolution, in which tidal forces tend to circularize the orbit. However, some of the identified WD+AFGK binary candidates show eccentric orbits, indicating that these systems are either formed through a different mechanism or perhaps they are not close WD+AFGK binaries. We observed one of these eccentric WD+AFGK binaries with SPHERE and find that the system TYC 7218-934-1 is in fact a triple system where the WD is a distant companion. The inner binary likely consists of the G-type star plus an unseen low-mass companion in an eccentric orbit. Based on this finding, we estimate the fraction of triple systems that could contaminate the WD+AFGK sample. We find that less than 15 per cent of our targets with orbital periods shorter than 100 d might be hierarchical triples.
Address [Lagos, F.; Schreiber, M. R.; Hernandez, M-S; Tappert, C.; Zorotovic, M.] Univ Valparaiso, Inst Fis & Astron, Valparaiso, Chile, Email: felipe.lagos@pmigrado.uv.cl;
Corporate Author Thesis
Publisher Oxford Univ Press Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0035-8711 ISBN Medium
Area Expedition Conference
Notes WOS:000535885900070 Approved
Call Number UAI @ eduardo.moreno @ Serial 1197
Permanent link to this record