			Home About us Contact

Vehicle Routing Problem (vehicle + routing_problem)

Distribution by Scientific Domains

Mathematics and Statistics	72%

Selected Abstracts

Classical and modern heuristics for the vehicle routing problem

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 4-5 2000
G. Laporte
Abstract This article is a survey of heuristics for the Vehicle Routing Problem. It is divided into two parts: classical and modern heuristics. The first part contains well-known schemes such as, the savings method, the sweep algorithm and various two-phase approaches. The second part is devoted to tabu search heuristics which have proved to be the most successful metaheuristic approach. Comparative computational results are presented. [source]

The one-commodity pickup-and-delivery traveling salesman problem: Inequalities and algorithms

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2007
Hipólito Hernández-Pérez
Abstract This article concerns the "One-commodity Pickup-and-Delivery Traveling Salesman Problem" (1-PDTSP), in which a single vehicle of fixed capacity must either pick up or deliver known amounts of a single commodity to a given list of customers. It is assumed that the product collected from the pickup customers can be supplied to the delivery customers, and that the initial load of the vehicle leaving the depot can be any quantity. The problem is to find a minimum-cost sequence of the customers in such a way that the vehicle's capacity is never exceeded. This article points out a close connection between the 1-PDTSP and the classical "Capacitated Vehicle Routing Problem" (CVRP), and it presents new inequalities for the 1-PDTSP adapted from recent inequalities for the CVRP. These inequalities have been implemented in a branch-and-cut framework to solve to optimality the 1-PDTSP that outperforms a previous algorithm (Hernández-Pérez and Salazar-González, Discrete Appl Math 145 (2004), 126,139). Larger instances (with up to 100 customers) are now solved to optimality. The classical "Traveling Salesman Problem with Pickups and Deliveries" (TSPPD) is a particular case of the 1-PDTSP, and this observation gives an additional motivation for this article. The here-proposed algorithm for the 1-PDTSP was able to solve to optimality TSPPD instances with up to 260 customers. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 258,272 2007 [source]

Exact methods based on node-routing formulations for undirected arc-routing problems

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2006
R. Baldacci
Abstract This article proposes a new transformation of undirected arc-routing problems into equivalent node-routing problems, with emphasis on the transformation of Capacitated Arc Routing Problems (CARP) into Capacitated Vehicle Routing Problems (CVRP). For this last case, an analogue transformation has already been proposed in Pearn et al., where each required CARP edge is mapped onto a triplet of CVRP nodes. In our case, only two CVRP nodes are needed for every CARP required edge. The transformed instances have a structure and a dimension that make most CARP benchmarks solvable by state of the art CVRP techniques. We thus propose a general purpose transformation of arc into node-routing problems and new results on lower bounds and exact methods for CARP instances. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 47(1), 52,60 2006 [source]

Edge assembly-based memetic algorithm for the capacitated vehicle routing problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2009
Yuichi Nagata
Abstract Vehicle routing problems are at the heart of most decision support systems for real-life distribution problems. In vehicle routing problem a set of routes must be determined at lowest total cost for a number of resources (i.e., fleet of vehicles) located at one or several points (e.g., depots, warehouses) to efficiently service a number of demand or supply points. In this article a new memetic algorithm is suggested for the standard capacitated vehicle routing problem. The proposed algorithm combines the edge assembly (EAX) crossover with well-known local searches and allows for infeasible solutions with respect to capacity and route duration constraints after invoking the crossover. To address the constraint violation, an efficient modification algorithm is also suggested. Experimental tests on 47 standard benchmarks demonstrate that the suggested method is robust and competitive, finding new best-known solution to 20 well-studied instances and repeating the existing best-known solution for 24 problems in a reasonable computing time. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source]

A JavaÔ universal vehicle router for routing unmanned aerial vehicles

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 3 2004
R.W. Harder
Abstract We consider vehicle routing problems in the context of the Air Force operational problem of routing unmanned aerial vehicles from base locations to various reconnaissance sites. The unmanned aerial vehicle routing problem requires consideration of heterogeneous vehicles, vehicle endurance limits, time windows, and time walls for some of the sites requiring coverage, site priorities, and asymmetric travel distances. We propose a general architecture for operational research problems, specified for vehicle routing problems, that encourages object-oriented programming and code reuse. We create an instance of this architecture for the unmanned aerial vehicle routing problem and describe the components of this architecture to include the general user interface created for the operational users of the system. We employ route building heuristics and tabu search in a symbiotic fashion to provide a user-defined level-of-effort solver interface. Empirical tests of solution algorithms parameterized for solution speed reveal reasonable solution quality is attained. [source]

Classical and modern heuristics for the vehicle routing problem

Flexibility and complexity in periodic distribution problems

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 2 2007
Peter Francis
Abstract In this paper, we explore trade-offs between operational flexibility and operational complexity in periodic distribution problems. We consider the gains from operational flexibility in terms of vehicle routing costs and customer service benefits, as well as the costs of operational complexity in terms of modeling, solution methods, and implementation challenges for drivers and customers. The period vehicle routing problem (PVRP) is a variation of the classic vehicle routing problem in which delivery routes are constructed for a period of time; the PVRP with service choice (PVRP-SC) extends the PVRP to allow service (visit) frequency to become a decision of the model. For the periodic distribution problems represented by PVRP and PVRP-SC, we introduce operational flexibility levers and a set of quantitative measures to evaluate the trade-offs between flexibility and complexity. We develop a Tabu Search heuristic to incorporate a range of operational flexibility options. We analyze the potential value and the increased operational complexity of the flexibility levers. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007 [source]

A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 1 2006
Luigi Moccia
Abstract The quay crane scheduling problem consists of determining a sequence of unloading and loading movements for cranes assigned to a vessel in order to minimize the vessel completion time as well as the crane idle times. Idle times originate from interferences between cranes since these roll on the same rails and a minimum safety distance must be maintained between them. The productivity of container terminals is often measured in terms of the time necessary to load and unload vessels by quay cranes, which are the most important and expensive equipment used in ports. We formulate the quay crane scheduling problem as a vehicle routing problem with side constraints, including precedence relationships between vertices. For small size instances our formulation can be solved by CPLEX. For larger ones we have developed a branch-and-cut algorithm incorporating several families of valid inequalities, which exploit the precedence constraints between vertices. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006 [source]

A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2009
Eric Prescott-Gagnon
Abstract Given a fleet of vehicles assigned to a single depot, the vehicle routing problem with time windows (VRPTW) consists of determining a set of feasible vehicle routes to deliver goods to a set of customers while minimizing, first, the number of vehicles used and, second, total distance traveled. A large number of heuristic approaches for the VRPTW have been proposed in the literature. In this article, we present a large neighborhood search algorithm that takes advantage of the power of branch-and-price which is the leading methodology for the exact solution of the VRPTW. To ensure diversification during the search, this approach uses different procedures for defining the neighborhood explored at each iteration. Computational results on the Solomo's and the Gehring and Homberge's benchmark instances are reported. Compared to the best known methods, the proposed algorithm produces better solutions, especially on the largest instances where the number of vehicles used is significantly reduced. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source]

Edge assembly-based memetic algorithm for the capacitated vehicle routing problem

Path inequalities for the vehicle routing problem with time windows

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2007
Brian Kallehauge
Abstract In this paper we introduce a new formulation of the vehicle routing problem with time windows (VRPTW) involving only binary variables. The new formulation is based on the formulation of the asymmetric traveling salesman problem with time windows by Ascheuer et al. (Networks 36 (2000) 69,79) and has the advantage of avoiding additional variables and linking constraints. In the new formulation, time windows are modeled using path inequalities that eliminate time and capacity infeasible paths. We present a new class of strengthened path inequalities based on the polyhedral results obtained by Mak (Ph.D. Thesis, 2001) for a variant of the TSP. We study the VRPTW polytope and determine its dimension. We show that the lifted path inequalities are facet defining under certain assumptions. We also introduce precedence constraints in the context of the VRPTW. Computational experiments are performed with a branch and cut algorithm on the Solomon test problems with wide time windows. Based on results on 25-node problems, the outcome is promising compared to leading algorithms in the literature. In particular, we report a solution to a previously unsolved 50-node Solomon test problem R208. The conclusion is therefore that a polyhedral approach to the VRPTW is a viable alternative to the path formulation of Desrochers et al. (Oper Res 40 (1992), 342,354). © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 273,293 2007 [source]

Metaheuristics for the vehicle routing problem with loading constraints

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2007
Karl F. Doerner
Abstract We consider a combination of the capacitated vehicle routing problem and a class of additional loading constraints involving a parallel machine scheduling problem. The work is motivated by a real-world transportation problem occurring to a wood-products retailer, which delivers its products to a number of customers in a specific region. We solve the problem by means of two different metaheuristics algorithms: a Tabu Search and an Ant Colony Optimization. Extensive computational results are given for both algorithms, on instances derived from the vehicle routing literature and on real-world instances. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 294,307 2007 [source]

Network service scheduling and routing

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 6 2004
G. Groves
Abstract Real-life vehicle routing problems generally have both routing and scheduling aspects to consider. Although this fact is well acknowledged, few heuristic methods exist that address both these complicated aspects simultaneously. We present a graph theoretic heuristic to determine an efficient service route for a single service vehicle through a transportation network that requires a subset of its edges to be serviced, each a specified (potentially different) number of times. The times at which each of these edges are to be serviced should additionally be as evenly spaced over the scheduling time window as possible, thus introducing a scheduling consideration to the problem. Our heuristic is based on the tabu search method, used in conjunction with various well-known graph theoretic algorithms, such as those of Floyd (for determining shortest routes) and Frederickson (for solving the rural postman problem). This heuristic forms the backbone of a decision support system that prompts the user for certain parameters from the physical situation (such as the service frequencies and travel times for each network link as well as bounds in terms of acceptability of results) after which a service routing schedule is suggested as output. The decision support system is applied to a special case study, where a service routing schedule is sought for the South African national railway system by Spoornet (the semi-privatised South African national railways authority and service provider) as part of their rationalisation effort, in order to remain a lucrative company. [source]