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.     

Comparing local search metaheuristics for the maximum diversity problem

The Maximum Diversity Problem (MDP) requires to extract a subset M of given cardinality from a set N, maximising the sum of the pair-wise diversities between the extracted elements. The MDP has recently been the subject of much research, and several sophisticated heuristics have been proposed to solve it. The present work compares four local search metaheuristics for the MDP, all based on the same Tabu Search procedure, with the aim to identify what additional elements provide the strongest improvement. The four metaheuristics are an Exploring Tabu Search, a Scatter Search, a Variable Neighbourhood Search and a simple Random Restart algorithm. All of them prove competitive with the best algorithms proposed in the literature. Quite surprisingly, the best ones are the simple Random Restart algorithm and a Variable Neighbourhood Search algorithm with an unusual parameter setting, which makes it quite close to random restart. Although this is probably related to the elementary structure of the MDP, it also suggests that, more often than expected, simpler algorithms might be better.     

An Iterated Local Search heuristic for the Heterogeneous Fleet Vehicle Routing Problem

This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP is $\mathcal{NP}$ -hard since it is a generalization of the classical Vehicle Routing Problem (VRP), in which clients are served by a heterogeneous fleet of vehicles with distinct capacities and costs. The objective is to design a set of routes in such a way that the sum of the costs is minimized. The proposed algorithm is based on the Iterated Local Search (ILS) metaheuristic which uses a Variable Neighborhood Descent procedure, with a random neighborhood ordering (RVND), in the local search phase. To the best of our knowledge, this is the first ILS approach for the HFVRP. The developed heuristic was tested on well-known benchmark instances involving 20, 50, 75 and 100 customers. These test-problems also include dependent and/or fixed costs according to the vehicle type. The results obtained are quite competitive when compared to other algorithms found in the literature.     

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.     

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 Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints

We present a metaheuristic methodology for the Capacitated Vehicle Routing Problem with two-dimensional loading constraints (2L-CVRP). 2L-CVRP is a generalisation of the Capacitated Vehicle Routing Problem, in which customer demand is formed by a set of two-dimensional, rectangular, weighted items. The purpose of this problem is to produce the minimum cost routes, starting and terminating at a central depot, to satisfy the customer demand. Furthermore, the transported items must be feasibly packed into the loading surfaces of the vehicles. We propose a metaheuristic algorithm which incorporates the rationale of Tabu Search and Guided Local Search. The loading aspects of the problem are tackled using a collection of packing heuristics. To accelerate the search process, we reduce the neighbourhoods explored, and employ a memory structure to record the loading feasibility information. Extensive experiments were conducted to calibrate the algorithmic parameters. The effectiveness of the proposed metaheuristic algorithm was tested on benchmark instances and led to several new best solutions.     

Efficient elementary and restricted non-elementary route pricing

Column generation is involved in the current most efficient approaches to routing problems. Set partitioning formulations model routing problems by considering all possible routes and selecting a subset that visits all customers. These formulations often produce tight lower bounds and require column generation for their pricing step. The bounds in the resulting branch-and-price are tighter when elementary routes are considered, but this approach leads to a more difficult pricing problem. Balancing the pricing with route relaxations has become crucial for the efficiency of the branch-and-price for routing problems. Recently, the ng-routes relaxation was proposed as a compromise between elementary and non-elementary routes. The ng-routes are non-elementary routes with the restriction that when following a customer, the route is not allowed to visit another customer that was visited before if they belong to a dynamically computed set. The larger the size of these sets, the closer the ng-route is to an elementary route. This work presents an efficient pricing algorithm for ng-routes and extends this algorithm for elementary routes. Therefore, we address the Shortest Path Problem with Resource Constraint (SPPRC) and the Elementary Shortest Path Problem with Resource Constraint (ESPPRC). The proposed algorithm combines the Decremental State-Space Relaxation technique (DSSR) with completion bounds. We apply this algorithm for the Generalized Vehicle Routing Problem (GVRP) and for the Capacitated Vehicle Routing Problem (CVRP), demonstrating that it is able to price elementary routes for instances up to 200 customers, a result that doubles the size of the ESPPRC instances solved to date.     

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

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

Tabu Search Heuristics for the Arc Routing Problem with Intermediate Facilities under Capacity and Length Restrictions

This paper deals with the Arc Routing Problem with Intermediate Facilities under Capacity and Length Restrictions(CLARPIF), a variant of the classical Capacitated Arc Routing Problem(CARP), in which vehicles may unload or replenish at intermediate facilities and the length of any route may not exceed a specified upper bound. Three heuristics are developed for the CLARPIF: the first is a constructive procedure based on a partitioning approach while the second and the third are tailored Tabu Search procedures. Computational results on a set of benchmark instances with up to 50 vertices and 92 required edges are presented and analyzed.     

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.     

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.     

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.     

A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls

We consider an extension of the capacitated Vehicle Routing Problem (VRP), known as the Vehicle Routing Problem with Backhauls (VRPB), in which the set of customers is partitioned into two subsets: Linehaul and Backhaul customers. Each Linehaul customer requires the delivery of a given quantity of product from the depot, whereas a given quantity of product must be picked up from each Backhaul customer and transported to the depot. VRPB is known to be NP-hard in the strong sense, and many heuristic algorithms were proposed for the approximate solution of the problem with symmetric or Euclidean cost matrices. We present a cluster-first-route-second heuristic which uses a new clustering method and may also be used to solve problems with asymmetric cost matrix. The approach exploits the information of the normally infeasible VRPB solutions associated with a lower bound. The bound used is a Lagrangian relaxation previously proposed by the authors. The final set of feasible routes is built through a modified Traveling Salesman Problem (TSP) heuristic, and inter-route and intra-route arc exchanges. Extensive computational tests on symmetric and asymmetric instances from the literature show the effectiveness of the proposed approach.     

A branch-and-cut algorithm for the plant-cycle location problem

The Plant-Cycle Location Problem (PCLP) is defined on a graph G=(I∪J, E), where I is the set of customers and J is the set of plants. Each customer must be served by one plant, and the plant must be opened to serve customers. The number of customers that a plant can serve is limited. There is a cost of opening a plant, and of serving a customer from an open plant. All customers served by a plant are in a cycle containing the plant, and there is a routing cost associated to each edge of the cycle. The PCLP consists in determining which plants to open, the assignment of customers to plants, and the cycles containing each open plant and its customers, minimizing the total cost. It is an NP-hard optimization problem arising in routing and telecommunications. In this article, the PCLP is formulated as an integer linear program, a branch-and-cut algorithm is developed, and computational results on real-world data and randomly generated instances are presented. The proposed approach is able to find optimal solutions of random instances with up to 100 customers and 100 potential plants, and of instances on real-world data with up to 120 customers and 16 potential plants.     

Tabu Search heuristics for the Vehicle Routing Problem with Time Windows

This paper surveys the research on the Tabu Search heuristics for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes for a fleet of vehicles 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. In addition to describing basic features of each method, experimental results for Solomon’s benchmark test problems are presented and analyzed. This work was partially supported by the Emil Aaltonen Foundation, Liikesivistysrahasto Foundation, the Canadian Natural Science and Engineering Research Council and the TOP program funded by the Research Council of Norway. This support is gratefully acknowledged.     

A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries,Selective Pickups and Time Windows

In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers.     

A hybrid shifting bottleneck procedure algorithm for the parallel-machine job-shop scheduling problem

In practice, parallel-machine job-shop scheduling (PMJSS) is very useful in the development of standard modelling approaches and generic solution techniques for many real-world scheduling problems. In this paper, based on the analysis of structural properties in an extended disjunctive graph model, a hybrid shifting bottleneck procedure (HSBP) algorithm combined with Tabu Search (TS) metaheuristic algorithm is developed to deal with the PMJSS problem. The original-version shifting bottleneck procedure (SBP) algorithm for the job-shop scheduling (JSS) has been significantly improved to solve the PMJSS problem with four novelties: (i) a topological-sequence algorithm is proposed to decompose the PMJSS problem in a set of single-machine scheduling (SMS) and/or parallel-machine scheduling subproblems; (ii) a modified Carlier algorithm based on the proposed lemmas and the proofs is developed to solve the SMS subproblem; (iii) the Jackson rule is extended to solve the PMS subproblem; (iv) a TS metaheuristic algorithm is embedded under the framework of SBP to optimise the JSS and PMJSS cases. The computational experiments show that the proposed HSBP is very efficient in solving the JSS and PMJSS problems.     

A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm

The Vehicle Routing Problem (VRP) is one of the most well studied problems in operations research, both in real life problems and for scientific research purposes. During the last 50 years a number of different formulations have been proposed, together with an even greater number of algorithms for the solution of the problem. In this paper, the VRP is formulated as a problem of two decision levels. In the first level, the decision maker assigns customers to the vehicles checking the feasibility of the constructed routes (vehicle capacity constraints) and without taking into account the sequence by which the vehicles will visit the customers. In the second level, the decision maker finds the optimal routes of these assignments. The decision maker of the first level, once the cost of each routing has been calculated in the second level, estimates which assignment is the better one to choose. Based on this formulation, a bilevel genetic algorithm is proposed. In the first level of the proposed algorithm, a genetic algorithm is used for calculating the population of the most promising assignments of customers to vehicles. In the second level of the proposed algorithm, a Traveling Salesman Problem (TSP) is solved, independently for each member of the population and for each assignment to vehicles. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the average quality is less than 1%. More specifically in the set with the 14 classic instances proposed by Christofides, the quality is 0.479% and in the second set with the 20 large scale vehicle routing problems, the quality is 0.826%. The algorithm is ranked in the tenth place among the 36 most known and effective algorithms in the literature for the first set of instances and in the sixth place among the 16 algorithms for the second set of instances. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the Expanding Neighborhood Search Strategy is used.     

Lower and upper bounds for the m-peripatetic vehicle routing problem

The m-Peripatetic Vehicle Routing Problem (m-PVRP) consists in finding a set of routes of minimum total cost over m periods so that two customers are never sequenced consecutively during two different periods. It models for example money transports or cash machines supply, and the aim is to minimize the total cost of the routes chosen. The m-PVRP can be considered as a generalization of two well-known NP-hard problems: the Vehicle Routing Problem (VRP or 1-PVRP) and the m-Peripatetic Salesman Problem (m-PSP). In this paper we discuss some complexity results of the problem before presenting upper and lower bounding procedures. Good results are obtained not only on the m-PVRP in general, but also on the VRP and the m-PSP using classical VRP instances and TSPLIB instances.     

A column generation algorithm for the vehicle routing problem with soft time windows

The Vehicle Routing Problem with Time Windows consists of computing a minimum cost set of routes for a fleet of vehicles of limited capacity visiting a given set of customers with known demand, with the additional constraint that each customer must be visited in a specified time window. We consider the case in which time window constraints are relaxed into “soft” constraints, that is penalty terms are added to the solution cost whenever a vehicle serves a customer outside of his time window. We present a branch-and-price algorithm which is the first exact optimization algorithm for this problem.