An Exact Method for the Car Pooling Problem Based on Lagrangean Column Generation
- 1 June 2004
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 52 (3), 422-439
- https://doi.org/10.1287/opre.1030.0106
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
This publication has 22 references indexed in Scilit:
- A new method for solving capacitated location problems based on a set partitioning approachComputers & Operations Research, 2002
- 9. VRP with Pickup and DeliveryPublished by Society for Industrial & Applied Mathematics (SIAM) ,2002
- 7. VRP with Time WindowsPublished by Society for Industrial & Applied Mathematics (SIAM) ,2002
- A branch-and-cut algorithm for vehicle routing problemsAnnals of Operations Research, 1994
- A set partitioning approach to the multiple depot vehicle scheduling problemOptimization Methods and Software, 1994
- The pickup and delivery problem with time windowsEuropean Journal of Operational Research, 1991
- An Additive Bounding Procedure for Combinatorial Optimization ProblemsOperations Research, 1989
- A Dynamic Programming Solution of the Large-Scale Single-Vehicle Dial-A-Ride Problem with Time WindowsAmerican Journal of Mathematical and Management Sciences, 1986
- State‐space relaxation procedures for the computation of bounds to routing problemsNetworks, 1981
- An Algorithm for the Vehicle-dispatching ProblemJournal of the Operational Research Society, 1969