Concept

Arc routing

Publications associées (50)

A Branch-and-Price Approach to the Vehicle Routing Problem with Simultaneous Distribution and Collection

The vehicle routing problem with simultaneous distribution and collection (VRPSDC) is the variation of the capacitated vehicle routing problem that arises when the distribution of goods from a depot to a set of customers and the collection of waste from th ...

2006

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

Matteo Salani

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a gr ...

2006

Distributed routing algorithms for sensor networks

Guillermo Barrenetxea Kobas

Recent advances in wireless communications and computing technology are enabling the emergence of low-cost devices that incorporate sensing, processing, and communication functionalities. A large number of these devices are deployed in the field to create ...

EPFL2006

On Average Throughput Benefits and Alphabet Size in Network Coding

Christina Fragouli, Emina Soljanin

We examine the throughput benefits that network coding offers with respect to the average through- put achievable by routing, where the average throughput refers to the average of the rates that the indi- vidual receivers experience. We relate these benefi ...

2006

A pricing algorithm for the vehicle routing problem with soft time windows

Matteo Salani

The Vehicle Routing Problem with Soft Time Windows consists in computing a minimum cost set of routes for a fleet of vehicles of limited capacity that must visit a given set of customers with known demand, with the additional feature that each customer exp ...

2006

Efficient routing with small buffers in dense networks

Martin Vetterli, Guillermo Barrenetxea Kobas

The analysis and design of routing algorithms for finite buffer networks requires solving the associated queue network problem which is known to be hard. We propose alternative and more accurate approximation models to the usual Jackson’s Theorem that give ...

2005

New dynamic programming algorithms for the resource constrained shortest path problem

Matteo Salani

The resource constrained elementary shortest path problem (RCESPP) arises as a pricing subproblem in branch-and-price algorithms for vehicle routing problems with additional constraints. We address the optimization of the RCESPP and we present and compare ...

2005

An online throughput-competitive algorithm for multicast routing and admission control

Monika Henzinger, Ashish Goel

We present the first polylog-competitive online algorithm for the general multicast admission control and routing problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to the expected number of reque ...

2005

Problèmes de cheminements optimaux dans les réseaux avec contraintes associées aux arcs

In this thesis we consider two optimal routing problems in networks. Both are NP-hard and are often used to modelize real life problems of large size. We first present the capacitated arc routing problem (CARP). In this problem, we have to serve a set of c ...

EPFL2000

Active Shape Models for Visual Speech Feature Extraction

Most approaches for lip modelling are based on heuristic constraints imposed by the user. We describe the use of Active Shape Models for extracting visual speech features for use by automatic speechreading systems, where the deformation of the lip model as ...

Springer Verlag1996

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search