网约车共享在很大程度上缓解了出行、环境和资源压力,网约车共享工作主要有两个方面:订单指派和路径规划。本文从这两方面出发,同时兼顾乘客和司机的利益,提出了基于矩阵划分的多目标订单指派算法（Matrix Partition-based Multi-Objective Order Assignment Algorithm,MPB-MOOAA）和基于地标分段的多目标路径规划算法（Landmark Segmentation-based Multi-Objective Route Planning Algorithm,LSBMORPA）,从而解决共享环境下的订单指派和路径规划问题,主要研究工作如下:1.以最大服务质量和最大共享里程率为目标,建立了多目标订单指派问题优化模型,并提出MPB-MOOAA对该模型进行求解。该算法首先采用两点间近似最短距离以代替计算昂贵的最短路径距离,从而降低了算法的时间复杂度;其次采用关系矩阵划分算法,使具有相似旅程的乘客和司机聚集起来,从而将一个矩阵分解为多个小矩阵进行处理,大幅度缩小了问题规模;最后提出了矩阵压缩机制减少了解的存储空间,从而降低了算法的空间复杂度。实验结果表明,MPB-MOOAA适用于不同实际场景,相比其他经典的多目标进化算法在处理订单指派问题上更具优势。2.以最小行驶距离和最大可兼容乘客数为目标,建立了多目标路径规划问题优化模型,并提出了LSB-MORPA对该模型进行求解。该算法以进化算法为基本算法,在初始解构造中引入双向随机游走思想,设计了全新的交叉和变异算子,预测了非支配解集,从而平衡了行驶距离和载客数之间的关系。为了提高推荐路径的效率和多样性,该算法通过引入地标对路径进行了分段处理,提高了路径覆盖乘客率。实验结果表明,LSB-MORPA解的多样性和收敛性较好,相比未引入地标的算法,引入地标的算法非支配路径推荐成功率明显提高。3.实现了网约车路径规划系统。基于开源的j Metal框架实现了MPB-MOOAA和LSB-MORPA,为了使其更适合处理路径规划问题,在j Metal框架中增加了新的交叉算子和变异算子。使用JSP结合Servlet实现了网约车共享路径规划系统可视化展示。