Separating capacity constraints in the CVRP using tabu search

doi:10.1016/S0377-2217(97)00290-7

European Journal of Operational Research

Volume 106, Issues 2–3, 16 April 1998, Pages 546-557

https://doi.org/10.1016/S0377-2217(97)00290-7 Get rights and content

Abstract

Branch and Cut methods have shown to be very successful in the resolution of some hard combinatorial optimization problems. The success has been remarkable for the Symmetric Traveling Salesman Problem (TSP). The crucial part in the method is the cutting plane algorithm: the algorithm that looks for valid inequalities that cut off the current nonfeasible linear program (LP) solution. In turn this part relies on a good knowledge of the corresponding polyhedron and our ability to design algorithms that can identify violated valid inequalities. This paper deals with the separation of the capacity constraints for the Capacitated Vehicle Routing Problem (CVRP). Three algorithms are presented: a constructive algorithm, a randomized greedy algorithm and a very simple tabu search procedure. As far as we know this is the first time a metaheuristic is used in a separation procedure. The aim of this paper is to present this application. No advanced tabu technique is used. We report computational results with these heuristics on difficult instances taken from the literature as well as on some randomly generated instances. These algorithms were used in a Branch and Cut procedure that successfully solved to optimality large CVRP instances.

References (25)

M. Fisher
Vehicle routing
L. Bodin et al.
Routing and scheduling of vehicles and crews: the state of the art
Computers and Operations Research
(1983)
N. Christofides
Vehicle routing
T.L. Magnanti
Combinatorial optimization and vehicle fleet planning: Perspectives and prospects
Networks
(1981)
I.H. Osman
Vehicle routing and scheduling: applications, algorithms and developments
P. Augerat et al.
Computational results with a branch and cut code for the capacitated vehicle routing problem
T.K. Ralphs
Parallel Branch and Cut for the Vehicle Routing
D. Naddef et al.
Experiments with a branch and cut code to solve large TSP instances
(1997)
F. Glover
Tabu search-Part 1
ORSA Journal of Computing
(1989)
F. Glover
Tabu search-Part II
ORSA Journal of Computing
(1990)

E. Taillard et al.

A user's guide to tabu search

Annals of Operations Research

(1993)

D. Naddef et al.

Separation heuristics for the Traveling Salesman Problem I: generalities and comb separation

(1997)

Cited by (117)

Routing and scheduling of platform supply vessels in offshore oil and gas logistics
2024, Computers and Operations Research
In this work, we focus on an operational logistics problem that arises in the offshore oil and gas exploration and production industry. In particular, we aim to design cost-effective routes and schedules for platform supply vessels, which are routinely employed to deliver necessary supplies to the platforms as well as to collect from those platforms used materials that need to be transported back to the onshore base for maintenance, reuse, or discarding. To address the rich-featured routing problem that arises in this offshore logistics application, we introduce a novel mixed-integer linear programming formulation and propose a specialized branch-and-cut algorithm to solve such a model. Furthermore, in order to evaluate our proposed algorithm’s performance, we conduct an extensive computational study using representative benchmark instances inspired by real operational data. The computational results show that our algorithm solved the majority of those instances to optimality, demonstrating its potential for practical use in offshore oil and gas logistics operations.
A parallel branch-and-cut and an adaptive metaheuristic to solve the Family Traveling Salesman Problem
2024, Expert Systems with Applications
This paper addresses the Family Traveling Salesman Problem (FTSP), a variant of the Traveling Salesman Problem that group nodes into families. The goal is to select the best route by visiting only a subset of nodes from each family. We developed two methods to solve the FTSP: $(i)$ a parallel branch-and-cut algorithm with an efficient local search procedure (P-B&C) to obtain an optimal solution, and $(i i)$ an adaptive metaheuristic that combines the Biased Random-key Genetic Algorithm (BRKGA) with a reinforcement learning algorithm. In this case, the $Q$ -Learning algorithm controls the parameters of the BRKGA during the evolutionary process. We perform computational experiments on a well-known benchmark dataset with 185 instances. Our P-B&C proves the optimal value for 179 instances, improving the best upper bounds in 19 open instances. The new local search component of the P-B&C finds the best upper bounds for 50% of instances. The BRKGA-QL finds the optimal solution in 131 instances, improving the best upper bounds in 21 open instances. Finally, we compare our results with the best results in the literature, and both methods show robustness and efficiency in solving the FTSP.
Time window optimization for attended home service delivery under multiple sources of uncertainties
2023, Computers and Operations Research
We consider a vehicle routing problem variant to optimize time window assignments together with vehicle routing and scheduling decisions, under the uncertainties of trip time, service time and possible customers’ cancellations. We minimize the expected cost of vehicles’ overtime, idleness, and customer waiting, when also allowing to add new customers to existing schedules. We formulate a two-stage stochastic mixed-integer programming model using finite samples of the uncertain parameters, where in the first stage, we optimize vehicle routes and assign service time windows to customers, and in the second stage, we construct a linear program to compute the resultant undesirable cost given routes and time windows. We also propose a re-optimization method and an insertion-based linear program for accommodating real-time requests in a rolling horizon way for dynamic operations. To speed up computation, we further decompose the problem into three phases and propose Assignment–Routing–Scheduling heuristics. We first design three clustering algorithms based on spatial similarities to assign customers to vehicles, and then combine the nearest-neighbor and smallest-variance rules to decide the route for each vehicle. Finally, we cast the scheduling part as a Newsvendor problem variant and apply inventory approximations to derive closed-form solutions for determining time windows. We conduct numerical studies on diverse instances generated using both well-established benchmark data sets and Ford’s mobile service data, to compare different approaches and demonstrate the benefits of allowing flexible time-window assignments.
An evolutionary algorithm for solving Capacitated Vehicle Routing Problems by using local information
2022, Applied Soft Computing
The Capacitated Vehicle Routing Problem (CVRP) is a widely investigated NP-hard problem, which aims to determine the routes for a fleet of vehicles to serve a group of customers with minimum travel cost. In this paper, a fast evolutionary algorithm is proposed to solve CVRPs. To this end, a relevance matrix storing the probability that two customers are served successively by the same vehicle is calculated according to the local information of customer location and elite individuals in population. Based on the relevance matrix, an evolutionary algorithm called RMEA is proposed, where the relevance matrix is used to guide the crossover operation and accelerate the convergence of algorithm. Moreover, a relevance matrix based diversity preservation strategy is designed to increase the population diversity and solution quality. In the experiments, the proposed RMEA is compared to eight state-of-the-art heuristic methods tailored for CVRPs. Experimental results on three CVRP benchmarks demonstrate that the proposed RMEA is superior over eight compared algorithms and shows fast convergence speed.
The consistent vehicle routing problem considering path consistency in a road network
2021, Transportation Research Part B: Methodological
This paper investigates a new variant of the consistent vehicle routing problem considering path consistency based on the underlying road network (ConVRP $_{R N}$ ). It is the problem of determining a set of consistent paths for vehicles within a certain period (e.g. a week). We propose a flexible strategy to achieve path consistency, providing a discount for the cost of roads that are traversed every day. The objective is to minimize the total travel costs considering the discount for the paths’ consistent parts. We formulate the problem as a set partitioning model and a general arc-flow model, and then solve the problem by a branch-price-and-cut algorithm. The algorithm is based on a two-layer network, including an underlying road-network graph (lower layer) and a serial of customer-based graphs (upper layer). Furthermore, an innovative aggregation technique is proposed to accelerate the algorithm, which is specifically designed for ConVRP $_{R N}$ . Finally, we construct a road network based on the real road-network structure of West Jordan and demonstrate the effectiveness of our approach on a set of numerical experiments. The impact of consistency discount is also analyzed to provide information and inspiration for tactical decision making.
Improved branch-and-cut for the Inventory Routing Problem based on a two-commodity flow formulation
2021, European Journal of Operational Research
This paper examines the Inventory Routing Problem (IRP) with Maximum Level inventory policy. The IRP is a broad class of hard to solve problems with numerous practical applications in the field of freight transportation and logistics. A supplier is responsible for determining the timing and the quantity of replenishment services offered to a set of customers over a multi-period time horizon. In addition, vehicle routes have to be defined jointly with the inventory related decisions. A novel two-commodity flow formulation is introduced together with a new set of valid inequalities. On this basis, a branch-and-cut algorithm that employs methods for separating various families of cuts is proposed. Extensive computational experiments are reported on well-established benchmark data sets. The proposed solution approach outmatches results of current state-of-the-art branch-and-cut, branch-and-price, metaheuristic and mathematical programming based heuristic approaches, especially for hard-to-solve instances. Notably, we report 116 new upper bounds out of 640 problems of a well-known benchmark data set. Moreover, for the first time, we present new lower and upper bounds for the same data set with a larger number of vehicles. Finally, we improve 139 upper bounds out of 200 hard-to-solve larger problems of the IRP literature.

View all citing articles on Scopus

View full text

Separating capacity constraints in the CVRP using tabu search

Abstract

Routing and scheduling of vehicles and crews: the state of the art

Computers and Operations Research

Vehicle routing

Combinatorial optimization and vehicle fleet planning: Perspectives and prospects

Networks

Vehicle routing and scheduling: applications, algorithms and developments

Computational results with a branch and cut code for the capacitated vehicle routing problem

Parallel Branch and Cut for the Vehicle Routing

Experiments with a branch and cut code to solve large TSP instances

Tabu search-Part 1

ORSA Journal of Computing

Tabu search-Part II

ORSA Journal of Computing

A user's guide to tabu search

Annals of Operations Research

Separation heuristics for the Traveling Salesman Problem I: generalities and comb separation