基于三角形剖分改进算法的外卖配送最短路径规划探讨.docx

摘要:随着O2O模式的发展，越来越多的人使用外卖平台就餐，因此外卖配送能力很大程度上影响着一家餐饮企业的竞争力。对于商家的外卖配送人员来说，尽可能快的配送完全部的餐点成了必须解决的问题，这就需要规划出一条最短的穿过各个餐点的路径。本文基于最邻近法，采用三角形剖分的思想，模拟出苏州大学附近常用配餐点的赋权图，通过寻找最小权值的三角形再删除其最长边获得优化的路径，最终找到一条适用于外卖配送的Hamilton回路，并评价改进算法在最短回路寻找问题中的实用性。

关键词：最小权三角形  Hamilton回路  最邻近法  配送路径规划  三角形剖分法

目录

摘要

Abstract

第一章 前言-3

第二章 问题的提出与建模-4

2.1餐饮企业的外卖配送-4

2.2图的定义与概念-5

2.3旅行售货员问题-5

第三章 现有算法-6

3.1 最邻近算法-6

3.2 改良圈算法-7

3.3 现有算法的优缺点-9

3.3.1优点-9

3.3.2缺点-9

第四章 基于三角形剖分改进算法-10

4.1改进算法原理-10

4.2改进三角形剖分算法的基本思路-10

4.3算法步骤-13

4.4流程图-14

第五章 算例模拟-15

5.1建模-15

5.2基于最邻近法的求解-18

5.3基于改进的三角形剖分算法的求解-19

5.4改进算法的矩阵表达-21

5.5小结-24

结语-25

参考文献-26

致谢-27

文献综述-28