Search results for "Branch-and-cut"
showing 10 items of 10 documents
A New Branch-and-Cut Algorithm for the Generalized Directed Rural Postman Problem
2016
The generalized directed rural postman problem, also known as the close-enough arc routing problem, is an arc routing problem with some interesting real-life applications, such as routing for meter reading. In this article we introduce two new formulations for this problem as well as various families of new valid inequalities that are used to design and implement a branch-and-cut algorithm. The computational results obtained on test bed instances from the literature show that this algorithm outperforms the existing exact methods
Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem
2017
[EN] The generalized directed rural postman problem is an arc routing problem with many interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets closer than a certain distance to a meter, the receiver is able to record the gas, water, or electricity consumption. Therefore, the vehicle does not need to traverse every street, but only a few, to get close enough to each meter. We study an extension of this problem in which a fleet of vehicles is available. Given the characteristics of the mentioned application, the vehicles have no capacities but there is a maximum distan…
Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem
2021
The soft-clustered capacitated arc-routing problem (SoftCluCARP) is a variant of the classical capacitated arc-routing problem. The only additional constraint is that the set of required edges, that is, the streets to be serviced, is partitioned into clusters, and feasible routes must respect the soft-cluster constraint, that is, all required edges of the same cluster must be served by the same vehicle. In this article, we design an effective branch-price-and-cut algorithm for the exact solution of the SoftCluCARP. Its new components are a metaheuristic and branch-and-cut-based solvers for the solution of the column-generation subproblem, which is a profitable rural clustered postman tour …
A branch-and-cut algorithm for the Profitable Windy Rural Postman Problem
2016
[EN] In this paper we study the profitable windy rural postman problem. This is an arc routing problem with profits defined on a windy graph in which there is a profit associated with some of the edges of the graph, consisting of finding a route maximizing the difference between the total profit collected and the total cost. This problem generalizes the rural postman problem and other well-known arc routing problems and has real-life applications, mainly in snow removal operations. We propose here a formulation for the problem and study its associated polyhedron. Several families of facet-inducing inequalities are described and used in the design of a branch-and-cut procedure. The algorithm…
A Branch-and-Cut method for the Capacitated Location-Routing Problem
2011
International audience; Recent researches in the design of logistic networks have shown that the overall distribution cost may be excessive if routing decisions are ignored when locating depots. The Location-Routing Problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. The aim of this paper is to propose an exact approach based on a Branch-and-Cut algorithm for solving the LRP with capacity constraints on depots and vehicles. The proposed method is based on a zero-one linear model strengthened by new families of valid inequalities. The computational evaluation on three sets of instances (34 instances in total), with 5–10 potential depots and 20–88 …
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.
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.
A branch-and-cut algorithm for the Orienteering Arc Routing Problem
2016
[EN] In arc routing problems, customers are located on arcs, and routes of minimum cost have to be identified. In the Orienteering Arc Routing Problem (OARP),in addition to a set of regular customers that have to be serviced, a set of potential customers is available. From this latter set, customers have to be chosen on the basis of an associated profit. The objective is to find a route servicing the customers which maximize the total profit collected while satisfying a given time limit on the route.In this paper, we describe large families of facet-inducing inequalities for the OARP and present a branch-and-cut algorithm for its solution. The exact algorithm embeds a procedure which builds…
The stacker crane problem and the directed general routing problem
2015
[EN] This article deals with the polyhedral description and the resolution of the directed general routing problem (DGRP) and the stacker crane problem (SCP). The DGRP contains a large number of important arc and node routing problems as special cases, including the SCP. Large families of facet-defining inequalities for the DGRP are described and a branch-and-cut algorithm for these problems is presented. Extensive computational experiments over different sets of DGRP and SCP instances are included.
A branch-and-cut algorithm for the Team Orienteering Problem
2017
The Team Orienteering Problem aims at maximizing the total amount of profit collected by a fleet of vehicles while not exceeding a predefined travel time limit on each vehicle. In the last years, several exact methods based on different mathematical formulations were proposed. In this paper, we present a new two-index formulation with a polynomial number of variables and constraints. This compact formulation, reinforced by connectivity constraints, was solved by means of a branch-and-cut algorithm. The total number of instances solved to optimality is 327 of 387 benchmark instances, 26 more than any previous method. Moreover, 24 not previously solved instances were closed to optimality.