Javier Moraga-Correa

Franco Quezada

Luis Rojo-González

C Vásquez

The balanced dispatching problem in passengers transport services on demand

Keywords: Dispatching problem, Online algorithm, Passengers transport services, Drivers incomes balancing, Mixed integer quadratic programming

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).

Introduction

Worldwide, the dispatching process is one of the main concerns that the transport companies dedicated to passengers transport services on demand, such as taxi services, face on a daily basis in where all the necessary information is only revealed by the arrival of the solicited transport services. This process involves six main steps, which are described as follows: i) Receive a request: The passenger solicits a transport service via phone or through an online platform. ii) Dispatch transport vehicle: The availability of a transport vehicle is firstly verified according to the requirements of the passenger by an online dispatching algorithm. If a set of transport vehicles is available, the online dispatching algorithm assigns an available transport service to the transport vehicle on an online platform, and it waits for the confirmation of the driver. If the set of the transport vehicles are not available, it is necessary to consult the remaining time of the current transport services to communicate the new transport service conditions to the passenger, which could either be accepted or refused by the passenger. iii) Register the passenger's information: Once the passenger has accepted the transport service, that information is registered. iv) Start transport service: Once the driver has accepted the assigned transport service, it has to pick up the passenger.

Once the trip has finished, the transport service is declared ended by entering the transport service information on the driver's platform. v) Validate the trip information on the application: When the transport service is completed, the passenger has to validate the information entered by the driver and, therefore, complete the transport service given. vi) Report the arrival to the hub: Once the validation of the information from the last finished transport service, the driver comes back to the nearest work base, reporting the arrival and availability. These work bases are parking points defined by the historical data of performed transport services and locations constraints. The goal is to minimize both the time response to the solicited transport services and the cost related to fuel consumption by the transport vehicles.

This dispatching process is usually managed by a transport company, which has affiliated a fleet of transport vehicles and coordinates their assignments to transport services solicited by the passengers. Consequently, the dispatching solution obtained in the pay period defines the performed transport services, the incomes received by the drivers who perform the transport services and the income of the transport company who manage the dispatching process.

Thus, an efficient dispatching solution in terms of service quality and balancing the incomes received by the drivers is particularly relevant, due to at least two reasons. On the one hand, a good service quality determines customer satisfaction which increases the probability of choosing the transport company for a new transport service. On the other hand, income equality may impact on more productivity ,creating a bond with the managers which means more confidence, allowing growth and prosperity in the transport company. The previous points ease the improvement of the organizational climate (OECD, 2016, Chapter 2).

In the last years, the advance on information and communications technologies (ICT) has been mainly focused on the service quality of a dispatching solution. In practice, it has contributed to tackling the transport vehicles dispatching problem occurred in the dispatching process, Step ii), developing new online dispatching algorithms according to some service quality objective, reducing mainly the waiting times of passengers and the unnecessary movements of transport vehicles.

However, balancing the incomes received by drivers is still a challenge for transport companies in environments where the dispatching solution can be influenced by assignment decisions that are not necessarily seeking the transport company objectives. In particular, this is relevant for the transport companies in developing countries, where the hardware infrastructure is basic, and a human-operator generally provides the dispatching solution without centralized control. Then, an arbitrary assignment decision cannot always be avoided. For instance, some assignment decisions determined by an informal agreement between a specific driver and the human operator, which is unknown by the other drivers and managers of the transport company. For these environments, an online dispatching algorithm capable of reducing more efficiently the income dispersion among the drivers and guaranteeing a good level of service quality is a target to be achieved.

Our Contribution

In this work, the balanced dispatching problem in passengers transport services (BDP-PTS) on demand is introduced. This problem aims to seek a dispatching solution which minimizes the variance of the incomes per unit of working time among the drivers, by assigning any solicited transport service to a transport vehicle whenever possible.

In order to give us insights about a quality measure for a possible resolution of our problem regarding service quality for the passenger and the transport company (e.g. solicited transport services to be performed and the associated income of the transport company), we address the BTP-PTS under an offline scenario, where all the necessary information from the instances to minimize the variance per unit of working time among the drivers is previously known, guaranteeing that the maximum number of solicited transport services is performed

In particular, we focus on a set of specific instances, called complete, which admit at least a feasible solution where each solicited transport service is performed by a transport vehicle. For these instances, we prove the NP-completeness in the strong sense of the BDP-PTS under an offline scenario, which 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. Consequently, we formulate a mixed integer quadratic programming (MIQP) model to determine the optimal solution of a complete instance.

We propose five easy-to-implement online dispatching algorithms to solve our problem These are based on dispatching rules obtained from the income variance analysis per unit of working time. Those also include the algorithm currently used by a Chilean transport company located in Santiago city, one of the principal South American capitals. That implementation exhibits a simple dispatching system supported by a basic hardware infrastructure, as it is the case of many transport companies in developing countries. Finally, computational experiments are conducted to compare our five easy-to-implement online dispatching algorithm, along with the MIQP model. That considers several performance indicators on three different datasets of real complete instances from the Chilean transport company. The obtained results show that the proposed online dispatching algorithm based on a 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 services and allowing a practical implementation into an automated dispatching system into a basic hardware infrastructure.

Outline of the paper

This work is organized as follows: Section 2 provides the current works related to the transport vehicles dispatching problem. Section 3 states the balanced dispatching problem in passengers transport services (BDP-PTS) on demand. In Section 4, we formally define a particular instance under study, which is called complete, showing the NP-completeness for BDP-PTS under an offline scenario and providing a mixed integer quadratic programming (MIQP) to determine its optimal solution. Section 5 exhibits the five proposed resolution methods and Section 6 shows the computational experiments carried out. Finally, the conclusions and future work are presented in Section 7.

Literature review

In literature, the transport vehicles dispatching problem has been studied from different perspectives, mainly considering an offline scenario, in which it is assumed that all the information is known in the dispatching process [START_REF] Toth | Vehicle routing: problems, methods, and applications[END_REF]. However, in a real situation, this assumption is not satisfied. Then, the dispatching decisions must be made when the necessary information is revealed by the arrival of the solicited transport service [START_REF] Borodin | Online computation and competitive analysis[END_REF]. This latter version of the transport vehicles dispatching problem, under an online scenario, is daily faced by transport companies, particularly those that must manage the dispatching of a fleet of transport vehicles, combining critical company's objectives such as service quality, with the individual goals of the drivers.

In the last decade, the transport vehicles online dispatching problem has been studied by several authors based on the advances in information and communications technologies (ICT). These work can be mainly categorized into a service quality setting, which seeks to reduce the waiting times of passengers and the unnecessary movements of transport vehicles.

Von [START_REF] Massow | Fareplay: an examination of taxicab drivers' response to dispatch policy[END_REF] work on how is the response of taxicab drivers according to two main dispatch policies from a probabilistic approach. These are related to where drivers wait under the assumption that they have knowledge of arrival rates of potential passengers. They can see the queues for different zones and high demand locations on their dispatch computer. This work concludes in moving drivers closer to the centres of gravity for specific zones will decrease the passenger waiting times and spreading the vehicles out when high demand zones do not exist. [START_REF] Santos | Taxi and ride sharing: A dynamic dial-a-ride problem with money as an incentive[END_REF] present the ride and taxi-sharing as a single problem from an optimization point of view where the objective is to maximize the number of attended requests and to minimize the total value paid by all passengers. They address this problem dynamically since a new request arrives online and routes can be modified. [START_REF] Maciejewski | An assignment-based approach to efficient real-time city-scale taxi dispatching[END_REF] present an application of a widerange microscopic model covering the city of Berlin and the Brandenburg region to assess the performance of a real-time dispatching strategy based on solving the taxi dispatching problem. The obtained results show improvements for both drivers (less idle driving) and passengers (less waiting). However, computing the assignments for thousands of taxis in a vast road network turned out to be computationally demanding. [START_REF] Gao | Optimal multi-taxi dispatch for mobile taxi-hailing systems[END_REF] propose a new Mobile Taxi-hailing System (MTS) based on an optimal algorithm for multi-taxi dispatching, which differs from the competition modes used in traditional taxi-hailing systems, assigning vacant taxis to taxihailing passengers proactively. The system utility function involves the total net incomes of taxis and waiting times of passengers subject to the individual net revenues of taxis and passenger requirements for specified classes of taxis. [START_REF] Liu | A parallel genetic algorithm with region division strategy to solve taxi-passenger matching problem[END_REF] formulate the taxi-passenger matching by considering the pickup rate and average waiting time of passengers, proposing a parallel genetic algorithm to solve the problem. The experimental results show the effectiveness and ef-ficiency of the proposed algorithm, improving the quality of service provided by the taxi systems. [START_REF] Hyland | Dynamic autonomous vehicle fleet operations: Optimization-based strategies to assign avs to immediate traveler demand requests[END_REF] develop and compare six dispatching strategies, that provide direct origin-to-destination transport service to travelers who request rides via a mobile application and expect to be picked up within a few minutes. The more sophisticated strategies significantly improve the operational efficiency when the fleet utilization is high (e.g. during the morning or evening peak). Conversely, when the fleet utilization is low, it dispatches passengers sequentially to the nearest idle transport vehicle is comparable to the more advanced strategies. [START_REF] Billhardt | Taxi dispatching strategies with compensations[END_REF] propose an algorithm for taxi dispatching which exploits dynamic taxi reassignment, i.e. taxis that had been dispatched to pick up a customer but are still on their way may be reassigned to another customer, combined with an economic compensation schema. [START_REF] Gong | Real-time taxipassenger matching using a differential evolutionary fuzzy controller[END_REF] develop a two-stage taxi-passenger matching system; where the first stage calculates the matching degree for each possible taxi-passenger assignment. The second stage is the matching module to solve the optimal assignment problem, whose result is to maximize the quality of service and increase the incomes for the taxi transport service company. [START_REF] Park | Online optimization with lookahead for freeway emergency vehicle dispatching considering availability[END_REF] propose online dispatching strategies to minimize the response time to a sequence of requests on emergency vehicle context. This work assumes that events are interdependent considering a look-ahead contingent on past emergency. It is used to decide on which vehicle assign under future available emergency vehicles in different network-wide event distributions. [START_REF] Yu | Bi-objective green ride-sharing problem: Model and exact method[END_REF] formulate a model to assign services considering two main objectives. The former is related to the minimization of carbon emission. The latter relates to the maximization of the average ride profit. Thus, every driver is satisfied regarding their interests. [START_REF] Duan | Centralized and decentralized autonomous dispatching strategy for dynamic autonomous taxi operation in hybrid request mode[END_REF] work on a hybrid request mode autonomous taxi (aTaxi) system with no ride-sharing, from both centralized and decentralized point of view, which are operated in a freefloating mode without stations with possibilities to park anywhere in the service area. That works aims to find a sequence of pickup locations, drop-off locations, and rebalance locations in real-time with travel requests arriving dynamically. [START_REF] Chang | An optimallycompetitive algorithm for maximum online perfect bipartite matching with iid arrivals[END_REF] introduce a DISPATCH algorithm, a 0.5-competitive randomized algorithm for the online weighted perfect bipartite matching problem with independent and identically distributed arrivals.

Complementary to the previous works in this field, our research tackles the problem of assignment transport vehicles to solicited transport services, while the incomes received by the drivers is balanced. This problem is motivated by real environments found generally in transport companies from developing countries, where the hardware structure is basic, and a human-operator usually provides the dispatching solution without centralized control. Then, some assignment decisions can be arbitrarily determined, for instance, by an informal agreement between a specific driver and the human operator, which is unknown by the other drivers and managers of the transport company. To the best of our knowledge, this is the first time such an extension is studied in the context of passenger transport services.

The balanced dispatching problem in transport services on demand

An instance of the balance dispatching problem in transport services on demand is defined as follows: consider a set M of transport vehicles. Let I be the set of transport services solicited during a pay period defined by a transport company in accordance with legal, political and economic management criteria.

Let J be the set of time windows J during the pay period. Each time window j ∈ J has a starting time e j and a duration time e j . Each transport vehicle m ∈ M has a working time defined by the sum over the time windows J m ⊆ J, where the transport vehicle m ∈ M is available. We assume this information beforehand known and denote êm = j∈J m e j , for simplicity. Note that the pay period corresponds to the time window that involves the set of time windows J. Formally, it is defined by min j∈J d j and max j∈J d j + e j .

Each transport service i ∈ I is solicited at time h i with a fare v i , a starting time a i and a travel time b i , which implicitly state a particular time window for the transport service i ∈ I given by a starting time a i and duration b i and assumed within the pay period.

For convenience and simplicity, we define the subsets I j ⊆ I of solicited transport services which must be performed within a time window j ∈ J, i.e. the starting time a i ≥ d j and the starting time plus the travel time a i + b i ≤ d j + e j , and then the implicitly time windows of the transport services are controlled by these sets.

We assume a value h i very close to a i and hence, the solicited transport service i is only assigned within a time window j ∈ J m for an available transport vehicle m such that I j ∅. Consequently, each vehicle m ∈ M has a subset of solicited transport services i ∈ I m ⊆ I that can be performed. Note that each transport vehicle performs at most one solicited transport service at a time, and a solicited transport service can be only performed by one transport service. Table 1 provides the notation used in the balance dispatching problem in transport services on demand.

Given an instance of the balanced dispatching problem. An online dispatching algorithm is defined as an algorithm that assigns each solicited transport service i ∈ I to a single and available transport vehicle at time t := h i + for a negligible value according to a particular criterion, whenever possible. Note that this criterion is generally based on the magnitude of its value (e.g few seconds) in comparison to the magnitude of values for the other parameters (e.g. tens of minutes). The resulting of assignments obtained by the instance is defined as a dispatching solution, i.e. a set of solicited transport services assigned to each transport vehicles. Consequently, the dispatching solution defines the number of performed transport service and, hence, the incomes received by drivers and transport company.

Formally, BDP-PTS on demand determines a dispatching solution that seeks to minimize the variance of the incomes per : Subset of solicited transport services that can be performed by the transport vehicle m. I j : Subset of solicited transport services that can be performed within the time window j.

unit of working time among the drivers. Note that this definition has an important underlying property. By definition, an online dispatching algorithm assigns a transport vehicle to a solicited transport service whenever possible. As a result, a certain service quality level and income are guaranteed. Note that an empty assignment solution is feasible if and only if no assignment is feasible. Figure 1 illustrates an instance and an optimal dispatching solution of the balanced dispatching problem in transport services on demand.

In order to obtain insights about a quality measure for a dispatching solution in terms of service quality for the passenger and the transport company (e.g. the number of solicited transport services that could be performed and the potential income of the transport company), we address the BDP-PTS under an offline scenario, where all the necessary information from the instances to minimize the variance per unit of working time among the drivers is previously known, guaranteeing that the maximum number of solicited transport services is performed. In practice, this value is considered as the maximum level possible for the service quality of an instance, highlighting that it also holds for the BDP-PTS on demand. Note that it could be expressed as a fraction of the set cardinality I, whose value is equal to zero when no assignment is feasible and, equal to one when all solicited transport services can be performed.

In this research, we focus on the latter kind of instances called complete, which allows us to compute the minimum variance of the incomes per unit of working time among the drivers, while the maximum income for transport company is achieved. Moreover, the maximum possible level for the service quality is reached by all solicited transport services performed. These instances allow us to assess the impact of the solution given by the BDP-PTS on demand over other objectives, such as service quality and income of the transport company. A formal definition is provided in the next Section 4. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 travel time

! ℎ ! # ! $ ! % ! & ' " ( " ) (̂#

The complete instances

We define a complete instance as an instance of BDP-PTS on demand, which admits at least a feasible solution where each solicited transport service is performed by a transport vehicle. Therefore, the total solicited transport services correspond to the maximum number of solicited transport services to be performed by instance definition. A complete instance is depicted in Figure 1.

For these instances, we address the BDP-PTS under an offline scenario. We first prove the NP-completeness in the strong sense of this problem and formulate it as mixed integer quadratic programming model to determine an optimal solution of a complete instances. These results will provide understanding about the service quality level and, drivers and company's incomes that can be reached from these instances, allowing us to assess the performance of the online dispatching algorithms proposed in Section 5.

We remark that the status of computational complexity of the BDP-PTS under an offline scenario 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.

Computational complexity results

We fix an arbitrary complete instance and consider the problem decision version of the BDP-TPS under an offline scenario as follows:

Instance: Consider an arbitrary complete instance with a set I of transport services and a set M of transport vehicles. Each solicited transport service i ∈ I has a fare v i , a starting time a i , and a travel time b i . Each transport vehicle m ∈ M has a set of time windows J m .

Question: Does there exist a dispatching solution for the set I of solicited transport services to transport vehicles M such that the variance of the incomes per unit of working time among transport vehicles is equal to zero?.

From the above decision version of BDP-TPS, we now provide the computational complexity status for the BDP-TPS under an offline scenario, considering the 3-PARTITION problem to construct an complete instance such that a quantity of α different transport vehicles perform three solicited transport services, whose sum of fares is equal to V and thus the variance of the incomes per unit of working time among transport vehicles is equal to zero as shows the proof of Theorem 1. Note that a link between the "decision" and "minimization" version problems exists. i.e. if there exists a polynomial algorithm that solves the "decision" problem, then one can find the minimum value for the minimization problem in polynomial time by applying this algorithm iteratively while decreasing the goal value. On the other hand, if an algorithm finds the minimum value of the minimization problem in polynomial time, then the decision problem can be solved in polynomial time by comparing the value of the solution output by this algorithm with the goal value. Therefore both versions are of similar theoretical difficulty.

Theorem 1. Consider a complete instance. The BDP-TPS under an offline scenario is NP-complete in the strong sense.

Proof. Consider a complete instance. The BDP-PTS under an offline scenario is clearly in NP, as the conditions on the income variance per working time among drivers for a feasible solution can be checked in polynomial time.

To show that the problem is NP-complete in the strong sense, we consider the 3-PARTITION problem [START_REF] Garey | A guide to the theory of np-completeness[END_REF].

Instance: Given 3α positive integers v 1 , . . . , v 3α , V with V/4 < v i < V/2, ∀i ∈ {1, . . . , 3α} and 3α i=1 v i = αV. Question: Does there exist α pairwise disjoint three element subset S j ⊂ {1, . . . , 3α} such that i∈S j v i = V, ∀ j = {1, . . . , α}?.

We construct a complete instance F of the problem as follows:

We assume a set of transport vehicles M, a set of time windows J and a fare v i for each transport service i ∈ {1, . . . , 3α}, such that V/4 < v i < V/2, where 3α i=1 v i = αV. We consider that each transport vehicle m ∈ M has a single time window identically defined by [0, e]. Finally, we assume starting times a 3m , a 3m-i-1 and transport service times b 3m , b 3m-i-1 such that a 3m-i-1 + b 3m-i-1 < a 3m-i and a 3m + b 3m < e, ∀i ∈ {1, . . . , 3α}, ∀m ∈ {1, . . . , |M|}.

We claim that this complete instance F has a solution where all solicited transport services are performed with a variance equal to zero if and only if there exists a solution of 3-PARTITION instance.

In the easy direction, given a 3-PARTITION instance solution, we construct a solution where three different transport services are considered for each transport vehicle m ∈ M, whose sum of fares is equal to V and are performed into a fixed time window with equal starting time and duration. Since the transport services have equal starting times a 3m , a 3m-i-1 and travel times b 3m , b 3m-i-1 such that a 3m-i-1 + b 3m-i-1 < a 3m-i and a 3m + b 3m < e, ∀i ∈ {1, . . . , 3α}, ∀m ∈ {1, . . . , |M|}, then each transport service is performed by a single transport vehicle and each transport vehicle performs a single transport service at a time. Straightforward verification shows that the resulting solution has the required value for the variance.

In the hard direction, we conduct a systematic analysis. We consider a solution where each transport service is performed by a single transport vehicle and each transport vehicle performs a single transport service at a time, and then we observe: i) if the solution has at least a transport vehicle with a number of solicited transport services to be performed less than three, then there exists another transport vehicle with at least four solicited transport services to be performed, whose sum of fares is greater than V by definition. Thus, the variance of this solution is greater than zero; and ii) if the solution assigned to all transport vehicle a number of three solicited transport services, then a sum of fares lower than V for at least a single vehicle transport implies at least another transport vehicle with a fares sum greater than V and therefore the variance value of this solution is greater than zero. Finally, we deduce that the solution with a variance of zero is only obtained by a solution to the 3-PARTITION instance, where each transport vehicle has a sum of fares equal to V, concluding the proof.

Mixed integer quadratic programming (MIQP) model

We consider a complete instance and formulate a mixed integer quadratic programming (MIQP) model to minimize the balanced dispatching problem in passenger transport services under offline scenario.

Let x i, j be a binary variable that respectively takes the value 1 if the transport service i is dispatched to the time window j, and value 0 otherwise, ∀i ∈ I, j ∈ J. Let z i,i be a binary variable that takes the value 1 if the transport service i is assigned before to the transport service i , 0 otherwise, ∀i, i ∈ I, j ∈ J.

Moreover, let B m and y i be the real variables that define the income of transport vehicle m ∈ M during the pay period and the finishing time of transport service i ∈ I, respectively. For convenience, we denote B as a real variable, which defines the income average per unit of working time during the pay period. Also, we denote J i where the transport service i can be performed. The objective function (1) and the set of constraints (2)-( 8) provide a valid MIQP model of the problem as follows [MIN] 1

|M| m∈M (B m -B) 2 , (1)
subject to

B m = j∈J m i∈I m x i, j v i j∈J m e j ∀ m ∈ M (2) B = 1 |M| m∈M B m (3) j∈J i x i, j = 1 ∀ i ∈ I (4) y i -(y i -b i ) ≤ N(1 -z i,i ) ∀ j ∈ J, ∀ i, i ∈ I j (5) x i, j + x i , j ≤ 1 + z i,i + z i ,i ∀ j ∈ J, ∀ i, i ∈ I j (6) x i, j , x i , j , z i,i , z i ,i ∈ {0, 1} ∀ i, i ∈ I, ∀ j ∈ J (7) y i , B m , B ∈ R + ∀ i ∈ I, ∀ m ∈ M (8)
Expression (1) defines the objective function, which minimizes the income variance per unit of working time among transport drivers during the pay period defined by the transport company. Constraints (2) state the income per unit of working time of each transport vehicle m ∈ M during the pay period. Constraint (3) provides the income average per unit of working time during the pay period. Constraints (4) define that each transport service i ∈ I has to be assigned to a single available time window j ∈ J i . Set of constraints ( 5) and ( 6) state that two different solicited transport services i, i ∈ I cannot be assigned to the same time window j ∈ J avoiding overlapping. Expressions ( 7) and ( 8) define the domain of the variables. The big-N coefficient in (5) is set to max i, j {b i + e j }.

Online dispatching algorithms

In this section, we propose five easy-to-implement online dispatching algorithms in order to solve BDP-PTS on demand. In practice, each online dispatching algorithm considers a specific dispatching rule, which is verified among the available transport vehicles to perform the new solicited transport service i , such as Algorithm 1 shows at line 1 and 2. Otherwise, it offers a new starting time denoted by âi for the transport service to be performed by the first available transport vehicle either be accepted or refused by the passenger (Algorithm 1, lines 3-9).

In what follows, we focus on developing new dispatching rules for the problem. These rules are based on theoretical results obtained from the variance analysis of the incomes per unit of working time.

Let i be a new solicited transport service, which is assigned to the transport vehicle m * ∈ M at time t := h i + for a negligible value according to the particular criterion given by the magnitude of its value (e.g few seconds) in comparison to the magnitude of values for the other parameters (e.g. tens of minutes). We assume that each transport vehicle m ∈ M has a partial income A m and working time êm at time t. Thus, the variance of incomes per unit of working time among the drivers at time t is defined by Expression (9), where the new solicited transport service i is the unique decision assignment to the transport vehicle m * at time t and any other past decisions are given.

1 |M|         A m * + v i êm * - 1 |M|         |M| m=1,m m * A m êm + A m * + v i êm *                 2 + 1 |M| |M| m=1,m m *         A m êm - 1 |M|         |M| =1, m * A ê + A m * + v i êm *                 2 = 1 |M|         C + 2 v i êm *         A m * êm * - 1 |M| |M| m=1 A m êm         + v i êm * 2 (|M| -1) |M|         , (9)
where

C := |M| m=1 A m êm -1 |M| |M| =1
A ê 2 is a constant value independent of transport vehicle m * considered by the assignment. Intermediate steps between above Expressions are provided in Appendix A.

Dispatching rules

The dispatching rules obtained from the income variance analysis per unit of working time are the main element of the online dispatching algorithm proposed in this research. These aim to avoid arbitrariness in the dispatching decision involved in order to assign the new solicited transport service i and the transport vehicle m * , incorporating variables such as the incomes of each driver, their working time within the defined pay period (e.g. a labour day, one week, one month) and the partial income obtained at time t by using an online dispatching algorithm. The five dispatching rules are defined as follows:

Time rule

This dispatching rule assigns the new solicited transport service i to an available transport vehicle with the shortest income, i.e. m * =argmin m∈M A m . Note that this dispatching rule minimizes Equation ( 9) under the assumption that all transport vehicles have an equal working time, i.e. êm = ê, ∀m ∈ M.

Income rule

This rule allows to minimize Equation ( 9) under the assumption that all transport vehicles have equal incomes per unit of working time, i.e. A m /ê m = A/ê, ∀m ∈ M. In practice, this rules assigns the new solicited transport service i to the available transport vehicle, which has the greatest working time, i.e. m * =argmax m∈M êm .

Greedy rule

This simple dispatching rule assigns the new solicited transport service i to the available transport vehicle, which minimizes Expression (9) at time t , i.e. m * = argmax m∈M Expression (9). Note that the goal to minimize the variance of the incomes per unit of working time is the same that the objective function in the MIQP model proposed in subsection 4.2 but the information available at the time decision are different, while in the greedy rule minimize the variance of the incomes per unit of working time when the new solicited transport service i is the unique decision assignment to be considered and any other decisions are given, the MIQP model involves all decision assignment based on the full information of the instance under an offline scenario.

SR rule

This dispatching rule considers additional information which can be obtained from historical data of the transport company. Formally, this considers a vector {r(m, f , t)} 1≤m≤|M|, f ∈|F | as input defined by a transport vehicle ranking ordered in decreasing order according to waiting time from its last performed transport service which belongs to the interval of fare transport service given by [ f min , f max ) and denoted by f ∈ F at time t, where F involves a set of disjoint intervals for defined fares values. Thus, each solicited transport service i ∈ I belongs to a single interval f ∈ F according to its fare v i ∈ [ f min , f max ).

In practice, this rule assigns the new solicited transport service i to the available transport vehicle at the first position in the ranking, which exhibits the longest waiting time to perform a transport service whose fare belongs to the interval f , i.e.m * = argmax m∈M,v i ∈[ f min , f max ) r(m, f, t). We highlight that this rule corresponds to the current dispatching rule used in the online dispatching algorithm by a Chilean transport company.

SRV rule

Finally, we introduce the dispatching S RV rule, which incorporates the above ranking definition and a possible order modification based on The working time order rule defined as follows:

Definition 1 (The working time order rule). Consider a new solicited service i with v i ∈ [ f min , f max ) and two transport vehicles m 1 and m 2 with r(m 1 , f, t) = m 1 and r(m 2 , f, t) = m 1 + 1, respectively. The working time order rule maintains the order of the vehicles in the ranking when δ m 1 ,m 2 := êm 1 /ê m 2 belong to the interval defined by Expression (10)

A m 1 -A m 2 -v i v i + 2v i + 2A m 2 ± (v i + A m 2 -A m 1 ) 2 + (v i + 2v i + 2A m 2 )(v i + 2A m 1 ) v i + 2v i + 2A m 2 , (10)
otherwise, the order of the two vehicles in the ranking is reversed, i.e. r(m 1 , f, t) = m 1 + 1 and r(m 2 , f, t) = m 1 .

In practice, this ordering rule is applied to the first two transport vehicles ordered in ranking when a new solicited transport service i arrives. Notice that this ordering rule minimizes the variance value in the case that only two transport vehicles are considered as is shown in Theorem 2.

Theorem 2. Consider a new solicited service i with v i ∈ [ f min , f max ). Given a set M of two transport vehicles and r(m, f , t) = m without loss of generality, which is available to perform the transport service i , when it is solicited. The working time order rule minimizes the variance of incomes per unit of working time of the transport vehicles at time t.

Proof. We consider a proof by case analysis. The case (a) where the new solicited transport service i is assigned to the transport vehicle m = 1, which is the first in the ranking in the interval f at time t; and the case b) where it is assigned to the transport vehicle m = 2. The resulting variance of the incomes per unit of working time for case (a) is given by Expression ( 11)

1 |M| A 2 + v i ê2 - 1 2 A 2 + v i ê2 + A 1 + v i ê1 2 + 1 |M| A 1 + v i ê1 - 1 2 A 2 + v i ê2 + A 1 + v i ê1 2 = 2 |M| ê1 (v i + A 2 ) -ê2 (A 1 + v i ) 2ê 1 ê2 2 , (11)
and for case (b) is given by Expression ( 12)

1 |M| A 2 + v i + v i ê2 - 1 2 A 2 + v i + v i ê2 + A 1 ê1 2 + 1 |M| A 1 ê1 - 1 2 A 2 + v i + v i ê2 + A 1 ê1 2 = 2 |M| ê1 (v i + v i + A 2 ) -ê2 A 1 2ê 1 ê2 2 . ( 12
)
Intermediate steps for the above Expression are provided in Appendix B. We compare both expressions ( 11) and ( 12), replacing δ 1,2 = ê1 /ê 2 . Thus, we have

δ 2 1,2 (v i + 2v i + 2A 2 ) + δ 1,2 (2v i + 2A 2 -2A 1 ) -(v i + 2A 1 )
= 0, which is a convex function with at most two roots defined by Expression (10). Therefore, the case (a) has minimum variance when δ 1,2 belongs to interval (10), and then the new solicited transport service i is assigned to transport vehicle m = 1, which concludes the proof.

Computational experiments

In this section, the computational experiments are carried out in order to assess the performance of the online dispatching algorithm proposed for solving BDP-PTS on demand.

Implementation

The resolution methods are implemented in Python 3.7 programming language and executed in a MacBook Air Intel i5, 1.6 Ghz, 8GB RAM, simulating a real basic hardware infrastructure generally available in the transport companies in developing countries. Based on the current values used by a Chilean transport company, we fixed the disjoint sets of the interval of fares transport service by the following lower value of each one, {0; 10, 000; 20, 000; 40, 000} Chilean pesos, where solicited transport services with a fare greater than 40, 000 belong to the last interval. Note that a solicited transport service non-assigned at the first time is discarded by considering that the acceptation of a new starting time for the services is not guaranteed.

In addition, we implemented the proposed MIQP model in C++ programming language and was executed in NLHPC infrastructure (National Laboratory for High Performance Computing) using CPLEX 12.6.1 as a solver. For these experiments, we set the cluster to use 20 cores and 10,000MB of RAM memory to solve the model, imposing stop criteria of 7,200 seconds (120 min) for computing time or a gap of 1%.

Datasets

We consider different datasets of real complete instances such a labour day, one week, and one month, respectively. Table 2 reports a summary for the instances taken from the datasets, providing the following metrics: the total number of solicited transport services (|I|), the total number of transport vehicles (|M|), the sum over the fare of solicited transport services ( i∈J v i ) in thousands of Chilean pesos, the sum over the travel time of solicited transport service ( i∈I b i ) in minutes, the sum over the working time of transport vehicles ( m∈M êm ) in minutes. Notice that the number of available transport vehicles for each dataset remains constant.

Table 2: Summary of instances for datasets. The reported metrics are: the total number of solicited transport services (|I|), the total number of transport vehicles (|M|), the sum over the fare of solicited transport services ( i∈J v i ) in thousands of Chilean pesos, the sum over the working time of transport vehicles ( m∈M êm ) in minutes and the sum over the travel time of solicited transport service ( i∈I b i ) in minutes.

Performance indicators

We define six performance indicators for each complete instance of the datasets. These are defined as follows: a) Ave: This computes the average dispatching time of each solicited transport service including those non-dispatched transport services, in seconds. This value is defined by the quotient between simulation running time and the number of solicited transport services. b) Trp: This is the total number of solicited transport services that is performed. In addition, the percentage value respect to the total number of solicited transport services is provided. c) Trv: This corresponds to the number of transport vehicles that performed at least one solicited transport service. The percentage value according to the total number of transport vehicle available during the pay period is also computed. d) Inc: This reports the sum of incomes in thousands of Chilean pesos obtained by the drivers from the solicited transport service that were performed. In addition, the percentage value according to the sum over the fare of requested transport services is reported. e) Std Dev: This provides the standard deviation of the incomes in Chilean pesos per minute obtained by the drivers from the solicited transport service that were performed. Note that this value is equal to the square root of the variance, which is the goal to be minimized. Also, it is provided with the percentage of respect to the best-known solution, where all solicited transport services are performed. f) Gap: This corresponds to the gap exhibited by MIQP over CPLEX. The Gap value is computed as 100%•(U B-LB)/U B, in which U B and LB stand for the upper and the lower bounds reported by the best feasible solution and the best relaxed solution of CPLEX within the imposed time limit.

Results

MIQP model

Table 3 shows the results obtained by MIQP over CPLEX, grouping the complete instances of each dataset. The reported indicators are the number of transport vehicle that performed at least one solicited transport service and its equivalent percentage respect to the total number of transport vehicle available during the pay period (rows Trv). The standard deviation of the incomes in thousands of Chilean pesos per minute obtained by the drivers from the solicited transport service that were performed and its equivalent percentage according to the best-known solution (rows Std Dev) and the Gap in percentage metrics (row Gap).

The obtained results underline the limits of CPLEX and the MIQP model to determine the optimal solution for the problem of the income variance minimization per unit of working time among the drivers for the complete instances of datasets under an offline scenario. Specifically, CPLEX cannot solve all of the complete instances of datasets to optimality within the imposed time limit (120 minutes). However, CPLEX provides a feasible solution for all complete instances of datasets, which Table 3: Results obtained by MIQP over CPLEX. The data is grouped for the complete instance of each dataset. The reported indicators are the number of transport vehicle that performed at least a demanded transport service and its equivalent percentage respect to the total number of available transport vehicles during the pay period (rows Trv), the standard deviation of the incomes in thousands of Chilean pesos per minute obtained by the drivers from the solicited transport service that were performed and its equivalent percentage according to the best-known solution (rows Std Dev) and the Gap in percentage metrics (rows Gap). corresponds to the best-known solution found in the computational experiments. Note the inability of CPLEX to improve the lower bound equal to zero for the dataset 3 (month), which implies the gap value despite being the single solution with a value equal to the total number of the available vehicle transport.

Online dispatching algorithms

Table 4 reports the performance indicators estimated for the complete instance of each dataset. All online dispatching algorithms were able to solve the complete instances of each dataset within a similar average dispatching time (Ave) less than onetenth of a second of running time, being omitted.

The obtained results show a similar value for the total number of solicited transport services performed by a transport vehicle for each complete instance of each dataset (rows Trp) for the online dispatching algorithms. Note that the percentage according to the total number of solicited transport service in each complete instances is at least 98%, which implies an important service level provided by the proposed online dispatching algorithms for all complete instances under study.

Regarding the number of transport vehicles that performed at least one solicited transport service (rows Trv), the online dispatching algorithms exhibit an increasing trend according to pay period defined by complete instance of each dataset under study. These values are similar in each instance, excepting the online dispatching algorithm based on the dispatching rule called Time, which shows the lowest value. Note that only for the dataset 3 (month), all online dispatching algorithms, excepting one, reach the 100% according to the total number of transport vehicle available during the pay period. That gives insight into the positive correlation between the number of the transport vehicle and the pay period.

The sum of incomes in thousands of Chilean pesos obtained by the drivers from the solicited transport service that were performed (rows Inc) reports a similar value for the online dispatching algorithms in each dataset, reaching a percentage according to the total number of solicited transport service in each complete instances is at least 96%. The above value is an important management index for the transport company, representing that at most 4% of total incomes from the solicited transport services were not obtained in the pay period.

The standard deviation of the incomes in thousands of Chilean pesos per minute obtained by the drivers from the solicited transport service that were performed and its equivalent percentage according to the best-known solution (rows Std Dev), shows an increasing value according to the pay period of the complete instance. Dataset 1 reports values between 118.49% and 296.01%, whereas the dataset 3 exhibits values between 608.81% and 4,973.09%. A particular case is presented in the dataset 2; The values are between 98.37% and 274.53%, where the online dispatching algorithm based on the dispatching rule called SRV obtains a value less than the standard deviation value from the best-known solution by CPLEX. This difference could be explained by the number of solicited transport service that were performed for this algorithm, which only reached 98.88%, showing the non-linear correlation with the number of solicited transport services to be performed.

In general, the obtained results suggest that the online dispatching algorithm based on dispatching rule called SRV reports the best performance indicator values.

To compare the best online dispatching algorithm with the solution obtained under an offline scenario, a comparison with the MIQP model over CPLEX is carried out. Figure 2 shows the values obtained by the above online dispatching algorithm and the MIQP over CPLEX, showing the boxplot and the data distribution of incomes in Chilean pesos per minute obtained by the drivers from the solicited transport service that were performed in both cases for each dataset under study.

The main differences between the distribution are found in the minimum, and the maximum values for each complete instance of the datasets (row Q and Q, respectively), in particular for the pay period equal to one month. However, the distribution converges to be similar in central values when the size of the during of pay period. This implies that the incomes per minute in Chilean pesos obtained by most drivers from the solicited transport service that were performed by using the proposed online dispatching algorithm are similar to the incomes obtained by an expert solver, as CPLEX, in an offline scenario, where all necessary information from instance to minimize the variance of the incomes per unit of working time among drivers during a pay period is previously known and each solicited transport is guaranteed to be performed by a transport vehicle.

Conclusions and future work

In this paper, we introduce the balanced dispatching problem in passengers transport services BDP-PTS on demand, where all the necessary information is only revealed with the arrival of the solicited transport services, i.e. under an online scenario. The goal is to minimize the income variance per unit of working time among the drivers during the pay period defined by the transport company, assuming that any solicited transport service will be performed by a transport vehicle wherever possible.

To give us insights about a quality measure for a possible solution of the balanced dispatching problem in transport passengers transport services on demand, we addressed BDP-PTS under an offline scenario, where all necessary information from Table 4: Results obtained for the online dispatching algorithms. The data is grouped for the complete instance of each dataset. The reported indicators are: the total number of solicited transport services that are performed along with the percentage value respect to the total number of solicited transport services (rows Trp), the number of transport vehicle that performed at least a demanded transport service and its equivalent percentage respect to the total number of transport vehicle available during the pay period (rows Trv), the sum of the incomes in thousands of Chilean pesos obtained by the drivers from the solicited transport service that were performed and its percentage value according to the sum over the fare of solicited transport services is reported (rows Inc) and the standard deviation of the incomes in thousands of Chilean pesos per minute obtained by the drivers from the solicited transport service that were performed and its equivalent percentage according to the best-known solution (rows Std Dev). the instance to minimize the variance the income variance per unit of working time among the drivers is previously known, guaranteeing that the maximum number of solicited transport services are performed. Our research is focused on a set of particular instances, called complete, which admit at least a feasible solution where each solicited transport service is performed by a transport vehicle. Consequently, we prove the NP-completeness in the strong sense of BDP-PTS under an offline scenario for these instances and formulate a mixed integer quadratic programming (MIQP) model for solving it.

Dataset

In order to devise a solution to BDP-PTS on demand, we propose five easy-to-implement online dispatching algorithms based on dispatching rules. These rules are based on the variance analysis of the incomes per unit of working time.

We explore the performance of the proposed online dispatching algorithms, conducting computational experiments. Different data sets of real complete instances from a Chilean transport company are considered. In general, the obtained results show that all algorithms for all datasets under study report an average dispatching time is less than one-tenth of a second, at least 98% of solicited transport service were performed, and at most 4% of total incomes from the solicited transport ser-vices were not obtained in the considered pay periods, such as a labour day, one week and one month.

The main difference is obtained in the standard deviation of the incomes in Chilean pesos per minute, suggesting that the online dispatching algorithm based on the dispatching rule, called SRV, reports the best performance indicator values. These results are consistent with an easy-to-implement online dispatching algorithm able to reduce more efficiently the income dispersion among drivers within reduced running times, allowing a practical implementation into an automated dispatching system on a basic hardware structure generally available in the transport companies in developing countries.

From the computational experiments, we remark that the second-best was the current online dispatching algorithm based on the dispatching rule, called SR, which is used by a Chilean transport company.

To compare the best online dispatching algorithm with the solution obtained under an offline scenario, a comparison with the MIQP model over CPLEX is carried out. The main results are: a) the limits of CPLEX to determine the optimal solution, even in the small complete instance i.e. a pay period of 1 day. However, CPLEX provides a better solution for all considered datasets; and b) the main differences between the distribution 1 (day) Figure 2: Distribution of incomes in Chilean pesos per minute obtained by the drivers from the solicited transport service that were performed. The axis y in the boxplot and all quantity reported in the table correspond to Chilean pesos per minute obtained by the drivers from the solicited transport service that were performed. The data is grouped by datasets for the online dispatching algorithm based on the dispatching rule called SRV and the MIQP model over CPLEX. The Q, Q and Q denote the minimum, average and maximum values, respectively. The first, second and third quartiles values are respectively described by Q 1 , Q 2 and Q 3 . of both solutions are found in the extremes values (minimum and maximum value, converging to be similar in central values when the size of pay period increases. These results imply that most drivers obtain a similar income per unit of working time.

Finally, we propose to address two associated problems for future research, which could improve the performance indicators of the online dispatching algorithms: a) the determination of the pay period and b) the definition of the disjoint intervals of the fare transport services that determine the ranking considered in the dispatching rules SR and SRV. We open the decision problem on the completeness of an arbitrary instance of BDP-PTS on demand, the possible linearization of the mathematical model in order to find the optimal solution or near optimal solution for the general case in reduced running times, and the study of the trade off among different objectives such as service quality among others by using different formulations, implementation and online dispatching algorithms, aiming towards a multi-objective framework. The equality of these two above expressions give us the following (omitted the 1/|M| factor):

0 =2 ê1 (A 2 + v i ) -ê2 (A 1 + v i ) 2ê 1 ê2 2 -2 ê1 (A 2 + v i + v i ) -ê2 A 1 2ê 1 ê2 2 = 2 (2ê 1 ê2 ) 2 (ê 1 (A 2 + v i + v i ) -ê2 A 1 ) 2 -(ê 1 (A 2 + v i ) -ê2 (A 1 + v i )) 2 = 2 (2ê 1 ê2 ) 2 ((ê 1 (A 2 + v i ) -ê2 A 1 ) + ê1 v i ) 2 -((ê 1 (A 2 + v i ) -ê2 A 1 ) -ê1 v i ) 2 = 2 (2ê 1 ê2 ) 2 2v i (ê 2 (A 2 + v i ) -ê2 A 1 ) (ê 1 + ê2 ) + (ê 1 v i ) 2 -(ê 2 v i ) 2 ,
then, since 0 < δ 1,2 := ê1 /ê 2 < ∞ and have

0 = 2ê 2 2 v i (2ê 1 ê2 ) 2 2δ 2 1,2 (A 2 + v i ) + 2δ 1,2 (A 2 + v i ) -δ 1,2 A 1 -2A 1 + δ 2 1,2 v i -v i = 2ê 2 2 v i (2ê 1 ê2 ) 2 δ 2 1,2 (2A 2 + 2v i + v i ) + δ 1,2 (2A 2 + 2v i -2A 1 ) -(2A 1 + v i )
Finally, we focus on the convex function

δ 2 1,2 (2A 2 + 2v i + v i ) + δ 1,2 (2A 2 + 2v i -2A 1 ) -(2A 1 + v i ) ,
which the roots are given by

δ * 1,2 = A 1 -A 2 -v i v i + 2v i + 2A 2 ± (v i + A 2 -A 1 ) 2 + (v i + 2v i + 2A 2 )(v i + 2A 1 ) v i + 2v i + 2A 2

Figure 1 :

 1 Figure 1: Illustration of an instance and a dispatching solution for BDP-PTS on demand. The instances have |I| = 14 solicited transport services and |M| = 6 transport vehicles. The time windows are |J| = 6 with a pay period equal to 15. Each solicited transport services i ∈ I has a fare service v i proportional to the travel time b i .The dispatching solution is that each transport service can be performed. Each vehicle m ∈ M has a subset of time windows J m ⊂J, a subset of solicited transport services i ∈ I m ⊂ I that can performed and the working time êm . The dispatching solution is represented by the number of solicited transport services, in bold type, performed by each transport service. Notice that the variance of the incomes per unit of working time among the drivers is equal to zero. Consequently, this instance admits at least a feasible solution where each solicited transport service is performed by a transport vehicle.

Algorithm 1 :

 1 Online dispatching algorithm. Data: Information of transport vehicles and a new solicited transport service i . Result: A new solicited transport service i discarded or assigned to a transport vehicle m * 1 if there is an available transport vehicle m such that I j ∩ I m ∅ then 2 Dispatch the transport vehicle m which can perform the new solicited transport service i defined by a dispatching rule, m * := m 3 else 4 Propose a new starting time âi at which the first available transport vehicle m would perform the new solicited transport service i . 5 if âi is accepted then 6 Dispatch the transport vehicle m which can perform the new solicited transport service i defined by a dispatching rule, m * := m

  CRediT authorship contribution statement Javier Moraga-Correa: Conceptualization, Methodology, Software, Validation, Data Curation, Formal analysis, Investigation, Writing -original draft, Writing -review & editing, Visualization. Luis Rojo-González: Conceptualization, Method-ology, Software, Validation, Data Curation, Formal analysis, Investigation, Writing -original draft, Writing -review & editing, Visualization. Franco Quezada: Conceptualization, Methodology, Software, Validation, Data Curation, Formal analysis, Investigation, Writing -original draft, Writing -review & editing, Visualization. Óscar C. Vásquez: Conceptualization, Methodology, Software, Validation, Data Curation, Formal analysis, Investigation, Writing -original draft, Writing -review & editing, Visualization, Project administration.

Table 1 :

 1 Notation used in the balance dispatching problem in transport services on demand

	Symbol	Meaning
	I	: Set of solicited transport services and i ∈ I denotes a trans-
		port service.
	h i	: Request time of solicited transport service i
	a i	: Starting time of solicited transport service i
	b i	: Travel time of solicited transport service i
	v i	: Fare of solicited transport service i
	J	: Set of time windows and j ∈ J denotes a time window
	d j	: Starting time of time window j
	e j	: Duration of time window j
	M	: Set of transport vehicles and m ∈ M denotes a transport
		vehicle.
	J m	: Subset of time windows where transport vehicle m is avail-
		able.
	êm	: Working time of transport vehicle m ( êm := j∈Jm d j )
	I m

  Q 1 96.80 38.16 100.41 101.84 130.18 123.08 Q 2 116.67 99.60 116.21 115.96 131.66 130.73 Q 92.13 91.14 99.37 101.04 130.86 126.47 Q 3 123.79 122.74 125.10 127.87 132.92 135.82 Q 188.30 215.29 168.56 145.89 137.07 254.45

				2 (week)	3 (month)
		MIQP	SRV	MIQP	SRV	MIQP	SRV
	Q	0.00	0.00	0.00	0.00 102.34	35.13

Acknowledgement

The authors would like to thank Patricio J. Araya-Córdova and Fabián Díaz-Nuñez in preliminary versions of this research, and the anonymous referees who spotted errors and provided important suggestions to improve this manuscript. The authors are grateful for partial support from the following sources: ANID Beca Magíster en el Extranjero, Becas Chile, Folio 73190041 (Javier Moraga-Correa) and Folio 73201112 (Luis Rojo-González), ANID Beca Doctorado en el Extranjero, Becas Chile, Folio 72190160 (Franco Quezada), Universidad de Santiago de Chile, Proyecto DICYT 061817VP ( Óscar C. Vásquez), and the supercomputing infrastructure of the NLHPC (ECM-02).

Appendix A. Variance of the incomes per unit of working time among the drivers at time t during the pay period defined by the transport company

The variance of the incomes per unit of working time among the drivers during the pay period defined by the transport company at time t is defined as follows: