The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains challenging. In this work we provide an explanation to such challenge, by proving that when demands are given as a finite set of scenarios, solving the LP relaxation of such formulation is strongly NP-Hard. We also prove a hardness result for the case of independent normal demands.     

Polyhedral study of the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP) considered in this paper occurs when goods must be delivered from a central depot to clients with known demands, usingk vehicles of fixed capacity. Each client must be assigned to exactly one of the vehicles. The set of clients assigned to each vehicle must satisfy the capacity constraint. The goal is to minimize the total distance traveled. When the capacity of the vehicles is large enough, this problem reduces to the famous traveling salesman problem (TSP). A variant of the problem in which each client is visited by at least one vehicle, called the graphical vehicle routing problem (GVRP), is also considered in this paper and used as a relaxation of CVRP. Our approach for CVRP and GVRP is to extend the polyhedral results known for TSP. For example, the subtour elimination constraints can be generalized to facets of both CVRP and GVRP. Interesting classes of facets arise as a generalization of the comb inequalities, depending on whether the depot is in a handle, a tooth, both or neither. We report on the optimal solution of two problem instances by a cutting plane algorithm that only uses inequalities from the above classes.This work was supported in part by NSF grant DDM-8901495.     

A transformation for the mixed general routing problem with turn penalties

In this paper, we study a generalization of the Mixed General Routing Problem (MGRP) with turn penalties and forbidden turns. Thus, we present a unified model of this kind of extended versions for both node- and arc-routing problems with a single vehicle. We provide a polynomial transformation of this generalization into an asymmetric travelling salesman problem, which can be considered a particular case of the MGRP. We show computational results on the exact resolution on a set of 128 instances of the new problem using a recently developed code for the MGRP.     

Optimised crossover genetic algorithm for capacitated vehicle routing problem

This paper presents a genetic algorithm for solving capacitated vehicle routing problem, which is mainly characterised by using vehicles of the same capacity based at a central depot that will be optimally routed to supply customers with known demands. The proposed algorithm uses an optimised crossover operator designed by a complete undirected bipartite graph to find an optimal set of delivery routes satisfying the requirements and giving minimal total cost. We tested our algorithm with benchmark instances and compared it with some other heuristics in the literature. Computational results showed that the proposed algorithm is competitive in terms of the quality of the solutions found.     

EVE-OPT: a hybrid algorithm for the capacitated vehicle routing problem

This paper presents EVE-OPT, a Hybrid Algorithm based on Genetic Algorithms and Taboo Search for solving the Capacitated Vehicle Routing Problem. Several hybrid algorithms have been proposed in recent years for solving this problem. Despite good results, they usually make use of highly problem-dependent neighbourhoods and complex genetic operators. This makes their application to real instances difficult, as a number of additional constraints need to be considered. The algorithm described here hybridizes two very simple heuristics and introduces a new genetic operator, the Chain Mutation, as well as a new mutation scheme. We also apply a procedure, the k-chain-moves, able to increase the neighbourhood size, thereby improving the quality of the solution with negligible computational effort. Despite its simplicity, EVE-OPT is able to achieve the same results as very complex state-of-the art algorithms.     

On the tour partitioning heuristic for the unit demand capacitated vehicle routing problem

The tour partitioning heuristic for the vehicle routing problem assumes an unlimited supply of vehicles. If the number of vehicles is fixed, this heuristic may produce infeasible solutions. We modify the heuristic to guarantee feasibility in this situation and we analyze the worst-case performance of the modified heuristic.     

The capacitated arc routing problem with refill points

This article introduces the capacitated arc routing problem with refill points (CARP-RP). The vehicle servicing arcs must be refilled on the spot by using a second vehicle. The problem consists on simultaneously determining the vehicles routes that minimize the total cost. An integer linear programming model is proposed and tested.     

The mixed capacitated general routing problem under uncertainty

We study the General Routing Problem defined on a mixed graph and with stochastic demands. The problem under investigation is aimed at finding the minimum cost set of routes to satisfy a set of clients whose demand is not deterministically known. Since each vehicle has a limited capacity, the demand uncertainty occurring at some clients affects the satisfaction of the capacity constraints, that, hence, become stochastic. The contribution of this paper is twofold: firstly we present a chance-constrained integer programming formulation of the problem for which a deterministic equivalent is derived. The introduction of uncertainty into the problem poses severe computational challenges addressed by the design of a branch-and-cut algorithm, for the exact solution of limited size instances, and of a heuristic solution approach exploring promising parts of the search space. The effectiveness of the solution approaches is shown on a probabilistically constrained version of the benchmark instances proposed in the literature for the mixed capacitated general routing problem.     

Solving arc routing problems with turn penalties

In several arc routing problems, it is necessary to take turn penalties into account when designing a solution. Traditionally, this is done through a transformation of the arc routing problem into an equivalent vertex routing problem. In this paper it is shown that a more direct approach, not resorting to such a transformation, may be more efficient.     

The school bus routing problem: A review

This paper aims to provide a comprehensive review of the school bus routing problem (SBRP). SBRP seeks to plan an efficient schedule for a fleet of school buses where each bus picks up students from various bus stops and delivers them to their designated schools while satisfying various constraints such as the maximum capacity of a bus, the maximum riding time of a student in a bus, and the time window of a school. This class of problem consists of different sub-problems involving data preparation, bus stop selection, bus route generation, school bell time adjustment, and bus scheduling. In this paper, the various assumptions, constraints, and solution methods used in the literature on SBRP are summarized. A list of issues requiring further research is also presented.     

The single vehicle routing problem with toll-by-weight scheme: A branch-and-bound approach

Expressways in China make use of the toll-by-weight scheme, in which expressway tolls are collected based on the weight and traveling distance of the vehicle. Most vehicle routing models assume that the cost of traversing each edge is equivalent to edge length or some constant; as a result, such models cannot be practically applied to the Chinese expressway transportation system. This study addresses a new single vehicle routing problem that takes the vehicle’s (laden and unladen) weight into account. To solve this problem exactly, we provide a branch-and-bound algorithm with a provably valid lower bound measure, along with five dominance checkers for additional pruning. We analyze our algorithm using instances generated from standard TSP test cases, as well as two new sets of test cases based on real expressway information from the Gansu and Jiangxi provinces in China. The algorithm can be applied to any toll scheme in which the toll per unit distance monotonically increases with weight, even if the toll function is non-linear.     

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

We present a new branch-and-cut algorithm for the capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed capacity, generalized capacity, strengthened comb, multistar, partial multistar, extended hypotour inequalities, and classical Gomory mixed-integer cuts. For each of these classes of inequalities we describe our separation algorithms in detail. Also we describe the other important ingredients of our branch-and-cut algorithm, such as the branching rules, the node selection strategy, and the cut pool management. Computational results, for a large number of instances, show that the new algorithm is competitive. In particular, we solve three instances (B-n50-k8, B-n66-k9 and B-n78-k10) of Augerat to optimality for the first time.     

Approximation algorithms for a vehicle routing problem

In this paper we investigate a vehicle routing problem motivated by a real-world application in cooperation with the German Automobile Association (ADAC). The general task is to assign service requests to service units and to plan tours for the units such as to minimize the overall cost. The characteristics of this large-scale problem due to the data volume involve strict real-time requirements. We show that the problem of finding a feasible dispatch for service units starting at their current position and serving at most k requests is NP-complete for each fixed k ≥ 2. We also present a polynomial time (2k − 1)-approximation algorithm, where again k denotes the maximal number of requests served by a single service unit. For the boundary case when k equals the total number |E| of requests (and thus there are no limitations on the tour length), we provide a -approximation. Finally, we extend our approximation results to include linear and quadratic lateness costs.     

Local search for the undirected capacitated arc routing problem with profits

This paper deals with a recently introduced routing problem variant called the undirected capacitated arc routing problem with profits (UCARPP). The UCARPP model considered in the present study is primarily aimed at generating the route set which maximizes the profit collected from a set of potential customers, represented by edges of the examined transportation network. The secondary objective is to minimize the total route travel time. The generated routes are subject both to capacity and travel time constraints. To tackle the examined problem, we propose a local search metaheuristic development which explores two solution neighborhood structures. The conducted search is effectively diversified by means of the promises concept which is based on the aspiration criteria used in tabu search approaches. The proposed algorithm was tested on UCARPP benchmark instances taken from the literature. It efficiently produced high-quality results, improving several previously best known solutions.     

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.     

Applications of the vehicle routing problem with trailers and transshipments

The vehicle routing problem with trailers and transshipments (VRPTT) is a recent and challenging extension of the well-known vehicle routing problem. The VRPTT constitutes an archetypal representative of the class of vehicle routing problems with multiple synchronization constraints (VRPMSs). In addition to the usual task covering constraints, VRPMSs require further synchronization between vehicles, concerning spatial, temporal, and load aspects. VRPMSs possess considerable practical relevance, but limited coverage in the scientific literature. The purpose of the present paper is to describe how several important types of VRPMSs, such as multi-echelon location-routing problems and simultaneous vehicle and crew routing problems, can be modelled as VRPTTs.     

Modeling and solving the mixed capacitated general routing problem

We tackle the mixed capacitated general routing problem (MCGRP) which generalizes many other routing problems. We propose an integer programming model for the MCGRP and extend some inequalities originally introduced for the capacitated arc routing problem (CARP). Identification procedures for these inequalities and for some relaxed constraints are also discussed. Finally, we describe a branch and cut algorithm including the identification procedures and present computational experiments over instances derived from the CARP.     

The pyramidal capacitated vehicle routing problem

This paper introduces the pyramidal capacitated vehicle routing problem (PCVRP) as a restricted version of the capacitated vehicle routing problem (CVRP). In the PCVRP each route is required to be pyramidal in a sense generalized from the pyramidal traveling salesman problem (PTSP). A pyramidal route is defined as a route on which the vehicle first visits customers in increasing order of customer index, and on the remaining part of the route visits customers in decreasing order of customer index.     

Multi-ant colony system (MACS) for a vehicle routing problem with backhauls

The vehicle routing problem with backhaul (VRPB) is an extension of the capacitated vehicle routing problem (CVRP). In VRPB, there are linehaul as well as backhaul customers. The number of vehicles is considered to be fixed and deliveries for linehaul customers must be made before any pickups from backhaul customers. The objective is to design routes for the vehicles so that the total distance traveled is minimized. We use multi-ant colony system (MACS) to solve VRPB which is a combinatorial optimization problem. Ant colony system (ACS) is an algorithmic approach inspired by foraging behavior of real ants. Artificial ants are used to construct a solution by using pheromone information from previously generated solutions. The proposed MACS algorithm uses a new construction rule as well as two multi-route local search schemes. An extensive numerical experiment is performed on benchmark problems available in the literature.