详情

原文传递基于智能优化的共乘调度算法

论文题名：	基于智能优化的共乘调度算法
关键词：	共享拼车;共乘调度;差分进化;模糊计算
摘要：	近年来，随着公共交通的发展，私家车保有量不断增多，带来了交通拥堵，汽车尾气污染等问题。因此，人们提出了一种经济便捷的出行方式，共享拼车，通过具有相似行程的人共乘的方式，提高车辆的座位利用率，在一定程度上节约能源，减少尾气排放，缓解交通拥堵。共享拼车问题是一个NP难的组合优化问题，求解复杂度高，应用场景复杂。本文讨论了静态拼车和动态拼车两种主要的拼车场景，并设计了基于智能优化的共乘调度算法以给出较优的拼车调度方案。　　本文首先讨论了静态拼车问题，并提出基于差分进化的静态拼车算法（Differential Evolution-based Ridesharing Algorithm,DERA）优化拼车分配方案。算法首先以集合的方式构建了一个综合考虑服务质量和成本的拼车模型，以最大化服务率和用户体验，并利用基于集合的差分进化算法（Set-based Differential Evolution,S-DE）来搜索可行解。特别地，根据拼车问题的特性提出跨维度变异算子，基于维度和基于个体的两级选择算子，种群多样性增强算子等，大大提高了算法在求解静态拼车问题的适应性和优化效率。在模拟的城市交通数据集上，我们的算法相较于对比算法在收敛性能和目标表现上要更加优化。　　然后本文讨论了拓展到外卖配送领域的动态拼车问题，构建了拼车匹配率和拼车效益率的多目标多约束拼车模型，并提出基于模糊计算的动态拼车算法（Fuzzy System-based Ridesharing Algorithm,FBRA）完成外卖和乘客的拼车调度。算法首次利用模糊系统进行拼车行程的实时匹配。特别地，设计了近似绕路距离等输入变量表征匹配行程的相似性，以提高模糊系统的匹配质量。此外，FBRA由线上和线下两个模块，线下模块利用差分进化算法（Differential Evolution，DE）训练进一步优化模糊匹配系统，线上模块通过模糊系统评估乘客或外卖与出租车的匹配度并选择最高匹配度的出租车进行匹配的方式完成实时响应。在实验上，模拟了北京的实时交通数据集并测试了算法的表现，实验证明我们的算法在综合表现上优于现有的算法，且在大规模数据集上也有稳定的效果。
作者：	张心怡
专业：	计算机科学与技术
导师：	龚月姣
授予学位：	硕士
授予学位单位：	华南理工大学
学位年度：	2021