In this paper, we describe an effective exact method for solving both the capacitated vehicle routing problem (cvrp) and the vehicle routing problem with time windows (vrptw) that improves the method proposed by Baldacci et al. [Baldacci, R., N. Christofides, A. Mingozzi. 2008. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2) 351–385] for the cvrp. The proposed algorithm is based on the set partitioning (SP) formulation of the problem. We introduce a new route relaxation called ng-route, used by different dual ascent heuristics to find near-optimal dual solutions of the LP-relaxation of the SP model. We describe a column-and-cut generation algorithm strengthened by valid inequalities that uses a new strategy for solving the pricing problem. The new ng-route relaxation and the different dual solutions achieved allow us to generate a reduced SP problem containing all routes of any optimal solution that is finally solved by an integer programming solver. The proposed method solves four of the five open Solomon's vrptw instances and significantly improves the running times of state-of-the-art algorithms for both vrptw and cvrp.

The capacitated vehicle routing problem (CVRP) is the problem in which a set of identical vehicles located at a central depot is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. In this paper, we describe a new integer programming formulation for the CVRP based on a two-commodity network flow approach. We present a lower bound derived from the linear programming (LP) relaxation of the new formulation which is improved by adding valid inequalities in a cutting-plane fashion. Moreover, we present a comparison between the new lower bound and lower bounds derived from the LP relaxations of different CVRP formulations proposed in the literature. A new branch-and-cut algorithm for the optimal solution of the CVRP is described. Computational results are reported for a set of test problems derived from the literature and for new randomly generated problems.

Car pooling is a transportation service organized by a large company which encourages its employees to pick up colleagues while driving to/from work to minimize the number of private cars travelling to/from the company site. The car pooling problem consists of defining the subsets of employees that will share each car and the paths the drivers should follow, so that sharing is maximized and the sum of the path costs is minimized. The special case of the car pooling problem where all cars are identical can be modeled as a Dial-a-Ride Problem. In this paper, we propose both an exact and a heuristic method for the car pooling problem, based on two integer programming formulations of the problem. The exact method is based on a bounding procedure that combines three lower bounds derived from different relaxations of the problem. A valid upper bound is obtained by the heuristic method, which transforms the solution of a Lagrangean lower bound into a feasible solution. The computational results show the effectiveness of the proposed methods.