www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/17635

Title: Theory and practice in large carpooling problems
Authors: Hartman, I.
Keren, D.
Abu Dbai, A.
Cohan, E.
KNAPEN, Luk
YASAR, Ansar
JANSSENS, Davy
Issue Date: 2014
Publisher: Elsevier Science BV
Citation: Procedia Computer Science 32, p. 339-347
Series/Report: Procedia Computer Science
Series/Report no.: 32
Abstract: We address the carpooling problem as a graph-theoretic problem. If the set of drivers is known in advance, then for any car capacity, the problem is equivalent to the assignment problem in bipartite graphs. Otherwise, when we do not know in advance who will drive their vehicle and who will be a passenger, the problem is NP-hard. We devise and implement quick heuristics for both cases, based on graph algorithms, as well as parallel algorithms based on geometric/algebraic approach. We compare between the algorithms on random graphs, as well as on real, very large, data.
Notes: [Hartman, Irith Ben-Arroyo; Keren, Daniel; Abu Dbai, Abed; Cohen, Elad] Univ Haifa, Dept Comp Sci, IL-3498838 Haifa, Israel. [Hartman, Irith Ben-Arroyo] Univ Haifa, Caesarea Rothschild Inst, IL-3498838 Haifa, Israel. [Knapen, Luk; Yasar, Ansar-Ul-Haque; Janssens, Davy] Hasselt Univ, Transportat Res Inst IMOB, B-3950 Diepenbeek, Belgium.
URI: http://hdl.handle.net/1942/17635
Link to publication: http://www.sciencedirect.com/science/article/pii/S1877050914006334#
DOI: 10.1016/j.procs.2014.05.433
ISI #: 000361562600041
ISSN: 1877-0509
Category: C1
Type: Proceedings Paper
Validation: ecoom, 2016
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A215.9 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.