Taxi-sharing: Parameterized complexity and approximability of the dial-a-ride problem with money as an incentive

Among other results, we prove that 1-DARP-M is NP-Complete and max-DARP-M and max-1-DARP-M cannot be approximated in polynomial time to within any variable ratio even if α, capa and TW are fixed and if the road network is a planar graph. We also give a polynomial algorithm for max-1-DARP-M for the case where capa and TW are fixed and where the network does not contain a circuit. This algorithm implies a 1n-polynomial approximation for max-DARP-M.