Search results for " Routing"
showing 10 items of 229 documents
A flexible and tunable route discovery mechanism for on-demand protocols
2004
Mobile ad-hoc networks are characterized by multihop wireless links and absence of cellular infrastructure. For the last years, routing has been the area under most intensive research. In particular, on-demand routing protocols proposed are extremely attractive due to their low-overhead and efficiency. Currently, wireless ad-hoc networks lack multipath routing protocols. Multipath routing enables increased QoS support, load balancing and enhanced route stability. In this paper we present a new route discovery solution that increases the number of routes found, while reducing the routing overhead when compared to previous proposals. Simulation results show that the additional routing overhea…
Logic-Based Distributed Routing for NoCs
2008
The design of scalable and reliable interconnection networks for multicore chips (NoCs) introduces new design constraints like power consumption, area, and ultra low latencies. Although 2D meshes are usually proposed for NoCs, heterogeneous cores, manufacturing defects, hard failures, and chip virtualization may lead to irregular topologies. In this context, efficient routing becomes a challenge. Although switches can be easily configured to support most routing algorithms and topologies by using routing tables, this solution does not scale in terms of latency and area. We propose a new circuit that removes the need for using routing tables. The new mechanism, referred to as logic-based dis…
In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem
2015
Recently, Bode and Irnich [Bode C, Irnich S (2012) Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60(5):1167–1182] presented a cut-first branch-and-price-second algorithm for solving the capacitated arc-routing problem (CARP). The fundamental difference to other approaches for exactly solving the CARP is that the entire algorithm works directly on the typically sparse underlying graph representing the street network. This enables the use of highly efficient dynamic programming-based pricing algorithms to solve the column-generation subproblem also known as the pricing problem. The contribution of this paper is the in-depth analysis of the CARP pricing…
The Capacitated Arc Routing Problem: Lower bounds
1992
In this paper, we consider the Capacitated Arc Routing Problem (CARP), in which a fleet of vehicles, based on a specified vertex (the depot) and with a known capacity Q, must service a subset of the edges of a graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity. New lower bounds are developed for this problem, producing at least as good results as the already existing ones. Three of the proposed lower bounds are obtained from the resolution of a minimum cost perfect matching problem. The fourth one takes into account the vehicle capacity and is computed using a dynamic programming algorithm. Computational results, in which these bounds…
Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem
2015
A dynamic time window relates to two operations that must be executed within a given time meaning that the difference between the points in time when the two operations are performed is bounded from above. The most prevalent context of dynamic time windows is when precedence is given for the two operations so that it is a priori specified that one operation must take place before the other. A prominent vehicle routing problem with dynamic time windows and precedence is the dial-a-ride problem (DARP), where user-specified transportation requests from origin to destination points must be serviced. The paper presents a new branch-and-cut-and-price solution approach for the DARP, the prototypi…
Evaluating the Performance of Real Time Videoconferencing in Ad Hoc Networks Through Emulation
2008
The validation of new video protocols and applications for mobile ad hoc networks in a real environment is an important task. In this work we present Castadiva, a test-bed architecture that allows validating software solutions for ad hoc networks using low-cost, off-the-shelf devices and open source software. We use this tool to test a videocall using the OLSR protocol in different scenarios, varying the number of hops between the caller and the receiver. The results obtained in this paper show that, for an ad hoc network with a large number of hops, the quality of videocalls suffers a significant degradation even in the absence of mobility.
RutaRep: a computer package to design dispatching routes in the meat industry
2005
In this paper we present a computer program that has been developed to design the dispatching routes of a medium-sized meat company in Spain. We have modelled the real problem as a variant of the vehicle routing problem with Time Windows and implemented a number of heuristic algorithms based on the most advanced solution techniques for this problem. These algorithms have been embedded in a computer package that is intended to be used as a decision support system for the distribution manager. The program runs under Windows System and is straightforward to use. We also present some computational experiences based on real instances provided by the company. This experience shows important impro…
OLSR Mesh Networks for Broadband Access: Enhancements, Implementation and Deployment
2008
In the context of an EU FP6 project, ADHOCSYS, we have developed a reliable and cost-effective solution for broadband Internet access in rural and mountainous areas. This solution is built based on multi-hop wireless mesh networking technologies and covers many aspects such as routing, reliability, QoS, security, self-configuration, self-healing, remote network monitoring, power management etc. In this paper, we present solely the routing aspect of the developed mesh network, focusing on new routing features that have been designed, implemented, and deployed in a real-life operational network. These new features are developed based on an extended version of the OLSR protocol. The test resul…
Static and dynamic policies with RFID for the scheduling of retrieval and storage warehouse operations
2013
Warehouses are essential components of logistics and supply chains. The performance of warehouse operations significantly affects the efficiency of the whole chain it belongs to. Radio frequency identification (RFID) is an emerging technology capable of providing real-time information about the location and properties of tagged object(s), such as people, equipment or products. The objective of this article is threefold, to propose and compare different offline and online policies for the scheduling of warehouse operations, to design a tool that allows the decision maker to compare policies and environments without putting them into practice, and to study the benefits that can be obtained if…
Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic
2010
International audience; This paper proposes lower and upper bounds for the split-delivery capacitated arc-routing problem (SDCARP), a variant of the capacitated arc-routing problem in which an edge can be serviced by several vehicles. Recent papers on related problems in node routing have shown that this policy can bring significant savings. It is also more realistic in applications such as urban refuse collection, where a vehicle can become full in the middle of a street segment. This work presents the first lower bound for the SDCARP, computed with a cutting plane algorithm and an evolutionary local search reinforced by a multistart procedure and a variable neighborhood descent. Tests on …