动态约束与松弛分割的多目标上车点推荐

Multi-Objective Pick-Up Point Recommendation with Dynamic Constraint and Relaxed Segmentation

合理优化网约车乘客上车点,可以有效减少司机接驾和乘客步行距离,提升接驾效率、降低乘客聚集度,从而缓解节点拥堵并提升乘客的出行体验。影响上车点规划结果的因素较多,均衡考虑各影响因子且保证规划方案的可行性具有较大难度。针对上述问题,提出了一种涵盖乘客步行收益、路况收益和司机驾驶收益的多目标整数规划模型,并且设计了一种松弛分割迭代算法以及一种基于动态约束法的帕累托前沿生成法。对时空轨迹数据进行分析与筛选,获取路网中可达的潜在上车点。以分支定界法将松弛问题分割为子问题并对原问题定界,以单纯形法求解转换为标准型的目标函数。分别求解单目标模型获取边界值,再动态调整边界值作为约束条件生成帕累托前沿曲面。通过大量实验对各目标的耦合性和互斥性进行分析,得出目标函数的均衡取值点,从而以不同角度对上车点进行有效推荐。

Optimization of online ride-sharing pick-up points effectively reduces driver pick-up and passenger walking distances,enhances pick-up efficiency,alleviates passenger aggregation and node congestion,and improves passenger travel experience.However,the results of the pick-up point planning are influenced by various factors,and it is challenging to address these factors comprehensively to ensure the feasibility of the planning scheme.In response to these challenges,a multi-objective integer linear planning model is proposed,covering passenger and driver benefit as well as road condition.Moreover,a relaxed segmentation iterative algorithm and a Pareto front generation method based on dynamic constraints are developed.Firstly,the spatial and temporal trajectory data is analyzed and filtered to obtain potential pick-up points that are accessible on the road network.Secondly,the relaxation problem is partitioned into subproblems by the branch-and-bound method,which is solved by the simplex method to convert the objective function to its standard form.Thirdly,the single-objective models are solved separately to obtain the boundary values,which are dynamically adjusted as constraints to generate Pareto surfaces.Finally,the correlation among the objectives is analyzed through a large number of experiments to derive the equilibrium point,so as to effectively recommend pick-up points from different perspectives.