Taxi Transportation Optimization Problem

S.Ali Yahoubnejad, Mojtaba Farokhi

In this project, we asked to optimize the following aspects of scheduling a workday for a hypothetical taxi agency.

• Phase 1: Minimizing the number of taxi drivers

• Phase 2: Minimizing the amount of time in which the taxi has no passenger in order to minimize the environmental cost

• Phase 3: To find an optimal point according to the trade-off between minimizing the number of cars and environmental cost

This project contains several datasets, and each dataset consist of N trips which are denoted by a_i, b_i, s_i (a.k.a. c) , d_i:

• a_i: the start time of trip i

• b_i: the end time of trip i

• s_i: the starting point of the trip i

• d_i: the ending point of the trip i

In the project, the class Trip is defined to model trips in our implementation.

There is also a MatrixD which shows the distances between every point in our problem, e.g. element d_zy indicates the distance between location z and y. There is a dictionary in our implementation called dist that represents this matrix.

Note that the taxi agency is located at location 1.

After each trip, the taxi driver can go back to the agency or go for another trip. After finishing a trip, we can decide whether the driver come back to the agency with no passenger or taking another available trip.

---

Phase 1

This minimization can be achieved using either Minimum Cost Flow network problem or mathematical modeling (Integer Programming).

Minimum Cost Flow Problem Model

Assume that the flow in the minimum cost flow problem denotes the number of taxi drivers and each trip is represented by two nodes (s_i, d_i). Hence, the problem is modeled in a way that the capacity of edges and the demands of nodes restrict the network flow to solve the problem.

In the figure below, the network model is depicted for only two trips. Obviously, the maximum required number of cars is equal to two. The lower and upper bound of the edges (S₁, D₁) and (S₂, D₂) force the model to assign exactly one taxi to each trip.

The cost of bypass arc (Agency, Agency) is set to be -1 so that the model passes flow through this arc as much a possible and minimizes the flow (number of cars) in the main network. The upper bound of the bypass arc is equal to N. If the flow fills the bypass arc completely, it means there is no car assigned to any trip.

The edge (D₁, S₂) shows if a taxi can start trip 2 after trip 1 was finished.

Considering the fact that the Netwokx library does not support lower bound constraints on edges, we had to do a technique and simulate these constraints by the corresponding demand capabilities of nodes. The technique is to set -1 as demands on S_i and 1 on D_i respectively as depicted in the following figure.

After solving this model using networkx.network_simplex, the minimum number of cars is equal to N-f where f is the flow of bypass arc.

The following figure is the solved network for General-Dataset-1.txt. The orange arcs show the passed flows (taxies). Note that the bypass arc is not plotted in order to simplify the model. The optimal car assignment for this problem is:

• taxi 1: trip 0 - trip 8

• taxi 2: trip 1 - trip 3 - trip 9 - trip 5

• taxi 3: trip 2 - trip 7

• taxi 4: trip 4 - trip 6

The minimum number of required taxis is equal to 4.

The solved model for dataset d1.txt:

• taxi 1: trip 0 - trip 6 - trip 7

• taxi 2: trip 1 - trip 8

• taxi 3: trip 2 - trip 9

• taxi 4: trip 3 - trip 5

• taxi 5: trip 4

The minimum number of required taxis is equal to 5.

Integer Programming Model

The Integer Programming model is basically our network model which is formulated mathematically to be solved by an integer programming solver (in this case pulp library). The formulation is as follows:

Table 1. Benchmarks

Dataset	Network Simplex RunTime (sec)	ILP RunTime (sec)
General-Dataset-1	0.00131	0.01856
General-Dataset-2	0.21077	0.77281
General-Dataset-3	7.55162	25.65958
d1	0.00119	0.01160
d2	0.08989	0.31820
d3	15.74275	61.40548

Table 2. Results

Dataset	Network Simplex Optimal Solution	ILP Optimal Solution
General-Dataset-1	4	4
General-Dataset-2	47	47
General-Dataset-3	173	173
d1	5	5
d2	36	36
d3	200	200

Phase 2

Like the 1^st phase, this minimization can also be achieved using either Minimum Cost Flow network problem or mathematical modeling (Integer Programming).

Minimum Cost Flow Problem Model

In this phase, the objective is to minimize the time in which the taxies are traveling without any passengers. The arcs that indicate this situation are:

• (Aency, S_i): The taxi leaving the agency to pick up a passenger

• (D_i, Agency): The taxi returning to the agency with no passenger

• (D_i, S_j): The i^th trip is finished and the taxi is going for the j^th trip

Each arc has its own cost which is calculated according to the distance between its source and destination.

The following figure indicates the model for two trips. In this phase, there is no concern about minimizing the number of required cars, so the cost of bypass arc is set to be zero.

The following figure is the solved network for General-Dataset-1.txt. The optimal car assignment for this problem is:

• taxi 1: trip 0 - trip 3 - trip 9 - trip 5

  • cost = 18 + 0 + 11 + 7 + 11

• taxi 2: trip 1 - trip 8

  • cost = 20 + 8 + 20

• taxi 3: trip 2 - trip 4 - trip 6

  • cost = 11 + 0 + 12 + 6

• taxi 4: trip 7

  • cost = 4 + 18

The number of required taxies: 4 The minimum environmental cost: 146

The solved model for dataset d1.txt:

• taxi 1: trip 0

  • cost: 16 + 0

• taxi 2: trip 1 - trip 6

  • cost: 20 + 8 + 4

• taxi 3: trip 2 - trip 5

  • cost: 19 + 0 + 19

• taxi 4: trip 3 - trip 7

  • cost: 20 + 8 + 20

• taxi 5: trip 4 - trip 8 - trip 9

  • cost: 16 + 4 + 0 + 0

The number of required taxies: 5 The minimum environmental cost: 154

Integer Programming Model

Same as phase1, the Integer Programming model our network model which is formulated mathematically to be solved by pulp. The formulation is as follows:

Table 3. Benchmarks

Dataset	Network Simplex RunTime (sec)	ILP RunTime (sec)
General-Dataset-1	0.00133	0.01215
General-Dataset-2	0.17367	12.92621
General-Dataset-3	6.90205	N.A
d1	0.00126	0.01155
d2	0.07989	2.99807
d3	4.32141	N.A

Table 4. Results

Dataset	Network Simplex Optimal Solution		ILP Optimal Solution
	Min Env. Cost	Car Number	Min Env. Cost	Car Number
General-Dataset-1	146	4	146	4
General-Dataset-2	1382	54	1382	47
General-Dataset-3	4905	177	N.A	N.A
d1	154	5	154	5
d2	997	42	997	36
d3	5769	201	N.A	N.A

Tip	The differences between the car numbers in the network model and ILP model is just because of Alternative Optimal Solution

Phase 3

From real-life experience, we know that salvation is to obtain the best of the two worlds (phase 1&2). In another word, in this phase, we want to minimize not only the number of required cars but also the environmental cost.

We have two main ideas to obtain this objective:

Idea 1

The phase2 model can also be improved with a few tweaks to achieve the desired behavior. By setting the cost of bypass arc to -1, the solver chooses the minimum number of required cars and then assigns these cars in a way that the environmental cost will also get minimized.

The minimum number of required cars and environmental cost is calculated as below:

• The minimum number of required cars: N - f

• The environmental cost: model objective value + f

Idea 2

According to this idea, the minimum number of required cars is calculated using phase1. Suppose that the minimum number of required cars is equal to n. Then we check if allowing more cars up to a certain threshold (10%) can reduce environmental cost by running phase2 and comparing its results for the corresponding number of cars. Therefore, the phase2 model should be changed in order to utilize all of the input flows (cars). It means that no flow is permitted to pass through the bypass arc. In order to do this, the cost of bypass arc should be equal to infinity.

The optimal answer according to the specified situation (with respect to 10% loss in profit for the benefit of the environment) is the best solution of the mentioned iterations.

As you may have already noticed, there is a performance problem here due to the number of iterations. However, to make things a little bit better, we can calculate the minimum environmental cost (using phase2) and then use it to terminate the iterations whenever we reach the minimum environmental cost.

Table 5. Results

Dataset	Version 1		Version 2
	Optimal Car Number	Optimal Env. Cost	Optimal Car Number	Optimal Env. Cost
General-Dataset-1	4	146	4	146
General-Dataset-2	47	1382	47	1382
General-Dataset-3	173	4905	173	4905
d1	5	154	5	154
d2	36	997	36	997
d3	200	5769	200	5769