A hybrid search method for the vehicle routing problem with time windows

Vehicle Routing Problems have been extensively analyzed to reduce transportation costs. More particularly, the Vehicle Routing Problem with Time Windows (VRPTW) imposes the period of time of customer availability as a constraint, a common characteristic in real world situations. Using minimization of the total distance as the main objective to be fulfilled, this work implements an efficient algorithm which associates non-monotonic Simulated Annealing to Hill-Climbing and Random Restart. The algorithm is compared to the best results published in the literature for the 56 Solomon instances and it is shown how statistical methods can be used to boost the performance of the method.     

集货送货一体化的物流配送车辆路线问题的标号算法

本文结合实际情况,对具有时间窗约束的集货送货一体化的车辆路线问题进行了研究,针对该问题的特点,采用修正的多属性标号算法对该问题进行求解,并通过C 编程语言实现了该算法,最后用一个示例表明本文的算法是有效的.     

VRPTW的扰动恢复及其TABU SEARCH算法

本文对带时间窗的车辆路线安排扰动恢复问题进行了讨论,分析了各种可能的扰动:增加减少客户,时间窗、客户需求及路线可行性的扰动,构造了扰动模型.利用禁忌搜索算法对问题进行求解,同时通过对模型参数重新设置,得到了多个满足要求的不同的解,这样使解更具有实际可行性和有效性.     

Very large street routing problem with mixed transportation mode

Providers of logistic services in recent years are under a big pressure to lower their expenses. One way to accomplish this task is centralization of logistic activities. This creates a distribution centers with a large number of customers. The capacity or time of one delivery person is limited, but, at the same time, it usually serves many customers. This problem is often called a Street Routing Problem (SRP). This paper is a survey of aggregation heuristics that can be used for a solution of Very Large SRP (VLSRP). Performance of heuristics has been evaluated based on real data. This paper presents several approximations of length for a SRP with mixed transportation mode and compares them with published approximations used for Vehicle Routing Problem (VRP) or Traveling Salesman Problems (TSP). The method was tested in seven real world instances ranging from 11000 to 29000 customers. Several aggregation methods including two new are presented and compared for the creation of delivery districts. New measurements for the quality of aggregation are created and tested on real data with all discussed aggregation methods.     

A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows

The aim of this paper is to propose an algorithm based on the philosophy of the Variable Neighborhood Search (VNS) to solve Multi Depot Vehicle Routing Problems with Time Windows. The paper has two main contributions. First, from a technical point of view, it presents the first application of a VNS for this problem and several design issues of VNS algorithms are discussed. Second, from a problem oriented point of view the computational results show that the approach is competitive with an existing Tabu Search algorithm with respect to both solution quality and computation times.     

A new subtour elimination constraint for the vehicle routing problem

Vehicle Routing Problems (VRP) are concerned with the delivery of a single commodity from a centralized depot to a number of specified customer locations with known demands. In this paper we consider the VRP characterized by: fixed or variable number of vehicles, common vehicle capacity, distance restrictions, and minimization of total distance travelled by all vehicles as the objective. We develop an exact algorithm based on a new subtour elimination constraint. The algorithm is implemented using the CPLEX package for solving the relaxed subproblems. Computational results on 1590 simulated problems and 10 literature problems (without distance restrictions) are reported and a comparative analysis is carried out.     

A way to optimally solve a time-dependent Vehicle Routing Problem with Time Windows

In this paper we deal with a generalization of the Vehicle Routing Problem with Time Windows that considers time-dependent travel times and costs. Through several steps we transform this extension into an Asymmetric Capacitated Vehicle Routing Problem, so it can be solved both optimally and heuristically with known codes.     

Guidelines for the computational testing of machine learning approaches to vehicle routing problems

Despite the extensive research efforts and the promising results obtained by the ML community on Vehicle Routing Problems, most of the proposed techniques are still seldom employed by the OR community. With the current work, we highlight a number of challenges arising during the computational evaluation of heuristics for VRPs. The resulting guidelines aim at defining a common testing setup for the approaches designed by the two communities, thus promoting and strengthening the collaboration between them.     

A unified exact method for solving different classes of vehicle routing problems

This paper presents a unified exact method for solving an extended model of the well-known Capacitated Vehicle Routing Problem (CVRP), called the Heterogenous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles having different capacities, routing and fixed costs is used to supply a set of customers. The HVRP model considered in this paper contains as special cases: the Single Depot CVRP, all variants of the HVRP presented in the literature, the Site-Dependent Vehicle Routing Problem (SDVRP) and the Multi-Depot Vehicle Routing Problem (MDVRP). This paper presents an exact algorithm for the HVRP based on the set partitioning formulation. The exact algorithm uses three types of bounding procedures based on the LP-relaxation and on the Lagrangean relaxation of the mathematical formulation. The bounding procedures allow to reduce the number of variables of the formulation so that the resulting problem can be solved by an integer linear programming solver. Extensive computational results over the main instances from the literature of the different variants of HVRPs, SDVRP and MDVRP show that the proposed lower bound is superior to the ones presented in the literature and that the exact algorithm can solve, for the first time ever, several test instances of all problem types considered.      

Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery

This work proposes a Branch-cut-and-price (BCP) approach for the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). We also deal with a particular case of the VRPSPD, known as the Vehicle Routing Problem with Mixed Pickup and Delivery. The BCP algorithm was tested in well-known benchmark instances involving up to 200 customers. Four instances were solved for the first time and some LBs were improved.     

Two-stage vehicle routing problem with arc time windows: A mixed integer programming formulation and a heuristic approach

In this paper, we introduce a new variant of the Vehicle Routing Problem (VRP), namely the Two-Stage Vehicle Routing Problem with Arc Time Windows (TS_VRP_ATWs) which generally emerges from both military and civilian transportation. The TS_VRP_ATW is defined as finding the vehicle routes in such a way that each arc of the routes is available only during a predefined time interval with the objective of overall cost minimization. We propose a Mixed Integer Programming (MIP) formulation and a heuristic approach based on Memetic Algorithm (MA) to solve the TS_VRP_ATW. The qualities of both solution approaches are measured by using the test problems in the literature. Experimental results show that the proposed MIP formulation provides the optimal solutions for the test problems with 25 and 50 nodes, and some test problems with 100 nodes. Results also show that the proposed MA is promising quality solutions in a short computation time.     

An Ant Colony Algorithm for the Capacitated Vehicle Routing

The Vehicle Routing Problem (VRP) requires the determination of an optimal set of routes for a set of vehicles to serve a set of customers. We deal here with the Capacitated Vehicle Routing Problem (CVRP) where there is a maximum weight or volume that each vehicle can load. We developed an Ant Colony algorithm (ACO) for the CVRP based on the metaheuristic technique introduced by Colorni, Dorigo and Maniezzo. We present preliminary results that show that ant algorithms are competitive with other metaheuristics for solving CVRP.     

Some applications of the generalized vehicle routing problem

The Generalized Vehicle Routing Problem (GVRP) is an extension of the classical Vehicle Routing Problem (VRP) in which the vertex set is partitioned into clusters and vehicles must visit exactly one (or at least one)vertex per cluster. The GVRP provides a useful modelling framework for a wide variety of applications. The purpose of this paper is to provide such examples of applications and models. These include the Travelling Salesman with Profits, several VRP extensions, the Windy Routing Problem,and the design of tandem configurations for automated guided vehicles.     

A two-pheromone trail ant colony system—tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products

This paper considers a practical variant of the Vehicle Routing Problem (VRP) known as the Heterogeneous Vehicle Routing Problem with Time Windows and Multiple Products (HVRPTWMP). As the problem is NP-hard, the resolution approach proposed here is a sequential Ant Colony System (ACS)—Tabu Search algorithm. The approach introduces a two pheromone trail strategy to accelerate agents’ (ants) learning process. Its convergence to good solutions is given in terms of fleet size and travel time while completing tours and service to all customers. The proposed procedure uses regency and frequency memories form Tabu Search to further improve the quality of solutions. Experiments are carried out using instances from literature and show the effectiveness of this procedure.     

Multi-depot Multiple TSP: a polyhedral study and computational results

We study the Multi-Depot Multiple Traveling Salesman Problem (MDMTSP), which is a variant of the very well-known Traveling Salesman Problem (TSP). In the MDMTSP an unlimited number of salesmen have to visit a set of customers using routes that can be based on a subset of available depots. The MDMTSP is an NP-hard problem because it includes the TSP as a particular case when the distances satisfy the triangular inequality. The problem has some real applications and is closely related to other important multi-depot routing problems, like the Multi-Depot Vehicle Routing Problem and the Location Routing Problem. We present an integer linear formulation for the MDMTSP and strengthen it with the introduction of several families of valid inequalities. Certain facet-inducing inequalities for the TSP polyhedron can be used to derive facet-inducing inequalities for the MDMTSP. Furthermore, several inequalities that are specific to the MDMTSP are also studied and proved to be facet-inducing. The partial knowledge of the polyhedron has been used to implement a Branch-and-Cut algorithm in which the new inequalities have been shown to be very effective. Computational results show that instances involving up to 255 customers and 25 possible depots can be solved optimally using the proposed methodology.     

A unified heuristic for a large class of Vehicle Routing Problems with Backhauls

The Vehicle Routing Problem with Backhauls is a generalization of the ordinary capacitated vehicle routing problem where goods are delivered from the depot to the linehaul customers, and additional goods are brought back to the depot from the backhaul customers. Numerous ways of modeling the backhaul constraints have been proposed in the literature, each imposing different restrictions on the handling of backhaul customers. A survey of these models is presented, and a unified model is developed that is capable of handling most variants of the problem from the literature. The unified model can be seen as a Rich Pickup and Delivery Problem with Time Windows, which can be solved through an improved version of the large neighborhood search heuristic proposed by Ropke and Pisinger [An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Technical Report, DIKU, University of Copenhagen, 2004]. The results obtained in this way are comparable to or improve on similar results found by state of the art heuristics for the various variants of the problem. The heuristic has been tested on 338 problems from the literature and it has improved the best known solution for 227 of these. An additional benefit of the unified modeling and solution method is that it allows the dispatcher to mix various variants of the Vehicle Routing Problem with Backhauls for the individual customers or vehicles.     

A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem

This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP generalizes the classical Capacitated Vehicle Routing Problem by considering the existence of different vehicle types, with distinct capacities and costs. The objective is to determine the best fleet composition as well as the set of routes that minimize the total costs. The proposed hybrid algorithm is composed by an Iterated Local Search (ILS) based heuristic and a Set Partitioning (SP) formulation. The SP model is solved by means of a Mixed Integer Programming solver that interactively calls the ILS heuristic during its execution. The developed algorithm was tested in benchmark instances with up to 360 customers. The results obtained are quite competitive with those found in the literature and new improved solutions are reported.     

A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem

In this paper we consider the Cumulative Capacitated Vehicle Routing Problem (CCVRP), which is a variation of the well-known Capacitated Vehicle Routing Problem (CVRP). In this problem, the traditional objective of minimizing total distance or time traveled by the vehicles is replaced by minimizing the sum of arrival times at the customers. We propose a branch-and-cut-and-price algorithm for obtaining optimal solutions to the problem. To the best of our knowledge, this is the first published exact algorithm for the CCVRP. We present computational results based on a set of standard CVRP benchmarks and investigate the effect of modifying the number of vehicles available.     

Heuristics for multi-attribute vehicle routing problems: A survey and synthesis

The attributes of vehicle routing problems are additional characteristics or constraints that aim to better take into account the specificities of real applications. The variants thus formed are supported by a well-developed literature, including a large variety of heuristics. This article first reviews the main classes of attributes, providing a survey of heuristics and meta-heuristics for Multi-Attribute Vehicle Routing Problems (MAVRP). It then takes a closer look at the concepts of 64 remarkable meta-heuristics, selected objectively for their outstanding performance on 15 classic MAVRP with different attributes. This cross-analysis leads to the identification of “winning strategies” in designing effective heuristics for MAVRP. This is an important step in the development of general and efficient solution methods for dealing with the large range of vehicle routing variants.     

On a periodic vehicle routing problem

This paper deals with a study on a variant of the Periodic Vehicle Routing Problem (PVRP). As in the traditional Vehicle Routing Problem, customer locations each with a certain daily demand are given, as well as a set of capacitated vehicles. In addition, the PVRP has a horizon, say T days, and there is a frequency for each customer stating how often within this T-day period this customer must be visited. A solution to the PVRP consists of T sets of routes that jointly satisfy the demand constraints and the frequency constraints. The objective is to minimize the sum of the costs of all routes over the planning horizon. We develop different algorithms solving the instances of the case studied. Using these algorithms we are able to realize considerable cost reductions compared to the current situation.