作品名称：基于C-TSP模型与改进GA算法的城市地下配送系统设计

　　学     校：南京师范大学

　　指导教师：温永宁

　　团队成员：王哲 王纯 戴文昱 王妍鳕

       2019年，中国数字经济在GDP中的占比首次突破三分之一。而在新冠疫情对出行与交通的巨大限制下，人们对在线购物的依赖性在今年（2020）更是急剧增长，数字经济的GDP占比很有可能迎来全球性的激增。

       O2O服务（online to offline）是在数字经济兴起下快速成长的一类服务形式，并已成为支撑数字经济发展的必要条件。O2O服务主要以配送为服务手段，实现线上线下的对接，如物流、外卖等实体以及在线打车、上门化妆、上门理发等服务的配送。近年来，人们对O2O服务的需求日益强烈，应运而生地相继出现了众多专业的O2O平台提供各种O2O服务，如美团外卖、速易递等。

       配送系统是O2O服务的核心和骨架。配送系统的快速发展，也产生了众多亟待解决的问题。一来，配送实体量的上升占用了过多交通资源，造成交通拥堵和用地紧张；二来，为了追求配送的效率和业绩，人工配送员常常追求配送速度而忽视交通规则，形成安全隐患，导致安全事故频发；最后，大量配送任务的管理，需要不断消耗人力、物力和空间，带来诸多方面的城市问题。为此，许多西方国家率先提出并着手研究地下配送系统。2018年6月，京东与美国Magplane Technology公司签署战略合作协议，标志中国正式开始着手的地下配送系统。

       本研究以苏州市姑苏区为例，通过爬虫技术和SuperMap iDesktopX软件完成对该区域商业、交通、人口等多方面数据的获取与预处理工作。在此基础上，构建C-TSP（colored-TSP）模型，并发明了基于模拟退火中的温度因子优化后的遗传算法对模型进行求解，最终生成地下配送网络，对实际工程建设的设计和落地提供思路参考和决策支持。

解决思路

       一条完整的配送路线可以抽象为：

       商业点->地上线路->地下无人配送仓->地下线路->地下无人配送站->需求点

       其中，配送实体从地下无人仓进入地下配送网络，并在到达需求点后回到地上。所以，地下配送网络可以抽象为一个由无人配送仓、地下线路、无人配送站三个部分组成的点-线结构。由此，网络的建设问题可以分为两大部分，即选址问题和基于选址结果的连通问题。

图【解决思路与流程】

无人配送仓选址

       对得到的商业POI数据，进行核密度分析，生成核密度栅格数据。

       对核密度栅格数据，使用数字地形分析中的山顶点提取算法，提取潜在的配送热点。

       对配送热点数据，以核密度为属性，绘制洛伦兹曲线，取能够反映大于70%信息量的配送热点作为无人仓。

       无人仓数量应占全部配送热点数量的30%左右。

图【基于爬虫得到的商业POI】

图【双对数变换后的热点直方图】

图【基于热力值的洛伦兹曲线】

无人配送站选址

       对得到的居住类POI数据，采用KMeans算法，进行聚类，保证各个类属于二维平面的凸类，取各个类别的几何中心作为无人站。

       无人站的数量应当与算法中的N_cluster参数值相同。

图【聚类后的居民点POI】

地下网络生成

       本地下配送网络模型将网络分为两个级别，分别为一级网络（用于无人仓之间的连接）和二级网络（用于连接无人仓和无人站）。

       一级网络

       使用prim算法在各个无人仓之间生成最小连通图，作为一级网络。

       二级网络

       将无人仓视为起始点和终止点，无人站作为站点，构建C-TSP模型。使用基于模拟退火中的温度因子优化后的遗传算法对模型求解，生成二级网络。

图【区域商业热力图】

图【使用引力模型生成的地下配送系统】

图【使用距离模型生成的地下配送系统】

核心算法迭代过程演示

图【初始线路】

图【迭代十次后的线路】

图【迭代50次后的线路】

图【迭代100次后的线路】

图【最终线路】

图【成本函数下降过程】