基于k-means聚类算法的共享汽车调度方案.doc

PAGE PAGE 1 2021年数学建模论文 基于k-means聚类算法的共享汽车调度方案 摘要 针对共享汽车调度费用高、相关企业盈利难的问题，本文首先分析了共享汽车的使用数据，总结了相关的规律。并且，在此基础上，本文提出了降低共享汽车调度费用的方法，即选取最优的汽车投放位置，提高汽车被租用的可能性。为此，本文建立了静态的分析模型，将所有可停车位置采用k-means聚类算法分类，得到可用汽车数个类别，并在每个类别中选取距离该类别中心点最近的停车位，作为投放共享汽车的位置，从而实现降低调度费用的目的。本文还对算法做了分析，并提出了改进的方向。 关键词 共享汽车、调度算法、k聚类分析算法 问题重述 随着“共享经济”的迅速普及，共享汽车也随之悄然进入人们的视野之内。这些共享汽车的平台也像共享单车的发展模式，出现在大城市之中，在市场之上有着一定的反响。共享汽车的出现为人们的生活带来了方便和快捷，但是新事物的诞生还是需要和社会实际情况不断磨合相适应。但是共享汽车有很多的问题，同时也由于消费者有了更高的追求和随着盈利难、用户体验差、管理问题多等诸多问题的出现和发生。导致了曾经风光一时的共享汽车热潮开始逐渐退却。 为了降低共享汽车公司的运营成本，必须首先要解决共享汽车的调度问题。在阅读题目并查看了相关的数据之后，本文认为题目提供的数据有以下几个特点：一是数据量较大，有一百余万条；二是时间跨度比较大，不利于分析；三是缺少关键信息，如每次租用汽车的租金，以及行驶的里程、路线等等，因此本文难以建立一个动态的汽车调度模型来实时调度所有的汽车，同时达到最低调度费用和最大租金收益。为了解决这个问题，本文考虑了一种静态的汽车调度模型，通过选取共享汽车的最佳投放位置，来间接达到最大的租金收益和最小的调度费用。通过查找资料和分析，本文认为使用k聚类算法 REF _Re\r \h 【1】 来建立相关的模型，可以很好的解决共享汽车投放位置选取的问题。 模型假设与约定 为了简化计算过程，本文忽略了每个点停车的次数，车与车之间不会有相互的影响，每个车在运动的过程中不会出现故障。 假设数据中的簇数是可取的，而且分类的过程中我们会找到最好聚类质量的k(最好的聚类质量k存在)。每一个簇都要保持其自身的完整性。 符号说明及名词定义 L 样本属性 T 对象个数 N 抽取的样本个数 r 样本元素 R 样本簇 k 抽取样本簇 i ,j 簇序号 c 簇中心停车点 J 平方和准则函数 allcars 可用汽车数量 GPS 总停车位置 问题的分析 为了选取最优的共享汽车投放位置，本文首先必须统计该汽车公司一共拥有多少可以投入使用的共享汽车，即总可用汽车allcars。接下来，还需要对该汽车公司运营范围内所有可以停车的位置，即总停车位置GPS，进行统计并去除重复的位置。 在了解了相关的信息之后，本文将着手分析这些位置，观察它们的分析情况，总结它们的分布规律。考虑到本文希望得到的最优的投放位置具有以下特点，即人群最密集，最可能租车，同时还必须使得每辆车尽量的均匀分布，保证它们都有机会被出租。 有鉴于此，本文希望把点分成大致均匀的、距离上相近的allcars个类别，每个类别都是在某个范围内是聚在一起的。这样，本文就可以在每个类别中选取一个中心位置，并且把每辆车放在最靠近每个类别的中间位置的停车点，通过选择这样的位置投放共享汽车，就可以最优化人们借它的可能。 通过借助k-means聚类算法，可以很好的解决了上述的问题，将所有的停车位置划分为allcars个类别，从而得到想要得到的结果。在分类完成之后，就来计算每个类的中心点，本文通过直接将所有点的经度纬度分别求平均值，得到该类别的中心点，然后计算距离得到该中心点最近的停车位置。这里，本文采取的方法是先计算所有点到中心点的欧氏距离大小，然后选取距离最小的那一个点，就得到了距离中心点最近的点，这个点就是停车位置所求的点。在找出找出所有这些点之后，就完成了算法并解决了核心问题。也就是我们模型需要的allcars个调度位置。 模型的建立与求解 问题一：共享汽车分布情况 对于问题一，由于数据量大，而且时间不是连续的。所以我们不能通过以时间为轴线而建立一个连续的动态模型。为了更好的实现共享汽车的分布情况。本文通过不同的时间段分别展示汽车的分布情况。以下是本文的详细分析情况。 我们通过Excel统计数据大概有1048575行数据。如果直接将所有的数据全部导入Python中，大量的数据，可能会显得重复。在将汽车的停车位置相同的分别归为一类。在分别截取月、天、小时为时间段描述汽车的分布情况。下面就是时间截止到2019.1这一月的汽车分布情况，如下图所示： 图 SEQ 图表 \* ARABIC 12019.1 汽车停车位