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 deal is that Indiana Loans Online online can save your time, nerves and make a solution of all your financial problems. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Cheap Levitra, but also as part of its analogs.