Order dispatch problem of the inter-city or inter-district ridesplitting service

This study formulates the order dispatch problem of the inter-city/inter-district ridesplitting service as an integer linear programming, and a solution framework that combines Lagrangian relaxation (LR) and alternating direction methods of multipliers is constructed. Specifically, LR problem is constructed by relaxing coupling constraints; based on this, the augmented Lagrangian relaxation (ALR) problem is constructed by adding a quadratic penalty term. Then, the ALR problem can be decomposed into a series of interdependent vehicle route subproblems by using linearisation technique and block coordinate descent method. The upper bound of the model is generated by ALR and a heuristic, and the solution quality can be evaluated by the lower bound provided by LR. Finally, numerous experiments are conducted to verify the effectiveness of proposed algorithms. The results show that the proposed algorithm could achieve an average cost saving of 10% and an average detour reduction of over 20% than the existing algorithm.