基于多目标和动态解空间规划的可持续网约车调度问题建模与求解  

Modeling and Solution of Sustainable Online Ride-hailing Scheduling Problem Based on Multi-objective and Dynamic Solution Space Programming

作　　者：李振 郭羽含 LI Zhen;GUO Yu-Han(Software College,Liaoning Technical University,Huludao 125105,China;College of Science,Zhejiang University of Science&Technology,Hangzhou 310023,China)

机构地区：[1]辽宁工程技术大学软件学院,葫芦岛125105 [2]浙江科技大学理学院,杭州310023

出　　处：《计算机系统应用》2025年第1期236-247,共12页Computer Systems & Applications

基　　金：国家自然科学基金(61404069);辽宁省自然科学基金(2019-ZD-0048);浙江省自然科学基金重点项目(LZ22F020007);浙江科技学院青年科学基金(2023QN022)。

摘　　要：针对网约车运营中经济、环境和社会效益这3方面存在的相互制衡关系,提出了一种平衡经济、环境和社会效益三重底线的多目标调度问题模型以及基于动态解空间规划的求解算法.问题模型首次将传统出租车服务与共享出行模式整合,全面覆盖4种不同的司机与乘客互动情景,旨在通过优化策略实现3方面效益的协同提升.求解算法创新性地结合了LAPJV算法与分支限界法,确保在给定阈值约束下,能够高效探索并确定满足多目标优化的最优匹配策略.该算法相比于SCIP,结果平均误差在4%内,求解平均速度提升了99.1%.研究进一步通过系统性地应用此算法,针对不同阈值约束条件,求解并生成帕累托前沿图,直观展示了经济、环境与社会效益这3个目标在其他两项指标约束下的权衡与变化趋势,为网约车运营提供了决策参考依据.Considering the balance among economic,environmental,and social benefits in ride-hailing operations,this study proposes a multi-objective schedule model that balances these three benefits,as well as an algorithm based on dynamic space programming.The model integrates traditional taxi services and shared transport for the first time,comprehensively covering four different interaction scenarios between drivers and passengers,to achieve synergistic improvement of the three benefits through optimization strategies.The algorithm creatively combines the LAPJV algorithm and the branch and bound method to ensure that the optimal matching strategy satisfying multi-objective optimization can be efficiently explored and determined under the given threshold constraints.Compared with SCIP,the average error of the algorithm is within 4%,and the average solving speed is improved by 99.1%.This study systematically applies this algorithm to solve and generate Pareto frontier graphs for different threshold constraints,intuitively displaying the trade-offs and changing trends of one of the three objectives(economic,environmental,and social benefits)under the constraints of the other two objectives.This study provides a decision-making basis for ridehailing operations.

关 键 词：网约车 LAPJV算法 分支限界法 帕累托前沿 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]