Publications related to Arc routing

Differentially private multi-agent constraint optimization

Boi Faltings, Aleksei Triastcyn, Sankarshan Damle, Sujit Prakash Gujar

Distributed constraint optimization (DCOP) is a framework in which multiple agents with private constraints (or preferences) cooperate to achieve a common goal optimally. DCOPs are applicable in several multi-agent coordination/allocation problems, such as ...

Springer2024

Contextual Stochastic Bilevel Optimization

Daniel Kuhn, Yifan Hu, Andreas Krause, Jie Wang

We introduce contextual stochastic bilevel optimization (CSBO) -- a stochastic bilevel optimization framework with the lower-level problem minimizing an expectation conditioned on some contextual information and the upper-level decision variable. This fram ...

2023

Waste collection inventory routing with non-stationary stochastic demands

Michel Bierlaire, Sacha Varone, Mohammad Yousef Maknoon, Iliya Dimitrov Markov

We solve a rich routing problem inspired from practice, in which a heterogeneous fixed fleet is used for collecting recyclable waste from large containers over a finite planning horizon. Each container is equipped with a sensor that communicates its level ...

PERGAMON-ELSEVIER SCIENCE LTD2020

The electric autonomous dial-a-ride problem

Claudia Bongiovanni

This thesis develops mathematical programming frameworks to operate electric autonomous vehicles in the context of ride-sharing services. The introduced problem is a novel variant of the Dial-a-Ride Problem (DARP), denoted by the electric Autonomous Dial-a ...

EPFL2020

The electric autonomous dial-a-ride problem

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

In the Dial-a-Ride-Problem (DARP) a fleet of vehicles provides shared-ride services to users specifying their origin, destination, and preferred arrival time. Typically, the problem consists of finding minimum cost routes, satisfying operational constraint ...

Elsevier2019

Stability-Aware Integrated Routing and Scheduling for Control Applications in Ethernet Networks

Amir Aminifar

Real-time communication over Ethernet is becoming important in various application areas of cyber-physical systems such as industrial automation and control, avionics, and automotive networking. Since such applications are typically time critical, Ethernet ...

2018

Constant factor approximation for ATSP with two edge weights

Ola Nils Anders Svensson, Jakub Tarnawski

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was give ...

SPRINGER HEIDELBERG2018

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Ola Nils Anders Svensson, Jakub Tarnawski

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of th ...

ASSOC COMPUTING MACHINERY2018

Vehicle routing with cross-dock selection

Mohammad Yousef Maknoon

The vehicle routing problem with cross-dock selection is a variant of the vehicle routing problem containing spatial and load synchronization constraints by which products are transferred and processed via at least one cross-dock. This paper presents a mat ...

Pergamon-Elsevier Science Ltd2016

Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities

Michel Bierlaire, Sacha Varone, Iliya Dimitrov Markov

We consider a complex recyclable waste collection problem that extends the class of vehicle routing problems with intermediate facilities by integrating a heterogeneous fixed fleet and a flexible assignment of destination depots. Several additional side co ...

Pergamon-Elsevier Science Ltd2016

Constant Factor Approximation for ATSP with Two Edge Weights

Ola Nils Anders Svensson, Jakub Tarnawski

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was give ...

Springer Int Publishing Ag2016

Approximation algorithms for geometric dispersion

Alfonso Bolívar Cevallos Manzano

The most basic form of the max-sum dispersion problem (MSD) is as follows: given n points in R^q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This is a prominent diversity problem, with w ...

EPFL2016

Removing and Adding Edges for the Traveling Salesman Problem

Ola Nils Anders Svensson

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a d ...

Assoc Computing Machinery2016

Ant Metaheuristics with Adapted Personalities for Vehicle Routing Problem

Rémy Glardon, Nicolas Zufferey, Jaime Farres

At each generation of an ant algorithm, each ant builds a solution step by step by adding an element to it. Each choice is based on the greedy force (short term profit or heuristic information) and the trail system (central memory which collects informatio ...

2015

Ant Metaheuristic with Adapted Personalities for the Vehicle Routing Problem

Rémy Glardon, Nicolas Zufferey, Jaime Farres

At each generation of an ant algorithm, each ant builds a solution step by step by adding an element to it. Each choice is based on the greedy force (short term profit or heuristic information) and the trail system (central memory which collects informatio ...

Springer Int Publishing Ag2015

Generalized impedance boundary conditions for strongly absorbing obstacle: The full wave equation

Hoài-Minh Nguyên

This paper is devoted to the study of the generalized impedance boundary conditions (GIBCs) for a strongly absorbing obstacle in the time regime in two and three dimensions. The GIBCs in the time domain are heuristically derived from the corresponding cond ...

World Scientific Publishing2015

Pliable Index Coding

Christina Fragouli, Siddhartha Brahma

We formulate a new variant of the index coding problem, where instead of demanding a specific message, clients are pliable, and are interested in receiving any t messages that they do not have. We term this problem pliable index coding or PICOD(t). We prov ...

Ieee-Inst Electrical Electronics Engineers Inc2015

Approximation algorithms for regret minimization in vehicle routing problems

Adrian Aloysius Bock

In this thesis, we present new approximation algorithms as well as hardness of approximation results for NP-hard vehicle routing problems related to public transportation. We consider two different problem classes that also occur frequently in areas such a ...

EPFL2014

Neutral solar photo-Fenton degradation of 4-nitrophenol on iron-enriched hybrid montmorillonite-alginate beads (Fe-MABs)

César Pulgarin, Salvatore Barreca

Hybrid montmorillonite-alginate beads (MABs) were prepared by the ion-gelation method from alginate and montmorillonite clay suspension dropped in a calcium chloride solution. Similarly, iron-enriched beads (Fe-MABs) were prepared using iron-exchanged mont ...

Elsevier Science Sa2014

The School Bus Problem on Trees

Laura Sanità, Adrian Aloysius Bock

The School Bus Problem is an NP-hard vehicle routing problem in which the goal is to route buses that transport children to a school such that for each child, the distance travelled on the bus does not exceed the shortest distance from the child's home to ...

Springer US2012