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

Roberto Baldacci (), Vittorio Maniezzo () and Aristide Mingozzi ()
Additional contact information
Roberto Baldacci: DISMI, University of Modena and Reggio Emilia, Viale A. Allegri, 15, 42100 Reggio Emilia, Italy
Vittorio Maniezzo: Department of Mathematics, University of Bologna, Piazza di Porta S. Donato, 5, 40127 Bologna, Italy
Aristide Mingozzi: Department of Computer Science, University of Bologna, Mura Anteo Zamboni, 7, 40127 Bologna, Italy

Operations Research, 2004, vol. 52, issue 3, 422-439

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

Keywords: programming; integer; set partitioning; relaxation/subgradient; transportation; car pooling (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (52)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1030.0106 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:52:y:2004:i:3:p:422-439

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().