This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Baldacci, R. Articles by Mingozzi, A. Search for Related Content

An Exact Method for the Car Pooling Problem Based on Lagrangean Column Generation

DISMI, University of Modena and Reggio Emilia, Viale A. Allegri, 15, 42100 Reggio Emilia, Italy
Department of Mathematics, University of Bologna, Piazza di Porta S. Donato, 5, 40127 Bologna, Italy
Department of Computer Science, University of Bologna, Mura Anteo Zamboni, 7, 40127 Bologna, Italy
baldacci.roberto{at}unimore.it
maniezzo{at}csr.unibo.it
mingozzi{at}csr.unibo.it

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.

Subject classifications: programming; integer; set partitioning; relaxation/subgradient; transportation; car pooling.
History: Received October 2000; revision received February 2003; accepted April 2003.