Search results for "routing"
showing 10 items of 587 documents
The Hierarchical Mixed Rural Postman Problem: Polyhedral analysis and a branch-and-cut algorithm
2017
[EN] The Hierarchical Mixed Rural Postman Problem is defined on a mixed graph where arcs and edges that require a service are divided into clusters' that have to be serviced in a hierarchical order. The problem generalizes the Mixed Rural Postman Problem and thus is NP-hard. In this paper, we provide a polyhedral analysis of the problem and propose a branch-and-cut algorithm for its solution based on the introduced classes of valid inequalities. Extensive computational experiments are reported on benchmark instances. The exact approach allows to find the optimal solutions in less than 1 hour for instances with up to 999 vertices, 2678 links, and five clusters.
Bundle generation for last-mile delivery with occasional drivers
2022
In this paper, we present the vehicle routing problem (VRP) with occasional drivers (OD) and order bundles (OB). The problem VRP-OD-OB is an extension of the VRP-OD, where instead of assigning one customer per driver, drivers are assigned bundles of customers. To deal with the bundle-to-driver assignment, a bidding system is exploited, in which a company offers a set of bundles and the drivers raise their bids. These bids depend on features such as the drivers’ destination, flexibility in deviating from the shortest path, and willingness to offer service. To generate valuable bundles of customers, we propose two strategies: (i) an innovative approach based on the creation of corridors, and …
Cost-Effective Congestion Management for Interconnection Networks Using Distributed Deterministic Routing
2010
The Interconnection networks are essential elements in current computing systems. For this reason, achieving the best network performance, even in congestion situations, has been a primary goal in recent years. In that sense, there exist several techniques focused on eliminating the main negative effect of congestion: the Head of Line (HOL) blocking. One of the most successful HOL blocking elimination techniques is RECN, which can be applied in source routing networks. FBICM follows the same approach as RECN, but it has been developed for distributed deterministic routing networks. Although FBICM effectively eliminates HOL blocking, it requires too much resources to be implemented. In this …
Evaluation of an Alternative for Increasing Switch Radix
2011
In large switch-based interconnection networks, increasing the switch radix results in a decrease in the total number of network components. In this paper we evaluate an interesting strategy for building high-radix switches going beyond the integration scale bounds. This approach is independent of the evolution of single-chip switches and will remain valid as integration scale keeps evolving. Simulation results show that with a correct internal switch design, this kind of switches achieves almost the same performance as single-chip switches with the same radix, which would be unfeasible with current integration scale.
Heuristics for a Real-World Mail Delivery Problem
2011
We are solving a mail delivery problem by combining exact and heuristic methods. The problem is a tactical routing problem as routes for all postpersons have to be planned in advance for a period of several months. As for many other routing problems, the task is to construct a set of feasible routes serving each customer exactly once at minimum cost. Four different modes (car, moped, bicycle, and walking) are available, but not all customers are accessible by all modes. Thus, the problem is characterized by three interdependent decisions: the clustering of customers into districts, the choice of a mode for each district, and the routing of the postperson through its district. We present a t…
Updating the OSPF routing protocol for communication networks by optimal decision-making over the k-shortest path algorithm
2019
Internet routing protocols such as Routing Information Protocol (RIP) pre-compute all the shortest paths by Dijkstra's algorithm (shortest path first, SPF) based on the number of hops between one node and another. Every time any communication is intended, RIP looks-up for the optimal choice in a routing table. This is a high speed method in the decision-making process but not necessary fast for data traffic as it does not take into account any real-time measure of route congestion. Open Shortest Path First (OSPF) presents a dynamic version of this problem by computing the shortest paths taking into account network features such as bandwidth, delay and load. OSPF thereby maintains link-state…
Formulations for an inventory routing problem
2014
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.
Convergence of iterative methods in perturbation theory
1995
We discuss iterative KAM type methods for eigenvalue problems in finite dimensions. We compare their convergence properties with those of straight forward power series expansions.
Advanced techniques for solving groundwater and surface water problems in the context of inverse methods and climate change.
2021
[ES] El tema de la investigación se centra en técnicas avanzadas para manejar problemas de aguas subterráneas y superficiales relacionados con métodos inversos y cambio climático. Los filtros de Kalman, con especial atención en Ensemble Smoother with Multiple Data Assimilation (ES-MDA), se analizan y mejoran para la solución de diferentes tipos de problemas inversos. En particular, la principal novedad es la aplicación de estos métodos para la identificación de series temporales. La primera parte de la tesis, luego de la descripción del método, presenta el desarrollo de un software escrito en Python para la aplicación de la metodología propuesta. El software cuenta con un flujo de trabajo f…
The smoothed particle hydrodynamics method via residual iteration
2019
Abstract In this paper we propose for the first time an iterative approach of the Smoothed Particle Hydrodynamics (SPH) method. The method is widespread in many areas of science and engineering and despite its extensive application it suffers from several drawbacks due to inaccurate approximation at boundaries and at irregular interior regions. The presented iterative process improves the accuracy of the standard method by updating the initial estimates iterating on the residuals. It is appealing preserving the matrix-free nature of the method and avoiding to modify the kernel function . Moreover the process refines the SPH estimates and it is not affected by disordered data distribution. W…