The balanced dispatching problem in passengers transport services on demand - Sorbonne Université
Article Dans Une Revue Expert Systems with Applications Année : 2021

The balanced dispatching problem in passengers transport services on demand

Résumé

In the passengers' transport services on demand, such as taxi services, a dispatching solution determines the service quality level and the incomes received by both drivers and the transport company. In the last years, related work has been mainly focused on improving the service quality. However, the drivers' incomes balancing is still a challenge, especially for emerging economies. To address this situation, we introduce the balanced dispatching problem in passengers transport services (BDP-PTS) on demand, which seeks a dispatching solution that aims to minimize the variance of the incomes per unit of working time among the drivers. We propose five easy-to-implement online dispatching algorithms, which rely on dispatching rules obtained from the variance analysis and explore the performance measures for a dispatching solution provided by them. Those algorithms consider the BDP-PTS under an offline scenario, where all the information is revealed beforehand, and the maximum number of solicited transport services is performed. We are focused on a specific set of instances, called complete, which admit at least a feasible solution where all requested transport services are performed. Consequently, we prove the NP-completeness in the strong sense of the BDP-PTS under an offline scenario for these instances, and formulate a mixed integer quadratic program (MIQP) model to solve it. This complexity computation status implies that no polynomial or pseudo time algorithms exist for solving it, unless P=NP, involving an important quantity of running time and memory resources to model and to resolve it in an empirical computation. Finally, computational experiments are carried out to compare the proposed online dispatching algorithms and the MIQP model on datasets of real complete instances from a Chilean transport company. The obtained results show that the proposed online dispatching algorithm based on the dispatching rule, called SRV, is able to reduce more efficiently the income dispersion among drivers within reduced running times, assigning over a 98% of total solicited transport service and allowing a practical implementation into an automated dispatching system on a basic hardware A preliminary and reduced version of this article entitled "The balanced dispatching problem in passengers transport services on demand" appeared in Proc. of the 9th Conf. on Computational Logistics (ICCL 2018). * Corresponding author infrastructure, as it is the case of the transport companies in developing countries.
Fichier principal
Vignette du fichier
Quezada2021 The balanced dispatching problem in passengers transport services on demand.pdf (305.91 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03252086 , version 1 (07-06-2021)

Identifiants

Citer

Javier Moraga-Correa, Franco Quezada, Luis Rojo-González, Óscar Vásquez. The balanced dispatching problem in passengers transport services on demand. Expert Systems with Applications, 2021, 177, pp.114918. ⟨10.1016/j.eswa.2021.114918⟩. ⟨hal-03252086⟩
59 Consultations
90 Téléchargements

Altmetric

Partager

More