郑建国，李园园

(东华大学旭日工商管理学院，上海200051)

0 引言

有效的出租车合乘模式，可以提高座位利用率，缓解城市交通压力，降低能源消耗等，可产生社会、环境、经济等综合效益.近些年，一些国内外学者围绕出租车合乘问题展开了相关研究.

根据乘客需求是否变化，合乘可分为静态合乘与动态合乘.Lin等[1]研究了静态有时间窗的出租车合乘路径优化模型；Tao等[2]提出动态出租车合乘，但主要研究合乘匹配，并未解决路径问题，而综合考虑合乘匹配与路径优化可以进一步实现系统成本最优.

同时，多数研究将乘客上车时间定义为硬时间窗，且所有请求必须满足，如Cordeau等[3]；部分学者假设在硬时间窗的约束下可以不满足所有乘客，如 Hosni[4]、Jung[5]等.而实际上，略超出时间窗，客户也可能接受，硬时间窗则限制了该情形.目前，部分VRP文献做了相关研究，如：刘家利等[6]在开环VRP问题研究中以软时间窗在一定程度上避免严格约束，但车辆到达时间可能过早或过晚；而杨翔等[7]综合利用硬、软时间窗的特点，使时间窗模糊化.现实中，乘客对出行时间窗的认知也是非严格理性的，故模糊时间窗更符合实际.

另外，乘客对绕行、合乘等服务的偏好不尽相同.考虑乘客不希望绕行，Hosni H.等[4]引入行驶时间约束，Jung J.等[5]增加最大绕行约束；而在合乘意愿方面，当前研究存在“乘客均接受合乘”的一般假设，显然与实际不符，如何对合乘意愿进行量化、区分描述，还需进一步研究.

综上，鉴于当前出租车合乘模型与实际偏离的情况，本文定义模糊时间窗，考虑合乘意愿，建立更切实际的问题模型，并设计改进的差分进化算法求解，最后通过算例验证模型和算法的有效性.

1 基于模糊时间窗的出租车合乘问题描述及建模

1.1 出租车合乘问题描述

本文所研究的出租车合乘为多上车点到多下车点的多对多模式.具体描述为：多辆出租车在某区域行驶，车上可能有乘客；同时，有多名新的乘客预约，各有其上下车位置与时间要求.调度中心根据当前乘客与出租车的状态，在满足多种约束的条件下确定乘客与出租车的最佳匹配方案及行驶路径.

数学描述为：给定包含4个子集的点集V，V=V1⋃V2⋃V3⋃V4，其中，V1表示出租车坐标集，V2表示车上乘客的下车点集，V3、V4分别表示预约乘客的上下车点集，乘客p的上下车点分别为s(p)、f(p)；T、O、S分别表示出租车、车上乘客、预约乘客集合，乘客全集P=O⋃S；乘客具有是否接受合乘2种态度，将其量化为占用座位数Q(p)，取值为1或q(出租车最大容量)；乘客最早、最迟上车时间分别为表示p的出行时间上限；i、j之间距离为dij、用时为Uij、成本为Cij.决策变量，0-1决策变量表示如果p乘t车从i到j则为1，否则为 0；0-1决策变量表示若t车从i至j则否则为0；0-1决策变量dpt，表示若p乘t车则dpt=1，否则为0；非负决策变量uti表示t车到达i的时间.

1.2 模糊时间窗

根据模糊集理论，定义“及时度”Jp(t)，表征出租车到达上车点的及时程度.若t在原时间窗内，及时度为1；当t超出原时间窗且在之内，导致车辆等待或客户满意度下降，及时度降低；当t超出容忍限度时，及时度为0.因此，梯形模糊数更加契合，故用其表征基于模糊时间窗的及时度隶属函数Jp(t)为

及时度为1时，惩罚费用为0；及时度为0时，出租车因到达过早产生车辆等待成本μ，或过晚而产生客户惩罚成本∂；t超出原时间窗且在之内时，产生相应比例成本.时间惩罚费用函数Lp(t)为

1.3 模型建立

式(3)为目标函数，表示总成本最小化，成本项依次是路径成本、拒载成本、时间惩罚成本；式(4)为最大容量约束；式(5)表示任1位乘客最多被1辆车服务；式(6)和式(7)为乘客上车时间容忍限度约束；式(8)为绕行约束；式(9)～式(17)为节点流量及路径规则约束，详见文献[4]，此不赘述；式(18)表示二进制变量和非负变量约束.

本模型参考文献[4]建立，主要区别有3点：①目标函数不同，文献[4]从出租车单方面考虑，以利润最大化为目标，而本文考虑乘客服务因素(拒载、服务及时度等)，量化其造成的客户损失及车辆等待成本等，从乘客与出租车两个角度考虑系统成本最小化.②时间窗定性不同，文献[4]为硬时间窗，而本文为模糊时间窗，并考虑因其匹配差异产生的相关成本.③文献[4]假设“乘客都愿意合乘”，本文对合乘意愿进行区分描述.

2 基于个体排序的差分进化算法设计

2.1 编码、解码及种群初始化

(1)分段编码与初始化.

乘客分为车上和预约2种，故二进制编码无法直接应用[8]；而以实数编码、并用0间隔表示不同车辆[9]，计算复杂度增加，且在DE算法中会产生大量不可行解.因此，本文设计一种分段取值的实数编码方案.

假设有m个车，s个预约乘客(上车点SO、下车点 SD)，oi个车上乘客(下车点 OD)，将个乘客节点以{SO，SD，OD}的顺序编码，个体可表示为

其中，SO、SD的xi取值范围为：1≤xi≤m+1；OD的xi取值范围为：1≤xi≤mi+1(mi为该乘客所在车辆编号).

按照上述编码，所有乘客节点数即为维度D，各维元素在其取值范围内随机生成，产生初始种群.

(2)解 码.

将个体按如下步骤解码为m行的元胞矩阵P，表示各出租车服务乘客及行驶路径.

Step 1根据SO的取值范围1≤xi≤m+1为每个预约乘客分配车辆，如1≤xi≤2，即m=1，该乘客由车1服务.

Step 2根据Step1的分配结果，将各车服务的乘客节点编号按从小到大的顺序排列，构成该车辆的可能路径R1.应注意，是否有乘客的下车点在其上车点之前，若有，则转Step3；否则，转Step4.

Step 3路径调整，将下车点在上车点之前的乘客互换两点位置，构成路径R2，转step4.

Step 4判断是否满足车辆到达时间的最大容忍限度及车的容量约束，若有任一条件不满足，则将该乘客的上下车节点从原有路径中去除，视为拒载；路径更新为R3.

Step 5按以上4个步骤完成所有车辆的路径解码，即构成元胞矩阵P.

2.2 适应度函数设计

本文模型为最小化问题，故将式(3)中Z的倒数作为适应度函数，即f=1/Z=1/(TD+TR+TL)，其中，TD、TR、TL分别为总路径成本、总拒载成本与总时间惩罚成本，目标函数越小、适应度越大，个体越优秀.

2.3 算子设计

(1)基于个体排序的变异策略.

采用DE/rand/1变异策略，公式为

式中：r0,r1,r2∈[1,NP]，为互不相同且与i不等的随机整数；一般，变异率F∈(0,1).本文利用种群信息，设计基于个体适应度排序的变异率Fi为

式中：Rank(xi)为个体按照适应度从优到劣的排序值，则个体从优到劣的Fi值从1/NP到1变化，从而精英个体以较小缩放步长实现局部精确寻优，而较差个体以较大缩放步长全局寻优.

(2)基于个体排序的交叉策略.

而Gong等[10]根据当前种群的适应度排序按比例选择变异算子的基准向量与终点向量，以实现较优个体的信息有更大机会被繁殖.受此启发，本文设计一种新的基于个体排序的交叉概率CRi为

由式(21)，越优秀个体的CRi越小，其携带信息越可能被选择贡献给试验个体；其中，CRmin、CRmax为CR的最小、最大值.

(3)混合轮盘赌的半贪婪选择策略.

具体步骤为：

Step 1对第G代种群XG，执行轮盘赌，产生新种群XG1.

Step 2比较XG中个体xi,G与相应试验个体ui,G的适应度，如果f(ui,G)＜f(xi,G)，则选择ui,G作为下一代第i个个体；否则，选择XG1种群中的xi,G1作为新一代个体.

2.4 改进的差分进化算法(ISDE)基本流程

算法步骤为：

Step 1设置参数，包括种群规模NP、最大进化代数GM及CRmin、CRmax等，生成初始种群，运行代数t=0.

Step 2对第t代xi,G执行基于个体排序的变异操作产生vi,G，详见2.3节(1)所述.

Step 3对第t代vi,G执行基于个体排序的交叉操作产生ui,G，详见2.3节(2)所述.

Step 4对原种群进行轮盘赌选择产生新种群，以半贪婪的选择方式产生新一代个体，详见2.3节(3)所述.

Step 5判断是否达到代数限制，若是，则停止，输出最优解；否则，t=t+1，转Step2再次循环，直到达到终止条件.

算法流程如图1所示.

图1 ISDE算法的基本流程Fig.1 The basic flow of the ISDE algorithm

3 实验结果及分析

3.1 测试算例

参照文献[4]创建一个20辆出租车，60个预约乘客及20个车上乘客的测试算例：出租车及乘客接送点坐标根据均匀分布在[-10,10]×[-10,10]范围内随机产生，假设Uij是i到j的欧氏距离，Cij=Uij，客容量为4；根据U(10,15)随机生成，模糊时间窗宽度前5组算例数据如表1和表2所示.

表1 出租车信息Table 1 The information of taxies

表2 乘客信息Table 2 The information of passengers

3.2 算法有效性分析

分别独立运行10次DE、GA及ISDE算法求解本文算例，NP=50、GM=200，其他算法参数设置如表3所示；运行环境为win7、Intel(R)Pentium(R)CPU、2.13GHZ、matlab2012b.算法对比结果如图2和表4所示.

表3 算法参数设置Table 3 The parameter settings of the algorithms

图2 算法收敛曲线Fig.2 The convergence curve of the algorithm

由图2和表4可知，求解效果由好到差依次为ISDE、DE、GA；与GA相比，DE收敛速度更快，但易陷入局优，而ISDE算法收敛较快，同时精度较优，说明该算法的优越性.

表4 算法求解结果对比Table 4 The comparison of the algorithms solution results

3.3 模型有效性分析

分别独立运行10次ISDE算法分别求解合乘与非合乘2种模式，结果对比如表5所示，所求最优解分别如表6和表7(仅列5组)所示.

表5 合乘与非合乘模式的求解对比Table 5 The comparison of solutions between the shared and non-shared model

表6 合乘模式所求最优解Table 6 The best solution solved in the shared model

表7 非合乘模式所求最优解Table 7 The best solution solved in the non-shared model

由表6可知，本文模型能保证出租车将车上乘客送至目的地的同时，接送新的预约乘客，且出现合乘；由表7可知，在非合乘模式中，出租车均是先将车上乘客送至目的地，再接送其他预约乘客，不出现合乘；而由表5可知，与非合乘模式相比，合乘模式能服务更多乘客，节约总成本，充分说明本文模型求解出租车合乘问题的有效性.

3.4 模糊时间窗宽度的影响分析

改变模糊时间窗的宽度W，10次求解结果如表8所示.

表8 不同时间窗宽度下的模型求解对比Table 8 The comparison of solutions among models with various width of time window

由表8可知，模糊时间窗的宽度越大，总成本越小，平均服务乘客越多.因此，在实际运营时，获取乘客的模糊时间要求，并通过一定措施放松其宽度，具有一定价值.

3.5 合乘意愿的影响分析

改变拒绝合乘的人数N，10次求解结果如表9所示.

表9 拒绝合乘人数不同的模型求解对比Table 9 The comparison results of various number of people rejecting to share a taxi

由表9可知，拒绝合乘的人数越多，总成本越大，平均服务乘客越少，说明接受合乘的人数越多，合乘模式越能节约成本，此外，考虑合乘意愿能提升乘客满意度.因此，在实际运营时，了解合乘意愿，并通过一定措施激励乘客接受合乘，也具有一定价值.

4 结论

为提高出租车的座位利用率，考虑模糊时间窗及合乘意愿，建立更切实际的出租车合乘模型，并设计改进的差分进化算法(ISDE)求解.该算法采用分段实数编码，设计一种基于个体排序的缩放因子F与交叉概率CR，并提出混合轮盘赌的半贪婪选择策略，使种群多样性与收敛速度得到有效平衡.仿真结果表明，所构建的问题模型及改进的差分进化算法均为求解带时间窗的多对多出租车合乘问题的有效方法，为后续研究奠定一定基础.动态环境下的仿真、时间窗设置、合乘意愿的影响因素等问题，还需进一步深入研究.

[1]LIN Y,LI W,QIU F,et al.Research on optimization of vehicle routing problem for ride-sharing taxi[J].Procedia-Social and Behavioral Sciences,2012(43):494-502.

[2]TAO C C.Dynamic taxi-sharing service using intelligent transportation system technologies[C]//International Conference on Wireless Communications,Networking and Mobile Computing.IEEE Xplore,2007:3209-3212.

[3]CORDEAU J-F.A branch-and-cut algorithm for the dial-a-ride problem[J].Operations Research,2006,54(3):573-586.

[4]HOSNI H,NAOUM-SAWAYA J,ARTAIL H.The shared-taxi problem: Formulation and solution methods[J].Transportation Research Part B:Methodological,2014(70):303-318.

[5]JUNG J,JAYAKRISHNAN R,PARK J Y.Dynamic shared-taxi dispatch algorithm with hybrid-simulated annealing[J].Computer-Aided Civil and Infrastructure Engineering,2016,31(4):275-291.

[6]刘家利,马祖军.存在车辆租赁及共享且有时间窗的多配送中心开环VRP[J].系统工程理论与实践,2013,33(3):666-675.[LIU J L,MA Z J.Multi-depot open vehicle routing problem with time windows based on vehicle leasing and sharing[J].Systems Engineering-Theory&Practice,2013,33(3):666-675.]

[7]杨翔,范厚明,张晓楠,等.基于模糊时间窗的多中心开放式车辆路径问题[J].计算机集成制造系统,2016(7):1768-1778.[YANG X,FAN H M,LI X N.The multi centers and open vehicle routing problem based on fuzzy time window[J].Computer Integrated Manufacturing Systems,2016(7):1768-1778.]

[8]YE Q,MA C,HE R,et al.Multi-objective optimisation for taxi ridesharing route based on non-dominated sorting genetic algorithm[J].International Journal of Wireless&Mobile Computing,2015,8(3):262-270.

[9]程杰,唐智慧,刘杰,等.基于遗传算法的动态出租车合乘模型研究[J].武汉理工大学学报(交通科学与工程版),2013(1):187-191.[CHENG J,TANG Z H,LIU J,et al.Research on the dynamic taxi sharing model based genetic algorithm[J].Journal of Wuhan University of Technology(Transportation Science Engineering),2013(1):187-191.]

[10]GONG W,CAI Z.Differential evolution with rankingbased mutation operators[J].IEEE Transactions on Cybernetics,2013,43(6):2066-2081.

[11]DAS S,SUGANTHAN P N.Differential evolution:A survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation,2011,15(1):4-31.

[12]王海燕,赵燕伟,张景玲,等.基于混合差分进化的混排Flow-shop分批优化调度[J].计算机集成制造系统,2013(7):1613-1625.[WANG H Y,ZHAO Y W,ZHANG J L,et al.Batch optimized scheduling of intermingling flow-shop based on hybrid differential evolution algorithm[J].Computer Integrated Manufacturing Systems,2013(7):1613-1725.]