快递末端配送路径规划及应用开发

发布时间：2020-08-27 07:14

【摘要】：智慧物流在智慧城市中充当着重要角色,为了减少快递员配送快递时的时间消耗和距离消耗,提高快递末端配送效率,研究了基于启发式智能搜索算法的城市两级配送路径规划算法,基于云平台完成了快递路径规划系统的开发。结合国内快递进入目标城市范围之后的配送特点,将其分为两个级别:城市级别和城区级别。城市级别配送点数少且分散,由大货车配送,以时间总消耗作为路径质量评估值,提出了一种改进贪婪自进化过程的模拟退火算法,采用贪婪算法产生的初始路径作为待进化染色体,进行基因交换和片段倒置的自我进化操作,借助Metropolis准则决定是否用进化后的解取代进化前的解,并在进化过程中始终记录当前状态之前的最优个体,进行退火降温后再次进化,直到温度降至预设温度停止。仿真结果表明,单次配送二十个点时,改进后的算法在其稳定性和当前最优距离上更优。城区级别配送点数多且密集,由电动三轮车配送,因为三轮车灵活轻巧,受城市交通影响小,以骑行距离消耗作为路径质量评估值,为了获得距离消耗较短的路径,改进了一种基于Metropolis准则的选择遗传算法。在遗传算法中,移除交叉率,采用Metropolis准则决定经过交叉和变异后的个体是否遗传进入子代种群,调节每代交叉和变异时接受较差解的概率,达到避免种群早熟的目的。仿真结果表明,单次配送五十个点时选择遗传算法不仅有效消除搜索中易陷入局部最优解的现象,而且在达到相对稳定解时选择遗传算法最终规划结果相比于传统算法缩短了 10%,相比于遗传模拟退火算法缩短了4%。将上述两种算法应用到快递路径规划服务云平台中,用西安市圆通快递区配送中心分布点验证城市级别配送路径规划功能,证明该功能切实可用,用西安市南二环附近随机的五十个真实地点验证城区级别配送路径规划功能,得到了比较理想的推荐配送路径。
【学位授予单位】：西安科技大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18;F252.1
【图文】：

模型图,模型图

为了确保算法的收敛性，提升算法的性能和效率算法的思想，加入定向自进化过程，得到一种基于贪婪自是经典的组合优化问题，其基本数学模型可以作如下描述两个城市之间的距离都是确定的，现要求一个旅行商从某市且只在一个城市逗留一次，最后回到出发的城市，在这历顺序 (,,...,)min 123nT tttt，使得函数 f(T)值最小：f(T)d(t,t)d(t,t)n1n-1i1ii1 min 城市，下角标 1 到n表示n个不同的城市， d(t,t)i i 1代表 2.1 是 TSP 模型图，可以直观展示 TSP 所要达到的目标目标点，两个圆圈虚连线上的数字表示这两个点之间的消最短路径。

有向图,矩阵,随机因子,矩角

图 2.2 带权有向图 G有向图 G 后，还需建立一个n n的矩角线上的元素取值都为 0，ijS,的数时，从点i到点 j 的这条路段消耗的其他边（，）在最优路径上01iji, jX 经过每个顶点恰好一次的回路，产生消耗 TSP 就是要找出G 中W 最小的 i,ji,jmin WSXSP 的常用方式之一，该算法本质上属随机因子，在迭代的过程中并不是只中跳出局部最优解，从而有机会找到所示，若初代解为最左边的点 A，算

模拟退火算法,搜索过程

其他边（，）在最优路径上01iji, jX 路径就是经过每个顶点恰好一次的回路，产生的消，非对称消耗 TSP 就是要找出G 中W 最小的回路 i,ji,jmin WSX法是解决 TSP 的常用方式之一，该算法本质上属于贪中加入了随机因子，在迭代的过程中并不是只一味迭代过程中跳出局部最优解，从而有机会找到全局如图 2.3 所示，若初代解为最左边的点 A，算法会，此时算法会继续向右搜索到点 C，显然点 C 的结会接受点 C，将其作为新的搜索方向继续搜索。对都做相同处理，使算法有机会继续搜索，或许经过 D。

【参考文献】