Search results for "routing"
showing 10 items of 587 documents
An efficient variable neighborhood search heuristic for very large scale vehicle routing problems
2007
In this paper, we present an efficient variable neighborhood search heuristic for the capacitated vehicle routing problem. The objective is to design least cost routes for a fleet of identically capacitated vehicles to service geographically scattered customers with known demands. The variable neighborhood search procedure is used to guide a set of standard improvement heuristics. In addition, a strategy reminiscent of the guided local search metaheuristic is used to help escape local minima. The developed solution method is specifically aimed at solving very large scale real-life vehicle routing problems. To speed up the method and cut down memory usage, new implementation concepts are use…
GRASP for the uncapacitated r-allocation p-hub median problem
2014
In this paper we propose a heuristic for the Uncapacitated r-Allocation p-Hub Median Problem. In the classical p-hub location problem, given a set of nodes with pairwise traffic demands, we must select p of them as hub locations and route all traffics through them at a minimum cost. We target here an extension, called the r-allocation p-hub median problem, recently proposed by Yaman [19], in which every node is assigned to r of the p selected hubs (r@?p) and we are restricted to route the traffic of the nodes through their associated r hubs. As it is usual in this type of problems, our method has three phases: location, assignment and routing. Specifically, we propose a heuristic based on t…
Active-guided evolution strategies for large-scale capacitated vehicle routing problems
2007
We present an adaptation of the active-guided evolution strategies metaheuristic for the capacitated vehicle routing problem. The capacitated vehicle routing problem is a classical problem in operations research in which a set of minimum total cost routes must be determined for a fleet of identical capacitated vehicles in order to service a number of demand or supply points. The applied metaheuristic combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure. The computational experiments were carried out on a set of 76 benchmark problems. The results demonstrate that the suggested method is highly competitive, …
Most Diverse Near-Shortest Paths
2021
Computing the shortest path in a road network is a fundamental problem that has attracted lots of attention. However, in many real-world scenarios, determining solely the shortest path is not enough as users want to have additional, alternative ways of reaching their destination. In this paper, we investigate a novel variant of alternative routing, termed the k-Most Diverse Near-Shortest Paths (kMDNSP). In contrast to previous work, kMDNSP aims at maximizing the diversity of the recommended paths, while bounding their length based on a user-defined constraint. Our theoretical analysis proves the NP-hardness of the problem at hand. To compute an exact solution to kMDNSP, we present an algori…
On Using a Hierarchy of Twofold Resource Allocation Automata to Solve Stochastic Nonlinear Resource Allocation Problems
2007
Recent trends in AI attempt to solve difficult NP-hard problems using intelligent techniques so as to obtain approximately-optimal solutions. In this paper, we consider a family of such problems which fall under the general umbrella of "knapsack-like" problems, and demonstrate how we can solve all of them fast and accurately using a hierarchy of Learning Automata (LA). In a multitude of real-world situations, resources must be allocated based on incomplete and noisy information, which often renders traditional resource allocation techniques ineffective. This paper addresses one such class of problems, namely, Stochastic Non-linear Fractional Knapsack Problems. We first present a completely …
Optimal Delay-Power Tradeoff in Sparse Delay Tolerant Networks: a preliminary study
2006
In this paper we present a first attempt to study analytically the tradeoff between delivery delay and resource consumption for epidemic routing in Delay Tolerant Networks. We assume that the nodes cooperate in order to minimize a common cost equal to a weighted sum of the packet delivery delay and the total number of copies, which is strongly related to the power consumption. In this framework we determine the best policy each node should deploy in a very simple scenario where all the nodes have perfect knowledge of the system status. The result is used as an ideal reference to evaluate the performance of some heuristics proposed, investigating potential performance improvements and config…
On the Distance-Constrained Close Enough Arc Routing Problem
2021
[EN] Arc routing problems consist basically of finding one or several routes traversing a given set of arcs and/or edges that must be serviced. The Close-Enough Arc Routing Problem, or Generalized Directed Rural Postman Problem, does not assume that customers are located at specific arcs, but can be serviced by traversing any arc of a given subset. Real-life applications include routing for meter reading, in which a vehicle equipped with a receiver travels a street network. If the vehicle gets within a certain distance of a meter, the receiver collects its data. Therefore, only a few streets which are close enough to the meters need to be traversed. In this paper we study the generalization…
Lower bounds and heuristics for the Windy Rural Postman Problem
2020
[EN] In this paper we present several heuristic algorithms and a cutting-plane algorithm for the Windy Rural Postman Problem. This problem contains several important Arc Routing Problems as special cases and has very interesting real-life applications. Extensive computational experiments over different sets of instances are also presented.
Separating capacity constraints in the CVRP using tabu search
1998
Abstract Branch and Cut methods have shown to be very successful in the resolution of some hard combinatorial optimization problems. The success has been remarkable for the Symmetric Traveling Salesman Problem (TSP). The crucial part in the method is the cutting plane algorithm: the algorithm that looks for valid inequalities that cut off the current nonfeasible linear program (LP) solution. In turn this part relies on a good knowledge of the corresponding polyhedron and our ability to design algorithms that can identify violated valid inequalities. This paper deals with the separation of the capacity constraints for the Capacitated Vehicle Routing Problem (CVRP). Three algorithms are prese…
Two-phase branch-and-cut for the mixed capacitated general routing problem
2015
The Mixed Capacitated General Routing Problem (MCGRP) is defined over a mixed graph, for which some vertices must be visited and some links must be traversed at least once. The problem consists of determining a set of least-cost vehicle routes that satisfy this requirement and respect the vehicle capacity. Few papers have been devoted to the MCGRP, in spite of interesting real-world applications, prevalent in school bus routing, mail delivery, and waste collection. This paper presents a new mathematical model for the MCGRP based on two-index variables. The approach proposed for the solution is a two-phase branch-and-cut algorithm, which uses an aggregate formulation to develop an effective …