多方有益的出租车拼车调度方法

摘要

本发明提供一种多方有益的出租车拼车调度方法，其包括：对于乘客发送的乘车请求，调度中心分析其中包含的信息：乘客数目、上车位置和上车位置时间范围、下车位置和下车位置时间范围、愿意支付的小费；调度中心跟踪各出租车的状态，包括出租车位置和车上乘客数目，根据乘车请求中的信息和出租车状态设定整数线性规划的目标函数，计算得到最优解，将求解整数线性规划得到的调度作为当前出租车拼车调度方案。该方法还包括一个动态的规划更新机制，只有当新调度对于目标函数的提升能够达到或超过一个阈值，才对当前的出租车调度进行更新。本发明可以降低乘客打车的花费，增加出租车司机的收益，使得多方受益。

主权项

一种多方有益的出租车拼车调度方法，其特征在于：对于乘客发送的乘车请求，调度中心分析其中包含的信息：乘客数目、上车位置和上车位置时间范围、下车位置和下车位置时间范围、愿意支付的小费；调度中心跟踪各出租车的状态，包括出租车位置和车上乘客数目，根据乘车请求中的信息和出租车状态设定整数线性规划的目标函数，计算得到最优解，将求解整数线性规划得到的调度作为当前出租车拼车调度方案；所述整数线性规划具体包括：刻画出租车拼车调度：首先，使用来表示当前正要处理的乘车请求集合，n表示乘车请求数，使用来表示道路上出租车的集合，m表示出租车数；接着，将出租车拼车调度问题刻画在一个有向图G(N,A)中，N用来表示有向图G中节点的集合，A用来表示有向图G中有向边的集合，其中N＝O∪P∪D,O＝{1,…,m}，P＝{m+1,…,m+n}，D＝{m+n+1,…,m+2n}；集合P和D用来表示上车位置和下车位置，集合O用来表示出租车当前的位置；用c来表示每辆出租车的最大载客数目；每一个有向图G中的节点i都赋予一个负载q_i；对于i属于O或P，负载q_i≥1，对于i属于D，负载q_i＝‑q_i‑n；负载q_i用来表示一个乘车请求中乘客的人数；对于每一个P和D中的节点，设定一个时间窗口[e_i,l_i]来表示最早和最晚到达这个节点i的时间限制；对于每一个节点i属于D，使用β_i来表示对于乘车请求R_i‑m‑n的线性递减系数；对于有向图G中每一条有向边(i,j)和每一辆出租车，如果车辆k被调度去通行(i,j)这条道路，则将设置为1，否则设置为0；表示出租车k是否通行(i,j)这条道路，取值1表示通行，取值0表示不通行；使用来表示出租车k到达节点i时的时间，使用来表示出租车到达节点i时，车上的乘客数目；设定整数线性规划的限制条件：1)从出租车位置出来的流最多为一：$\begin{array}{cc}{\Sigma }_{j\in N}{x}_{k,j}^k\le 1& \forall k\in v.\end{array}---\left(1\right)$2)所有进入上车位置即接客位置的流都会离开这个位置：$\begin{array}{cc}{\Sigma }_{j\in N}{x}_{ji}^k={\Sigma }_{j\in N}{x}_{ij}^k& \forall i\in P,k\in v.\end{array}---\left(2\right)$3)限制所有出租车从上车位置出来的流最多为一，用公式(3‑1)表示；限制经过上车位置的出租车，最终会到达下车位置，用公式(3‑2)表示；$\begin{array}{cc}{\Sigma }_{k\in v}{\Sigma }_{j\in N}{x}_{ij}^k=1& \forall i\in P\end{array}.---(3-1)$$\begin{array}{cc}{\Sigma }_{j\in N}{x}_{ij}^k={\Sigma }_{j\in N}{x}_{j,i+n}^k& \forall i\in P,k\in v\end{array}.---(3-2)$4)到达终点的流的总数目大于等于进入终点的流的总数目：$\begin{array}{cc}{\Sigma }_{j\in N}{x}_{ji}^k\ge {\Sigma }_{j\in N}{x}_{ij}^k& \forall i\in D,k\in v.\end{array}---\left(4\right)$5)刻画出租车到达每一个位置的时间关联性，用公式(5‑1)表示；限制出租车到达每一个位置的时间处于规定范围内，用公式(5‑2)表示；限制出租车会先到达上车位置，再达到下车位置，用公式(5‑3)表示；$\begin{array}{cc}{T}_j^k\ge (T_i^k+t_{ij})x_{ij}^k& \forall i\in N,j\in N,k\in v.\end{array}---(5-1)$$\begin{array}{cc}{e}_i\le T_i^k\le l_i& \forall i\in P\cup D,k\in v\end{array}.---(5-2)$$\begin{array}{cc}{T}_i^k\le T_{n+i}^k& \forall i\in P,k\in v\end{array}.---(5-3)$其中，t_ij表示从有向图G中节点i到节点j所需要的时间；6)刻画出租车达到每一个位置时，车上乘客的数量，用公式(6‑1)表示；限制乘客数量小于车的容量c，用公式(6‑2)表示：$\begin{array}{cc}{Q}_j^k\ge (Q_i^k+q_j)x_{ij}^k& \forall i\in N,j\in N,k\in v.\end{array}---(6-1)$$\begin{array}{cc}{Q}_i^k\le c& \forall i\in N,k\in v.\end{array}---(6-2)$设定整数线性规划的目标函数；有两个目标函数，第一个目标函数用于优化司机赚到的小费的数目，用公式(7)表示：$\begin{array}{cc}{\mathrm{max\Sigma }}_{i\in D}({\alpha }_i-{\beta }_i({\Sigma }_k{T}_i^k-e_i)).& ,k\in v\end{array}---\left(7\right)$其中，α_i为每位发送乘车请求的乘客愿意最多支付的消费；第二个目标函数用于最小化所有乘客送达延时的加权和，用公式(8)表示：$\begin{array}{cc}{\mathrm{min\Sigma }}_{i\in D}{\beta }_i{\Sigma }_k{T}_i^k.& ,k\in v\end{array}---\left(8\right)$求得公式(7)或(8)中的一个最优解，然后将求解整数线性规划得到的调度作为当前出租车拼车调度方案。