Friday, 11:30 - 11:55 h, Room: H 3010


Enrico Bartolini
The single-vehicle dial-a-ride problem

Coauthors: Roberto Baldacci, Aristide Mingozzi


The single-vehicle dial-a-ride problem (SV-DARP) is a generalization of the traveling salesman problem with pickup and delivery (TSPPD) where the travel time between the visit of each pickup and the corresponding delivery cannot exceed a maximum ride time. The SV-DARP has several applications, e.g., in door-to-door transportation services for elderly or disabled people. We propose an exact algorithm that is based on a new mathematical formulation of the SV-DARP involving an exponential number of variables that correspond to the possible paths for each pickup-delivery pair. A valid lower bound is computed by a cut-and-column generation procedure that solves the LP relaxation of the mathematical formulation strengthened by valid inequalities. The resulting lower bound and the corresponding dual solution are used to generate all paths having reduced cost not greater than the gap between the lower bound computed and a known upper bound. The resulting integer problem is solved by means of an integer programming solver. We report on preliminary computational experiments over a large set of SV-DARP instances derived from the main TSPPD benchmark sets.


Talk 3 of the contributed session Fri.1.H 3010
"Approximation of vehicle routing problems" [...]
Cluster 1
"Approximation & online algorithms" [...]


  The main criterion for them is your ability to repay any Wisconsin Loans Online, they are not interested in your previous attempts, the current one is all that matters. Female Cialis is prescribed to improve the quality of sexual life, to enhance the sensual reaction. It is also prescribedin case of frigidity and anorgasmia, decreased libido and hormonal changes that cause sexual dysfunction.