出租车是城市交通的重要组成部分，为出行者提供便捷、舒适、通达的交通服务. 然而，在许多城市仍然有大量出租车巡航在城市道路上，以街头叫车的方式寻找乘客^[1]. 一方面，出租车空载率高，导致出租车司机运营成本增加的同时收入降低，且一些地方的乘客须等待较长时间才能乘坐出租车，降低了其出行满意度. 例如，上海市出租车的日均时间利用率为59%^[2]，四川成都出租车的小时时间利用率约为50%^[3]. 这意味着出租车须花费大量时间寻找乘客. 另一方面，大量空闲出租车在城市道路上巡航占用了大量的道路空间，加剧了交通拥堵和空气污染^[4]. 因此，为出租车推荐路线对提高出租车运营效率、减少交通污染，为乘客提供更高效、便捷的出行服务具有重要意义.

随着智能手机、GPS导航仪的普及，很多出租车都安装了GPS全球定位系统，使得对人们行为特征的探索成为可能^[5-10]. 移动顺序推荐是基于出租车GPS轨迹数据的重要研究领域之一. 虽然滴滴、优步网约车平台的出现使乘客可以通过更多的方式乘坐出租车，如手机App预约，但在没有订单请求的情况下，出租车司机仍然须根据自己的经验寻找乘客需求较高的区域，以便尽快接到订单. 因此，提出有效且高效的出租车移动顺序推荐方法受到了大量学者的关注.

Ge等^[11]提出出租车移动顺序推荐（mobile sequential recommendation, MSR）的问题. 该问题通过考虑接载乘客的概率和搜索距离提出潜在行驶距离（potential travel distance, PTD）模型，旨在为空闲出租车提供一系列上客点，减少出租车从当前位置到下一个乘客之间的距离，增加出租车成功接载乘客的可能性. 为了使MSR更好地应用于实际，Ge等^[12]进一步改进了MSR提出了宽松假设的路线推荐（route recommendation with relaxed assumptions, RR-RA）和面向目的地的路线推荐（destination-oriented route recommendation, DORR）问题，为出租车司机提供了更为全面的路线推荐建议. 其他学者也对MSR存在的问题开展了研究，使出租车在存在多辆出租车的情况下也能够以较短的距离接载乘客. 如Luo等^[13]通过改进PTD模型提出了潜在巡航距离（potential cruising distance, PCD）模型，进一步考虑了出租车根据推荐路线行驶后上客点的容量变化，解决了PTD模型可能为出租车推荐具有较低接客概率的路线及在同一位置存在多辆出租车时的路线推荐的问题. Xiao等^[14]针对MSR只能为单个出租车带来有效的解决方案，进一步提出了多用户移动顺序推荐（multi-user mobile sequential recommendation, MMSR）模型，解决了多用户场景下更为复杂的出租车路线推荐问题. 此外，MSR本质上是一个具有高计算复杂度的问题. 为了降低MSR的计算成本，Huang等^[15]提出基于动态规划的方法来解决MSR问题，该方法包括离线预处理和在线搜索2个独立阶段. Ye等^[16]提出将并行计算和模拟退火算法与全局和局部搜索相结合的新方法，能够实现为空闲出租车实时搜索最佳路线，而无需离线预处理. 然而，上述研究没有考虑到在交通拥堵的情况下，根据推荐路线出租车可能需要长时间行驶才能接载乘客. 因此，Liang等^[17]进一步考虑时间因素，提出基于时空矩阵的路线推荐（route recommendation based on temporal-spatial metric, RTS）模型.

综上所述，现有关于出租车移动顺序推荐的研究考虑了接客概率、搜索时间和搜索距离3个因素. 然而，对于出租车司机来说，最关心的问题是如何实现收益最大化，只考虑接客概率、搜索时间和搜索距离为出租车司机推荐一系列上客点，从长远来看无法确保司机更高的收入. 此外，现有研究忽略了上客点中需求大小对空闲出租车成功接载乘客的可能性的影响，会高估一些上客点成功接载乘客的可能性. 针对上述问题，本研究考虑出租车接载下一个乘客的收益及上客点的需求对出租车路线推荐问题进行建模，采用模拟退火算法和贪心算法对出租车路线推荐问题进行求解，最后通过上海市GPS轨迹数据对上述模型进行验证，实验结果验证了本研究所提出的出租车收益路线推荐模型的有效性和优越性.

假设空闲出租车当前位置为$ {C_0} $，出租车周围存在一组潜在的上客点$ C = \{ {C_1},{C_2}, \cdots ,{C_N}\} $，其中，$ N $为潜在的上客点数量. 空闲出租车在上客点$ {C_i} $发生上车事件的可能性为$ {P_i} $，$ {P_i} $假设服从独立分布，则$ P = \{ {P_1},{P_2}, \cdots ,{P_N}\} $为上客点对应的概率集合. 令$ {\boldsymbol{r}} = [{C_1},{C_2}, \cdots ,{C_L}] $为候选路线，其中$ L $为候选路线$ {\boldsymbol{r}} $的上客点的数量，$ 1 \leqslant L \leqslant N $. 假设每条候选路线中的上客点彼此不同. ${\boldsymbol{d}} = [{C_0},{\boldsymbol{r}}]$为行驶路线. $ R = $ $\{ {{\boldsymbol{r}}_1},{{\boldsymbol{r}}_2}, \cdots ,{{\boldsymbol{r}}_M}\}$为一组候选路线集合，其中$ M $为可能的所有候选路线的数量.

设$f({\boldsymbol{d}})$为接载下一位乘客前的潜在出行成本. 基于上述定义和概念，定义基于移动顺序推荐的出租车收益路线推荐（profitable taxi route recommendation based on mobile sequential recommendation, PMSR）问题如下. 给定空闲出租车当前位置$ {C_0} $，一组潜在的上客点$ C $，概率集合$ P $和一组候选路线集合$ R $. 路线推荐的目标是为空闲出租车推荐最佳行驶路线，使出租车能够以最小的潜在出行成本接载新乘客，即

(1)$ \left.\begin{gathered}\min _{{\boldsymbol{r}} \in R} \;f(\boldsymbol{d}); \\\text { s.t. } C_a \neq C_b ,\;a,b \in\{1,2, \cdots, L\},a \ne b \text {. }\end{gathered}\right\} $

出租车移动顺序推荐问题区别于传统的旅行商问题和车辆调度问题. 旅行商问题是$ N $个给定位置的不同组合，车辆调度问题是车辆根据预先给定的程序将货物运送到确定的地点，而出租车移动推荐问题是出租车在$ N $个位置的子集位置之间的不确定接载乘客问题. 如图1所示，在出租车周围存在4个上客点，假设出租车到$ {C_1} $的潜在出行成本最小. 即使出租车在$ {C_1} $成功接载乘客的可能性较大，也不能简单地将$ {C_1} $作为第1个上客点，因为出租车在$ {C_1} $可能找不到乘客，这将会增加出租车到达下一个上客点的潜在出行成本. 相反，如果出租车选择$ {C_2} $作为第1个上客点，出租车将能充分利用一系列成功接载乘客的机会，从而减少出租车的潜在出行成本.

假设空闲出租车的行驶路线为${\boldsymbol{d}} = [{C_0},{C_1}, \cdots ,$$ {C_L}] $，行驶路线d的接客概率向量为${\boldsymbol{P}}({\boldsymbol{d}})= \left[{P}_{1},\right. \left.{\overline{P}}_{1} {P}_{2},\;\cdots ,\;{\displaystyle \prod _{i=1}^{L-1}{\overline{P}}_{i} {P}_{L}},{\displaystyle \prod _{i=1}^{L}{\overline{P}}_{i}}\right], \;{\bar P_i} = 1 - {P_i}$；行驶路线d的搜索距离向量和搜索时间向量分别为${\boldsymbol{D}}({\boldsymbol{d}})= \Big[{d}_{1}, \left.{d}_{1}+{d}_{2},\;\cdots ,\;\displaystyle\sum\limits_{j = 1}^L {{d_j}} ,{D_{\max }}\right]和{\boldsymbol{t}}({\boldsymbol{d}}) = [{t_1},$$ {t}_{1}+{t}_{2},\;\cdots ,\;\displaystyle \sum _{j=1}^{L}{t}_{j}$，$\left.{{T}_{\mathrm{max}}}\right] $， 其中$ {d_j} $和$ {t_j} $分别为从$ {C_{i - 1}} $到$ {C_i} $之间的距离和时间，$ {D_{\max }} $和$ {T_{\max }} $分别为司机寻找新乘客的最大可接受距离和最大可接受时间；行驶路线${\boldsymbol{d}}$的预期票价向量${\boldsymbol{F}}({\boldsymbol{d}}) = [{F_1},{F_2}, \cdots ,{F_L},{F_{\min }}]$，其中$ {F_i} $为上客点$ {C_i} $的预期票价，$ {F_{\min }} $为出租车根据推荐路线行驶后没有接到乘客的最小预期票价. 本研究在已有研究基础上进一步考虑预期票价因素，旨在为出租车推荐具有搜索距离和搜索时间尽可能小、接客概率和预期票价尽可能大的路线，即潜在出行成本$f({\boldsymbol{d}})$最小的路线. 因此，行驶路线${\boldsymbol{d}}$的潜在出行成本表达式如下：

(2)$ f({\boldsymbol{d}})=\frac{{\boldsymbol{D}}({\boldsymbol{d}}) \cdot {\boldsymbol{T}}({\boldsymbol{d}})}{{\boldsymbol{P}}({\boldsymbol{d}}) \cdot {\boldsymbol{F}}({\boldsymbol{d}})} .$

例如，若$ L $=2，则潜在出行成本为$f({\boldsymbol{d}}) =$$\dfrac{{{d_1}{t_1}+({d_1}+{d_2})({t_1}+{t_2})}}{{{P_1}{F_1}+(1 - {P_1}){P_2}{F_2}}}$.

在出租车路线推荐中，常用的出租车上客点，即出租车需求热点识别方法有K-means聚类^[18]、带噪声的基于密度的空间聚类（density-based spatial clustering of applications with noise, DBSCAN）^[19-20]、基于网格的聚类^[21]等. 由于DBSCAN方法可以发现任意形状和大小的簇，并且可以有效处理噪声和异常数据，本研究选择DBSCAN方法对乘客上车的位置进行聚类. 簇的质心即为上客点的位置. 为了计算上客点的接客概率，设置簇中乘客上车位置坐标的最大值和最小值为上客点的边界. 因此，上客点$ {C_i} $的接客概率，表达式如下：

(3)$ P_i(t)=\dfrac{n_i^0(t)}{n_i^0(t)+n_i^{\mathrm{c}}(t)}. $

式中：$n_i^{0}(t)$为时间段$t$内$ {C_i} $中的上车事件数量，$n_i^{\text{c}}(t)$为时间段$t$内经过$ {C_i} $的空闲出租车数量.

空闲出租车在上客点$ {C_i} $成功接载乘客的可能性不仅与上客点$ {C_i} $的接客概率有关，还应与上客点$ {C_i} $的需求大小有关. 若2个上客点的接客概率均为0.7，其中一个上客点的需求为140，另一个为20. 只考虑接客概率，出租车在这2个上客点成功接载乘客的可能性相同. 但是显然，出租车在需求为140的上客点具有更多的乘客需求，选择更多，更有可能接载乘客. 上客点的需求越接近其最大值${n_{\max }}$，出租车在该上客点的选择数量越接近在具有最大需求的上客点的选择数量. 因此，本研究采用指数形式改进接客概率的计算方法，改进后的接客概率计算表达式如下：

(4)$ P_i^{\prime}(t)=P_i(t) \times \exp\; \left(\frac{n_i^0(t)-n_{\max }(t)}{n_{\max }(t)}\right). $

假设所有出租车占用行程接载乘客的数量均为1，${n_{\max }}(t) = \max \left\{ {n_1^{\text{o}}(t),} \right.$$ \left.{n}_{2}^{\text{o}}(t),\cdots ,{n}_{N}^{\text{o}}(t)\right\} $. 因此，考虑出租车需求的出租车收益路线推荐（profitable taxi route recommendation based on mobile sequential recommendation considering demand, PMSR-D）为在PMSR的基础上进一步考虑了上客点需求的大小对出租车成功接载乘客的可能性的影响.

上客点$ {C_{i - 1}} $到$ {C_i} $之间的距离$ {d_j} $和时间$ {t_j} $分别为从上客点$ {C_{i - 1}} $到$ {C_i} $之间的所有出租车的行驶时间和行驶距离的平均值. 出租车从$ {C_{i - 1}} $到$ {C_i} $之间的行驶时间为出租车从$ {C_{i - 1}} $到$ {C_i} $之间的相邻2个GPS轨迹点之间的时间的累加和. 同样，出租车从$ {C_{i - 1}} $到$ {C_i} $之间的行驶距离为出租车从$ {C_{i - 1}} $到$ {C_i} $之间的相邻2个GPS轨迹点之间的球面距离的累加和，相邻2个GPS轨迹点之间的球面距离通过Haversine公式计算^[22]. Haversine公式表达式如下：

(5)$ \begin{split} &d\left(p_h, p_{h+1}\right)= 2 R \times \arcsin\; \Bigg(\left(\sin ^2\;\left(\dfrac{\varphi_{h+1}-\varphi_h}{2}\right)+\right.\\&\qquad \left.\cos\; \left( \varphi_h \right) \cos \;\left( \varphi_{h+1} \right) \sin ^2\;\left( \dfrac{\lambda_{h+1}-\lambda_h}{2} \right) \right)^{{1}/{2}}\Bigg).\end{split} $

式中：$ {p_h} $和$ {p_{h+1}} $为出租车GPS轨迹数据的2个相邻的轨迹点；$ d({p_h},{p_{h+1}}) $为轨迹点$ {p_h} $和$ {p_{h+1}} $之间的球面距离；$ R $为地球的半径，长度为6 371 km；$ {\varphi _h} $和$ {\varphi _{h+1}} $分别为轨迹点$ {p_h} $和$ {p_{h+1}} $的纬度；$ {\lambda _h} $和$ {\lambda _{h+1}} $分别为轨迹点$ {p_h} $和$ {p_{h+1}} $的经度.

上客点$ {C_i} $的预期票价$ {F_i} $定义为在上客点$ {C_i} $上车的所有乘客的票价的平均值.

出租车路线推荐算法框架如图2所示. 出租车路线推荐由离线预处理和在线搜索2个阶段组成. 在离线预处理阶段，首先从出租车GPS轨迹数据中提取上车事件，并通过DBSCAN方法对提取的上车事件进行聚类获得一组潜在的上客点. 之后根据上客点的位置进一步处理出租车GPS轨迹数据获得接客概率、搜索时间、搜索距离和预期票价4个参数. 在在线搜索阶段，通过模拟退火算法和贪心算法对出租车收益路线推荐问题进行求解，为出租车推荐最优路线，实现出租车潜在出行成本的最小化.

当同一地点存在多辆空闲出租车请求路线推荐时，仅根据潜在出行成本的值为出租车推荐路线，同一地点的所有出租车会根据相同的路线行驶，从而导致过载问题. 为了解决该问题，本研究引入循环机制为同一地点的多辆出租车推荐路线，即根据潜在出行成本的值从小到大进行排序，取前k条路线推荐方案，当第1辆空闲出租车请求推荐路线时，为其分配第1条路线推荐方案，第2辆空闲出租车为其分配第2条路线推荐方案，以此类推，第k辆空闲出租车为其分配第k条路线推荐方案；当k小于请求的空闲出租车数量时，第k+1辆空闲出租车分配第1条路线推荐方案，第k+2辆空闲出租车分配第2条路线推荐方案，以此类推，直至所有请求的空闲出租车均分配到路线推荐方案.

假设计算一次潜在出行成本$f({\boldsymbol{d}})$的成本为1，搜索最优路线的计算复杂度等于$ C $中所有可能性序列的总数$ M $. 对于出租车周围存在的一组潜在的上客点集合$ C $，搜索最优行驶路线的计算复杂度分析可以分为从$ C $中选择非空且不存在重复上客点的集合$ B $和$ B $中上客点的所有可能性序列2个步骤，其中$ B $中上客点的数量为$ L $，则其计算复杂度$ M $可以表示为$M = \displaystyle\sum\limits_{L = 1}^N {C_N^L \times L!}$. $ M $的表达式可以进一步转换为$M = N!\left(1+1+\dfrac{1}{{2!}}+ \cdots +\dfrac{1}{{(N - 1)!}}\right)$. 因此，根据$ M $转化的表达式可以获得$\dfrac{5}{2}N! < M < 3N!$. 基于上述分析，搜索最优行驶路线的计算复杂度为$ {\rm O}(N!) $.

为了简化出租车路线推荐问题及其计算复杂度，推荐路线的上客点数量$L$通常固定为常数^[11,17]. 在$L$固定为常数的情况下，搜索最优行驶路线的计算复杂度为$ M={C}_{N}^{L}\times L!. \; M $可以进一步转化为$M = N(N - 1)(N - 2) \cdots (N - L+1)$. 因此，当$L$固定为常数时，搜索最优路线的计算复杂度为$ {\rm O}({N^L}) $.

模拟退火（simulated annealing, SA）算法是求解出租车路线推荐问题的常用算法之一^[16-17]，源于固体退火原理，能够以一定的概率跳出局部最优解并最终趋于全局最优. 因此，本研究选择模拟退火算法对1.1节提出的出租车路线推荐问题进行求解. 算法具体描述如算法1所示. 首先，初始化候选路线$ {\boldsymbol{r}} $. 之后，从候选路线$ {\boldsymbol{r}} $中随机选择一个上客点$ {C_i} $. 为了减少算法的计算成本，采用贪心算法（greedy algorithm, GA）贪婪地从上客点集合$ C = $$ \{ {C_1},{C_2}, \cdots ,{C_N}\} $中选择一个具有最小潜在出行成本的上客点$ {C_j} $. 若$ {C_j} $在候选路线${\boldsymbol{r}}$中，根据现有研究算子选择概率设置^[17]，进行交换$ {C_i} $和$ {C_j} $的位置、颠倒$ {C_i} $和$ {C_j} $之间的上客点的顺序、添加$ {C_j} $作为$ {C_i} $的下一个上客点等操作产生新路线${\boldsymbol{r}}'$，如算法1中步骤5）~12）；否则，替换$ {C_i} $为$ {C_j} $产生新路线${\boldsymbol{r}}'$，如算法1中步骤13）、14）. 最后，判断${\boldsymbol{r}}$和r'的潜在出行成本，若f(r')<f(r)或$\exp\; \left[{\left({f({\boldsymbol{r}}) - f({\boldsymbol{r}}')}\right)}/{T}\right] > {\rm{rand}}\;(0,1)$，则将${\boldsymbol{r}}$替换为新路线${\boldsymbol{r}}'$，如算法1中步骤15）、16）. 重复上述初始化之后的过程直至满足终止条件. 当且仅当目标函数的值收敛时，算法才停止. 为了使模拟退火算法充分搜索解空间的可行解，设置模拟退火算法的初始温度$ T $为潜在上客点数量的100倍，冷却率$ \lambda $=0.95.

算法1　　出租车路线推荐求解算法

输入：出租车当前位置$ {C_0} $，一组潜在的上客点集合$ C $，上客点对应的接客概率集合$ P $和预期票价集合$ F $，每对上客点之间的时间和距离，初始温度$ T $，冷却率$ \lambda $

输出：空闲出租车的最佳行驶路线$ {\boldsymbol{r}} $

1. 初始化路线$ {\boldsymbol{r}} $和参数$ T $、$ \lambda $

2. repeat

3. 　从$ {\boldsymbol{r}} $中随机选取上客点$ {C_i} $

4. 　贪婪选取上客点$ {C_j} $

5. 　if $ {C_j} $ in ${\boldsymbol{r}}$

6. 　　temp = rand (0,1)

7. 　　${\bf{if}}\;{\mathrm{temp}} \leqslant 0.2 $

8. 　　　交换$ {C_i} $与$ {C_j} $的位置产生新路线$ {\boldsymbol{r}}' $

9. 　　${\bf{else\; if}} \;0.2 < {\mathrm{temp}} \leqslant 0.7 $

10. 　　　颠倒$ {\boldsymbol{r}} $中$ {C_i} $与$ {C_j} $之间的上客点的顺序产生新路线$ {\boldsymbol{r}}' $

11. 　　else

12. 　　　添加$ {C_j} $作为$ {C_i} $的下一个上客点产生新路线$ {\boldsymbol{r}}' $

13. 　else

14. 　　替换$ {C_i} $为$ {C_j} $产生新路线$ {\boldsymbol{r}}' $

15. 　if $ f({\boldsymbol{r}}') < f({\boldsymbol{r}}) $或$\exp\; \left(\dfrac{{f({\boldsymbol{r}} ) - f( {\boldsymbol{r}}')}}{T}\right) > {\rm{rand}} \;(0,1)$　

16. 　　$ {\boldsymbol{r}} \leftarrow {\boldsymbol{r}}' $

17. 　$ T = \lambda T $

18. until 终止条件满足

19. return ${\boldsymbol{ r}} $

所使用的出租车GPS轨迹数据源于上海市强生出租车公司于2016年8月25日（星期四）—2016年8月31日（星期三）收集的约12000辆出租车的轨迹数据. 出租车GPS轨迹数据约10 s采集一次，包括车机号、空车（0：重车，1：空车）、GPS时间、经度、纬度等有效数据，部分出租车GPS 轨迹数据信息如表1所示. 在删除重复数据、存在缺失值的数据、空车状态异常的数据和不在研究区域的数据后，每天约有1亿条有效的出租车GPS轨迹数据. 在进一步对数据进行可视化分析后，选择出租车需求较为密集的上海市的市中心区域([121.25°E，31.05°N]~[121.70°E，31.35°N])作为本研究的研究区域.

上海市出租车的价格计算方法源于2014年发布的《上海市市民价格信息指南》^[23]，主要与乘客行驶的距离有关，表达式如下：

(6)$ F_o=\left\{\begin{array}{ll}14, & D_o \leq 3; \\14+\left(D_o-3\right) \times 2.4, & 3< D_o \leq 10; \\14 + (10 - 3) \times 2.4 + \left(D_o - 10\right) \times 3.6, & D_o>10.\end{array}\right. $

式中：$ {F_o} $为乘客$ o $的票价；$ {D_o} $为乘客$ o $的行程距离，通过对出租车占用行程的相邻2个轨迹点之间的球面距离进行累加获得.

实验采用Python语言编写，并在配备Intel(R) Core(TM) i5-1 035G1 CPU和16.00 GB内存的Window 10系统上运行.

出租车的空车状态为0表示出租车处于占用状态，空车状态为1表示出租车处于空闲状态. 因此，根据出租车GPS轨迹数据的车机号和GPS时间对出租车的轨迹数据进行排序，当出租车的空车状态从1变为0时，即视为发生了一次上车事件，以小时为单位统计这些上车事件，即可获得出租车上车事件的时变特性图. 2016年8月29日出租车上车事件的时变特性图如图3所示. 图中，$ {n_{\mathrm{o}}} $为上车事件数量. 上车事件数量在3:00达到了全天上车事件数量的最低值，在10:00、14:00和19:00呈现了较为明显的高峰，其变化趋势与现有研究结果一致^[19,24]. 本研究主要关注7:00—10:00和13:00—16:00这2个典型的时间段，后面的研究也基于这2个时间段开展.

通过DBSCAN对提取的上车事件进行聚类，可以识别出租车需求热点区域，即潜在的上客点，也就是上车事件密度较大的区域. DBSCAN聚类效果取决于Eps半径和MinPts参数的选择. 在本研究中，Eps半径和MinPts参数分别设置为0.5 km和20^[19]. 在聚类过程中，可以针对不同时期和区域采取不同粒度的空间挖掘. 2016年8月29日7:00—10:00和13:00—16:00上车事件的聚类结果如图4、5所示. 聚类之后分别获得51和120个潜在的上客点，根据上客点上车事件的数量从大到小为上客点编号，图中绿色的点和红色的点分别为出租车当前位置$ {C_0} $及一组潜在的上客点$ C $.

为了验证出租车路径推荐求解算法，即使用模拟退火算法和贪心算法（SA+GA）对出租车路线推荐问题求解的有效性，选择蛮力搜索（brute-force search, BFS）算法和基于路由优势和受限子路由优势的序列剪枝搜索（search with sequence pruning via route dominance and constrained subroute dominance，LCPS）算法为基准模型. BFS搜索$ R $中的所有可能路线，并找出潜在出行成本最小的路线. LCPS通过路由优势和受限子路由优势2个剪枝策略修剪搜索空间，从而减少搜索最优路线花费的时间. 潜在上客点数量$ N $对SA+GA、BFS和LCPS的运行时间的影响如图6所示. 图中，$ {T_{\text{r}}} $为运行时间. 当$ N $＜9时，SA+GA、BFS和LCPS的运行时间均接近0. 当$ N $＞9时，BFS和LCPS算法的运行时间开始上升，而SA+GA算法运行时间仍然能够维持在接近于0的水平，证明了SA+GA的有效性.

为了验证本研究所提出的模型的有效性，选择PTD和RTS模型作为基准模型. PTD模型考虑了上客点的接客概率和搜索距离，目标是最小化接载下一个乘客之前的行驶距离. RTS模型考虑了上客点的接客概率、搜索距离和搜索时间，目标是最小化接载下一个乘客之前的行驶距离和时间. RTS模型涉及2个参数$\alpha $和$\beta $的设置. 本研究认为时间和距离同样重要，因此，$\alpha $和$\beta $均设置为0.5. 然而，上述2种方法可能会为出租车推荐接客概率较小的路线，本研究所提出的出租车收益路线推荐PMSR模型进一步考虑了这个问题对目标函数$f({\boldsymbol{d}})$进行了改进. 为了进一步分析PTD、RTS和PMSR模型的路线推荐结果，设置$L$=5. 7:00—10:00和13:00—16:00的PTD、RTS和PMSR模型的路线推荐结果如表2~4和表5~7所示. 表中，T_i、D_i分别为向量T（d）、D（d）的第i个元素.

由表2~4可知，在7:00—10:00，PTD模型的推荐路线为$ {C_0} \to {C_4} \to {C_{17}} \to {C_{14}} \to {C_{29}} \to $$ {C_{10}} $，RTS模型的推荐路线为$ {C_0} \to {C_{17}} \to {C_4} \to {C_{14}}\to {C_{29}} \to $$ {C_{32}} $，PMSR模型的推荐路线为$ {C_0} \to {C_{17}} $$ \to {C_{47}} \to {C_{10}} \to {C_{11}} \to {C_{43}} $. PTD模型推荐路线的上客点的接客概率分别为0.095、0.243、0.120、0.051、0.546；RTS模型推荐路线的上客点的接客概率分别为0.243、0.095、0.120、0.051、0.233；PMSR模型推荐路线的上客点的接客概率分别为0.243、0.846、0.546、0.829、0.155. 因此，PMSR模型推荐路线的接客概率与PTD和RTS模型推荐路线的接客概率相比分别平均提高了148.2%和253.0%，意味着PMSR模型能够为空闲出租车推荐具有较高接客概率的路线. 此外，PMSR模型推荐路线的上客点的预期票价均在20元以上，而PTD和RTS模型为出租车推荐路线时并没有考虑预期票价，其推荐路线取决于接客概率、搜索距离和搜索时间，会为空闲出租车推荐具有较低预期票价的上客点，如PTD和RTS模型推荐路线中的上客点$ {C_{14}} $.

同样，由表5~7可知，在13:00—16:00，PTD、RTS和PMSR模型的推荐路线分别为C₀→C₉₉→C₁₁₇→C₄₀→C₈₄→C₁₀₉、 C₀→C₉₉→C₈→C₄₀→C₈₄→C₈₆和 C₀→C₄₈→C₁₂→C₄₁→C₁₃→C₈₂，其推荐路线上客点的概率分别为0.400、0.217、0.353、0.386、0.220，0.400、0.621、0.353、0.386、0.243和0.295、0.567、0.356、0.990、0.757，PSMR模型推荐路线的接客概率与PTD和RTS模型相比分别平均增加了88.1%和48.0%. 同时，PMSR推荐路线上客点的最低票价也高于PTD和RTS模型（PTD和RTS模型的最低票价均为16.938，PMSR的最低票价为17.223）.

上述分析结果表明，PMSR模型能够综合考虑推荐路线的所有上客点的预期票价为空闲出租车推荐接载乘客概率更高的路线，优于PTD和RTS模型.

为了进一步探索PTD、RTS和PMSR模型推荐路线的搜索时间和距离的差异，绘制PTD、RTS和PMSR模型推荐路线的搜索时间和搜索距离向量折线图如图7~10所示. 相较于不考虑搜索时间的PTD模型，RTS和PMSR模型推荐路线的搜索时间在7:00—10:00分别平均减少了11.6%、14.3%，在13:00—16:00分别平均减少了19.4%、24.2%. PMSR模型相比RTS在7:00—10:00和13:00—16:00分别平均减少了3.2%和5.9%. 与PTD和RTS模型相比，PMSR模型的推荐路线搜索距离更短，在7:00—10:00平均减少了17.3%和14.9%，在13:00—16:00平均减少了32.0%和4.9%. 上述分析结果表明PMSR模型能够为空闲出租车推荐具有较短搜索时间和距离的路线.

为了验证考虑上客点的出租车需求的出租车收益路线推荐的有效性，在出租车当前位置进一步开展考虑出租车需求的出租车收益路线推荐实验分析，结果如表8、9所示. 在7:00—10:00和13:00—16:00，PMSR-D模型的推荐路线分别为C₀→C₁₇→C₂→C₁₁→C₁₀→C₄₃和C₀→C₄₈→C₈→C₄₁→C₈₂→C₁₃，与PMSR模型推荐路线的主要区别均是第2个上客点不同. 在7:00—10:00，PMSR和PMSR-D模型推荐路线中第2个上客点分别为$ {C_{47}} $和$ {C_2} $，$ {C_{47}} $的接客概率为0.846，$ {C_2} $的接客概率为0.532. 虽然$ {C_{47}} $的接客概率大于$ {C_2} $，但是$ {C_{47}} $的需求为23，而$ {C_2} $的需求为148，相比$ {C_{47}} $增加了125个潜在的乘客需求，出租车在$ {C_2} $的选择更多. 在13:00—16:00，PMSR和PMSR-D的第2个上客点分别为$ {C_{12}} $和$ {C_8} $，需求分别为101和121，且$ {C_8} $的接客概率高于$ {C_{12}} $. 此外，在7:00—10:00和13:00—16:00，与PMSR模型相比，PMSR-D模型推荐路线的搜索时间分别平均减少了13.6%、6.4%，预期票价分别平均增加了17.0%、8.0%. 然而，PMSR-D模型推荐路线和PMSR模型推荐路线的搜索距离差异不大. 上述分析结果表明通过进一步考虑上客点的需求，可以为出租车推荐需求较大的路线，增加出租车成功接载乘客的可能性.

本研究通过考虑出租车接载下一个乘客获得的收益及上客点需求对移动顺序推荐问题进行了改进，之后基于上海市GPS轨迹数据，采用DBSCAN算法、模拟退火算法和贪心算法对改进的出租车收益路线推荐模型和考虑需求的出租车收益路线推荐模型进行了验证. 结果表明，相比于PTD和RTS模型，出租车路线收益推荐PMSR模型的推荐路线的搜索时间和搜索距离更小，上客点的最低预期票价也较高. 此外，PMSR模型推荐路线的接客概率与PTD和RTS模型相比在7:00—10:00分别平均提高了148.2%和253.0%，在13:00—16:00分别平均提高了88.1%和48.0%. 考虑需求的出租车路线收益推荐PMSR-D模型能够为出租车推荐需求较大的路线，与PMSR模型相比在7:00—10:00和13:00—16:00分别增加了125和20个潜在的乘客需求，验证了PMSR-D模型的有效性.

本研究主要关注当前出租车根据推荐路线行驶后接载新乘客获得的收入问题，不足之处在于出租车在整个运营周期内的订单布局对其收益的影响尚不清楚，未来可以进一步探索订单布局对出租车收益的影响，从而为出租车提供更精准的路线推荐，增加出租车司机的收入. 此外，探索适用于全市范围的自适应出租车需求热点识别方法也是未来的研究方向之一.