Search results for "Automation"
showing 10 items of 1181 documents
Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms
2005
This paper presents a survey of the research on the vehicle routing problem with time windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval, all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. Both traditional heuristic route construction methods and recent local search algorithms are examined. The basic features of each method are described, and experimental results for Solom…
Performance modeling of epidemic routing
2006
In this paper, we develop a rigorous, unified framework based on ordinary differential equations (ODEs) to study epidemic routing and its variations. These ODEs can be derived as limits of Markovian models under a natural scaling as the number of nodes increases. While an analytical study of Markovian models is quite complex and numerical solution impractical for large networks, the corresponding ODE models yield closed-form expressions for several performance metrics of interest, and a numerical solution complexity that does not increase with the number of nodes. Using this ODE approach, we investigate how resources such as buffer space and the number of copies made for a packet can be tra…
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.
Some improvements in solving radial distributions networks through the backward/forward method
2005
In the electrical radial distribution networks analysis, the backward/forward method shows good features in terms of robustness, independence from load nature, small use of hardware resources and limited calculation time. In the present paper, some procedures to improve the b/f method with the aim of reducing the calculation time are presented. The adopted procedures regard the choice of the initial values of the nodes voltages and the way in which the convergence criterion is applied. The results of some tests carried out on some electrical test systems here reported have shown the efficiency of the proposed methodology in terms of calculation time reduction, especially when solving heavil…
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…
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…