A multi-destination daily carpooling problem and an ant colony based resolution method

Yuhan Guo; Gilles Goncalves; Tienté Hsu

RAIRO - Operations Research - Recherche Opérationnelle (2013)

  • Volume: 47, Issue: 4, page 399-428
  • ISSN: 0399-0559

Abstract

top
The rising car usage deriving from growth in jobs and residential population causes air pollution, energy waste and consumption of people’s time. Public transport cannot be the only answer to this increasing transport demand. Carpooling, which is based on the idea that sets of car owners pick up colleagues while driving to or from the workplace, has emerged to be a viable possibility for reducing private car usage in congested areas. Its actual practice requires a suitable information system support and, the most important, the capability of effectively solving the underlying combinatorial optimization problem. This paper describes an ant colony algorithm based hybrid approach (HAC) for solving the multi-destination carpooling problem. Experiments have been performed to confirm the efficiency and the effectiveness of the approach.

How to cite

top

Guo, Yuhan, Goncalves, Gilles, and Hsu, Tienté. "A multi-destination daily carpooling problem and an ant colony based resolution method." RAIRO - Operations Research - Recherche Opérationnelle 47.4 (2013): 399-428. <http://eudml.org/doc/275057>.

@article{Guo2013,
abstract = {The rising car usage deriving from growth in jobs and residential population causes air pollution, energy waste and consumption of people’s time. Public transport cannot be the only answer to this increasing transport demand. Carpooling, which is based on the idea that sets of car owners pick up colleagues while driving to or from the workplace, has emerged to be a viable possibility for reducing private car usage in congested areas. Its actual practice requires a suitable information system support and, the most important, the capability of effectively solving the underlying combinatorial optimization problem. This paper describes an ant colony algorithm based hybrid approach (HAC) for solving the multi-destination carpooling problem. Experiments have been performed to confirm the efficiency and the effectiveness of the approach.},
author = {Guo, Yuhan, Goncalves, Gilles, Hsu, Tienté},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {transportation; vehicle routing; carpooling problem; ant colony algorithm},
language = {eng},
number = {4},
pages = {399-428},
publisher = {EDP-Sciences},
title = {A multi-destination daily carpooling problem and an ant colony based resolution method},
url = {http://eudml.org/doc/275057},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Guo, Yuhan
AU - Goncalves, Gilles
AU - Hsu, Tienté
TI - A multi-destination daily carpooling problem and an ant colony based resolution method
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 4
SP - 399
EP - 428
AB - The rising car usage deriving from growth in jobs and residential population causes air pollution, energy waste and consumption of people’s time. Public transport cannot be the only answer to this increasing transport demand. Carpooling, which is based on the idea that sets of car owners pick up colleagues while driving to or from the workplace, has emerged to be a viable possibility for reducing private car usage in congested areas. Its actual practice requires a suitable information system support and, the most important, the capability of effectively solving the underlying combinatorial optimization problem. This paper describes an ant colony algorithm based hybrid approach (HAC) for solving the multi-destination carpooling problem. Experiments have been performed to confirm the efficiency and the effectiveness of the approach.
LA - eng
KW - transportation; vehicle routing; carpooling problem; ant colony algorithm
UR - http://eudml.org/doc/275057
ER -

References

top
  1. [1] R. Baldacci, V. Maniezzo and A. Mingozzi, An exact method for the car pooling problem based on Lagrangian column generation. Oper. Res.52 (2004) 422–439. Zbl1165.90555
  2. [2] C. Blumenthal, S. Michalak, B. Goble, M. Garner, M. Haselkorn and J. Spyridakis, Bellevue smart traveler: Design, demonstration and assessment, Internet, USA (1997). 
  3. [3] R.W. Calvo, F. Luigib, P. Haastrupc and V. Maniezzod, A distributed geographic information system for the daily car pooling problem. Comput. Oper. Res. Arch.31 (2004) 2263–2278. Zbl1067.68784
  4. [4] M. Dorigo and T. Stützle, Ant Colony Optimization MIT Press (2004). Zbl1092.90066
  5. [5] M. Dorigo, V. Maniezzo and A. Colorni, Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Part B26 (1996) 29–41. 
  6. [6] M. Dorigo, Optimization, learning and natural algorithms, Ph.D. Thesis Politecnico di Milano, Italie (1992). 
  7. [7] E. Ferrari and R. Manzini, The car pooling problem: heuristic algorithms based on savings functions. J. Adv. Transp.37 (2003) 243–272. 
  8. [8] M.L. Fisher, The Lagrangian relaxation method for solving integer programming problem. Manag. Sci.27 (1981) 1–18. Zbl0466.90054MR720492
  9. [9] B. Kallehauge, J. Larsen, B.G. Madsen and M.M. Solomon, Vehicle routing problem with time windows Column Generation (2005) 67–98. Zbl1130.90316
  10. [10] A.B. Kothari, Genghis: a multiagent carpooling system. Dissertation, University of Bath, UK (2004). 
  11. [11] H. Li and A. Lim, A metaheuristic for the pickup and delivery problem with time windows. Int. J. Artificial Intell. Tools12 (2003) 173–186. 
  12. [12] B. Maurizio, C. Diego, C. Alberto and L. Alessandro, PoliUniPool: a car pooling system for universities. Soc. Behavior. Sci.20 (2011) 558–567. 
  13. [13] D. Meyers, D.J. Dailey and D. Lose, Seattle smart traveler: dynamic ride matching on the World Wide Web. Transp. Res. C7 (1999) 17–32. 
  14. [14] M. Vargas, J. Sefair, J. Walteros, A.L. Medaglia and L. Rivera, Car pooling optimization: a case study in Strasbourg. Systems and Information Engineering Design Symposium, Virginia, USA (2008). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.