Vehicle routing problem with simultaneous deliveries and pickups

The vehicle routing problem with backhauls involves the delivery and pickup of goods at different customer locations. In many practical situations, however, the same customer may require both a delivery of goods from the distribution centre and a pickup of recycled items simultaneously. In this paper, an insertion-based procedure to generate good initial solutions and a heuristic based on the record-to-record travel, tabu lists, and route improvement procedures are proposed to resolve the vehicle routing problems with simultaneous deliveries and pickups. Computational characteristics of the insertion-based procedure and the hybrid heuristic are evaluated through computational experiments. Computational results show that the insertion-based procedure obtained better solutions than those found in the literature. Computational experiments also show that the proposed hybrid heuristic is able to reduce the gap between initial solutions and optimal solutions effectively and is capable of obtaining optimal solutions very efficiently for small-sized problems.     

Optimizing garbage collection vehicle routing problem with alternative fuel-powered vehicles

Abstract

This paper considers the garbage collection problem in which vehicles with multiple compartments are used to collect the garbage. The vehicles are considered to be Alternative Fuel-powered Vehicles (AFVs). Compared with the traditional fossil fuel powered vehicles, the AFVs have limited fuel tank capacity. In addition, AFVs are allowed to refuel only at the depot. We provide a mathematical formulation and develop two solution approaches to solve the problem. The first approach is based on the saving algorithm, while the second is based on the ant colony system (ACS) metaheuristic. New problem instances have been generated to evaluate the performance of the proposed algorithms.     

Selective and periodic inventory routing problem for waste vegetable oil collection

We consider a biodiesel production company that collects waste vegetable oil from source points that generate waste in large amounts. The company uses the collected waste as raw material for biodiesel production. The manager of this company needs to decide which of the present source points to include in the collection program, which of them to visit on each day, which periodic routing schedule to repeat over an infinite horizon and how many vehicles to operate such that the total collection, inventory and purchasing costs are minimized while the production requirements and operational constraints are met. For this selective and periodic inventory routing problem, we propose two different formulations, compare them and apply the better performing one on a real-world problem with 36 scenarios. We generate lower bounds using a partial linear relaxation model, and observe that the solutions obtained through our model are within 3.28% of optimality on the average. Several insights regarding the customer selection, routing and purchasing decisions are acquired with sensitivity analysis.     

Mixed integer formulations for a routing problem with information collection in wireless networks

We study a routing-collecting problem where a system of stations is considered. A vehicle is responsible for collecting information generated continuously in the stations and to deliver it to a base station. The objective is to determine the vehicle route and the collection operations, both physical and wireless, in order to maximize the amount of information collected during a time horizon. Three mixed integer programming models are introduced and a computational study is reported to compare the performance of a solver based on each one of the models.     

Heuristic method for a mixed capacitated arc routing problem: A refuse collection application

The capacitated arc routing problem (CARP) is known to be NP-hard. The aim of this paper is to present a new heuristic method to generate feasible solutions to an extended CARP on mixed graphs, inspired by the household refuse collection problem in Lisbon. Computational experience was done to compare the method with some well-known existing heuristics, generalised for a different extended CARP by Lacomme et al. [Fast algorithm for general arc routing problems, Presented at IFORS 2002 Conference, Edinburgh, UK], namely, the Path-Scanning, the Augment-Merge and the Ulusoy’s algorithms. The results reveal a good performance of the proposed heuristic method. Generally providing a good use of the vehicles capacity, the resulting sets of feasible trips may also be considered good. The test instances involve more than 300 randomly generated test problems with dimensions of up to 400 nodes and 1220 links.     

Designing routes for WEEE collection: the vehicle routing problem with split loads and date windows

This paper presents an integer programming model and describes a GRASP based algorithm to solve a vehicle routing and scheduling problem for the collection of Waste of Electric and Electronic Equipment (WEEE). The difficulty of this problem arises from the fact that it is characterized by four variants of the vehicle routing problem that have been studied independently in the literature, but not together. The experimental analysis on a large set of randomly-generated instances shows the good performance of the proposed algorithm. Moreover, computational results using real data show that the method outperforms real existing approaches to reverse logistics.     

Vehicle routing with cross-docking

Over the past decade, cross-docking has emerged as an important material handling technology in transportation. A variation of the well-known Vehicle Routing Problem (VRP), the VRP with Cross-Docking (VRPCD) arises in a number of logistics planning contexts. This paper addresses the VRPCD, where a set of homogeneous vehicles are used to transport orders from the suppliers to the corresponding customers via a cross-dock. The orders can be consolidated at the cross-dock but cannot be stored for very long because the cross-dock does not have long-term inventory-holding capabilities. The objective of the VRPCD is to minimize the total travel time while respecting time window constraints at the nodes and a time horizon for the whole transportation operation. In this paper, a mixed integer programming formulation for the VRPCD is proposed. A tabu search heuristic is embedded within an adaptive memory procedure to solve the problem. The proposed algorithm is implemented and tested on data sets provided by the Danish consultancy Transvision, and involving up to 200 pairs of nodes. Experimental results show that this algorithm can produce high-quality solutions (less than 5% away from optimal solution values) within very short computational time.     

Vehicle routing and the value of postponement

We study capacitated vehicle routing problems (CVRPs) in which the client demands occur over time and the collector or distributor performing the service can decide when to visit the clients. It has been reported in the literature that postponement of collection (or delivery) services may decrease the overall routing cost or distance. We investigate this issue in greater detail and report on experiments in different routing settings to uncover the impact of postponement on routing efficiency. We compare the results by a CVRP local search procedure with those obtained from an analytical, Continuous Approximation model. While the two approaches tend to generate similar results, the differences grow larger when the CVRPs’ bin packing characteristics become more intricate.     

Vehicle routing with split deliveries

This paper considers a relaxation of the classical vehicle routing problem (VRP), in which split deliveries are allowed. As the classical VRP, this problem is NP-hard, but nonetheless it seems more difficult to solve exactly. It is first formulated as an integer linear program. Several new classes of valid constraints are derived, and a hierarchy between these is established. A constraint relaxation branch and bound algorithm for the problem is then described. Computational results indicate that by using an appropriate combination of constraints, the gap between the lower and upper bounds at the root of the search tree can be reduced considerably. These results also confirm the quality of a previously published heuristic for this problem.     

Vehicle routing via column generation

This paper explores an approximate method for solving a routing problem in a four-level distribution which has “double-ended” demand. Routes are represented as columns in a linear program and column generation is used to improve the solution by generating new routes. The generation of new routes is based on an LP sub-problem. Its solution is rounded down to integer values to insure its feasibility as a route for inclusion in the restricted master problem. Finally, an illustrative problem is solved.     

On the capacitated vehicle routing problem

 We consider the Vehicle Routing Problem, in which a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. This difficult combinatorial problem contains both the Bin Packing Problem and the Traveling Salesman Problem (TSP) as special cases and conceptually lies at the intersection of these two well-studied problems. The capacity constraints of the integer programming formulation of this routing model provide the link between the underlying routing and packing structures. We describe a decomposition-based separation methodology for the capacity constraints that takes advantage of our ability to solve small instances of the TSP efficiently. Specifically, when standard procedures fail to separate a candidate point, we attempt to decompose it into a convex combination of TSP tours; if successful, the tours present in this decomposition are examined for violated capacity constraints; if not, the Farkas Theorem provides a hyperplane separating the point from the TSP polytope. We present some extensions of this basic concept and a general framework within which it can be applied to other combinatorial models. Computational results are given for an implementation within the parallel branch, cut, and price framework SYMPHONY. Received: October 30, 2000 / Accepted: December 19, 2001 Published online: September 5, 2002 Key words. vehicle routing problem – integer programming – decomposition algorithm – separation algorithm – branch and cut Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

A multi-stop routing problem

The problem of determining the sequence of stops and the amount of load to carry in each segment route, named the Multi-Stop Routing Problem (MSRP) is addressed. A 0/1 mixed integer linear program and formulation refinements which facilitate the solution process are presented. Since the constraint set of the MSRP includes 0/1 mixed rows, valid inequalities for this type of regions are presented. Then these results are applied to the constraint set of the routing problem, presenting additional valid inequalities. In addition, polynomial separation algorithms associated with the valid inequalities are given, computational results are also included.     

Vehicle routing considerations in distribution system design

In Distribution System Design, one minimizes total costs related to the number, locations and sizes of warehouses, and the assignment of warehouses to customers. The resulting system, while optimal in a strategic sense, may not be the best choice if operational aspects such as vehicle routing are also considered.We formulate a multicommodity, capacitated distribution planning model as anon-linear, mixed integer program. Distribution from factories to customers is two-staged via depots (warehouses) whose number and location must be chosen. Vehicle routes from depots to customers are established by considering the “fleet size and mix” problem, which also incorporates strategic decisions on fleet makeup and vehicle numbers of each type. This problem is solved as a generalized assignment problem, within an algorithm for the overall distribution/routing problem that is based on Benders decomposition. We furnish two version of our algorithm denoted Technique I and II. The latter is an enhaancement of the former and is employed at the user's discretion. Computer solution of test problems is discussed.     

Vehicle routing problem with uniform private fleet and common carrier: a node subset heuristic

Central European Journal of Operations Research - Optimizing the distribution of goods to customers is discussed on non-split delivery modification of vehicle routing problem with uniform private...     

On the collection depots location problem

In this paper we investigate the problem of locating a new facility servicing a set of demand points. A given set of collection depots is also given. When service is required by a demand point, the server travels from the facility to the demand point, then from the demand point to one of the collection depots (which provides the shortest route back to the facility), and back to the facility. The problem is analyzed and properties of the solution point are formulated and proved. Computational results on randomly generated problems are reported.     

Using mixed integer programming for solving the capacitated arc routing problem with vehicle/site dependencies with an application to the routing of residential sanitation collection vehicles

We present the Composite Approach for solving the Capacitated Arc Routing Problem with Vehicle/Site Dependencies (CARP-VSD). We also present two mixed integer programs, the Initial Fleet Mix Generator (IFM) and the Mathematical Programming Procedure (MPP), and a multi-criterion function called the Measure of Goodness. The IFM, MPP and Measure of Goodness are critical components of the Composite Approach. A key application area of the CARP-VSD is the routing of residential sanitation vehicles; throughout this paper, we derive parameters specific to this problem. In this paper, we describe the Composite Approach, the IFM, the MPP, the Measure of Goodness and work out several examples in detail.     

Path relinking for the vehicle routing problem

This paper describes a tabu search heuristic with path relinking for the vehicle routing problem. Tabu search is a local search method that explores the solution space more thoroughly than other local search based methods by overcoming local optima. Path relinking is a method to integrate intensification and diversification in the search. It explores paths that connect previously found elite solutions. Computational results show that tabu search with path relinking is superior to pure tabu search on the vehicle routing problem.