| Records |
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.; 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.; 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 |
