1,721,278 research outputs found
The granular tabu search and its application to the vehicle-routing problem
No full textWe describe a new variant, called granular tabu search, of the well-known tabu-search approach. The method uses an effective intensification/ diversification tool that can be successfully applied to a wide class of graph-theoretic and combinatorial-optimization problems. Granular tabu search is based on the use of drastically restricted neighborhoods, not containing the moves that involve only elements that are not likely to belong to good feasible solutions. These restricted neighborhoods are called granular, and may be seen as an efficient implementation of candidate-list strategies proposed for tabu-search algorithms. Results of computational testing of the proposed approach on the well-known symmetric capacitated and distance-constrained vehicle-routing problem are discussed, showing that the approach is able to determine very good solutions within short computing times
Models, relaxations and exact approaches for the capacitated vehicle routing problem
No full textIn this paper we review the exact algorithms based on the branch and bound approach proposed in the last years for the solution of the basic version of the vehicle routing problem (VRP), where only the vehicle capacity constraints are considered. These algorithms have considerably increased the size of VRPs that can be solved with respect to earlier approaches. Moreover, at least for the case in which the cost matrix is asymmetric, branch and bound algorithms still represent the state-of-the-art with respect to the exact solution. Computational results comparing the performance of different relaxations and algorithms on a set of benchmark instances are presented. We conclude by examining possible future directions of research in this field. © 2002 Elsevier Science B.V
An exact algorithm for the vehicle routing problem with backhauls
No full textThe Vehicle Routing Problem with Backhauls is an extension of the capacitated Vehicle Routing Problem where the customers' set is partitioned into two subsets. The first is the set of Linehaul, or Delivery, customers, while the second is the set of Backhaul, or Pickup, customers. The problem is known to be NP-hard in the strong sense and finds many practical applications in distribution planning. In this paper we consider, in a unified framework, both the symmetric and the asymmetric versions of the vehicle routing problem with backhauls, for which we present a new integer linear programming model and a Lagrangian lower bound which is strengthened in a cutting plane fashion. The Lagrangian lower bound is then combined, according to the additive approach, with a lower bound obtained by dropping the capacity constraints, thus obtaining an effective overall bounding procedure. A branch-and-bound algorithm, reduction procedures and dominance criteria are also described. Computational tests on symmetric and asymmetric instances from the literature, involving up to 100 customers, are given, showing the effectiveness of the proposed approach
An exact algorithm for the multitrip vehicle routing problem
No full textThe multitrip vehicle routing problem (MTVRP) is a variant of the capacitated vehicle routing problem where each vehicle can perform a subset of routes, called a vehicle schedule, subject to maximum driving time constraints. Despite its practical importance, the MTVRP has received little attention in the literature. Few heuristics have been proposed, and only an exact algorithm has been presented for a variant of the MTVRP with customer time window constraints and unlimited driving time for each vehicle. We describe two setpartitioning- like formulations of the MTVRP. The first formulation requires the generation of all feasible routes, whereas the second formulation is based on the generation of all feasible schedules. We study valid lower bounds, based on the linear relaxations of both formulations enforced with valid inequalities, that are embedded into an exact solution method. The computational results show that the proposed exact algorithm can solve MTVRP instances taken from the literature, with up to 120 customers. © 2013 INFORMS
Models and algorithms for the Traveling Salesman Problem with Time-dependent Service times
Full text linkThe Traveling Salesman Problem with Time-dependent Service times (TSP-TS) is a generalization of the Asymmetric TSP, in which the service time at each customer is given by a (linear or quadratic) function of the corresponding start time of service. TSP-TS calls for determining a Hamiltonian tour (i.e. a tour visiting each customer exactly once) that minimizes the total tour duration, given by the sum of travel and service times. We propose a new Mixed Integer Programming model for TSP-TS, that is enhanced by lower and upper bounds that improve previous bounds from the literature, and by incorporating exponentially many subtour elimination constraints, that are separated in a dynamic way. In addition, we develop a multi-operator genetic algorithm and two Branch-and-Cut methods, based on the proposed model. The algorithms are tested on benchmark symmetric instances from the literature, and compared with an existing approach. The computational results show that the proposed exact methods are able to prove the optimality of the solutions found for a larger set of instances in shorter computing times. We also tested the Branch-and-Cut algorithms on larger size symmetric instances with up to 58 nodes and on asymmetric instances with up to 45 nodes, demonstrating the effectiveness of the proposed algorithms. In addition, we tested the genetic algorithm on symmetric and asymmetric instances with up to 200 nodes
The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace
No full textThe integration of drones into civil airspace is one of the most challenging problems for the automation of the controlled airspace, and the optimization of the drone route is a key step for this process. In this paper, we optimize the route planning of a drone mission that consists of departing from an airport, flying over a set of mission way points and coming back to the initial airport. We assume that during the mission a set of piloted aircraft flies in the same airspace and thus the cost of the drone route depends on the air traffic and on the avoidance maneuvers used to prevent possible conflicts. Two air traffic management techniques, i.e., routing and holding, are modeled in order to maintain a minimum separation between the drone and the piloted aircraft. The considered problem, called the Time Dependent Traveling Salesman Planning Problem in Controlled Airspace (TDTSPPCA), relates to the drone route planning phase and aims to minimize the total operational cost. Two heuristic algorithms are proposed for the solution of the problem. A mathematical formulation based on a particular version of the Time Dependent Traveling Salesman Problem, which allows holdings at mission way points, and a Branch and Cut algorithm are proposed for solving the TDTSPPCA to optimality. An additional formulation, based on a Travelling Salesman Problem variant that uses specific penalties to model the holding times, is proposed and a Cutting Plane algorithm is designed. Finally, computational experiments on real-world air traffic data from Milano Linate Terminal Maneuvering Area are reported to evaluate the performance of the proposed formulations and of the heuristic algorithms
- …
