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.     

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.      

An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts

This paper presents a new exact algorithm for the Capacitated Vehicle Routing Problem (CVRP) based on the set partitioning formulation with additional cuts that correspond to capacity and clique inequalities. The exact algorithm uses a bounding procedure that finds a near optimal dual solution of the LP-relaxation of the resulting mathematical formulation by combining three dual ascent heuristics. The first dual heuristic is based on the q-route relaxation of the set partitioning formulation of the CVRP. The second one combines Lagrangean relaxation, pricing and cut generation. The third attempts to close the duality gap left by the first two procedures using a classical pricing and cut generation technique. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between an upper bound and the lower bound achieved. The resulting problem is solved by an integer programming solver. Computational results over the main instances from the literature show the effectiveness of the proposed algorithm.      

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 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.     

Approximating the chance-constrained capacitated vehicle routing problem with robust optimization

4OR - The Capacitated Vehicle Routing Problem (CVRP) is a classical combinatorial optimization problem that aims to serve a set of customers, using a set of identical vehicles, satisfying the...     

Heuristic Procedures for the Capacitated Vehicle Routing Problem

In this paper we present two new heuristic procedures for the Capacitated Vehicle Routing Problem (CVRP). The first one solves the problem from scratch, while the second one uses the information provided by a strong linear relaxation of the original problem. This second algorithm is designed to be used in a branch and cut approach to solve to optimality CVRP instances. In both heuristics, the initial solution is improved using tabu search techniques. Computational results over a set of known instances, most of them with a proved optimal solution, are given.     

Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem

The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an algorithm that combines both approaches: it works over the intersection of two polytopes, one associated with a traditional Lagrangean relaxation over q-routes, the other defined by bound, degree and capacity constraints. This is equivalent to a linear program with exponentially many variables and constraints that can lead to lower bounds that are superior to those given by previous methods. The resulting branch-and-cut-and-price algorithm can solve to optimality all instances from the literature with up to 135 vertices. This more than doubles the size of the instances that can be consistently solved.     

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.     

BoneRoute: An Adaptive Memory-Based Method for Effective Fleet Management

This paper presents an adaptive memory-based method for solving the Capacitated Vehicle Routing Problem (CVRP), called BoneRoute. The CVRP deals with the problem of finding the optimal sequence of deliveries conducted by a fleet of homogeneous vehicles, based at one depot, to serve a set of customers. The computational performance of the BoneRoute was found to be very efficient, producing high quality solutions over two sets of well known case studies examined.     

The asymmetric travelling salesman problem and a reformulation of the Miller–Tucker–Zemlin constraints

In this paper we compare the linear programming (LP) relaxations of several old and new formulations for the asymmetric travelling salesman problem (ATSP). The main result of this paper is the derivation of a compact formulation whose LP relaxation is characterized by a set of circuit inequalities given by Grotschel and Padberg (In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A., Shmoys, D.B. (Eds.), The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, New York, 1985). The new compact model is an improved and disaggregated version of a well-known model for the ATSP based on the subtour elimination constraints (Miller et al., Journal of ACM 7 (1960) 326–329). The circuit inequalities are weaker than the subtour elimination constraints given by Dantzig et al. However, each one of these circuit inequalities can be lifted into several different facet defining inequalities which are not dominated by the subtour elimination inequalities. We show that some of the inequalities involved in the previously mentioned compact formulation can be lifted in such a way that, by projection, we obtain a small subset of the so-called D_k^← and D_k^→ inequalities. This shows that the LP relaxation of our strongest model is not dominated by the LP relaxation of the model presented by Dantzig et al. (Operations Research 2 (1954) 393–410). The new models motivate a new classification of formulations for the ATSP.     

A variable neighborhood search heuristic for periodic routing problems

The aim of this paper is to propose a new heuristic for the Periodic Vehicle Routing Problem (PVRP) without time windows. The PVRP extends the classical Vehicle Routing Problem (VRP) to a planning horizon of several days. Each customer requires a certain number of visits within this time horizon while there is some flexibility on the exact days of the visits. Hence, one has to choose the visit days for each customer and to solve a VRP for each day. Our method is based on Variable Neighborhood Search (VNS). Computational results are presented, that show that our approach is competitive and even outperforms existing solution procedures proposed in the literature. Also considered is the special case of a single vehicle, i.e. the Periodic Traveling Salesman Problem (PTSP). It is shown that slight changes of the proposed VNS procedure is also competitive for the PTSP.     

Comparing backhauling strategies in vehicle routing using Ant Colony Optimization

In the Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW) customers either receive goods from the depot or send goods to the depot and pickup or delivery at a customer has to occur within a pre-specified time window. The main objective is to minimize the total required fleet size for serving all customers. Secondary objectives are to minimize the total distance travelled or to minimize the total route duration of all vehicles. In this paper we consider a variant of the mixed VRPBTW where backhauls may be served before linehauls on any given route. Besides the modelling aspect of this variant we will study its performance implications when compared to the standard VRPBTW using a heuristic algorithm based on Ant Colony Optimization.     

Internal Twists of <Emphasis Type="Italic">L</Emphasis>-Functions. II

The Capacitated Vehicle Routing Problem (CVRP) is a classic combinatorial optimization problem with a wide range of applications in operations research. Since the CVRP is NP-hard even in a finite-dimensional Euclidean space, special attention is traditionally paid to the issues of its approximability. A major part of the known results concerning approximation algorithms and polynomial-time approximation schemes (PTAS) for this problem are obtained for its particular statement in the Euclidean plane. In this paper, we show that the approach to the development of a PTAS for the planar problem with a single depot proposed by Haimovich and Rinnooy Kan in 1985 can be successfully extended to the more general case, for instance, in spaces of arbitrary fixed dimension and for an arbitrary number of depots.     

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.     

On the stochastic vehicle routing problem with time windows,correlated travel times,and time dependency

4OR - Most state-of-the-art algorithms for the Vehicle Routing Problem, such as Branch-and-Price algorithms or meta heuristics, rely on a fast feasibility test for a given route. We devise the...     

Branch-and-cut algorithms for the split delivery vehicle routing problem

In this paper we present two exact branch-and-cut algorithms for the Split Delivery Vehicle Routing Problem (SDVRP) based on two relaxed formulations that provide lower bounds to the optimum. Procedures to obtain feasible solutions to the SDVRP from a feasible solution to the relaxed formulations are presented. Computational results are presented for 4 classes of benchmark instances. The new approach is able to prove the optimality of 17 new instances. In particular, the branch-and-cut algorithm based on the first relaxed formulation is able to solve most of the instances with up to 50 customers and two instances with 75 and 100 customers.     

Time dependent vehicle routing problem with a multi ant colony system

The Time Dependent Vehicle Routing Problem (TDVRP) consists in optimally routing a fleet of vehicles of fixed capacity when travel times are time dependent, in the sense that the time employed to traverse each given arc, depends on the time of the day the travel starts from its originating node. The optimization method consists in finding solutions that minimize two hierarchical objectives: the number of tours and the total travel time.