Sage Journals: Discover world-class research

Abstract

The massive use of cars in cities brings several problems such as traffic congestion and air pollution. Carpooling is an effective way to reduce the use of cars on the premise of meeting passenger transport needs. However, route planning will influence the efficiency of carpooling. By now, most researches on the route planning of carpooling mainly pay attention to minimizing the total driving distance of cars, but for passengers, the most crucial thing is to get to the destination as soon as possible. And in most cases, the minimum total driving distance of cars does not mean the minimal average arriving distance of all passengers. To address this issue, in this article, we formulate a novel carpooling route calculation problem with the objective of minimizing the average arriving distance of all passengers in carpooling. Then, we prove that this problem is NP-hard. To solve this problem, for the situation that the vehicle capacity is sufficient to deliver all passengers, we propose a heuristic algorithm named SimilarDirection with $2 c$ approximation ratio in delivery order calculation phase, where $c$ is the capacity of each vehicle. For the situation that the vehicle capacity is insufficient, we provide three algorithms named DelFar, Unchanged, and DelRan. Experimental results show that our SimilarDirection algorithm can produce less average arriving distance of all passengers than other three contrast algorithms in both the real-world dataset experiments and the synthetic dataset experiments, and DelFar has the best performance in producing less average arriving distance when the vehicle capacity is insufficient.

Keywords

Carpooling route planning NP-hard average arriving distance

Introduction

Vehicles have become an indispensable part of human life in modern society. Among all the vehicles, cars play a critically salient role in current urban traffic. It gradually becomes one of the most common tools for people to travel for convenience and comfort. According toNational Statistics,¹ there were about 31.3 million cars used on the roads in Great Britain at the end of March 2018. However, substantial use of cars in cities engenders egregious impacts on many aspects, such as traffic congestion, air contamination, massive gas consumption, and so on.^2–4 Therefore, it is urgent to make reasonable use of limited resources to effectively alleviate these urban pressures. A phenomenon frequently happens in our daily life that numerous cars run with empty seats, which wastes the transportation resources. As a result, we should efficiently use the empty seats of the urban traffic systems to improve its efficiency.^5,6 To this end, in recent years, there has been an increasing interest in carpooling for the purpose of optimizing the use of cars. That is to say, we should try our best to make cars as fully loaded as possible. Carpooling is a relatively environmentally friendly way of traveling, in which drivers assign empty seats to passengers with similar travel routes.^7,8 Since the 1970s, carpooling was on the rise in some developed countries. For instance, in Germany, carpooling is considered as an environmental event, and the government takes administrative measures to encourage carpooling.⁹ Recently, in many cities of China, such as Beijing, Shanghai, and Guangzhou, more and more people choose carpooling as their way of traveling. Carpooling brings passengers, who have the same destination, or similar directions into one car, which can reduce fuel consumption, travel costs, and transportation costs, and significantly increase the occupancy rates.

There have been a number of studies that concentrate on carpooling on several aspects, such as route planning, carpooling applications, and social network in carpooling. However, most studies in terms of route planning mainly focus on minimizing the total driving distance of cars on the premise of delivering passengers to their destinations,^10–12 but it may give some passengers a bad user experience. For example, in Figure 1, there are three people $p_{1}$ , $p_{2}$ , and $p_{3}$ and two vehicles $v_{1}$ , and $v_{2}$ . Each vehicle has four seats. All the people and vehicles are at place $o$ at the beginning, and all three people have different destinations. If we use a method whose optimization objective is minimizing the total driving distance of vehicles, we will choose one of the two vehicles to deliver all the three people. This method minimizes the total driving distance. However, for $p_{3}$ , it takes more distance for him or her to get to the destination, because we have a better choice for delivering $p_{1}$ , $p_{2}$ by $v_{1}$ and $p_{3}$ by $v_{2}$ actually. In contrast, the latter method minimizes the average arriving distance of all people, which is a more concerned point for passengers.

Figure 1.

Three passengers $p_{1}$ , $p_{2}$ , $p_{3}$ with destinations $d_{1}$ , $d_{2}$ , $d_{3}$ set off at $o$ at the beginning, and two candidate vehicles $v_{1}$ , $v_{2}$ used for delivering the three passengers to their destinations also set off at $o$ at first. If we aim at minimizing the total driving distance of vehicles, we will choose one of the two vehicles to deliver all the three people. However, if we use $v_{1}$ to deliver $p_{1}$ , $p_{2}$ and use $v_{2}$ to deliver $p_{3}$ , we can reduce the distance for $p_{3}$ to get to his or her destination despite that the total driving distance is not the minimum.

Proposing an algorithm for minimizing the average arriving distance in carpooling is the motivation for us to write this article, while few studies take note of this kind of problem at present. We mathematically formulate a carpooling route calculation problem which focuses on minimizing the average arriving distance of all passengers. Then, we prove that this problem is NP-hard. A heuristic algorithm named SimilarDirection is provided to solve this problem for the situation that the total capacity of all vehicles is not less than the number of passengers. The main idea of the algorithm is to assign people whose destinations are located near a specific straight line to the same vehicle, including three phases: actual passenger number determination phase that determines the passenger volume of each vehicle, passenger assignment phase that decides which people will be assigned to the same car, and delivery order determination phase that determines the delivery order of passengers in the same vehicle. When the vehicle capacity is insufficient, we provide three algorithms called DelFar, Unchanged, and DelRan to solve this problem. We use BaiduMap API to obtain a dataset including the location of 400 hotels and the road length between each pair of hotels. This dataset is used for our real-world dataset experiments, and a synthetic dataset is used for our synthetic dataset experiments. The experimental results show that our algorithm has better performance than the other contrast algorithms in producing average arriving distance. In brief, we have made the following contributions:

Due to the fact that far too little attention has been paid to the minimization of the average arriving distance, we formulate a novel carpooling route calculation problem aiming at minimizing the average arriving distance of all people. To the best of our knowledge, it is the first work concentrating on minimizing the average arriving distance of all passengers in carpooling where drivers don’t have their own predetermined routes, and they serve passengers exclusively.

We prove the NP-hardness of the carpooling problem and propose a heuristic algorithm named SimilarDirection to solve this problem. The SimilarDirection algorithm has $2 c$ approximation ratio in delivery order calculation phase, where $c$ is the capacity of each vehicle. In our article, “approximation ratio” of an algorithm represents the arriving distance of all passengers obtained by this algorithm divided by the optimal arriving distance of all passengers. Considering the special situation of insufficient vehicle capacity, we also provide three algorithms based on SimilarDirection named DelFar, Unchanged, and DelRan.

A real-world dataset obtained from BaiduMap API is tested in our real-world dataset experiments, and a synthetic dataset in which the latitude and longitude of each vertex is randomly generated is tested in our synthetic dataset experiments. In both real-world dataset experiments and synthetic dataset experiments, SimilarDirection produces the least average arriving distance among different algorithms in sufficient vehicle capacity situation, and DelFar has the best performance in producing less average arriving distance on condition that the vehicle capacity is not sufficient.

The rest of the article is organized as follows. We introduce the related work in the “Related work” section. Basic concepts are listed in the “Network model” section and the carpooling route calculation problem formulation is presented in the section “Problem formulation.” In “SimilarDirection: a heuristic algorithm” section, we provide our heuristic algorithm for solving the carpooling route calculation problem. Then, we do several experiments to evaluate the performance of our algorithm and show the results in “Evaluation” section. Finally, we conclude this article in the “Conclusion” section.

Related work

Existing problems of urban traffic

Massive vehicles in the cities not only bring convenience to people but also bring some challenging problems, such as traffic accidents, air pollution, and traffic congestion. With regard to traffic accidents, the increase of vehicles has led to an increase in traffic accidents. In China, from 2015 to 2016, the number of traffic accidents increased by 13%, and the number of deaths due to traffic accidents increased by 8.7%.^13,14 It is foreseeable that the number of traffic accidents and the number of deaths due to traffic accidents will continue to rise in the future. Although this trend is inevitable, it is necessary to reduce the use of vehicles on the premise of meeting passenger transport needs. Meanwhile, the average car occupancy rate, which represents average number of persons carried by a car, is very low nowadays. In America, about 80 million commuters drive with no one else in their cars when commuting according to American Community Survey Reports.⁵ In the United Kingdom, a car carries an average of 1.5 passengers.⁶ It means that numerous cars are running with empty seats, which can be utilized to reduce the number of cars in use. Carpooling thus became a hot research field, because it helps to solve these problems, and allows the passengers to get a financial discount on the ride.

Researches about carpooling

Classical carpooling researches^7,15 mainly focus on the problem where the passengers are regular with fixed routes, so the problem is different from our work. Similar to previous works,^7,15 in He et al.,¹⁶ the authors obtained “frequent route” of passengers by mining users’ GPS trajectories, then they merged several frequent routes to generate a shared route for carpooling. In today’s carpooling researches, a person’s carpooling partners and carpooling routes are usually dynamically changing, which is closer to reality. There are several researches focusing on carpooling, a main concern is developing carpooling applications. Blerim Cici et al.¹⁰ developed a carpooling system named SORS, where drivers and passengers send their requests for a ride beforehand, to deal with dynamic carpooling requests. Desheng Zhang et al.¹¹ designed and implemented a carpooling system with both hardware and software design installed on taxis called coRide to deliver passengers with the object of reducing the total driving distance as possible. Many works explored the research of carpooling such as combining carpooling and social network. Maria Luísa Matos et al.¹² developed a system called GO! that allows passengers to build a network of friends when carpooling with others in. Ahmed Elbery et al.¹⁷ designed a carpooling recommendation system to recommend people join the trip of their friends for carpooling, and other papers focused on the social effects of carpooling such as.¹⁸ Obviously, among all the research directions, a common concern is routing planning. However, to the best of our knowledge, almost all work about carpooling mainly focus on minimizing the total driving distance of cars^10–12 instead of the average arriving distance of all passengers, which will probably cause bad user experiences for passengers. Shih-Chia Huang et al.¹⁹ put forward a concept called “average travel distance of passengers,” and one of their seven objectives is to minimize the “average travel distance of passengers” in carpooling, but a constraint in their study¹⁹ is that drivers have their own routes, which means that drivers are not dedicated to serving passengers, they only provide free ride service to passengers on the basis of completing their own driving routes; this constraint makes the problem different from ours. In fact, the route planning problem in carpooling is a well-known problem called vehicle routing problem (VRP).

VRP

VRP is a classical NP-hard problem which is combinational optimization and integer programming and appeared first in Dantzig and Ramser.²⁰ The purpose is to find the optimal routes that minimize the total routing cost for candidate cars to deliver a given group of passengers. It has many variations such as Vehicle Routing Problem with Pickup and Delivery (VRPPD),²¹ Vehicle Routing Problem with Time Windows (VRPTW),²² Capacitated Vehicle Routing Problem (CVRP),²³ Open Vehicle Routing Problem (OVRP),²⁴ and so on. Among all variations and specializations, OVRP is the most related to our problem because the setting is that vehicles do not need to return to the start point. There are many researches using different algorithms to solve this problem, such as in previous works.^25–32 But like most problems about route planning of vehicles, the objective of OVRP is also minimizing the total driving distance of all vehicles, instead of the total driving distance of all passengers.

Network model

In our problem, there are $m$ passengers denoted as $P = {p_{1}, p_{2}, \dots, p_{m}}$ ; each passenger has a unique destination. The destination set is $D = {d_{1}, d_{2}, \dots, d_{m}}$ . $n$ vehicles are denoted as $V = {v_{1}, v_{2}, \dots, v_{n}}$ ; each vehicle has three properties: capacity with fixed value $c$ , $p$ that represents the actual passenger number of this vehicle with initial value 0, an array names $Ω$ represents the passengers in this vehicle with array size of actual passenger number. Each element in this array is null at first. The definition of actual passenger number will be given later. At the beginning, all the passengers and vehicles are at the same starting point $o$ , which is not in $D$ . Both $o$ and $D$ are parts of a traffic network, which is a complete directed graph $G = (B, E)$ . $B$ is the vertex set. A vertex $b$ in $B$ represents a pair of coordinates $(x, y)$ to show its spatial location, where $x$ is the longitude coordinate of $b$ and $y$ is the latitude coordinate of $b$ . $E$ is the edge set including $| B |^{2}$ elements since $G$ is a complete directed graph. Each element $e$ in $E$ represents the road length (defined below) between two specific vertexes. Briefly speaking, in this article, we aim to find a driving plan that can minimize the average driving distance of all passengers to deliver all the passengers from their common starting point to their different destinations.

Definition 1 (road length)

Given a traffic network $G = (B, E)$ , the road length between vertexes $i$ and $j$ in set $B$ , denoted as $r_{ij}$ , is the minimal driving distance between the two vertexes. In real world, $r_{ij}$ may not be the linear distance between $i$ and $j$ , and even $r_{ij}$ may not be $r_{ji}$ . We will explain this phenomenon in the “Evaluation” section. In this article, we take the latitude and longitude coordinates of $i$ and $j$ as the input parameters, use BaiduMap API to calculate minimal driving distance between $i$ and $j$ . The calculation result is used as $r_{ij}$ , which represents the road length between vertex $i$ and vertex $j$ .

Definition 2 (actual driving distance)

Given a specific driving plan $G' = (B', E')$ , the actual driving distance from vertex $i$ to $j$ in set $B'$ , denoted as $a_{ij}$ , is the distance that a vehicle driving from $i$ to $j$ . Generally speaking, in different driving plans, the actual driving distances from one vertex to another one are different. The actual driving distance from $i$ to $j$ is equal to the road length if and only if it is nonstop from $i$ to $j$ or $e_{ij}$ is not in $E'$ .

Definition 3 (delivery request)

A delivery request $R = (o, D, c, n)$ based on a traffic network $G = (B, E)$ consists of a vertex $o$ and a vertex set $D$ . The vertex $o$ , an element in $B$ , is the starting point of all the people and vehicles. The vertex set $D$ is a subset of $B - {o}$ . It includes the destination of all people. The number of elements in set $D$ is equal to the number of people. In other words, everyone has a different destination; $c$ is the capacity of each vehicle; $n$ is the number of vehicles.

Definition 4 (actual passenger number)

The actual passenger number of a car is the number of passengers that the car will deliver according to a given delivery request $R$ ; it is not greater than the capacity of the car.

Definition 5 (driving plan)

Given a delivery request $R = (o, D, c, n)$ , a driving plan $DP$ is used to determine which passengers to take the same car and the delivery order for passengers in a car can be described as a graph $G' = (B', E')$ where $B' = {o} \cup D$ and the edges $E'$ satisfies (1) $o$ can reach all the vertexes in $D$ ; (2) branches only exists at the starting point $o$ .

Definition 6 (arriving distance)

Given a specific driving plan $G' = (B', E')$ where $B' = {o} \cup D$ , the arriving distance $A_{i}$ of a vertex $i$ in $D$ is equivalent to $a_{oi}$ , which represents the distance of a people whose destination is $i$ from his or her origin to his or her destination.

Problem formulation

Based on the network model and above definitions, we can formulate the carpooling route calculation problem as follows:

In a traffic network $G = (B, E)$ , a delivery request $R = (o, D, c, n)$ is given, and we find a driving plan $G' = (B', E')$ that can minimize the arriving distance of all people:

Minimize \sum_{i \in D} A_{i}

Subject to:

A passenger can only be delivered by one vehicle from the origin to his or her destination;

All passengers will be delivered to their destination at final;

Each vertex in $D$ will be visited once and only once. In this article, “visit” means that a vehicle passes by and stops at the vertex;

Each vehicle can only pick up the passengers at the starting point $o$ at the beginning. It is not allowed for any vehicle to return to the starting point and pick up other passengers after delivering the passengers;

The total capacity of all vehicles is not less than the number of passengers, that is, $c * n \geq | D |$ .

Theorem 1

The carpooling route calculation problem is NP-hard.

Proof

By imposing a bound on the value to be optimized, we can usually transform a given optimization problem into a related decision problem. In order to prove the NP-hardness of a given optimization problem, we can prove that the related decision problem of this optimization problem is NP-Complete.³³ It is obvious that the carpooling route calculation problem is an optimization problem. Therefore, if the related decision problem of the carpooling route calculation problem is a NP-complete problem, then the carpooling route calculation problem is NP-hard. The related decision problem of the carpooling route calculation problem is, in a traffic network $G = (B, E)$ , a delivery request $R = (o, D, c, n)$ is given, we have to determine whether there exists a driving plan $G' = (B', E')$ that the average arriving distance of all people is not greater than a specific number $k$ . The constraints of this problem are the same as constraints of the carpooling route calculation problem. We set “decision carpooling problem” as the alias of this problem. Next, we have to prove that the decision carpooling problem is NP-complete, in other words, we need to prove that the decision carpooling problem is both NP and NP-hard.

It is easy to prove that the decision carpooling problem is NP, because when a specific driving plan is given, we can consequently calculate the arriving distance of all people in polynomial time and determine whether it is greater than $k$ .

Next, we have to prove that the decision carpooling problem is NP-hard. Apparently, if a special case of the decision carpooling problem is NP-hard, then the decision carpooling problem is NP-hard. We consider a special case of the decision carpooling problem: (1) for any two vertexes $i$ and $j$ , the road length from $i$ to $j$ and the road length from $j$ to $i$ are the same, in other words, the traffic network degenerates from a directed graph to an undirected path; (2) there is only one vehicle in the delivery request $R$ . We set “special decision carpooling problem” as the alias of this problem. We will prove that the special decision carpooling problem is NP-hard.

If a problem is proved to be the reduction from a known NP-hard problem, then this problem is NP-Hard.³³ We will prove the NP-hardness of the special decision carpooling problem by proving hamiltonian path problem, a well-known NP-hard problem, is reducible to the special decision carpooling problem. Let $H = (B, L)$ be an instance of hamiltonian path problem. We formulate an instance of the special decision carpooling problem as follows. We form the traffic network in the special decision carpooling problem as $G = (B, E)$ , where $E = {e_{ij} | i, j \in B and i \neq j}$ , and we define the road length $r_{ij}$ by

r_{ij} = {\begin{matrix} 0 : if e_{ij} is in L \\ 1 : if e_{ij} is not in L \end{matrix}

$G$ is undirected, hence there is at most one edge between each pair of vertexes in $B$ . And for all vertexes in $B$ , the road length from one vertex to itself is 1. The instance of the special decision carpooling problem is with traffic network $G = (B, E)$ and delivery request $R = (o, B - {o}, | B - {o} |, 1)$ .

We will prove that “the graph $H$ has a hamiltonian path $h$ that starts from $o$ ” is equal to that “the special decision carpooling problem has a driving plan with average arriving distance is 0.” Provided that graph $H$ has a hamiltonian path $h$ that starts from $o$ . For any edge in $h$ , it is a part of $L$ , so it has a road length 0 in $G$ . As a result, $h$ is a driving plan of the special decision carpooling problem with the average arriving distance 0. On the contrary, provided that the special decision carpooling problem has a driving plan $h'$ that the average arriving distance is 0. Because the road length of each edge in $E$ is 0 or 1, each edge on the driving plan has exactly road length 0. Therefore, the edges in $h'$ only come from $L$ . Accordingly, $h'$ is a hamiltonian path that starts from $o$ in graph $H$ .³³ Thus, it can be seen that the special decision carpooling problem is the reduction from hamiltonian path problem.

Hamiltonian path problem is reduced to the special decision carpooling problem, so the special decision carpooling problem is proved to be NP-hard, thus the decision carpooling problem is NP-hard. Since the decision carpooling problem is NP, the decision carpooling problem is both NP and NP-hard, in other words, it is NP-complete. As the decision carpooling problem is NP-complete, the carpooling route calculation problem is NP-hard. ■

Since the carpooling route calculation problem is NP-hard, the time required for solving the carpooling route calculation problem grows rapidly along with the increase of the number of destinations in the delivery request. Hence, it is impossible to find an optimal algorithm to solve this problem. Therefore, a heuristic algorithm is proposed in this article.

SimilarDirection: a heuristic algorithm

In this section, we propose a heuristic algorithm called SimilarDirection including three phases: actual passenger number determination, passenger assignment, and delivery order determination. First, we give a brief description and the pseudo-code of the three phases of our heuristic algorithm, then give the pseudo-code of SimilarDirection.

Actual passenger number determination

In order to minimize the average arriving distance of all people, we will utilize all available vehicles as possible, so the key is how to determine the actual passenger number of each vehicle. It is forbidden to use the method that aims to simply fill up the vehicles because it will cause idle vehicles. For example, there are eight passengers and three vehicles; each vehicle has four seats. If we use the method we mentioned above, the first two vehicles will be full and the remaining vehicle will be empty. We need to find an effective algorithm to improve the utilization rate of all available vehicles.

The main idea of our actual passenger number determination algorithm is as follows: given a delivery request $R = (o, D, c, n)$ , we can know that there are $n$ vehicles, each has a capacity of $c$ , and the number of passenger is $| D |$ . Then, we define two integer variables $q$ and $w$ . $q$ represents the number of vehicles remained with initial value $n$ , and $w$ represents the minimum of the number of passengers remained with initial value $| D |$ and the total capacity of all vehicles. The actual passenger number of the first vehicle $p_{1}$ is $⌈ w / q ⌉$ . Then, the value of $w$ is decreased by $p_{1}$ ; the value of $q$ is decreased by 1; the actual passenger number of the second vehicle $p_{2}$ is $⌈ w / q ⌉$ and so on until the value of $w$ is 0.

Algorithm 1. Actual Passenger Number Determination
Input: traffic network $G = (B, E)$ , delivery request $R$ , Vehicles array $V$ Output: $V$ that the $p$ value of all elements in $V$ are assigned 1: $q = n$ 2: $w = \min {\| D \|, c \times n}$ 3: $i = 1$ 4: $p = 0$ 5: while $w \neq 0$ do 6: $p = ⌈ \frac{w}{q} ⌉$ 7: $v_{i} . p = p$ 8: $w = w - p$ 9: $q = q - 1$

Passenger assignment

In most cases, for a vehicle driver, when his or her vehicle is already loaded with passengers, he or she prefers to pick up a passenger that meets the following conditions: (1) on the direction that is the most similar to existing passengers in his or her vehicle among all candidate passengers and (2) causing least “extra distance” for existing people to arrive at their destinations among all candidate passengers. If condition (1) contradicts condition (2), the driver will choose the people that satisfies condition (2).

For example, in Figure 2, an empty vehicle $V$ with two seats set off at $o_{1}$ at first, and three passengers $p_{1}$ , $p_{2}$ , $p_{3}$ with destinations $d_{1}$ , $d_{2}$ , $d_{3}$ also set off at $o_{1}$ at the beginning. Suppose that passenger $p_{1}$ is an important person that must be delivered, so first we add passenger $p_{1}$ into $V$ . Now, $V$ is loaded with passenger $p_{1}$ and there is only one empty seat left. The driver should choose only one passenger from $p_{2}$ and $p_{3}$ , and use vehicle $V$ to deliver him or her. According to the two conditions we mentioned above, he or she will choose $p_{2}$ to pick up because $p_{2}$ satisfies both condition (1) and condition (2). If we change the position of $d_{2}$ and $d_{3}$ as Figure 3, then we will see that $p_{3}$ satisfies condition (2) and $p_{2}$ satisfies condition (1), as what we said before, condition (2) has a higher priority so the vehicle driver will choose $p_{3}$ to pick up.

Figure 2.

How will a driver choose passengers to deliver in reality: An empty vehicle $V$ with two seats set off at $o_{1}$ at first, and three passengers $p_{1}$ , $p_{2}$ , $p_{3}$ with destinations $d_{1}$ , $d_{2}$ , $d_{3}$ also set off at $o_{1}$ at the beginning. The number of passengers is three but there are only two empty seats on the vehicle $V$ , so the driver has to choose two passengers to deliver. First, the driver picks up passenger $p_{1}$ because we assume that passenger $p_{1}$ is an important person that must be delivered. Then, the driver should choose one passenger to be delivered from $p_{2}$ and $p_{3}$ , $p_{2}$ satisfies both condition (1) and condition (2), so $p_{2}$ will be chosen.

Figure 3.

The position of $d_{2}$ , $d_{3}$ are changed, so in this time, the driver should choose $p_{3}$ to pick up. The reason for picking up $p_{3}$ is that $p_{3}$ satisfies condition (2) while $p_{2}$ satisfies condition (1), and condition (2) has a higher priority.

Inspired by the passenger selection rules used frequently in reality, we provide a passenger assignment algorithm aiming at assigning passengers with similar directions to their destinations in a vehicle. This algorithm will formulate the driving route of each vehicle as a straight line as much as possible. The main idea of the passenger assignment algorithm is as follows: First, we find a passenger $p_{1}$ whose destination $d_{1}$ is farthest to the origin $o$ . Second, we add $p_{1}$ to an empty vehicle $v_{1}$ and use the direction from $o$ to $d_{1}$ as the baseline direction. Third, we connect $o$ and $d_{1}$ into a line $o d_{1}$ . Fourth, we need to find a group of passengers that satisfies this condition: for each passenger $p_{g}$ with destination $d_{g}$ in this group, the angle between line $o d_{1}$ and line $o d_{g}$ should be no more than a given angle. This condition is used to ensure the minimum level of direction similarity. In our algorithm, we set the angle as 45°. Fifth, we select some of the passengers in this group to fill up $v_{1}$ in accordance with the distances from their destinations to the line $o d_{1}$ from small to large. We repeat the five steps until there is no passenger to be assigned.

To describe the passenger assignment algorithm more graphically, we use Figure 4 to illustrate the algorithm. In Figure 4, there are two vehicles $v_{1}$ , $v_{2}$ , each with a capacity of four, and eight passengers $p_{1}$ , $p_{2}$ , …, $p_{8}$ with destinations $d_{1}$ , $d_{2}$ , …, $d_{8}$ at the starting point $o$ , so each vehicle should deliver four passengers. Now we show how to choose passengers for vehicle $v_{1}$ . First, we find that the farthest vertex $f$ from the starting point $o$ is $d_{1}$ , then we add passenger $p_{1}$ into vehicle $v_{1}$ . Then we find a set $Q$ = {vertex $b$ | the angle between $ob$ and $of$ is not greater than 45°, and $b$ is in set $D - {f}$ }, the passengers with destinations in $Q$ are regarded as candidate passengers to be added into vehicle $v_{1}$ . In Figure 4, the candidate passengers are $p_{2}$ , $p_{3}$ , $p_{4}$ , $p_{5}$ , we need to choose three passengers to be added into vehicle $v_{1}$ from the four candidate passengers. We order the four passengers according to the distance of their destinations to the line $o d_{1}$ from small to large; as we can see, the order of the four destinations according to the distance to the line $o d_{1}$ from small to large is $d_{2}$ , $d_{3}$ , $d_{4}$ , $d_{5}$ , then the order of the four passengers is $p_{2}$ , $p_{3}$ , $p_{4}$ , $p_{5}$ , so we add passengers $p_{2}$ , $p_{3}$ , $p_{4}$ into vehicle $v_{1}$ .

Figure 4.

An example of our passenger assignment algorithm.

Delivery order calculation

In delivery order calculation phase, we use a simple algorithm based on minimum spanning tree to determine the delivery order of passengers in the same vehicle, called VariantMST. The main idea is as follows: to calculate the delivery order of passengers in a given vehicle, we first define a completed directed graph $G_{0}$ , its vertex set includes the destination of the passengers in this vehicle and the origin $o$ , and each element in its edge set represents the road length between two specific vertexes. Second, we use an algorithm (such as Prim algorithm, Kruskal algorithm, etc.) to calculate the minimum spanning tree $MST$ of graph $G_{0}$ . Third, we use an algorithm given in Zhang et al.¹¹ to eliminate branches in $MST$ , then we get a tree $DO$ that represents the delivery order of the passengers in this vehicle.

We use Figure 5 to illustrate the branches elimination algorithm in Zhang et al.¹¹ The left tree $MST$ is a minimum spanning tree; in this tree, vertex $A$ is the origin, and the other five vertexes represent the destination of five passengers. To eliminate branches in this tree, we double the edges in $MST$ and get a depth-first traversal $A \to B \to D \to E \to D \to F \to D \to B \to A \to C$ . As we can see, the traversal has same vertexes so it cannot be a delivery order. Next, we shortcut some edges to ensure that each vertex is visited once and only once. Finally, we get the delivery order tree $DO$ , and the delivery order is $B \to D \to E \to F \to C$ .

Figure 5.

An example to show the branches elimination algorithm provided in Zhang et al.¹¹

Theorem 2

The VariantMST algorithm has an approximation ratio of $2 c$ , where $c$ is the capacity of each vehicle. That is, the arriving distance obtained by the VariantMST algorithm is at most $2 c$ times the optimal arriving distance.

Proof

We will prove that, for any vehicle, the arriving distance of passengers in this vehicle obtained by our VariantMST algorithm is at most $2 c$ times the optimal arriving distance of passengers in this vehicle. Let $Q (\cdot)$ and $R (\cdot)$ be two functions that calculate the total driving distance of a tree and the arriving distance of a tree, respectively. And we define $OPT$ as the tree that represents the optimal delivery order.

When $c = 1$ , the delivery order obtained by the VariantMST algorithm is the same as the optimal delivery order, for there is at most one passenger to be delivered. When $c > 1$ , (1) $R (DO) < cQ (DO)$ , this is because that, when we calculate the total driving distance of a tree, the length of each edge will be added only once. $cQ (DO)$ means that the length of each edge in $DO$ is added $c$ times. But when we calculate the arriving distance, there is only one edge in $DO$ whose length will be added $c$ times, the rest of the edges in $DO$ will be added at most $c - 1$ times. Therefore, $R (DO) < cQ (DO)$ . (2) $Q (DO) < 2 Q (MST)$ , because in the minimum spanning tree $MST$ , there may be branches, or there may be no branches. If there is no branch in $MST$ , then $DO$ is actually $MST$ , so $Q (DO) = Q (MST) < 2 Q (MST)$ . If there is at least one branch in $MST$ , there is no direct edge between at least one pair of points. In the simplest case, there is only one branch in the minimum spanning tree. That is to say, in doubled $MST$ , if you want to go from any point in the pair to another point in the pair, you need to go through at least two edges. To eliminate branches in $MST$ to get $DO$ , we should shortcut doubled $MST$ . For this pair of points without a direct edge between themselves, we delete at least two edges between the two points and add only one direct edge between the two points to obtain $DO$ . Because of the triangle inequality, the sum of the lengths of the edges we delete is always larger than the length of the added edge, so $Q (DO) < 2 Q (MST)$ . Similarly, the inequality is still valid in the case of multiple branches. (3) $Q (MST) \geq Q (OPT)$ . If $MST$ is exactly $OPT$ , then $Q (MST) = Q (OPT)$ . Otherwise, $Q (MST) < Q (OPT)$ , because $MST$ is the smallest spanning tree and $OPT$ is just a spanning tree. In conclusion, $Q (MST) \leq Q (OPT)$ . (4) It is self-evident that $Q (OPT) < R (OPT)$ , because when we calculate $Q (OPT)$ , the length of each edge in $OPT$ will be added only once. When we calculate $R (OPT)$ , there is only one edge in $OPT$ whose length will be added only once; the rest of the edges in $OPT$ will be added at least twice. So, $Q (OPT) < R (OPT)$ . In conclusion, $R (DO) < cQ (DO) < 2 cQ (MST) \leq 2 cQ (OPT) < 2 cR (OPT)$ , then $(R (DO) / R (OPT)) < 2 c$ . From here, we see that, for any vehicle, the arriving distance of passengers in this vehicle obtained by our VariantMST algorithm is at most $2 c$ times the optimal arriving distance of passengers in this vehicle. Therefore, the arriving distance of all passengers obtained by the VariantMST algorithm is at most $2 c$ times the optimal arriving distance. The VariantMST algorithm has an approximation ratio of $2 c$ , where $c$ is the capacity of each vehicle. ■.

Based on the above three algorithms, we give the pseudo-code of our algorithm SimilarDirection in Algorithm 4. And we will show the time complexity of the algorithm SimilarDirection.

Theorem 3

The time complexity of the algorithm SimilarDirection is $O (mn + n c^{2} \lg c)$ , where $m$ is the number of passengers, $n$ is the number of vehicles, $c$ is the capacity of each vehicle.

Proof

The SimilarDirection algorithm includes three phases: actual passenger number determination, passenger assignment and delivery order determination. So the time complexity of the SimilarDirection algorithm is the sum of the time complexity of the three phases.

In the first phase, we determine the actual passenger number of each vehicle with the number of remained passengers decreased by $⌈ w / q ⌉$ , where $q$ represents the number of vehicles remained with initial value $n$ , $w$ represents the minimum number of passengers remained with initial value $| D |$ and the total capacity of all vehicles. Apparently, the time complexity of the first phase is $O (m)$ .

In the second phase, for a particular vehicle, the time complexity of the step “Find a vertex $f$ that is farthest to $o$ in $Y$ ” in the worst case is $O (m)$ , because this step represents a search process. Similarly, the time complexity of the steps on line 8, line 10, and line 17 of Algorithm 2 are also $O (m)$ . Hence, for any vehicle, the time complexity required to complete the passenger assignment process is $O (m)$ . There are $n$ vehicles, so the time complexity of the second phase is $O (mn)$ .

Algorithm 2. Passenger Assignment
Input: traffic network $G = (B, E)$ , delivery request $R$ , Vehicles array $V$ Output: $V$ that passengers of each vehicle is assigned 1: $V$ = Actual Passenger Number Determination $(G, R, V)$ 2: $α = 1$ 3: $Y = D$ 4: while $α \leq n$ and $Y$ is not empty do 5: Find a vertex $f$ that is farthest to $o$ in $Y$ 6: $Y = Y - {f}$ 7: Add passenger whose destination is $f$ to $v_{α} . Ω$ 8: $Q$ = {vertex $b$ \| the angle between $ob$ and $of$ is not greater than 45 degrees, and $b$ is in $Y$ } 9: if $\| Q \| \leq v_{α} . p - 1$ then 10: $W$ = { $v_{α} . p - 1$ points in $Q$ in accordance with distance to the line $of$ from small to large} 11: Add passengers with destinations in $W$ into $v_{α} . Ω$ 12: $Y = Y - {W}$ 13: else 14: $β = v_{α} . p - \| Q \|$ 15: Add passengers with destinations in $Q$ into $v_{α} . Ω$ 16: $Y = Y - {Q}$ 17: $W$ = { $β$ points in $Y$ in accordance with distance to the line $of$ from small to large} 18: Add passengers with destinations in $W$ into $v_{α} . Ω$ . 19: $Y = Y - {W}$ 20: $α = α + 1$

Algorithm 2. Passenger Assignment

Input:
traffic network

G = (B, E)

,
delivery request

R

,
Vehicles array

V

Output:

V

that passengers of each vehicle is assigned
1:

V

= Actual Passenger Number Determination

(G, R, V)

α = 1

Y = D

4: while

α \leq n

and

Y

is not empty do
5: Find a vertex

f

that is farthest to

o

Y

Y = Y - {f}

7: Add passenger whose destination is

f

v_{α} . Ω

Q

= {vertex

b

| the angle between

ob

and

of

is not greater than 45 degrees, and

b

is in

Y

}
9: if

| Q | \leq v_{α} . p - 1

then
10:

W

= {

v_{α} . p - 1

points in

Q

in accordance with distance to the line

of

from small to large}
11: Add passengers with destinations in

W

into

v_{α} . Ω

12:

Y = Y - {W}

13: else
14:

β = v_{α} . p - | Q |

15: Add passengers with destinations in

Q

into

v_{α} . Ω

16:

Y = Y - {Q}

17:

W

= {

β

points in

Y

in accordance with distance to the line

of

from small to large}
18: Add passengers with destinations in

W

into

v_{α} . Ω

.
19:

Y = Y - {W}

20:

α = α + 1

The third phase aims to determine the delivery order of passengers in the same vehicle by using Algorithm 3. Algorithm 3 includes two processes for each vehicle: calculate the minimum spanning tree, eliminate branches of the minimum spanning tree to get the delivery order by depth-first search. For each vehicle, in the first process, we use either Prim’s algorithm or Kruskal’s algorithm to calculate the minimum spanning tree of a complete graph with at most $c + 1$ vertexes, which includes the destination of the passengers in this vehicle and the origin $o$ in the first process. It is known that the time complexity of either Prim’s algorithm or Kruskal’s algorithm is $O (| E | \lg | V |)$ , where $| E |$ is the number of edges and $| V |$ is the number of vertexes.³³ So the time complexity of the first process is $O (((c (c + 1)) / 2) \lg (c + 1)) = O (c^{2} \lg c)$ . The second process is exactly a depth-first search process. The time complexity of the depth-first search is $O (| E | + | V |)$ , where $| E |$ is the number of edges and $| V |$ is the number of vertexes.³³ In the minimum spanning tree, the number of edges is at most $c + 1$ and the number of vertexes is at most $c$ , so the time complexity of the second process is $O (c)$ . Therefore, for any vehicle, the time complexity of the two process is $O (c^{2} \lg c + c) = O (c^{2} \lg c)$ . There are $n$ vehicles, so the time complexity of the third phase is $O (n c^{2} \lg c)$ .

Algorithm 3. VariantMST
Input: traffic network $G = (B, E)$ , delivery request $R$ , Vehicles array $V$ Output: driving plan $G' = (B', E')$ 1: $V$ = Passenger Assignment $(G, R, V)$ 2: Define a graph $G'$ with vertex set $B' = {o} + D$ and empty edge set $E'$ 3: $α = 1$ 4: while $α \leq n$ do 5: $Q = v_{α} . Ω$ 6: $W$ = {the destinations of passengers in $Q$ } 7: $F = {o} + W$ 8: Define a completed directed graph $G_{}$ with vertex set $F$ 9: Calculate the minimum spanning tree $T'$ of $G_{}$ 10: Eliminate branches of $T'$ and get a depth-first delivery order tree $T_{}$ 11: Add all edges in $T_{}$ into $E'$ 12: $α = α + 1$

Algorithm 3. VariantMST

Input:
traffic network

G = (B, E)

,
delivery request

R

,
Vehicles array

V

Output:
driving plan

G' = (B', E')

V

= Passenger Assignment

(G, R, V)

2: Define a graph

G'

with vertex set

B' = {o} + D

and empty edge set

E'

α = 1

4: while

α \leq n

do
5:

Q = v_{α} . Ω

W

= {the destinations of passengers in

Q

}
7:

F = {o} + W

8: Define a completed directed graph

G_{*}

with vertex set

F

9: Calculate the minimum spanning tree

T'

G_{*}

10: Eliminate branches of

T'

and get a depth-first delivery order tree

T_{*}

11: Add all edges in

T_{*}

into

E'

12:

α = α + 1

Algorithm 4. SimilarDirection
Input: traffic network $G = (B, E)$ , delivery request $R$ , Vehicles array $V$ Output: driving plan $G' = (B', E')$ 1: Define a graph $G'$ 2: $G' = VariantMST (G, R, V)$

In conclusion, the time complexity of the SimilarDirection algorithm is $O (m) + O (mn) + O (n c^{2} \lg c) = O (mn + n c^{2} \lg c)$ .

Another situation: insufficient vehicle capacity

So far, what we have considered is a special situation that the total capacity of all vehicles is not less than the number of passengers. It is worth noting that there is another common situation in real life, that is, the vehicle capacity is insufficient, and it is impossible to deliver all passengers by using existing vehicles. Therefore, we can only select part of the passengers to deliver. In this article, there are three candidate algorithms to solve this problem.

DelFar: In this algorithm, first, we will select passengers in accordance with the distance from the starting point to their destination from small to large, so $k$ passengers farthest from the starting point will not be delivered, where $k$ is the number of passengers minus the total capacity of all vehicles. Then we will use the SimilarDirection algorithm to determine how to deliver the selected passengers. It should be noted that DelFar will make farthest passengers feel dissatisfied, because they are rejected to be delivered only for the reason that they are farthest from the starting point.

Unchanged: In this algorithm, we use the SimilarDirection algorithm directly. In this way, when all vehicles are fully loaded, the Passenger Assignment algorithm is terminated.

DelRan: In this algorithm, we will randomly select $k$ passengers that will not be delivered, where $k$ is the number of passengers minus the total capacity of all vehicles. Next, we will also use the SimilarDirection algorithm to determine the delivery order of the selected passengers as what DelFar does.

Evaluation

To compare the performance of different algorithms, we give two definitions as follows:

Definition 7 (average arriving distance performance ratio)

The average arriving distance performance result of an algorithm is that, for a given case, the average of average arriving distance in each experiment. The average arriving distance performance ratio (AADPR) of an algorithm in a given case is the average arriving distance performance result of SimilarDirection algorithm divided by the average arriving distance performance result of this algorithm when using the same data and running the same time experiments. AADPR is greater than 1 means that this algorithm produces less average arriving distance of all passengers than our algorithm, and the larger the value of AADPR, the better the performance of this algorithm in producing less average arriving distance.

Definition 8 (total driving distance performance ratio)

Similarly, the total driving distance performance result of an algorithm is the average of total driving distance for a given case in each experiment. The total driving distance performance ratio (TDDPR) of an algorithm in a given case is the total driving distance performance result of SimilarDirection algorithm divided by the total driving distance performance result of this algorithm when using the same data and running the same time experiments.

We have done several experiments to test the performance of our algorithm in producing the two kinds of distances. Next, we will introduce other algorithms we used to compare with our algorithm, and we will also introduce the synthetic dataset and the real-world dataset with their experiment settings and the experimental results.

We have also done several experiments to test the performance of the three algorithms for solving the problem when the vehicle capacity is insufficient, and we will show the experiment settings and results.

Algorithms used for comparing with our algorithm

We design two algorithms called Random and NearestFirst. We also implement the passenger assignment phase and delivery order calculation phase of coRide in Zhang et al.,¹¹ then we combine the two algorithms as a new algorithm for solving the carpooling route calculation problem. For ease of understanding, we also call this new algorithm coRide. We use the three algorithms to compare with our algorithm. Random and NearestFirst have three phases named actual passenger number determination, passenger assignment, and delivery order determination. In Random and NearestFirst, the algorithms used in the first phase and the third phase are the same as those used in the first and third phases of our algorithm. The brief descriptions of the three algorithms are as follows.

Random: In the second phase, the passengers assigned to each vehicle are randomly selected.

NearestFirst: In the second phase, the rule to assign passengers is as follows: find the passenger $p_{1}$ whose destination is nearest to the origin and add $p_{1}$ to the vehicle $v_{1}$ . Then we find the passenger $p_{2}$ in remaining passengers whose destination is nearest to the origin and add $p_{2}$ to $v_{1}$ , and so on.

coRide: Different from our algorithm, coRide only has two phases: passenger assignment and delivery order calculation. In passenger assignment phase, according to the delivery request $R = (o, D, c, n)$ , coRide will formulate a minimum spanning tree (MST) with vertex set ${o} + D$ and the root vertex is $o$ , the number of subtrees whose root are $o$ is the number of vehicles needed, the size of each subtree is the number of passengers each vehicle have to deliver. Due to the constraints on the number of vehicles and the capacity of each vehicle, the minimum spanning tree should be revised to meet the constraints. In delivery order calculation phase, coRide uses the same algorithm as what we use in the third phase of SimilarDirection.

Synthetic dataset

In the synthetic dataset experiments, the latitude and longitude of each vertex are randomly generated in given ranges, longitudes range from 125.1 to 125.5 and latitudes range from 43.8 to 44 to ensure that the randomly generated vertexes are located in Changchun city. For simplicity, in each time experiment, the vertexes in the delivery request, including the origin vertex and the destination vertexes, are the same as the vertexes in the traffic network.

Real-world dataset

To do the real-world dataset experiments, we get the latitude and longitude of 400 hotels in Changchun as vertexes and calculate the road length between all points as our traffic network by using BaiduMap Web API. We will concretely introduce how we use BaiduMap Web API to get these data.

Step 1. Get the location of 400 hotels

In the real-world dataset experiments, we should make sure that each vertex in the dataset corresponds to a real POI (Point of Interest) in Changchun. So we use place API, which is used to find a specific kind of POI in a given region, to find 400 hotels in Changchun. We randomly select the detailed information of two hotels in Changchun, the information will be used later. The detailed information of one of the two hotels is as follows:

Detailed information of hotel 1
Name: Jilin Province Hotel
Location: lat: 43.892479, lng: 125.333967
Address: 2598 Renmin Street, Nanguan District (next to people’s Square)
Province: Jilin Province
City: Changchun city
Area: Nanguan District
Street_id: 93df0dc36e5a5b32882fb541
Telephone: (0431)88488846, (0431)88488855, (0431)88488999
Detail: 1
Uid: 93df0dc36e5a5b32882fb541

The location information of each hotel will be used at the next step: get the road length between each pair of hotels.

Step 2. Get the road length between each pair of hotels

To get the road length between each pair of hotels, we use Direction API that can search for qualified driving route plan based on starting point and end point coordinates. The message returned contains an attribute named “distance,” which represents the driving distance in this plan. We regard the attribute “distance” as the road length between two hotels. To use this API, we need to input the latitude and longitude of starting point $A$ and end point $B$ .

It is worth noting that if we set $B$ as starting point and set $A$ as end point, the attribute “distance” we get from the returned message will be different from the “distance” when starting point is $A$ and end point is $B$ in most cases. For example, we name the two hotels we mentioned above, hotel 1 and hotel 2. If we regard hotel 1 as starting point and hotel 2 as end point, then the “distance” is 7445. Conversely, if we exchange the roles of the two hotels, the “distance” will change to 6875. To explain this situation, we show the graphical representation of the driving route in the Baidu map. In Figure 6, the two routes look very similar but are actually different, because it is retrograde if you start from hotel 2 and go back along the route from hotel 1 to hotel 2. As we said before, in real world, the road length from $i$ to $j$ , denoted as $r_{ij}$ , typically is not the linear distance between $i$ and $j$ , and $r_{ij}$ is usually not $r_{ji}$ .

Figure 6.

At first, hotel 1 is the starting point and hotel 2 is the end point. After exchanging the roles of the starting point and the end point, the driving route is different from the previous driving route.

In every experiment where the number of vehicles, the number of passengers, and the capacity of each vehicle are given, we randomly select some vertexes to establish a delivery request with such attributes.

Experiment settings

Settings for testing our SimilarDirection algorithm: In both the real-world dataset experiments and the synthetic dataset experiments, we use four situations to test the performances of our algorithm. In the first three situations, the number of passengers is equal to the product of the number of vehicles and the capacity of each vehicles. The first situation is that the number of passengers is fixed as 180; the number of vehicles and the capacity of each vehicle is variable in different cases. The second situation is that the capacity of each vehicle is fixed as 4; the number of passengers and the number of vehicles are variable in different cases. And in the third situation, the number of vehicles is fixed as 20 in the real-world dataset experiments and is fixed as 45 in the synthetic dataset experiments; the capacity of each vehicle and the number of passengers are variable in different cases. In the fourth situation, the number of passengers is not equal to the product of the number of vehicles and the capacity of each vehicles. The number of vehicles in the fourth situation is 90; the capacity of each vehicle in the fourth situation is 4; and the number of passengers increases from 100 to 360 with 20 passengers’ increasing each time in the fourth situation.

It is unnecessary to use the situation that the total capacity of all vehicles is less than the number of passengers, because for any “insufficient capacity” situation, there is a corresponding equivalent situation apparently where the number of passengers is equal to the product of the number of vehicles and the capacity of each vehicles.

A situation includes several cases, for example, in the first situation we mentioned above, there are cases such as 60 vehicles, each with a capacity of 3, and 45 vehicles, each with a capacity of 4, and so on. In each case, we use different data and run 100,000 times experiment, then we calculate the average of the average arriving distance and the average of the total driving distance of each time.

Settings for testing the performance of the three algorithms: In both the real-world dataset experiments and the synthetic dataset experiments, we use four cases to test the performances of the three algorithms which are used for solving the carpooling problem when the vehicle capacity is insufficient: DelFar, Unchanged, and DelRan. In all the four cases, the number of vehicles is fixed as 45; the capacity of each vehicle is fixed as 4; and the number of passengers in the four cases is 200, 220, 240, and 260, respectively. In other words, compared with the capacity of 180, there are a range of 20 to 80 extra passengers in the four cases. In each case, we also use different data and run 100,000 times experiment, then we calculate the average of the average arriving distance and the average of the total driving distance of each time.

Results

Results about the performance of our SimilarDirection algorithm: We show the experimental results of the real-world dataset experiments about the performance of our SimilarDirection algorithm in Figure 7(a)–(d) and Figure 9(a)–(d), and the synthetic dataset experiments about the performance of our SimilarDirection algorithm in Figure 8(a)–(d) and Figure 10(a)–(d) as follows. The “SD,”“R,”“NF,” and “CR” in Figures 7 –10 represent the abbreviation of “SimilarDirection,”“Random,”“NearestFirst,” and “coRide,” respectively. The error bars in Figures 7 –10 represent the value of standard deviation

Figure 7.

AADPR comparisons in the real-world dataset experiments with four situations: (a) The number of passengers is fixed as 180, (b) the capacity of each vehicle is fixed as 4, (c) the number of vehicles is fixed as 20, and (d) the number of vehicles is 90, the capacity of each vehicle is 4.

Figure 8.

AADPR comparisons in the synthetic dataset experiments with four situations: (a) The number of passengers is fixed as 180, (b) the capacity of each vehicle is fixed as 4, (c) the number of vehicles is fixed as 45, and (d) the number of vehicles is 90, the capacity of each vehicle is 4.

Figure 9.

TDDPR comparisons in the real-world dataset experiments with four situations: (a) The number of passengers is fixed as 180, (b) the capacity of each vehicle is fixed as 4, (c) the number of vehicles is fixed as 20, and (d) the number of vehicles is 90, the capacity of each vehicle is 4.

Figure 10.

TDDPR comparisons in the synthetic dataset experiments with four situations: (a) The number of passengers is fixed as 180, (b) the capacity of each vehicle is fixed as 4, (c) the number of vehicles is fixed as 45, and (d) the number of vehicles is 90, the capacity of each vehicle is 4.

As we can see, our algorithm can produce the least average arriving distance of all passengers among the four algorithms in all the eight situations we mentioned before in both the real-world dataset experiments and the synthetic dataset experiments. coRide has the second best AADPR in Figure 7(a)–(c) and Figure 8(a)–(c). In Figure 7(a) and (b), and Figure 8(a) and (b), the AADPR of Random and NearestFirst decreases at first, then increases in Figure 7(a) and (b), and Figure 8(a) and decreases in Figure 8(b). The AADPR of algorithms except ours are almost monotone decreasing in Figures 7(c) and 8(c).

In Figures 7(d) and 8(d), the AADPR of coRide is almost monotone increasing. In Figures 9(d) and 10(d), the TDDPR of coRide is almost monotone decreasing. The reason for the two phenomena is the algorithms except coRide aim to utilize all available vehicles as possible. When the number of passengers is small compared with the total capacity of all vehicles, the number of vehicles used by coRide will be smaller than the number of vehicles used by the other three algorithms.

Results about the performance of DelFar, Unchanged, and DelRan: We show the experimental results about the performance of the three algorithms used for solving the carpooling problem when the vehicle capacity is insufficient (Tables 1 –4). Tables 1 and 2 show the performance of the three algorithms in producing average arriving distance, Tables 3 and 4 show the performance of the three algorithms in producing total driving distance. The “aad” in Tables 1 and 2 represents the average of the average arriving distance of each time. The “tdd” in Tables 3 and 4 represents the average of the total driving distance of each time. The “ep” in Tables 1 –4 represents the number of extra passengers when total capacity of all vehicles is 180. The “alg” in Tables 1 –4 represents the abbreviation of “algorithm.” In Tables 1 –4, we can see that of all the three algorithms, in both the real-world dataset experiments and the synthetic dataset experiments, DelFar has the best performance in producing less average arriving distance and less total driving distance of all passengers and DelRan has the second best performance, while algorithm Unchanged produces the most average arriving distance and total driving distance of all passengers.

Table 1.

Average arriving distance (aad, m) performance comparisons of DelFar, Unchanged, and DelRan in the real-world dataset experiments.

aad(m) ep
alg	20	40	60	80
$DelFar$	13,664	14,566	12,588	10,393
$Unchanged$	19,446	21,669	19,108	17,294
$DelRan$	19,287	20,814	18,024	15,879

Table 2.

Average arriving distance (aad, m) performance comparisons of DelFar, Unchanged, and DelRan in the synthetic dataset experiments.

aad(m) ep
alg	20	40	60	80
$DelFar$	12,192	10,386	8921	7794
$Unchanged$	13,778	12,885	11,961	11,272
$DelRan$	13,487	12,292	11,192	10,345

Table 3.

Total driving distance (tdd, km) performance comparisons of DelFar, Unchanged, and DelRan in the real-world dataset experiments.

tdd(km) ep
alg	20	40	60	80
$DelFar$	822	875	784	757
$Unchanged$	1741	1662	1819	1893
$DelRan$	1457	1460	1451	1439

Table 4.

Total driving distance (tdd, km) performance comparisons of DelFar, Unchanged, and DelRan in the synthetic dataset experiments.

tdd(km) ep
alg	20	40	60	80
$DelFar$	864	807	760	721
$Unchanged$	970	992	1012	1029
$DelRan$	927	910	889	862

Conclusion

There are many researches nowadays focusing on carpooling to optimize the use of cars. However, most researches mainly concentrate on minimizing the total driving distance of cars in carpooling. It probably takes some passengers a bad user experience. Compared with the total driving distance of cars, the average arriving distance of all passengers is what passengers are more concerned about. In this article, we formulate a problem aiming at minimizing the average arriving distance of all passengers in carpooling where drivers do not have their own routes. Then we prove its NP-hardness. Finally, for the situation that the vehicle capacity is sufficient to deliver all passengers, we propose a heuristic algorithm called SimilarDirection including three phases: actual passenger number determination, passenger assignment, and delivery order determination in order to solve this problem. In delivery order calculation phase, we prove that the arriving distance of all passengers obtained by the VariantMST algorithm is at most $2 c$ times the optimal arriving distance, where $c$ is the capacity of each vehicle. For the situation that the vehicle capacity is insufficient, we propose three algorithms called DelFar, Unchanged, and DelRan for solving it. To evaluate the performance of our SimilarDirection algorithm, we use a real-world dataset got from BaiduMap API and some emulation datasets to do the real-world dataset experiments and the synthetic dataset experiments. Experimental results show that our heuristic algorithm can produce the least average arriving distance of all passengers in both the real-world dataset experiments and the synthetic dataset experiments in contrast with other three algorithms called Random, NearestFirst, and coRide. We also do both the real-world dataset experiments and the synthetic dataset experiments to test the performances of the three algorithms used for solving the carpooling problem when the vehicle capacity is insufficient, and it can be seen in experimental results that DelFar has the best performance in producing less average arriving distance of all passengers.

Footnotes

Handling Editor: Paolo Bellavista

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by the National Natural Science Foundations of China under Grant No. 61772230 and No. 61972450, Natural Science Foundation of China for Young Scholars No. 61702215, China Postdoctoral Science Foundation No. 2017M611322 and No. 2018T110247, and Changchun Science and Technology Development Project No.18DY005.

ORCID iD

En Wang

References

National Statistics. Vehicle licensing statistics: quarter 1. Department for Transport, 2018, https://assets.publishing.service.gov.uk/government/uploads/system/uploads/attachment_data/file/812253/vehicle-licensing-statistics-january-to-march-2019.pdf

Morris

Tran

Scora

, et al. Real-time video-based traffic measurement and visualization system for energy/emissions. IEEE Trans Intell Transp Syst 2012; 13(4): 1667–1678.

Terroso-Saenz

Valdes-Vela

Sotomayor-Martinez

, et al. A cooperative approach to traffic congestion detection with complex event processing and vanet. IEEE Trans Intell Transp Syst 2012; 13(2): 914–929.

Milanes

Godoy

Villagra

, et al. Automated on-ramp merging system for congested traffic situations. IEEE Trans Intell Transp Syst 2011; 12(2): 500–508.

McKenzie

Rapino

. Commuting in the United States: 2009. Washington, DC: US Department of Commerce, Economics and Statistics Administration, US Census Bureau, 2011.

Hartwig

Buchmann

. Empty seats traveling: next-generation ridesharing and its potential to mitigate traffic and emission problems in the 21st century, 2006, http://cts.cs.uic.edu/NRC-TR-2007-003.pdf

Fagin

Williams

. A fair carpool scheduling algorithm. IBM J Res Develop 1983; 27(2): 133–139.

Megalingam

Nair

Radhakrishnan

. Automated wireless carpooling system for an eco-friendly travel. In: Proceedings of the 3rd international conference on electronics computer technology (ICECT), Kanyakumari, India, 8–10 April 2011, vol. 4, pp.325–329. New York: IEEE.

Lei

ZCPL

. Research of car-sharing’s reason and its character research. Spec Zone Econ 2010; 9: 115.

10.

Cici

Markopoulou

Laoutaris

. Sors: a scalable online ridesharing system. In: Proceedings of the 9th ACM SIGSPATIAL international workshop on computational transportation science, Burlingame, CA, 31 October–3 November 2016, pp.13–18. New York: ACM Press.

11.

Zhang

, et al. Carpooling service for large-scale taxicab networks. ACM Trans Sensor Netw 2016; 12(3): 18.

12.

Matos

Cruz

Guimarães

, et al. A social network for carpooling. In: Proceedings of the 7th Euro American conference on telematics and information systems, Valparaiso, Chile, 2–4 April, p.10. New York: ACM Press.

13.

National Bureau of Statistics of China. China statistical yearbook 2016 (Chinese-English Edition). Beijing China: China Statistics Press, 2016.

14.

National Bureau of Statistics of China. China statistical yearbook 2017 (Chinese-English Edition). Beijing China: China Statistics Press, 2017.

15.

Naor

. On fairness in the carpool problem. J Algorithm 2005; 55(1): 93–98.

16.

Kai

. Intelligent carpool routing for urban ridesharing by mining GPS trajectories. IEEE Trans Intell Transp Syst 2014; 15(5): 2286–2296.

17.

Elbery

ElNainay

Chen

, et al. A carpooling recommendation system based on social vanet and geo-social data. In: Proceedings of the 21st ACM SIGSPATIAL international conference on advances in geographic information systems, Orlando, FL, 5–8 November 2013, pp.556–559. New York: ACM Press.

18.

Meurer

Stein

Randall

, et al. Social dependency and mobile autonomy: supporting older adults’ mobility with ridesharing ICT. In: Proceedings of the 32nd annual ACM conference on human factors in computing systems, Toronto, ON, Canada, 26 April–1 May 2014, pp.1923–1932. New York: ACM Press.

19.

Huang

Jiau

Chong

. A heuristic multi-objective optimization algorithm for solving the carpool services problem featuring high-occupancy-vehicle itineraries. IEEE Trans Intell Transp Syst 2018; 19(8): 2663–2674.

20.

Dantzig

Ramser

. The truck dispatching problem. Manage Sci 1959; 6(1): 80–91.

21.

Savran

Musaoglu

Yuce

, et al. Routeart: a new framework for vehicle routing problem with pickup and delivery using heuristic bubble algorithm. In: Proceedings of the 15th international symposium on computational intelligence and informatics (CINTI), Budapest, 19–21 November 2014, pp.91–96. New York: IEEE.

22.

Zhu

. A new genetic algorithm for VRPTW. In: Proceedings of the international conference on artificial intelligence. Citeseer, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.1316&rep=rep1&type=pdf

23.

Lysgaard

Letchford

Eglese

. A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math Program 2004; 100(2): 423–445.

24.

Golden

Wasil

. The open vehicle routing problem: algorithms, large-scale test problems, and computational results. Comput Operat Res 2007; 34(10): 2918–2930.

25.

Tyasnurita

Özcan

John

. Learning heuristic selection using a time delay neural network for open vehicle routing. In: IEEE congress on evolutionary computation (CEC), Donostia-San Sebastian, 5–8 June 2017, pp.1474–1481. New York: IEEE.

26.

Chen

Dong

Xiao

. Study on split delivery open vehicle routing problem within two splits. In: Proceedings of the 12th international conference on natural computation, fuzzy systems and knowledge discovery (ICNC-FSKD), Changsha, China, 13–15 August 2016, pp.724–728. New York: IEEE.

27.

Jinhui

Ying

Hongzhen

. An improved TS for the open vehicle routing problem with soft time windows. In: Proceedings of the 5th international symposium on computational intelligence and design (ISCID), Hangzhou, China, 14–15 December 2012, vol. 1, pp.382–385. New York: IEEE.

28.

Wang

Yang

, et al. An efficient prediction-based user recruitment for mobile crowdsensing. IEEE Trans Mobile Comput 2017; 17(1): 16–28.

29.

Yang

Liu

Wang

, et al. A prediction-based user selection framework for heterogeneous mobile crowdsensing. IEEE Trans Mobile Comput 2019; 2460–2473.

30.

Wang

Zhang

, et al. Heterogeneous multi-task assignment in mobile crowdsensing using spatiotemporal correlation. IEEE Trans Mobile Comput 2018; 18(1): 84–97.

31.

Jiang

, et al. Trust evaluation in online social networks using generalized network flow. IEEE Trans Comput 2015; 65(3): 952–963.

32.

Wang

Pang

Chen

, et al. Privacy-preserving crowd-sourced statistical data publishing with an untrusted server. IEEE Trans Mobile Comput 2018; 18(6): 1356–1367.

33.

Cormen

Leiserson

Rivest

, et al. Introduction to algorithms. Cambridge, MA: MIT Press, 2009.

Minimizing the average arriving distance in carpooling

Abstract

Keywords

Introduction

Related work

Existing problems of urban traffic

Researches about carpooling

VRP

Network model

Definition 1 (road length)

Definition 2 (actual driving distance)

Definition 3 (delivery request)

Definition 4 (actual passenger number)

Definition 5 (driving plan)

Definition 6 (arriving distance)

Problem formulation

Theorem 1

Proof

SimilarDirection: a heuristic algorithm

Actual passenger number determination

Passenger assignment

Delivery order calculation

Theorem 2

Proof

Theorem 3

Proof

Another situation: insufficient vehicle capacity

Evaluation

Definition 7 (average arriving distance performance ratio)

Definition 8 (total driving distance performance ratio)

Algorithms used for comparing with our algorithm

Synthetic dataset

Real-world dataset

Step 1. Get the location of 400 hotels

Step 2. Get the road length between each pair of hotels

Experiment settings

Results

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References